首頁
>
藍橋杯吧
>
瀏覽帖子
台灣正體
大陆简体
港澳繁體
马新简体
|
登錄
|
註冊
進入侃吧
進入個人空間
全部
僅作者
目前共有
8
篇帖子。
字體大小:
較小 - 100% (默認)▼
內容轉換:
不轉換▼
點擊
回復
288
7
【C语言】入门训练 Fibonacci数列
巨大八爪鱼
一派護法 十九級
1樓
發表于:
2015-11-21 21:26
回復
问题描述
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。
锦囊1 使用数组来保存F序列,只保存除10007的余数。
锦囊2 先令F[1]=1, F[2]=1,然后用F[i]=(F[i-1]+F[i-2])%10007来计算F[i]。
巨大八爪鱼
一派護法 十九級
2樓
發表于:
2015-11-21 21:27
回復
错误的答案:
#include <stdio.h>
//这是老师上课讲的递归法。。。
int F(int n)
{
if (n <= 2)
return 1;
else
return F(n - 1) + F(n - 2);
}
int main()
{
int n;
int reminder;
scanf("%d", &n);
reminder = F(n) % 10007;
printf("%d\n", reminder);
return 0;
}
评测结果 运行超时
得分 30
CPU使用 运行超时
内存使用 62.62MB
巨大八爪鱼
一派護法 十九級
3樓
發表于:
2015-11-21 21:28
回復
正确的答案:
#include <stdio.h>
int main()
{
int n, i;
int F[3] = {1, 1, 1};
scanf("%d", &n);
if (n >= 3)
{
for (i = 3; i <= n; i++)
{
F[2] = (F[1] + F[0]) % 10007;
F[0] = F[1];
F[1] = F[2];
}
}
printf("%d\n", F[2]);
return 0;
}
评测结果 正确
得分 100
CPU使用 0ms
内存使用 1.597MB
巨大八爪鱼
一派護法 十九級
4樓
發表于:
2015-11-21 21:30
回復
递归法写出的函数虽然简单,但是很耗系统资源。
巨大八爪鱼
一派護法 十九級
5樓
發表于:
2015-11-21 21:30
回復
输入:1000000
输出:114
--------------------------------
Process exited after 11.82 seconds with return value 0
Press any key to continue . . .
巨大八爪鱼
一派護法 十九級
6樓
發表于:
2015-11-21 21:31
回復
2楼的程序,即便是输入50,都无法得出计算结果。不过输入40的话:
40
2573
--------------------------------
Process exited after 2.181 seconds with return value 0
Press any key to continue . . .
巨大八爪鱼
一派護法 十九級
7樓
發表于:
2016-3-1 17:02
回復
其实,应该不需要判断n>=3:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i;
int F[3] = {1, 1, 1};
scanf_s("%d", &n);
for (i = 3; i <= n; i++)
{
F[2] = (F[0] + F[1]) % 10007;
F[0] = F[1];
F[1] = F[2];
}
printf("%d\n", F[2]);
system("pause");
return 0;
}
巨大八爪鱼
一派護法 十九級
8樓
發表于:
2016-3-1 17:03
回復
仍然是前两个数相加得到新数,只不过数组只存储三个元素,且都是存储的都是余数。
回復帖子
內容:
圖片
視頻
表情
用戶名:
您目前是匿名發表
驗證碼:
看不清?換一張
(快捷鍵:Ctrl+Enter)
本帖信息
點擊數:
288
回複數:
7
評論數:
?
作者:
巨大八爪鱼
最後回復:
巨大八爪鱼
最後回復時間:2016-3-1 17:03
公告板
【公告】關於Purasbar網站的一些聲明
【公告】阿斯蘭侃吧(Arslanbar)試用新logo
【公告】阿斯兰侃吧啟用新客服電話號碼
【公告】關於阿斯蘭侃吧(Arslanbar)再度恢復及開始試運營的公告
【新功能】现在可以直接在发帖框中粘贴图片啦!
【新功能】搜索框提示功能上線了
【公告】第十五次補丁包安裝完畢
【公告】從現在開始,管理員將停止審批會員
【公告】阿斯兰侃吧现在开始支持简繁混合搜索
【公告】阿斯蘭侃吧啟用https訪問
【公告】从今天开始,本站实行主题编号制
【新功能】图片缩放功能上线了
©2010-2025 Arslanbar Ver2.0
▲
除非另有聲明,
本站
採用
創用CC姓名標示-相同方式分享 3.0 Unported許可協議
進行許可。