フィボナッチワンライナー

fibonacci ruby
フィボナッチワンライナー

私は、Ruby one-linersのhttp://www.projecteuler.net [Project Euler]からの質問を解決しようとしていますが、http://projecteuler.net/index.phpにもっとエレガントなソリューションがあるかどうか興味があります。 ?section = problems&id = 2 [質問2]:

__
フィボナッチ数列の新しい項はそれぞれ、前の2つの項を追加することによって生成されます。 1と2から始めると、最初の10の用語は次のようになります。

1、2、3、5、8、13、21、34、55、89、…​

値が400万を超えないフィボナッチ数列の項を考慮して、偶数項の合計を求めます。
__

Rubyでの1行のソリューションを次に示します。

(1..32).inject([0,1]) {|arr, i| (arr << arr[-1] + arr[-2] if arr[-1] + arr[-2] <= 4000000) || arr}.inject(0) {|total, i| total += i.even? ? i : 0}

ここでの主な懸念は、フィボナッチ数列の数値が4,000,000を超え始めるまで必要なのはそれだけであることがわかっているため、範囲(1..32)を使用していることです。 どういうわけか、これが1行に組み込まれることを希望しますが、私はそれを理解することができませんでした。

セミコロンは許可されていません!

  20  14


ベストアンサー

これに対する私のお気に入りの解決策は、ハッシュを使用することです。その値は、匿名関数によって決定できます。

fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }

fibonacci[6]  # => 8
fibonacci[50] # => 12586269025

それは「本物の」ワンライナーで、非常にルビーっぽいです。

71


Ruby 1.9列挙子の使用:

fib = Enumerator.new do |yielder|
  i = 0
  j = 1
  loop do
    i, j = j, i + j
    yielder.yield i
  end
end

p fib.take_while { |n| n <= 4E6 }
# => [1, 1, 2 ... 1346269, 2178309, 3524578]

1行として:

p Enumerator.new { |yielder| i, j = 0, 1; loop {i, j = j, i + j; yielder.yield i} }.take_while { |n| n <= 4E6}

18


アレックスの答えに触発された:

# Ruby 1.8.7
f = lambda { |x| x < 2 ? x : f.call(x-1) + f.call(x-2) }
puts f.call(6)   #=> 8

# Ruby 1.9.2
f = ->(x){ x < 2 ? x : f[x-1] + f[x-2] }
puts f[6]        #=> 8

9


私のお気に入りは:

def fib(n)
  (0..n).inject([1,0]) { |(a,b), _| [b, a+b] }[0]
end

7


これはどう?

(((1 + 5 ** 0.5) / 2) ** 35 / 5 ** 0.5 - 0.5).to_i / 2

(https://stackoverflow.com/questions/4350607/is-it-possible-to-generate-40-000-element-of-fibonacci-recursively-in-lisp/4353194#4353194 [この回答を参照]説明については)

6


遅延ではないinject / reduceを使用しないruby 2.0ソリューションを次に示します。

(1..Float::INFINITY).
  lazy.
  with_object([0,1]).
  map { |x, last| last[1] = last[0] + (last[0] = last[1]) }.
  select { |x| x % 2 == 0 }.
  take_while { |x| x < 4_000_000 }.
  reduce(&:+)

最初の0が含まれていないため、フィボナッチジェネレーターは特に好きではありません。 このソリューションでは、最初の奇数がF〜3〜(このシーケンスジェネレーターではF〜1〜)であることも利用しています。

クリーナー(フィボナッチに関して)および正しい(Liber Abaciの定義では)ソリューションは次のようになります。

(1..Float::INFINITY).
  lazy.
  with_object([0,1]).
  map { |x, last| last[1] = last[0] + (last[0] = last[1]);last[0] }.
  select { |x| x % 2 == 0 }.
  take_while { |x| x < 4_000_000 }.
  reduce(&:+)

このソリューションにはセミコロンが含まれていますが、この方法で使用した場合にカウントされるかどうかはわかりません:)。

{空} [更新]

これは、セミコロンなしの適切なフィボナッチジェネレーター(0から開始)ソリューションです(ところで、これはjavascriptセミコロンウォーズモノですか?!?):)

(1..Float::INFINITY).
  lazy.
  with_object([0,1]).
  map { |x, last| last[0].tap { last[1] = last[0] + (last[0] = last[1]) } }.
  select { |x| x % 2 == 0 }.
  take_while { |x| x < 4_000_000 }.
  reduce(&:+)

5


アレックスのハッシュに基づいて、これはあなたを盲目にするかもしれませんが、それは1行であり、セミコロンはなく、範囲依存性を排除します。 instance_evalトリックはonelinersやゴルフに非常に便利ですが、恐ろしいRubyです。

Hash.new{|h,k|h[k]=k<2?k:h[k-1]+h[k-2]}.update(sum: 0,1=>1).instance_eval {self[:sum]+= self[keys.last+1].even? ? self[keys.last] : 0 while values.last < 4E6 || puts(fetch :sum)}

出力:4613732

恐ろしいと警告しました。 セミコロンを使用せずに実際に値を返すことはできません、ごめんなさい。

3


私はこれが古代の質問であり、回答済みと分類されていることを理解していますが、誰も1つのブロックで質問を解決することはできません。実際には、1つの行と1つのブロックで、セミコロンなしで偶数値の合計を与えません(ウェインズは1行で解決することに気づいたのですが、アロスに応じて1ブロックのソリューションがいいと思いました)。 これが解決策です:

(1..Float::INFINITY).inject([0,1,0]){|a| if a[0]+a[1] < 4000000 then [a[1],a[0]+a[1],(a[0]+a[1]).even? ? a[2] + (a[0]+a[1]) : a[2]] else break a[2] end }

セミコロンが1つある、少し明確なバージョンの場合。

(1..Float::INFINITY).inject([0,1,0]){|a| sum=a[0]+a[1]; if sum < 4000000 then [a[1],sum,sum.even? ? a[2] + sum : a[2]] else break a[2] end }

私もそれを説明すると思います。3つの情報が配列に繰り越されます(各反復で「a」として)、最初のフィボナッチ数、2番目のフィボナッチ数、偶数項の合計。 これを念頭に置いて、このコードは非常に明確なルビーだと思います。

これは1つのブロックを除いて基本的にクレムと同じであることに注意してください

3


`Fib(70)`までの正しい値を返します。 しかし、非常に高速です。

(((Math.sqrt(5.0) + 1.0) / 2.0)**n / Math.sqrt(5.0) + 0.5).floor

(https://en.wikipedia.org/wiki/Fibonacci_number#Computation_by_roundingを参照してください)

2


puts (1..20).inject([0, 1]){|Fibonacci| Fibonacci << Fibonacci.last(2).inject(:+) }

これは、injectキーワードを使用してフィボナッチシリーズを印刷するために使用した最高のソリューションです。 説明:1) `.inject([0,1])`は、シリーズのコレクション(1)要素のデフォルト値(0)最初の値を保持します。 2)最初にFibonacciオブジェクトは0、1を持ち、 `Fibonacci.last(2)`がインジェクトを通過します3) `.inject(:+)`は0 + 1を追加します4)これは0 + 1を追加します= 1である場合、「フィボナッチ」にプッシュされ、外側の「inject([0,1])」との次の反復で「inject(1,2)」になります。ここで、1は合計(0 + 1)の後の値です。 2は、コレクションの次の反復値です。 収集の終わりまでなど

シリーズは次のようになります

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946

2


タイトルとURLをコピーしました