| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2142 人关注过本帖
标题:斐波那契数列中的一个细节问题
只看楼主 加入收藏
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
结帖率:86%
收藏
已结贴  问题点数:20 回复次数:5 
斐波那契数列中的一个细节问题
问题描述
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。

输入格式
输入包含一个整数n。
输出格式
输出一行,包含一个整数,表示Fn除以10007的余数。
说明:在本题中,答案是要求Fn除以10007的余数,因此我们只要能算出这个余数即可,而不需要先计算出Fn的准确值,再将计算的结果除以10007取余数,直接计算余数往往比先算出原数再取余简单。

样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。

代码如下
程序代码:
#include <stdio.h>
int main( void )

 {
     unsigned n;
     scanf( "%u", &n );
     n %= 20016;

     unsigned a=1, b=0;
     while( n-- )
     {
         unsigned c = (a+b)%10007;
         a = b;
         b = c;
     }
     printf( "%u", b );

     return 0;

 }


请问那个20016是怎么推出来的? 因为F20016 = 0,F20017 = 1,以此循环,省去了大部分的运算量,我在想20016是怎么得出来的。
谢谢了!
搜索更多相关主题的帖子: 规模 
2017-02-08 23:44
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
20016是一个周期循环,每当n=20016时,取10007的余后就变成了0,以此类推,减少了运算量,防止跑飞程序。
20016是打表出来的。

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2017-02-09 00:55
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
好久不见~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-02-09 07:07
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:20 
程序代码:
#include <stdio.h>

int main( void )
{
    // f(-1)=1, f(0)=0, f(1)=1; f(n)=[f(n-1)+f(n-1)]%10007
    unsigned cycle = 1;
    for( unsigned a=0,b=1; !(a==1&&b==0); ++cycle )
    {
        unsigned c = (a+b)%10007;
         a = b;
         b = c;
    }

    printf( "cycle = %u\n", cycle ); // 20016

    return 0;
}
2017-02-09 08:51
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
回复 3楼 九转星河
嗯嗯,好久不见~

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2017-02-09 16:02
Redeyes
Rank: 4
来 自:中国
等 级:业余侠客
威 望:1
帖 子:301
专家分:292
注 册:2015-5-13
收藏
得分:0 
回复 4楼 rjsp
刚运行下了程序,分析了一下验算过程,懂了。 谢谢你

做一名健壮的技术青年,如果未来无法用代码去改变世界,还可以考虑去搬砖。
2017-02-09 16:03
快速回复:斐波那契数列中的一个细节问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017107 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved