0

我有下面的 C 代码（如果语法不符合 C 语言，请原谅我），它打印给定索引的斐波那契数。它工作正常。但是我在这里有两个问题。第一个是，我想知道它可能会在什么索引处溢出（假设 16 位编译器最大值 int 数据类型可以保存的是 65535）。第二个是当它溢出时它将打印什么值之后的索引？

我知道对于我的第一个问题，这完全取决于值 N，但我想知道是否有一种方法可以预测给定索引 n ，如果它在我们计算索引 n 处的斐波那契之前溢出

我的最后一个问题是，我们如何确保它不会溢出给定的用户输入值 n 并打印正确的斐波那契值。

 public static int fib_loop(int n)
    {
        int[] fib = new int[n];    
        Scanf("%d",&n);
        if(n==0)            
           fib[0] = 0;
        if(n==1)
          fib[1] = 1;
        for (int i = 2; i < n; i++)
            fib[i] = fib[i - 1] + fib[i - 2];

        return fib[n-1]; //because we only want to return for index 4 in case if n =4 :-)
    }
4

3 回答 3

2

如果您使用unsigned变量，则溢出是明确定义的。给定 fib(n-1) 和 fib(n-2) 没有溢出，如果 fib(n) 小于 fib(n-1) 则溢出。

unsigned fib[n];
...
fib[i] = fib[i-1] + fib[i-2];
if (fib[i] < fib[i-1]) {
  ; // handle overflow
}
于 2013-09-07T17:31:05.050 回答
0

使用项的渐近比（黄金比例）来预测最大可表示数的大小：

int biggest = (int)( Integer.MAX_VALUE / 1.618);
for (int i = 2; i < n; i++) {
    if (fib[i - 1] > biggest)
        // do something
    fib[i] = fib[i - 1] + fib[i - 2];
}
于 2013-09-07T21:29:12.793 回答
0

OP 说“我想知道是否有一种方法可以预测给定索引 N ，如果它在我们计算索引 N 处的斐波那契之前溢出”。

假设您的最大可表示数是Big。封闭形式：

r = (1 + sqrt(5))/2
fib(x) = (power(r,x) - power(-r,-x))/sqrt(5)
or
fib(x) = floor(power(r,x)/sqrt(5) + 0.5)

让 fib(x) 设置为Big，然后求解 x。然后确保你所有的索引都是<= x。

static size_t FibMaxIndex = 0;
if (FibMaxIndex == 0) {
  FibMaxIndex = (size_t) (log(Big *sqrt(5) - 0.5)/log((1+sqrt(5))/2)) + 1;
}
if (index > FibMaxIndex) {
  ;  //handle too large an index
}
于 2013-09-07T18:26:11.483 回答