Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Najpierw potrzebujemy szybkiej funkcji do wyliczenia sekwencji fib (wersja rekurencyjna w Ruby 1.8.6) jest za wolna dla n > 30 :
def fib(n)
a,b = 0,1
n.times { a+=b; a,b=b,a}
a
end
Teraz budujemy tablicę wartości z sekwencji które spełniają podane warunki:
code=ruby.map {|x| fib(x)}.select {|x| x % 2 == 0 && x < 4000000}.inject {|sum,n| sum+n}
=> 4613732[/code]
Rozwiązanie wg. mnie jest OK ale nie podoba mi się założenie z góry (1…100) na początku (zakładam że wiem że fib(100) jest o wiele większe niż 4 miliony)
Od wersji 1.8.7 można bardzo elegancko poradzić sobie z tym warunkiem < 4_000_000:
[code=ruby]def fib_iter
raise ArgumentError unless block_given?
a, b = 0, 1
loop do
yield a
a, b = b, a + b
end
end
puts enum_for(:fib_iter).take_while {|e| e < 4_000_000}.select {|e| e % 2 == 0}.inject {|sum, e| sum += e}[/code]
A może tak :]
i = [1,1]
while i.last < 4000000 do i.push(i[-1] + i[-2]) end
i.select {|i| i % 2 == 0}.inject(0) {|sum, a| sum + a}
i.push(i[-1] + i[-2]) while i.last < 4000000wyglada ladniej ;]
t << t[-1]+t[-2] while t[-1] < 4000000
p t.select { |x| x % 2 == 0 }.inject(0) { |x, y| x+y }
Moze tak co?
NameError: undefined local variable or method `t’ for main:Object
^^
zapomnialem o:
t = [0, 1]
w kodzie to mam
daj spokoj ten blad da sie szybko usunac
w kodzie mialem poprawnie tylko podczas wklejania popelnilem blad
IMHO najładniejsza kombinacja powyższych to:
fib = [1,2]
fib << fib[-1] + fib[-2] while fib.last < 4_000_000
fib.select(&:even?).inject(:+) # => 4613732
Wartość n-tego wyrazu ciągu Fibonacciego można także obliczać z takiego śmiesznego wzoru:
[code=Ruby]fn = (fi ** n - (1 - fi) ** n) / Math.sqrt(5)
fi = (1 + Math.sqrt(5)) / 2[/code]
Cały kod poniżej:
[code=Ruby]found = false
n = sum = 0
fn_max = 4000000
fi = (1 + Math.sqrt(5)) / 2
while !found
n += 1
fn = ((fi ** n - (1 - fi) ** n) / Math.sqrt(5)).to_i
sum += fn if (fn % 2 == 0) && (fn < fn_max)
found = true if fn > fn_max
end
p sum
#=> 4613732[/code]
Witam, poniżej zamieszam kod.
def fibonacci(max)
l1, l2 = 1, 2
n = []
while l1 <= max
n.push(l1)
l1, l2 = l2, l1 + l2
end
result = n
end
puts fibonacci(4000000)
wynik = fibonacci(4000000).inject {|suma, element| suma+element}
puts wynik # 9227463
Co może być przyczyną złego wyniku?
nie przefiltrowałeś tablicy na podstawie warunku z treści problemu
O co chodzi w tym warunku? Próbowałem ze słownikiem ale jakoś nie za bardzo kumam 8).
Przed chwilą to odkryłem mimo to dzięki za pomoc :D.
[quote=Shot]IMHO najładniejsza kombinacja powyższych to:
fib = [1,2]
fib << fib[-1] + fib[-2] while fib.last < 4_000_000
fib.select(&:even?).inject(:+) # => 4613732
[/quote]
Tak właśnie się zorientowałem, że powinno być:
fib = [1,2]
fib << fib[-1] + fib[-2] while fib[-1] + fib[-2] < 4_000_000
fib.select(&:even?).inject(:+) # => 4613732
I tylko dlatego, że pierwszy element tablicy przekraczający 4M jest nieparzysty (5_702_887) program daje poprawny wynik…