プログラミングのお題スレ Part16

[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (1002ﾚｽ)
上下前次1-新
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

514(6): 2019/12/31(火)09:03 ID:hkax3Wzu(1) AAS
お題
フィボナッチ数列のn番目をF(n)とした時
F(F(80))の下位8桁を求めよ

フィボナッチ数列は以下で定義される数列である
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1)

515(2): 2019/12/31(火)10:24 ID:NKLtpqnc(1/2) AAS
>>514
21055810
あってるかな。
フィボナッチ数列は行列を使うアルゴリズムでO(log n)で計算できるもんね。外側の計算はmod100000000 で計算すればいい。

517: 2019/12/31(火)12:26 ID:5aZymNkm(2/3) AAS
>>515じゃなくて>>514だった。

518: 2019/12/31(火)13:18 ID:5aZymNkm(3/3) AAS
>>514
Rでも多桁計算パッケージgmpを使ったら、正しく計算できた。
外部ﾘﾝｸ:ideone.com

519: 2019/12/31(火)17:23 ID:NKLtpqnc(2/2) AAS
>>514
>>516
515です。コード上げてなかった。
外部ﾘﾝｸ:ideone.com

521: 2019/12/31(火)18:47 ID:H+c+1UtF(2/2) AAS
>>514でした
すみません

541(1): 2020/01/04(土)17:22 ID:HJ66bOYq(1/2) AAS
お題
>>514に関連して、F(F(80))の桁数を求めよ。

計算式は簡単だが…