Fibonacci One-Liner
我正试图用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之前,所有这一切都是必要的。 我不希望这种情况以某种方式构建到单行中,但我无法弄明白。
不允许使用半冒号!
灵感来自亚历克斯的答案:
# 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
我最喜欢的解决方案是使用哈希值,其值可以由匿名函数确定:
fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] } fibonacci[6] # => 8 fibonacci[50] # => 12586269025
这是一个“真正的”单行和非常的Ruby-ish。
使用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}
我最喜欢的是:
def fib(n) (0..n).inject([1,0]) { |(a,b), _| [b, a+b] }[0] end
来自https://gist.github.com/1007228
这个怎么样?
(((1 + 5 ** 0.5) / 2) ** 35 / 5 ** 0.5 - 0.5).to_i / 2
( 请参阅此答案以获得解释。)
这是一个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 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(&:+)
这个解决方案包括一个分号,但我不知道用这种方式是否重要:)。
[更新]
这是一个合适的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(&:+)
在Alex的Hash的基础上,这可能会让你失明,但它是一行,没有分号,并消除了范围依赖。 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
我警告过你这太可怕了。 对不起,我不能让它实际返回值而不使用分号。
我意识到这是一个古老的问题,已被归类为已回答,但没有人设法在一个区块中解决问题,它们实际上没有给出一行中和一个区块中没有半冒号的偶数项的总和(只是注意到Waynes确实解决了一行,但我认为一个块解决方案可能很好响应aroth)。 这是一个解决方案:
(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 }
我想我也会解释它,三个信息在arrays中(在每次迭代时)在第一个斐波纳契数,第二个斐波纳契数和偶数项的总和上结转。 考虑到这一点我认为这段代码非常清楚ruby。
应该注意的是,除了一个方块外,这与clems基本相同
返回高达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 )
puts (1..20).inject([0, 1]){|Fibonacci| Fibonacci << Fibonacci.last(2).inject(:+) }
这是我曾经用过使用inject关键字打印Fibonacci系列的最佳解决方案。 说明:1) .inject([0,1])
将保持系列的collection(1)元素的默认值(0)第一个值。 2)首先Fibonacci对象将有0,1使用Fibonacci.last(2)
将通过注入3) .inject(:+)
将添加0 + 1 4)这将添加0 + 1 = 1然后将被推送到Fibonacci
,在下一次迭代时,外部inject([0,1])
将成为inject(1,2)
这里1是sum(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
使用ruby 2.0中的新懒人,你可以这样写。
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(:+)
作为上述答案的总结解决方案,我的简单补充:
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
案例:
take_while { |value| value < 4*10**6 }.
这是Euler prob#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(:+)
(1..32).inject([0, 1]) { |fib| fib << fib.last(2).inject(:+) }
简单而优雅是最好的方法,对吧?
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
这是我的一个class轮,当我们得到方法返回时, @fib
表被填充。
@fib=[0,1];def fib num; return 0 if num < 0; @fib[num]||=fib(num-1)+fib(num-2);end