lotnikoss
28 Czerwiec 2010 17:40
#1
witam, potrzebuje odpowiedzi następujących pytań. btw. wertowałem google ale nie znalazłem satysfakcjonującej mnie odpowiedzi.
Jak
rozpoznać, że rekurencja jest krańcowa?
Przedstaw algorytm wyznaczający n-ty wyraz ciągu Fibonacciego w czasie zależnym liniowo od n.
nie chodzi mi o przedstawianie algorytmu, tylko co znaczy w ‘czasie zalężnym liniowo od n’?
3.Wykaż, że algorytm wyczerpująco rozwiązujący problem komiwojażera jest klasy 0[n!]
Ile kroków rekurencyjnych wykona klasyczny algorytm (z rekurencją drzewiastą) wyznaczający n-ty wyraz ciągu Fibonacciego. Uzasadnij
Wykaż, że klasyczny algorytm potęgowania jest klasy 0[n].
z góry wielkie dzięki za pomoc, wskazówki.
lotnikoss
28 Czerwiec 2010 18:57
#3
czyli ilość kroków plus zero? dla 10 wyrazu to będzie 0 1 2 3 4 5 6 7 8 9 10?
#include
#include
#include
#include
int fib(int n){
if(n < 2){ return n; }
else{ return fib(n-1)+fib(n-2); }
}
int main(void){
printf(" **************************************************** \n");
printf("Wyliczenie wartosci n-tego wyrazu ciagu Fibonacciego \n");
printf(" **************************************************** \n");
int n, wynik;
char wybor;
do{
printf("Podaj n: "),
scanf("%d", &n);
wynik=fib(n);
printf("Wartosc ciagu Fibonacciego dla n= %d", n);
printf(" wynosi: %d\n", wynik);
printf("Czy nastepny wyraz ? [t/n]: \n"),
wybor=getch();
} while(wybor=='t'||wybor=='T');
system("PAUSE");
return 0;
}
co zmienić by ten program liczący nty wyraz ciągu finobaciego (rekurencyjnie) spełniał wymagania?
system
28 Czerwiec 2010 19:38
#4
pewnie chodzi o rekursję ogonową: http://pl.wikipedia.org/wiki/Rekursja_ogonowa
w językach funkcyjnych tak się realizuje pętle
coś w ten deseń (ogonowo) - nie mam dostępu do kompilatora więc nie sprawdzałem
int fib(int n){
return aux(n,1,1);
}
int aux(int n ,int f_n1 , int f_n2){
(n == 1) ? return f_n2 : return aux(n-1, f_n2 , f_n1 + f_n2) ;
}
korzystasz z matematycznej definicji potęgi:
x^0 = 1
x^n = x * x^n-1
i od razu widać, że wykładnik się musi zmienić n razy, żeby otrzymać szukana potęgę
_alex
28 Czerwiec 2010 19:39
#5
fib(0) - jedno wywołanie
fib(1) - jedno wywołanie
fib(2) - wywoła: fib(1) i fib(0), razem 3 wywołania
fib(3) - wywoła: fib(2) i fib(1), razem 5 wywołań
fib(4) - wywoła: fib(3) i fib(2), razem 9 wywołań
czyli:
IloscWywolanDla(0) = 1, IloscWywolanDla(1) = 1, IloscWywolanDla(N) = IloscWywolanDla(N-1)+IloscWywolanDla(N-2)+1
Wystarczy zmienić funkcje fib(). Ma być iteracyjna lub rekurencyjna z zapamiętywaniem.
lotnikoss
28 Czerwiec 2010 20:27
#6
#include
#include
#include
#include
int fib(int n) {
if(n==0) return 0;
int a, b,i;
a = 0; b = 1;
for(i=0;i<(n-1);i++) {
b += a;
a=b-a;
}
return b;
}
int main()
{
printf(" **************************************************** \n");
printf("Wyliczenie wartosci n-tego wyrazu ciagu Fibonacciego \n");
printf(" **************************************************** \n");
int n=50, wynik;
char wybor;
do{
wynik=fib(n);
printf("Wartosc ciagu Fibonacciego dla n= %d", n);
printf(" wynosi: %d\n", wynik);
printf("Czy nastepny wyraz ? [t/n]: \n"),
wybor=getch();
} while(wybor=='t'||wybor=='T');
system("PAUSE");
return 0;
}
dzięki Bogu za takich użytkowników jak [alex] & MasterOfPumpets i nie tylko. kłaniam się.
_alex
29 Czerwiec 2010 04:41
#7
ależ nakombinowałeś !
long long /*int*/ fib(int n)
cinekcnx
30 Czerwiec 2010 19:26
#8
przydałaby się definicja waszego algorytmu wyczerpującego ale zakładam że jest to taki który sprawdza wszystkie możliwe kombinacje czyli tworzy wszystkie możliwe trasy pomiędzy wierzchołkami grafu i sprawdza która jest najkrótsza (travelling salesman problem). Takie mieszanie wierzchołków aby powstał zestaw różnych tras nazywa się fachowo permutacją a wzór na nią to: n!
I to w sumie powinno odpowiedzieć na pytanie dlaczego złożoność tego algorytmu to O[n!]
