java - 斐波那契修改 :How to fix this algorithm?

Question

这个问题摆在我面前，我不知道如何解决。这是关于序列 0,1,1,2,5,29,866...(除了前两个数字之外的每个数字都是前两个数字的平方和 (2^2 +5^2=29))。在第一部分中，我必须编写一个算法(我不是母语人士，所以我真的不知道术语)，它会在系列中占有一席之地并返回它的值(6 返回 29)我是这样写的:

public static int mod(int n)
{
    if (n==1)
        return 0;
    if (n==2)
        return 1;
    else
        return (int)(Math.pow(mod(n-1), 2))+(int)(Math.pow(mod(n-2), 2));
}

但是，现在我需要算法将接收一个数字并返回系列 (6- 29+5+2+1+1+0=38) 中的总和我不知道该怎么做，我正在尝试，但到目前为止我真的无法理解递归，即使我写了正确的东西，我如何检查它才能确定？以及一般如何达到正确的算法？

禁止使用任何额外的参数。

提前致谢!

Answer 1

我们想要:

mod(1) = 0
mod(2) = 0+1
mod(3) = 0+1+1
mod(4) = 0+1+1+2
mod(5) = 0+1+1+2+5
mod(6) = 0+1+1+2+5+29

我们知道每个术语的定义如下:

   2^2+5^2=29

因此，为了计算 mod(7)，我们需要将序列 x 中的下一项添加到 mod(6)。

现在我们可以使用 mod 计算出该术语:

 x = term(5)^2 + term(6)^2
 term(5) = mod(5) - mod(4)
 term(6) = mod(6) - mod(5)
 x = (mod(5)-mod(4))^2 + (mod(6)-mod(5))^2

因此我们可以通过评估 mod(4)、mod(5)、mod(6) 并组合结果来计算 mod(7)。

当然，除非您记住该函数，否则这将非常低效!

示例 Python 代码:

def f(n):
    if n<=0:
        return 0
    if n==1:
        return 1
    a=f(n-1)
    b=f(n-2)
    c=f(n-3)
    return a+(a-b)**2+(b-c)**2

for n in range(10):
    print f(n)

打印:

0
1
2
4
9
38
904
751701
563697636866
317754178345850590849300