首頁
>
藍橋杯吧
>
瀏覽帖子
台灣正體
大陆简体
港澳繁體
马新简体
|
登錄
|
註冊
進入侃吧
進入個人空間
全部
僅作者
目前共有
8
篇帖子。
字體大小:
較小 - 100% (默認)▼
內容轉換:
港澳繁體▼
點擊
回復
343
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)
本帖信息
點擊數:
343
回複數:
7
評論數:
?
作者:
巨大八爪鱼
最後回復:
巨大八爪鱼
最後回復時間:2016-3-1 17:03
公告板
【新功能】現在手機版發帖也可以上傳圖片了
【公告】布拉斯侃吧(Purasbar)全站已啟用HTTP/2訪問以及TLS1.3加密
【新功能】樓中樓功能已上線
【公告】Purasbar http訪問方式已關閉,從現在起只能通過https方式訪問
【新功能】現在可以直接在發帖框中粘貼圖片啦!
【新功能】搜索框提示功能上線了
【公告】第十五次補丁包安裝完畢
【公告】從現在開始,管理員將停止審批會員
【公告】阿斯蘭侃吧現在開始支持簡繁混合搜索
【公告】阿斯蘭侃吧啟用https訪問
【公告】從今天開始,本站實行主題編號制
【新功能】圖片縮放功能上線了
©2010-2025 Purasbar Ver2.0
▲
除非另有聲明,
本站
採用
創用CC姓名標示-相同方式分享 3.0 Unported許可協議
進行許可。