Fibonacci修改:如何修复此算法？

Question

我面前有这个问题,我无法弄清楚如何解决它.它是关于系列的0,1,1,2,5,29,866...(除了前两个之外的每个数字都是前两个数字的平方和(2^2+5^2=29)).在第一部分我不得不写一个算法(不是母语,所以我真的不知道术语)将在系列中获得一个位置并返回它的值(6 returned 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

我可以想出一种方法来根据您评论中的限制来做到这一点，但这完全是一种黑客行为。您需要一种方法来完成两件事：查找当前值并添加以前的值。一种选择是使用负数来标记这些函数之一：

int f(int n) {
    if (n > 0)
        return f(-n) + f(n-1);
    else if (n > -2)
        return 0;
    else if (n == -2)
        return 1;
    else
        return f(n+1)*f(n+1)+f(n+2)*f(n+2);
}

前 8 个数字输出（溢出之前）是：

0
1
2
4
9
38
904
751701

我不推荐这个解决方案，但它确实满足您作为具有单个参数的单个递归方法的限制。