--> Archiwum Forum
Prezes_Krzychu [ PREZES ]
Programowanie: problem z c....takie mala zadanko
Ktos wie jak rozwiazac zadanie w c..napisac taki oto program :
Dana jest funcja int f(int a, int b). Pewien ciag liczb naturalnych okreslony jest indukcyjnie : a(1)=1 , a(2)=2, a(n)=f(a(n-1), a(n-2)) dla n>2. Napisz program w c tak aby nie przeciazyc pamieci komputera....
ladnie zadanko....moze ktos pomoze :)
CooN [ Generaďż˝ ]
A co ten program ma ewentualnie liczyc?
Pamir [ Generaďż˝ ]
eeee, napewno dobrze to napisałeś? a może to miał byc ciąg Fibonacciego?
Prezes_Krzychu [ PREZES ]
taka jest tresc zadania.....wlasnie kolosa z tego pisze....:>
CooN [ Generaďż˝ ]
Troche nie bardzo rozumiem tez, ze ciag okreslony jest indukcyjnie. Wg mnie raczej nie jest.
Juz bardziej zwiazek rekurencyjny...
Napisz, ze zadanie jest tak sformulowane, ze rozwiazaniem moze byc kazdy program, byle nie przeciazal pamieci komputera ;-))
Pamir [ Generaďż˝ ]
ehhhh, no dobra spoko, ale ja nie łapię w takim razie po co jest int b w tef f.
Jeśli chodzi juz o sam proces optymalizacji, chodzi najprawdopodobniej o zastosowanie tablicy aby przypisywać do niej liczone wartości ciagu a potem sprawdzać czy juz ch nie ma aby nie liczyc ich wielokrotnie, mi to strasznie przypomina optymalizację liczenia n kolejnych wyrazów ciagu Fibonacciego...
Metoda rekurencyjna
typedef int Type;
Type Fib(Type i)
‹
if(i < 1) return 0;
if(i == 1) return 1;
return (Fib(i – 1) + Fib(i – 2) );
›
Ta metoda ma wykładniczy czas działania, jest bardzo nieefektywna z powodu częstości obliczania tych samych wartości podczas przechodzenia przez drzewo rekurencji.
Sposobem poprawienia wydajności algorytmu jest zadeklarowanie tablicy już obliczonych liczb Fibonacciego i sprawdzania w każdym wywołaniu rekurencyjnym, czy wartość funkcji z aktualnym argumentem nie była już wcześniej obliczona. Jest to przykład dynamicznego programowania zstępującego. Czas wykonywania tego algorytmu jest liniowy.
typedef int Type;
Type Fib(Type i)
‹
static Type KnownFib[100];
// deklarowana tablica znalezionych liczb Fibonacciego
if(i < 0) return 0;
if(!KnownFib) return KnownFib;
// jeżeli w tablicy jest zapisana liczba
Type t = i;
if(i > 1) t = Fib(i – 1) + Fib(i – 2);
return KnownFib = t;
// przypisanie do tablicy i zwrócenie wartości
›
Bo tego twojego zapisu nie jestem wstani załapać, ale to byc może dlatego że spac mi się jeszcze chce :-D, ale jeszcze nad tym pomyślę...
Pozdrowienia Pamir
Prezes_Krzychu [ PREZES ]
...zapis zadania to wina kolesia od podstaw programowania...
ale dzieki wielkie
Prezes_Krzychu [ PREZES ]
program ma obliczac a(n).......
Prezes_Krzychu [ PREZES ]
..no i po kolosie.....za tydzien podziele sie wynikami...:)
Pamir [ Generaďż˝ ]
No nie ja już nie mogę, jak dla mnie to zadanie sensu nie ma...... :/, jaki to ma być qrna ciąg?? : 1, 2, a potem wynik f(a9n-1),a(n-2), ale co ma liczyć ta f ?? musisz wiedzieć co ma liczyć ta funkcja aby móc zwrócić jej wartość....
POzdrowienia Pamir