Fibonacci使用1个变量

Question

我在接受采访时被问到以下问题:

有没有什么方法可以使用只有1个变量生成Fibonacci系列？

我不知道该回答什么.我该说什么？

Answer 1

Yes, you can used the closed-form expression:

where

You can calculate the expression using a double and round the result to the nearest integer. Because of the finite precision of floating point arithmetic this formula will give a wrong answer for large enough n, but I think it will work in the case when the result fits into a Java 32-bit integer.

Answer 2

一点,是的(虽然在C中,你可以将它转换为Java - 它看起来会更加丑陋).

#include <stdio.h>
#include <stdlib.h>

int main (void) {
    unsigned long i = 1;
    printf ("0\n");
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) {
        printf ("%d\n", i & 0xffff);
        i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff));
    }
    return 0;
}

产生:

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657

:-)

当然,真正的问题是:你为什么要这样做？

如果你对它是如何工作感到好奇,那真的很简单.一个变量实际上分为两部分,这两部分维持Fibonacci序列的各个值.它在技术上仍然是一个变量,我们只是在它上面施加了一些额外的结构来实现我们的目的.

Answer 3

当然,使用递归:

public class Test {

    public static int fib(int n) {
        return n < 2 ? n : fib(n-1) + fib(n-2);
    }

    public static void main(String[] args) {
        for(int i = 0; i <= 10; i++) {
            System.out.print(fib(i)+", ");
        }
        System.out.println("...");
    }
}

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...