問題(和訳)

Problem 25 「1000桁のフィボナッチ数」
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2025

回答例

gawk -M 'BEGIN{a[1]=1;a[2]=1;print 1;print 1;for(i=3;i<=10000;i++){a[i%3]=a[(i-1)%3]+a[(i-2)%3];print a[i%3]}}' | awk '{print NR,length($1),$0}' | awk '$2>=1000{print $0;exit}'

実行結果

4782 1000 1070066266382758936764980584457396885083683896632151665013235203375314520604694040621889147582489792657804694888177591957484336466672569959512996030461262748092482186144069433051234774442750273781753087579391666192149259186759553966422837148943113074699503439547001985432609723067290192870526447243726117715821825548491120525013201478612965931381792235559657452039506137551467837543229119602129934048260706175397706847068202895486902666185435124521900369480641357447470911707619766945691070098024393439617474103736912503231365532164773697023167755051595173518460579954919410967778373229665796581646513903488154256310184224190259846088000110186255550245493937113651657039447629584714548523425950428582425306083544435428212611008992863795048006894330309773217834864543113205765659868456288616808718693835297350643986297640660000723562917905207051164077614812491885830945940566688339109350944456576357666151619317753792891661581327159616877487983821820492520348473874384736771934512787029218636250627816

real    0m0.061s
user    0m0.060s
sys     0m0.000s

解説

  • MPFR を有効にした awk で、愚直にフィボナッチ数列を計算し、初めて桁数が1000桁以上になる項を探します
  • 計算結果はリングバッファに格納していきます
# MPFR を有効にする(-M または --bignum)
gawk -M '
BEGIN{
  # フィボナッチ数列 F(1),F(2) を初期化&出力
  a[1]=1;
  a[2]=1;
  print 1;
  print 1;
  # 取り敢えず F(10000)まで表示
  for(i=3;i<=10000;i++){
    # フィボナッチ数列を計算
    a[i%3]=a[(i-1)%3]+a[(i-2)%3];
    print a[i%3]
  }
}' |
# F(n)の桁数を表示
# $1=n, $2=桁数, $3=F(n)
awk '{print NR,length($1),$0}' |
# 1000桁に達したら、表示して終了
awk '$2>=1000{print $0;exit}'

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2017-10-11 (水) 19:38:33