求斐波那契数列N项，求助！ - 编程论坛

#2

风过无痕19892020-10-27 20:46

回复楼主好烦、

程序代码：

#include<stdio.h>
int main(void)
{
    int N,f1,f2,i,A;
    f1 = 1;
    f2 = 1;
    scanf("%d",&N);
    if(N > 2)
    {
        for(i = 3;i <= N;i++)
        {
            A = f1 + f2;
            f1 = f2;
            f2 = A;
        }
        printf("%d\n",A);
    }
    else if(N <= 2)
        printf("1\n");

    return 0;
}

#3

rjsp2020-10-27 20:49

如果N==2，你相当于执行了下面的代码
  int A;
        printf("1");
    printf("%d",A%2000000003);
那A值是多少？这是“未定义行为”

#4

rjsp2020-10-27 21:08

printf("%d",A%2000000003);

从 A%2000000003 看，这道题不可能让你慢吞吞的一个个计算过去，你应该用“矩阵运算 & 快速幂”，我懒得写，你参考一下吧 https://bbs.bccn.net/viewthread.php?tid=481332&page=1#pid2645909

在你源代码上改，代码应该是

程序代码：

#include <stdio.h>

int main(void)
{
    unsigned n;
    scanf( "%d", &n );

    unsigned a=0, b=1;
    for( unsigned i=0; i!=n; ++i )
    {
        unsigned c = a+b;
        a = b;
        b = c%2000000003;
    }
    printf( "%u", a%2000000003 );
}

#5

好烦、2020-10-28 19:42

回复 4楼 rjsp

谢谢大佬！

#6

好烦、2020-10-28 19:47

回复 4楼 rjsp

那为什么我原来的不行啊

#7

rjsp2020-10-28 19:52

回复 6楼好烦、

我在3楼说了你错误的原因了呀，你 printf("1"); 之后又 printf("%d",A%2000000003);

#8

rjsp2020-10-28 19:58

回复 5楼好烦、

不谢，我帮你写一个完整的吧

程序代码：

#include <stdio.h>

unsigned long long fibonacci( unsigned n )
{
    // a *= b
    #define MUL(a,b) do {\
        unsigned long long t00 = (a##00*b##00+a##01*b##10)%2000000003;\
        unsigned long long t01 = (a##00*b##01+a##01*b##11)%2000000003;\
        unsigned long long t10 = (a##10*b##00+a##11*b##10)%2000000003;\
        unsigned long long t11 = (a##10*b##01+a##11*b##11)%2000000003;\
        a##00=t00, a##01=t01, a##10=t10, a##11=t11;\
    } while(0)

    unsigned long long r00=1,r01=0,r10=0,r11=1;
    for( unsigned long long v00=0,v01=1,v10=1,v11=1; n!=0; n/=2 )
    {
        if( n%2 == 1 )
            MUL(r,v); // r*=v
        MUL(v,v); // v*=v;
    }
    return r01%2000000003;

    #undef MUL
}

int main( void )
{
    unsigned n;
    scanf( "%u", &n );
    printf( "%llu\n", fibonacci(n) );
}

#9

好烦、2020-10-28 20:06

回复 7楼 rjsp

这个我后来改了，但是在OJ上还是不行，会不会可能是数据溢出啊

#10

好烦、2020-10-28 20:07

回复 8楼 rjsp

这个我更看不懂了。。。

#11

好烦、2020-10-28 20:09

回复 8楼 rjsp

完全看不懂，，，我是如此的菜

#12

rjsp2020-10-28 20:27

回复 9楼好烦、

当然溢出啦，否则求得结果后再%2000000003有什么意义？

#13

好烦、2020-10-28 20:30

回复 12楼 rjsp

ooo!!!

#14

rjsp2020-10-28 20:32

回复 13楼好烦、

你看我在4楼的代码
b = c%2000000003;
中间结果是可能溢出的