不使用数组的斐波那契数列

Question

我正在尝试通过编码斐波那契数列来练习JAVA，其中用户可以声明从0到n开始的斐波那契数列的长度。这是我的代码：

public class test {
public static void main(String args[]) throws IOException {
    BufferedReader pao = new BufferedReader(
            new InputStreamReader(System.in));

    System.out.print("Enter number: ");
    String enter = pao.readLine();
    int ent = Integer.parseInt(enter);

    int total1 = 0;
    int total2 = 1;
    int total3 = 0;

    for (int a = 0; a < ent; a++) {
        if (a <= 1) {
            System.out.print(" " + total3);
            total3 = total1 + total2;

        } else if (a == 2) {
            System.out.print(" " + total3);
        } else {
            total1 = total2;
            total2 = total3;
            total3 = total1 + total2;
            System.out.print(" " + total3);

        }
    }

}
}  

是否有另一种方法可以更简单、更短、“更好”地做到这一点？仍然没有使用数组。预先感谢您。

Answer 1

您可以使用递归斐波那契，但它会增加您的运行时间从

O(n)

到

O(2^n)

，就像下面的

int fib(int n) {
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}

还有另一种方法可以将运行时间减少到

O(log n)

，但它使用数组（使用矩阵的力量

{{1,1},{1,0}}

），你可以在这里阅读它。对于上述递归，如果您使用数组，您可以通过方法调用动态编程再次将运行时间更改为

O(n)

。

Answer 2

public class Fibo {
    public static void main(String[] args) {
        int n = 12;
        int a = 0;
        int b = 1;

        System.out.print(a + " ");
        System.out.print(b + " ");
        for (int i = 0; i < n-2; i++) {
            int temp = a + b;
            a = b;
            b = temp;
            System.out.print(temp+" ");         
        }
    }
}

Answer 3

使用递归：

public int fibonacci(int n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
      return 1;
   else
      return fibonacci(n - 1) + fibonacci(n - 2);
}

Answer 4

您的迭代解决方案很好（尽管如果这是代码审查，我还会提出其他挑剔）。递归实现将为您赢得更多风格点，但它速度慢得多并且更占用内存。

对于最大样式点 (*)，您还可以使用 Binet 公式来获得斐波那契序列的 封闭式解决方案。

(*) 不过，不要在生产代码中执行此操作，除非您真的、真的确定您需要它。

Answer 5

int x = 10, i=0, f=1, s=1, o = 1;
while (x > 0) {
    if(i!=0 && i!=1){
        o=f+s;
        f=s;
        s=o;
    }
    System.out.print(o);
    x--;
    i++;
}