Zadania-6-Przemysław-Burzawa-Gr2, Ujk Informatyka 2014, Asid

//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}Algorytmy i Struktury DanychZadanie 6Przemysław Burzawa1. Zaimplementuj iteracyjny i rekurencyjny algorytm wyznaczania n-tego elementu ciągu Fibonacciego#include <stdio.h>using namespace std;int N,n;unsigned int fib(unsigned int n){N++if (n < 2){Return n;}else{return fib(n-1) + fib(n-2);}}unsigned int fibIt(unsigned int n){if (n < 2){return n;}else{unsigned int n_1=1, n_2 =0,wynik;for (unsigned int i = 2; i <=n; ++i){wynik =n_1 + n_2;n_2 = n_1;n_1 = wynik;N++;}}}int main();{N=1;n=fib(20);cout << "Ci¹g Fibbonaciego metod¹ rekurecyjn¹: " << n << endl;cout << "Ilosc wywolan funkcji :"<< N << endl;cout << "\n\n" <<endl;N=1;n=fibIt(20);cout << "Ciag Fibbonaciego metoda iteracyjna:" << n << endl;cout << " Ilosc wywolan funkcji: "<< N << endl;return 0;Algorytmy i Struktury DanychZadanie 6Przemysław BurzawaMetoda rekurencyjna jest niewydajna ponieważ jest wywoływana bardzo dużo razy i każda wartośćjest odrzucana na stos co zajmuje bardzo dużo pamięci i wymaga ogromnej liczby niepotrzebnychobliczeń.Metoda iteracyjna jest troche bardziej złożona lecz dużo bardziej wydajna ponieważ liczy w pętlikolejne wyrazy ciągu odwołując się do wyrazu zapisanego tymczasowo i nie przechowuje wszystkichwartości w pamięci na raz.2. Przeprowadź analizę zależności liczby wykonanych operacji (N) odnumeru elementu ciągu (n). Wyniki analizy przedstaw w tabeli (dlawybranych co najmniej dziesięciu wartości n) oraz na wykresieprzedstawiającym zależność N od n dla obu algorytmów.Intel Core I3 | 2.25Ghz | 2 RdzenieMetoda RekurencyjnaNumer CiąguIlość wywołań5161017815197420218922524278630269253835298607044033116028245Wyszła liczba na minusie -62234349050Zajmuje za dużo czasu55-60-Czas Operacji0,103 s0,073 s0,063 s0,073 s0,071 s0,078 s0,197 s1,407 s13,818 s---Metoda IteracyjnaNumer CiąguIlość wywołań5510101515202025253030353540404545505055556060Czas Operacji0,060 s0,067 s0,064 s0,073 s0,071 s0,069 s0,063 s0,060 s0,073 s0,071 s0,067 s0,069 sAlgorytmy i Struktury DanychZadanie 6Przemysław BurzawaMetoda rekurencyjna35000000030000000025000000020000000015000000010000000050000000NumerCiągu510152025303540Ilość wywołańMetoda Iteracyjna7060504030201051015202530354045505560Ilość wywołań3. Dla algorytmu rekurencyjnego oszacujn,dla którego czasobliczania wartości elementu ciągu wynosi ok. tygodnia.Dla 40 elementu – 1,407 sDla 41 elementu – 2,290 sDla 42 elementu – 3,414 sDla 43 elementu – 5,490 sDla 44 elementu – 8,510 sDla 45 elementu – 13,818 sDla x elementu – 604800,000 sAlgorytmy i Struktury DanychZadanie 6Przemysław BurzawaWygląda na to że czas w liczeniu ciągu Fibbonaciego rośnie tak samo jak i ciąg Fibbonaciego (1,2,3,5,8,13 sekund ). Tydzień ma 604800 sekund. Przyjmijmy że nasz 40 element w funkcji to 2element ciągu Fibonacciego, 41 element to 3 element ciągu Fibonnaciego. Sprawdźmy teraz któryelement ciągu Fibonacciego ma wartość 604800.Fib ( 29 ) = 514 229Fib ( 30 ) = 832 040Przyjmijmy więc że ten tydzień to 29 element ciągu, więc z założenia że 40 element w funkcji to 2element ciągu Fibonaciego to musimy dodać do tego 29 elementu te 38 które nam zostaje ( 40-2 )więc otrzymamy liczbę 67.Obliczanie 67 wartości ciągu Fibonacciego metodą rekurencyjną zajmie nam troszke mniej jaktydzień.

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

kachorra.htw.pl