Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Ciąg Fibonacciego

powrót

Ciąg Fibonacciego definiujemy następująco:

pierwszy i drugi element ciągu jest równy {tex}1{/tex}. Każdy następny otrzymujemy dodając do siebie dwa poprzednie. Matematycznie wygląda to następująco:

{tex}F_n=\left\{\begin{matrix} 1 & ,\ dla\ n=1\\ 1 & ,\ dla\ n=2\\ F_{n-2}\ + F_{n-1}& ,\ dla\ n>2\\ \end{matrix}\right.{/tex}

Inna definicja przedstawia zerowy numer ciągu jako wartość {tex}0{/tex}, pierwszy jako wartość {tex}1{/tex}, a każdy następny otrzymujemy dodając dwa poprzednie:

{tex}F_n=\left\{\begin{matrix} 0 & ,\ dla\ n=0\\ 1 & ,\ dla\ n=1\\ F_{n-2}\ + F_{n-1}& ,\ dla\ n>1\\ \end{matrix}\right.{/tex}

Kilka kolejnych wyrazów tego ciągu według pierwszej definicji przedstawia się następująco:

{tex}1,1,2,3,5,8,13,21,...{/tex}

Pierwsze rozwiązanie zostanie przedstawione metodą iteracyjną, która jest wydajna i bez problemu wyznaczymy wszystkie wyrazy ciągu, które mieszczą się w dowolnym typie w C++.

Strategia jest następująca. Zmienna {tex}a{/tex} będzie przechowywać wyraz o numerze {tex}n-2{/tex}, zmienna {tex}b{/tex} wyraz o numerze {tex}n-1{/tex}. W każdym przejściu pętli, zmienna {tex}b{/tex} przeskoczy na element następny, czyli sumę elementów {tex}a{/tex} i {tex}b{/tex}

{tex}b=a+b{/tex},

natomiast zmienna {tex}a{/tex} przechowa to co przechowywała zmienna {tex}b{/tex} czyli

{tex}a = b - a = (a+b) - a = b. {/tex}.

 

#include<iostream>
#include<cstdlib>
using namespace std;
 
void fibonacci(int n)
{    
     long long a = 0, b = 1;
 
     for(int i=0;i<n;i++)
     {
            cout<<b<<" ";
            b += a; //pod zmienną b przypisujemy wyraz następny czyli a+b
            a = b-a; //pod zmienną a przypisujemy wartość zmiennej b
     }     
}
 
int main()
{
    int n;
 
    cout<<"Podaj ile chcesz wypisać wyrazów ciągu fibonacciego: ";
    cin>>n;
 
    fibonacci(n);
 
    system("pause");
    return 0;
}
 
 

 

Postać rekurencyjną przedstawimy do wyświetlenia pojedynczego wyrazu, ponieważ algorytm jest bardzo niewydajny i nadaje się tylko do wyznaczania niewielkiej ilości elementów ciągu.

 

#include<iostream>
#include<cstdlib>
using namespace std;
 
int fib(int n)
{
  if(n<3)
    return 1;
 
  return fib(n-2)+fib(n-1);
}
 
int main()
{
 
  int n;
 
  cout<<"Podaj nr wyrazu ciągu: ";
  cin>>n;
 
  cout<<n<<" wyraz ciągu ma wartość "<<fib(n)<<endl;
 
  system("pause");
  return 0;
}
 
 

 

Przeanalizujmy powyższy algorytm dla {tex}n=5{/tex}:

{tex}wynik=fib(5) = \underbrace{fib(4)}_{\underbrace{fib(3)}_{\underbrace{fib(1)}_1+\underbrace{fib(2)}_1}+\underbrace{fib(2)}_1}+\underbrace{fib(3)}_{\underbrace{fib(1)}_1+\underbrace{fib(2)}_1}=5{/tex}