Ruby
0
どのような問題がありますか?

投稿日

「フィボナッチ数を出力せよ」をRubyで

鍋谷さんの課題をやってみた。

コード

めっちゃ恥ずかしいのだけれど、素朴なやり方しか思いつかなかった。

Ruby
b, c = ARGV.map(&:to_i)
tm = Time.now

nxt = 1 + c
b1 = 1
s, t = 0, 1
(0..).each do |n|
  break if Time.now - tm > 1.0
  if nxt == n
    str = s.to_s
    result = "f(#{n})="
    result << if (l = str.length) <= 5
                str
              else
                str[0, 2] + "(ommit #{l - 4} digits)" + str[-2, 2]
              end
    puts result
    b1 *= b
    nxt = b1 + c
  end
  s, t = t, s + t
end

結果

$ ruby -v
ruby 3.0.0p0 (2020-12-25 revision 95aff21468) [x86_64-linux]

$ ruby fibo.rb 12 12
f(13)=233
f(24)=46368
f(156)=17(ommit 29 digits)92
f(1740)=19(ommit 360 digits)80
f(20748)=53(ommit 4332 digits)76
f(248844)=93(ommit 52001 digits)08

$ ruby fibo.rb 34 25
f(26)=12(ommit 2 digits)93
f(59)=95(ommit 8 digits)41
f(1181)=29(ommit 243 digits)81
f(39329)=84(ommit 8215 digits)29

$ ruby fibo.rb 99 99
f(100)=35(ommit 17 digits)75
f(198)=10(ommit 38 digits)24
f(9900)=42(ommit 2065 digits)00

$ ruby fibo.rb 2 0
f(1)=1
f(2)=1
f(4)=3
f(8)=21
f(16)=987
f(32)=21(ommit 3 digits)09
f(64)=10(ommit 10 digits)23
f(128)=25(ommit 23 digits)61
f(256)=14(ommit 50 digits)67
f(512)=44(ommit 103 digits)69
f(1024)=45(ommit 210 digits)43
f(2048)=45(ommit 424 digits)01
f(4096)=46(ommit 852 digits)47
f(8192)=47(ommit 1708 digits)29
f(16384)=50(ommit 3420 digits)63
f(32768)=57(ommit 6844 digits)41
f(65536)=73(ommit 13692 digits)27
f(131072)=11(ommit 27389 digits)89

鍋谷さんの実行例より、一桁以上少ない。

そもそも

tm = Time.now

s, t = 0, 1
1000000.times do
  s, t = t, s + t
end

puts Time.now - tm    #=>10.713040801

これで10秒以上かかってしまう。うーむ。
いいやり方、ありますかね。

ユーザー登録して、Qiitaをもっと便利に使ってみませんか。
  1. あなたにマッチした記事をお届けします
    ユーザーやタグをフォローすることで、あなたが興味を持つ技術分野の情報をまとめてキャッチアップできます
  2. 便利な情報をあとで効率的に読み返せます
    気に入った記事を「ストック」することで、あとからすぐに検索できます
この記事は以下の記事からリンクされています

コメント

(編集済み)
リンクをコピー
このコメントを報告

いいやり方、ありますかね。

は参考にできるのでは

1
(編集済み)
リンクをコピー
このコメントを報告

@fujitanozomuさん、ありがとうございます。

じつは元ページの@angel_p_57さんのコードを見て、行列を使う方法に気づきました。それを参考に、いちおう自分流にコードを書いてみていたので、載せておきます。

Ruby
require "matrix"

b, c = ARGV.map(&:to_i)
tm = Time.now

a = Matrix[[0, 1], [1, 1]]
v = (a ** c) * Vector[0, 1]
r = 1
loop do
  break if Time.now - tm > 1.0
  x = (a * v)[0]
  str = x.to_s
  result = "f(#{r + c})="
  result << if (l = str.length) <= 5
              str
            else
              str[0, 2] + "(ommit #{l - 4} digits)" + str[-2, 2]
            end
  puts result
  r *= b
  a **= b
end
2
リンクをコピー
このコメントを報告

ネタ記事にマジレスして申し訳ないのですが、普通はフィボナッチ数列は動的計画法(DP)で解きます。

0
どのような問題がありますか?
あなたもコメントしてみませんか :)
ユーザー登録
すでにアカウントを持っている方はログイン
記事投稿イベント開催中
2022年に流行る技術予想
~
0
どのような問題がありますか?
ユーザー登録して、Qiitaをもっと便利に使ってみませんか

この機能を利用するにはログインする必要があります。ログインするとさらに下記の機能が使えます。

  1. ユーザーやタグのフォロー機能であなたにマッチした記事をお届け
  2. ストック機能で便利な情報を後から効率的に読み返せる
ユーザー登録ログイン
ストックするカテゴリー