Ansi C, pyt problemowe.

mariohouseboy · Post autor: **mariohouseboy** » 28 cze 2010, o 19:38

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?
2. 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!]
4. Ile kroków rekurencyjnych wykona klasyczny algorytm (z rekurencją drzewiastą) wyznaczający n-ty wyraz ciągu Fibonacciego. Uzasadnij
5. Wykaż, że klasyczny algorytm potęgowania jest klasy 0[n].

mcbob · Post autor: **mcbob** » 28 cze 2010, o 21:03

Sorki ale nie bardzo rozumiem jak się ma ANSI C z tematu do tych zadań? Przecież to czysto algorytmiczne problemy.

mariohouseboy · Post autor: **mariohouseboy** » 28 cze 2010, o 21:26

mcbob pisze:Sorki ale nie bardzo rozumiem jak się ma ANSI C z tematu do tych zadań? Przecież to czysto algorytmiczne problemy.

sorki, jeśli źle sprecyzowałem nazwę tematu. ANSI C bo praktykują u nas C, dlatego tak.
czy ktoś może pomóc?

mcbob · Post autor: **mcbob** » 28 cze 2010, o 21:46

Miałem coś od siebie napisać na te pytania ale widzę że już trochę ci napisali tu

i tu coś też jest

Więc chyba nie ma co powtarzać tego co tam napisali