Ansi C, pytania problemowe,


(Mariohouseboy) #1

witam, potrzebuje odpowiedzi następujących pytań. btw. wertowałem google ale nie znalazłem satysfakcjonującej mnie odpowiedzi.

  1. Jak

rozpoznać, że rekurencja jest krańcowa?

  1. 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!]

  1. Ile kroków rekurencyjnych wykona klasyczny algorytm (z rekurencją drzewiastą) wyznaczający n-ty wyraz ciągu Fibonacciego. Uzasadnij

  2. Wykaż, że klasyczny algorytm potęgowania jest klasy 0[n].

z góry wielkie dzięki za pomoc, wskazówki. :smiley:


([alex]) #2
  1. Pierwszy raz słyszę o czymś takim jak rekurencja krańcowa.

  2. To znaczy nie kwadratowo nie wykładniczo nie logarytmicznie, zaś w czasie wprost proporcjonalnym numerowi elementu.

  3. "O" to ma się na myśli jakaś stała zaś n! to silnia z n, gdzie n - ilość wierzchołków grafu.

  4. Wystarczy że zrobisz prostą tabliczkę natychmiast zauważysz.

  5. "O" to ma się na myśli jakaś stała zaś n - to liczba potęgi, właściwie jest O[n-1] ale dla bardzo dużych n (n)==(n-1)


(Mariohouseboy) #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) #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]) #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.


(Mariohouseboy) #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ę. :smiley:


([alex]) #7

ależ nakombinowałeś !

long long /*int*/ fib(int n)

(Cinek Cnx) #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!]