标题:蓝桥杯练习题C++Fibonacci数列
只看楼主
aramanda
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-11-22
结帖率:0
已结贴  问题点数:20 回复次数:5 
蓝桥杯练习题C++Fibonacci数列
Fibonacci数列的递推公式为:Fn=Fn-1+Fn-2,其中F1=F2=1。当n比较大时,Fn也非常大,现在我们想知道,Fn除以10007的余数是多少。
输入格式:输入包含一个整数n。
输出格式:输出一行,包含一个整数,表示Fn除以10007的余数。
C++代码,一直提示错误,不知道错在哪了
#include <iostream>
using namespace std;
int main() {
    int max=1000000;
    int *F=new int[max];
    int n;
    F[0]=1;
    F[1]=1;
    int a;
    cin>>a;
    cout<<endl;
    int b;
    for(n=2;n<=a;n++)
    {        
        F[n]=F[n-1]+F[n-2];
        b=F[n]%10007;
    }
    cout<<b<<endl;
    return 0;
}
搜索更多相关主题的帖子: 练习题 C++ Fibonacci 数列 int 
2017-11-22 15:17
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:20 
你这是什么
首先 int max=1000000; 中 1000000 哪里来的?
其次 F[n]=F[n-1]+F[n-2]; 不怕溢出?
如果n大一些,你这算法准备算到哪一年?

矩阵运算 + 快速幂
见6楼我的答案 https://bbs.bccn.net/thread-481332-1-1.html
你需要的是中间数据加上模除10007

2017-11-22 16:32
aramanda
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-11-22
得分:0 
回复 2楼 rjsp
题中数据规模与约定是1 <= n <= 1,000,000
2017-11-22 17:51
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
以下是引用aramanda在2017-11-22 17:51:04的发言:

题中数据规模与约定是1 <= n <= 1,000,000

是你测试出来的,还是题目中本来就有但是你故意不说?
2017-11-22 18:00
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:507
帖 子:8890
专家分:53117
注 册:2011-1-18
得分:0 
任何情况下都要贴出完整的题目要求,因为不同的数据规模使用的算法也不一样。样例的输入输出也不可缺少,其一是补充题目的细节,其二是让对方快速测试正确性。

以下是我从网上搜来的完整题目,仔细看看吧
问题描述
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。
2017-11-22 18:10
aramanda
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2017-11-22
得分:0 
回复 4楼 rjsp
这是在题目下面的解析中提到的,我忘记打上去了
2017-11-22 18:24



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-482724-1-1.html




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

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