ciąg fibonaciego
Janusz: Witam.
Nie miałem nigdy do czynienia z ciągiem Fibonacciego stąd zadanie, którego treść brzmi:
"Napisz program, który wypisze kolejne wyrazy ciągu, ktorego wyrazy zdefiniowane są
następująco:
fib(0) = 1
fib(1) = 1
fib(n) = fib(n−1)+fib(n−2) dla n >=2
Pierwszym krokiem do napisania programu jest zrozumienie, o co w ogóle chodzi.
Przypuszczam, że zadanie polega na podstawieniu za n liczb równych i większych od 2 i wypisanie
wartości dla danego n, co wyglądałoby następująco:
fib(2) = fib(2−1)+fib(2−2) = 1+0 = 1
fib(3) = fib(3−1)+fib(3−2) = 2+1 = 3
fib(4) = fib(4−1)+fib(4−2) = 3+2 = 5
itd
Czy słusznie dedukuję?
21 mar 22:26
Benny: Masz podany wzór rekurencyjny. Aby obliczyć jakiś wyraz tego ciągu, komputer musi znać dwa
poprzednie wyrazy, jeśli ich nie zna, znowu rozbija ze wzoru.
21 mar 22:32
Adamm: no chyba że zna się wzór ogólny
21 mar 22:52
Janusz: Dzięki Panowie, rozjaśniliście mi aż nazbyt wiele.
21 mar 23:13
Mila:
W internecie chyba jest gdzieś wzór jawny.
21 mar 23:51
22 mar 00:01
Dziadek Mróz: fib(n) :
if n < 2:
return 1
else:
return fib(n−1) + fib(n−2)
fib(5):
5 < 2 − N
return fib(4)+fib(3)
fib(4):
4 < 2 − N
return fib(3)+fib(2)
fib(3):
3 < 2 − N
return fib(2)+fib(1)
fib(2):
2 < 2 − N
return fib(1)+fib(0)
fib(1):
1 < 2 − T
return 1
fib(0):
0 < 2 − T
return 1
return 2
fib(1):
1 < 2 − T
return 1
return 3
fib(2):
...
return 2
return 5
fib(3):
...
return 3
return 8
22 mar 00:41
Mariusz:
function fib(n:integer):real; {funkcja zbyt szybko przekroczy zakres typu integer}
var fib0,fib1,temp:real;
k:integer;
begin
fib0:=0;
fib1:=1;
for i:=1 to n do
begin
temp:=fib1;
fib1:=fib0+fib1;
fib0:=temp;
end;
fib:=temp1;
end;
Można wyeliminować zmienną lokalną tymczasowo przechowującą
wartość fib1
Możesz skorzystać z funkcji tworzącej i wyprowadzić wzór który będzie potrzebował
dwóch wywołań funkcji potęgującej
22 mar 02:47
Mariusz:
Oczywiście licznikiem iteracji jest k a nie i
22 mar 02:49
Mateusz: Najlepiej ten program napisać stosujac programowanie dynamiczne. Polega ona na tym, iż
rozwiązanie wyższego poziomu obliczamy z rozwiązań otrzymanych na poziomie niższym, które
odpowiednio zapamiętujemy. Dzięki temu podejściu program nie musi liczyć wszystkich składników
od początku, wykorzystuje wyniki poprzednich obliczeń. W efekcie klasa złożoności
obliczeniowej algorytmu spadnie do O(n)
22 mar 10:47
jc: Mateuszu, rozwiązanie Mariusza też daje czas O(n).
22 mar 11:07
Mateusz: Widziałem napisałem to do autora zadania żeby go uświadomić i żeby np porównał sobie
efektywność tradycyjnego algorytmu z tym
22 mar 11:29
Mariusz:
Zwracamy fib0
fib:=fib0;
ale to chyba oczywiste jeśli chcemy zachować warunek początkowy
22 mar 11:46