不递归地打印第 n 个斐波那契数

Question

我正在解决打印第 n 个斐波那契项的问题，而无需在在线判断中使用递归。它说打印输出模数 1000000007.

#include <stdio.h>
long long int fib(int q)
{
 if(q==1||q==2)return 1;
 else{
  long long int x=1,y=1,z;
  register int i;
  for(i=0;i<q-2;i++){
    z=x+y;
    y=x;
    x=z;
  }
  return z%1000000007;}
}
int main(void) {
 int t,i;
 scanf("%d",&t);
 for(i=0;i<t;i++)
 {
    int q;
    scanf("%d",&q);
    printf("%lld\n",fib(q));
 }
 return 0;
}

代码在代码块中运行良好，但显示错误答案（也未显示输出）。

Answer 1

第一件事：

请缩进您的代码以尽可能提高可读性，因为这样有助于使用为您提供更好的答案并且人们可以轻松理解代码

而且这个错误与模数有关。您需要提供模 1000000007 的答案。而且斐波纳契数列增长得非常快。

那么可能出现的就是long long类型溢出

您必须在算法的每一步计算模数。

让我们看下面的例子：

x 和 y 很大但仍然适合 long long 类型
x+y 不适合 long long
然后 x+y 是一些负值，因为（发生溢出）
我们用负数计算斐波那契数列！

求和时进行调制我们总是得到

x+y % 1000000007
总是小于 1000000007 所以总和总是适合 long long
所以我们没有溢出！

修改后的最终代码如下所示：

long long int fib(int q) {
  if(q==1||q==2) {
    return 1;
  } else {
    long long int x=1,y=1,z;
    register int i;
    for(i=0;i<q-2;i++){
        z=(x+y) % 1000000007;
        y=x;
        x=z;
    }
    return z % 1000000007;
  }
}

不递归地打印第 n 个斐波那契数

To print nth fibonnaci number without recursion

fibonacci