Фибоначчи с одним вкладышем

Question

Я пытаюсь решить вопросы из Project Euler в Ruby one-liners, и мне любопытно, есть ли более элегантное решение для вопроса два :

Каждый новый член в последовательности Фибоначчи генерируется путем добавления двух предыдущих членов.Начиная с 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

Мое любимое решение для этого - использовать хэш, значения которого могут быть определены анонимной функцией:

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, без использования инжекта / редуцирования, которое не лениво:

(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Решение Абачи) должно быть таким:

(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

Я понимаю, что это древний вопрос и был классифицирован как ответ, но никто не может решить вопрос в одном блоке, ни один из них на самом деле не дает сумму четных терминов в одной строке и в одном блоке и с нет двоеточий (просто заметил, что Уэйнс решает с одной строкой, но я думал, что решение с одним блоком может быть хорошим в ответ на 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 }

Полагаю, я тоже это объясню, три части информации переносятся в массиве (как a на каждой итерации): первое число Фибоначчи, второе число Фибоначчи и сумма четных членов. Имея это в виду, я думаю, что этот код вполне понятен Ruby.

следует отметить, что это в основном то же самое, что и clems, за исключением одного блока

Answer 8

Опираясь на хэш Алекса, это может заставить вас ослепнуть, но это одна строка, без точек с запятой и устраняет зависимость от диапазона. Трюк 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 9

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

Это лучшее решение, которое я когда-либо использовал для печати серии Фибоначчи с использованием ключевого слова inject.Объяснение: 1) .inject([0,1]) будет содержать значение по умолчанию (0) первого значения элемента collection (1) серии.2) Сначала объект Фибоначчи будет иметь 0, 1, используя Fibonacci.last(2), который будет передан через инъекцию 3) .inject(:+) добавит 0 + 1 4) Это добавит 0 + 1 = 1, а затем будет перемещено в Fibonacci который на следующей итерации с внешним 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

Answer 10

Возвращает правильные значения до 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 для объяснения)