如何在Java中使用递归生成负斐波那契序列？

Question

我必须写一个程序，返回斐波那契数，但不只是正数。我不知道我写代码的方式有什么不对，但我的代码使用正数，而不是负数。

public static int negFib(int n) {
    if(n==0 || n==1) {
        return n;
    }
    if(n==-1) {
        return 1;
    }
    if(n<0 && n%2==0) {
        //return negFib(n+2) - negFib(n+1);
        return (-1<<(n+1))*(negFib(n-1) + negFib(n-2); // Fibonacci negative
        //F(n)=F(n+2)−F(n+1)
        //F(−1)=F(1)−F(0)=1−0=1 , F(−2)=F(0)−F(1)=0−1=−1
    } 
    return negFib(n-1) + negFib(n-2); //Fibonacci positive      
}

Answer 1

试试这个：

long f[] = new long[(int) (n+2)];  
long i;

f[0]=0;
f[1]=1;

for (i=2; i <= n; i++) { 
   f[(int) i] = f[(int) (i-1)] + f[(int) (i-2)];
}

Answer 2

如果你想用F_−n=(−1） ⁿ¹F_n公式：

public static int negFib(int n) {
    if(n==0 || n==1) {
        return n;
    }
    if(n==-1) {
        return 1;
    }
    if(n<0) {
        int sign = n % 2 == 0 ? -1 : 1;
        return sign * negFib(-n);
    } else {
        return negFib(n-1) + negFib(n-2);
    }     
}

您的尝试有几个问题：

• 对于负n（奇数或偶数），您应该对-n-1和-n-2进行递归调用。
• 您对符号的计算-（-1