Fibonacci One-Liner

Question

我正试图用Ruby单行解决Project Euler中的问题,我很好奇是否有更优雅的问题解决方案:

Fibonacci序列中的每个新术语都是通过添加前两个术语生成的.从1和2开始,前10个术语将是:

1,2,3,5,8,13,21,34,55,89 ......

通过考虑Fibonacci序列中的值不超过四百万的项,找到偶数项的总和.

这是我在Ruby中的一行解决方案:

(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}

我主要担心的是我只使用范围(1..32),因为我碰巧知道在Fibonacci序列中的数字开始超过4,000,000之前,这一切都是必要的.我希望不知怎的,它会以某种方式构建在单行中,但我无法弄明白.

不允许使用半冒号!

Answer 1

我最喜欢的解决方案是使用哈希值,其值可以通过匿名函数确定:

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

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

这是一个"真正的"单行和Ruby-ish.

Answer 2

使用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]

作为一行:

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

Answer 3

灵感来自亚历克斯的答案:

# 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

Answer 4

我最喜欢的是:

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

来自https://gist.github.com/1007228

Answer 5

这个怎么样？

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

(请参阅此答案以获得解释.)

Answer 6

这是一个ruby 2.0解决方案,不使用非懒惰的inject/reduce:

(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 ₃(此序列发生器中的F ₁).

更清洁(斐波那契)和正确(在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(&:+)

这个解决方案包括一个分号,但我不知道这样使用时它是否重要:).

[更新]

这是一个合适的Fibonacci生成器(从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(&:+)