Detyra për analizimin e algoritmeve

[enes_212]

A ka mundesi te mi sqaron ndojkush keto detyra.



1.
Algoritmi rekurziv vijues, i përkthyer në gjuhën programuese C++:

#include
using namespace std;

int fib (int n)
{
if (n<3)
return (1);
else
return (fib(n-2)+fib(n-1));
}
int main()
{
cout<<"Fibbonaciu Numbers: 1, 1, 2, 3, 5, 8, 13, 21,...\n"< int n, Result;
cout<<"n = "; cin>>n;
Result=fib(n);
cout<<"\n\tfib ( "<

[edspace]

Për ushtrimin e parë, të duhet të masësh kohën e ekzekutimit kur numri është 1, 5, 10, 20, 30, 40, 50. Kohën mund ta masësh duke modifikuar programin si më poshtë:

#include <iostream>
#include <ctime>

using namespace std;

int fib (int n)
{
    if (n<3)
        return (1);
    else
        return (fib(n-2)+fib(n-1));
}

int main() {

    cout<<"Fibbonaciu Numbers: 1, 1, 2, 3, 5, 8, 13, 21,...\n" << endl;
    int n, Result;

    cout << "n = ";
    cin >> n;

    clock_t fillimi = clock();
    Result = fib(n);
    cout << "\n\tfib ( " << n << " ) = " << Result << endl;
    cout << "Koha: " << (double) (clock() - fillimi) / CLOCKS_PER_SEC << endl;

    cin.get();
    cin.get();

    return 0;
} 

Kjo do na japë këto të dhëna:

-------------------------------------------------------------
Fibbonaciu Numbers: 1, 1, 2, 3, 5, 8, 13, 21,...

n = 1
fib ( 1 ) = 1
Koha: 0
-------------------------------------------------------------
n = 5
fib ( 5 ) = 5
Koha: 0
-------------------------------------------------------------
n = 10
fib ( 10 ) = 55
Koha: 0
-------------------------------------------------------------
n = 20
fib ( 20 ) = 6765
Koha: 0
-------------------------------------------------------------
n = 30
fib ( 30 ) = 832040
Koha: 0.02
-------------------------------------------------------------
n = 40
fib ( 40 ) = 102334155
Koha: 2.073
-------------------------------------------------------------
n = 50
fib ( 50 ) = -298632863  <-- gabim mbingarkesë (overflow)
Koha: 261.726
-------------------------------------------------------------

Grafiku i të dhënave është bashkëngjitur më poshtë. Nga grafiku duket qartë se koha e ekzekutimit ka rritje eksponenciale. Koha e ekzekutimit të funksionit fib() është konstante, por funksioni ekzekutohet O(2^N) herë. Një analizë më të detajuar të funksionit e gjen këtu.

N = 1: 1                          = 2^0
N = 2: 2                          = 2^0
N = 3: 2, 1                       = 2^1
N = 4: 3, 2, 2, 1                 = 2^2
N = 5: 4, 3, 3, 2, 2, 1, 2, 1     = 2^3
...

[florxhi]

A ka mundesi te mi sqaron ndojkush keto detyra.



1.
Algoritmi rekurziv vijues, i përkthyer në gjuhën programuese C++:

#include
using namespace std;

int fib (int n)
{
if (n<3)
return (1);
else
return (fib(n-2)+fib(n-1));
}
int main()
{
cout<<"Fibbonaciu Numbers: 1, 1, 2, 3, 5, 8, 13, 21,...\n"< int n, Result;
cout<<"n = "; cin>>n;
Result=fib(n);
cout<<"\n\tfib ( "<

Përgjigju Duke Cituar

---