斐波那契单线

Question

我正在尝试用 Ruby 单行代码解决 Project Euler 中的问题，我很好奇是否还有更多问题二的优雅解决方案：

斐波那契数列中的每一项新项都是通过添加前两项而生成的。从 1 和 2 开始，前 10 项将是：

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

考虑斐波那契数列中值不超过四百万的项，求偶数项的总和。

这是我在 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) 只是因为我碰巧知道这就是斐波那契数列中的数字开始超过 4,000,000 之前所必需的全部内容。我希望以某种方式将其内置到单行中，但我一直无法弄清楚。

不允许使用分号！

Answer 1

我最喜欢的解决方案是使用 Hash，它的值可以由匿名函数确定：

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

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

它是一个“真正的”单行代码并且非常 Ruby 风格。

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 解决方案，不使用注入/减少，这并不懒惰：

(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(&:+)

该解决方案包含一个分号，但我不知道以这种方式使用它是否有效:)。

[更新]

这是一个正确的斐波那契生成器（从 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(&:+)

Answer 7

建立在 Alex 的哈希之上，这可能会让你失明，但它只有一行，没有分号，并且消除了范围依赖性。 instance_eval 技巧对于单线和高尔夫非常有用，尽管它是可怕的 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

我警告过你这太可怕了。抱歉，我无法让它在不使用分号的情况下实际返回值。

Answer 8

我意识到这是一个古老的问题，已被归类为已回答，但没有人能够在一个块中解决这个问题，他们中没有一个人真正给出一行和一个块中偶数项的总和，并且没有分号（刚刚注意到韦恩斯确实用一行解决了问题，但我认为一个块解决方案可能会很好地响应阿罗斯）。这是一个解决方案：

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

我想我也会解释一下，数组中会传递三条信息（在每次迭代时作为 a）：第一个斐波那契数、第二个斐波那契数以及偶数项的总和。考虑到这一点，我认为这段代码是相当清晰的 ruby​​。

应该注意的是，除了一个块之外，这与 clems 基本相同

Answer 9

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

这是我曾经使用过的使用注入关键字打印斐波那契数列的最佳解决方案。
解释：
1) .inject([0,1]) 将保存系列的集合 (1) 元素的默认值 (0) 第一个值。
2) 首先斐波那契对象将有 0, 1 使用 Fibonacci.last(2) 将通过注入传递
3) .inject(:+) 将添加 0+1
4) 这将添加 0+1 = 1，然后将被推送到 Fibonacci，在下一次迭代时外部 inject([0,1]) 将变为 注入(1,2)
这里1是sum(0+1)之后的值，2是collection的下一次迭代值。
依此类推，直到收集结束

所以该系列将是这样的

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

Answer 10

我现在能想到4种方法来实现斐波那契目标！

1. 使用稳定 lambda：

puts 'Fibonacci Sequence in a Line: ', ->(a=1, b=0) { 10.times.collect { (a, b = b, a + b)[0] } }.call

这会评估 10 系列。但如果你想获取用户的号码：

puts 'Fibonacci Sequence in a Line: ', ->(a=1, b=0) { gets.to_i.times.collect { (a, b = b, a + b)[0] } }.call

2. 使用 tap 方法：

[0, 1].tap { |a| 10.times { a.push(a[-1] + a[-2]) } }

3. 使用 reduce/inject 方法：

(1..10).reduce([0, 1]) { |a| a.push(a.last(2).sum) }

或

10.times.reduce([0, 1]) { |a| a.push(a.last(2).sum) }

4. 使用 each_with_object 或 map.with_object 方法：

10.times.each_with_object([0, 1]) { |_, a| a.push(a.last(2).sum) }

注意：如果您没有 Ruby 2.4+，则可能没有 sum 方法。在这种情况下，您可以使用 ary[-2] + ary[-1] 或 ary.last(2).reduce(:+) 添加最后两个元素。

来到你的问题：

考虑斐波那契数列中值不超过四百万的项，求偶数项的总和。

[0, 1].tap { |a| until (s = a.last(2).sum) > 4_000_000 do a.push(s) end }.select(&:even?).sum

或者（这不是那么好）：

[0, 1].tap { |a| loop while a.push(a.last(2).sum)[-1] < 4_000_000 }.tap(&:pop).select(&:even?).sum

输出：
4613732

希望这有帮助！

Answer 11

返回 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 用于解释）

Answer 12

使用ruby 2.0中新的lazy，你可以这样写。

puts (1..Float::INFINITY).lazy.map{|n| (0..n).inject([1,0]) {|(a,b), _| [b, a+b]}[0] }.take_while{|n| n < 4000000}.select{|x| x % 2 == 0}.reduce(:+)

Answer 13

作为上述答案的总结解决方案，我做了一些谦虚的补充：

32.
  times.
  lazy.
  with_object([0, 1]).map { |_, fib| fib[1] = fib[0] + fib[0] = fib[1]; fib[0] }.
  take_while(&:>.to_proc.curry(2)[4*10**6]).
  select(&:even?).
  inject(:+)

我不太喜欢柯里化的外观，但不希望它看起来与其他答案相似。针对这种情况的替代 take_while ：

  take_while { |value| value < 4*10**6 }.

Answer 14

这是 Euler 问题 #2 的单行 ruby​​ 解决方案

(0..4000000).take_while{|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0] <= 4000000 }.map{|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0] }.select{|i| i%2 == 0}.reduce(:+)

或者为了更好的可读性？

(0..4000000) .
take_while {|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0] <= 4000000} .
map {|i| (0..i).reduce([1,0]){|(a,b), _| [b, a+b]}[0]} .
select {|i| i%2 == 0} .
reduce(:+)

Answer 15

(1..32).inject([0, 1]) { |fib|纤维 << fib.last(2).inject(:+) }

Answer 16

这是我的一个行，当我们得到方法返回时，@fib 表被填充。

@fib=[0,1];def fib num; return 0 if num < 0; @fib[num]||=fib(num-1)+fib(num-2);end

Answer 17

简单又优雅才是最好的方式吧？

a0 = 1; a1 = 1; 20.times {|i| b = a0 + a1; a0 = a1; a1 = b; puts b };

输出：

2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
=> 20