Matematické Fórum

lander · 22. 10. 2010 23:09

Napište program, který nalezne 83 člen Fibonacciho posloupnosti $(f_n)^\infty_n_=_1$ , která
je denována vztahem $f_n_+_2 = f_n_+_1 + f_n; f_1 = 1; f_2 = 1$ .
Nemate niekto skusenosti ako riesit taketo pripady?
Dakujem za kazdu pomoc..

piiity · 22. 10. 2010 23:25 — Editoval piiity (22. 10. 2010 23:33)

↑ lander:
Toto jsem pred davnem resil. Existuji 2 zpusoby jak to naprogramovat (1) rekurzivne - docela slozite pro tenhle pripad nebo (2) smyckami
Umim jen c++, tak ti to napisu v tom
#include <iostream>
int pocitej(int pozice);
using namespace std;
int main()
{
int vysledek,pozice = 83;
vysledek = pocitej(pozice);
cout <<"Fibonacciho cislo je" << vysledek;
return 0;
}
int pocitej(int x)
{
int minusDruhy = 1, minusPrvni = 1, vysledek = 1;
if ( x < 3)
return 1;
for ( x -= 3; x; x--;)
{
minusDruhy = minusPrvni;
minusPrvni = vysledek;
vysledek = minusPrvni + minusDruhy;
}
return vysledek;
}

lander · 23. 10. 2010 17:21

Fuha,snazil som sa to pochopit ale C++ som ani nevidel,moc tomu nerozumiem.Ale dakujem za ochotu;-)

gladiator01 · 23. 10. 2010 18:51

↑ piiity:
Jseš si jistý, že ti to funguje správně?

vojta01 · 23. 10. 2010 19:36

Existují 3 způsoby výpočtu:

1) rekurzivně - pomalé

int Fib(int cislo)
{
if(cislo < 3) // 1 a 2
return 1;
else
return Fib(cislo-1)+Fib(cislo-2); // rekurzivně spočítá předchozí dvě fib. čísla, která se také spočítají rekurzivně atd...
}

2) pamatuji si vždy 2 předchozí Fibonaciho čísla, pomocí nich vytvořím třetí

int c1=1, c2=1, c3;

for(int i=3; i<=hledane_cislo; i++)
{
c3 = c1+c2; // výpočet dalšího fib. čísla
c1 = c2;
c2 = c3; // tyto 2 řádky zajišťují přesun hodnot proměnných, ve kterých jsou hodnoty posledních 2 fib. čísel
}

po výpočtu bude v c2 i c3 hledaná hodnota fib. čísla

3) nejrychlejší je použít vzorec na výpočet n-tého fib. čísla, který se dá získat diferenčními rovnicemi, nelekněte se těch odmocnin (sqrt):

int Fib = (((1+sqrt(5))/2)^N-((1-sqrt(5))/2)^N)/sqrt(5)

odkaz na vzorec: http://sustek.wz.cz/vzorce/004.png

piiity · 24. 10. 2010 13:15 — Editoval piiity (24. 10. 2010 13:30)

↑ gladiator01:
Omlouvám se skutečně tam byly chyby.

Code:

#include <iostream>
double pocitej(int pozice);
using namespace std;
int main()
{
       double vysledek;
       int pozice;
       cout << "Zadejte pozici: ";
       cin >> pozice;  //zadani pozice
       vysledek = pocitej(pozice); //tato hodnota se preda funkci pocitej
       cout <<"Fibonacciho cislo je" << vysledek; //vypise vysledek
       system("PAUSE");
       return 0;
}
double pocitej(int x)
{
        double minusDruhy = 1, minusPrvni = 1, vysledek = 2;  //nastaveni pocatecnich hodnot
        if ( x < 3)  // testovani jestli je x mensi jak 3, tak vrati vysledek 1
         return 1;
        for ( x -= 3; x; x--)
        {       
        minusDruhy = minusPrvni;
        minusPrvni = vysledek;
        vysledek = minusPrvni + minusDruhy;
        }
        return vysledek;
}

pocatecni pozice: minusDruhy a minusPrvni = 1 a jako odpoved je logicky 2, potom ve for smycce snizime hodnotu x o "-3", protoze prvni dve cisla uz zname z pocatecni pozice. Pro kazde cislo pak postupuje tak, ze vlozime hodnotu minusPrvni do minusDruhy a hodnotu vysledeku do minusPrvni. Novy vysledek je pak soucet techto cisel a zaroven se snizi x o "1". Takhle pokracujeme dokud nedosahne x "0". Potom zobrazi odpoved.
Vyuzival jsem vzorec na http://www.math.rutgers.edu/~erowland/fibonacci.html , kde si take muzete zkontrolovat spravnost odpovedi.

Edit: zmena int na double

gladiator01

Nejjednoduší bude tedy asi použít ten vzorec: Zadáš toto:

Code:

N=83
vysledek=((1+sqrt(5))^N-((1-sqrt(5))^N))/((2^N)*sqrt(5))

Zkus to, já teď nemam k dispozici matlab, ale je to tak primitivní, že by to mnělo fungovat.

Nebo zkusím přepsat některý z předchozích postupů.

Stýv · 24. 10. 2010 15:21

já bych se trochu obával zaokrouhlování při práci s desetinnými čísly... v octave jsem podle vzorečku dostal nepřesný výsledek

Matematické Fórum

#1 22. 10. 2010 23:09

Matlab - Fibonacciho postupnost

#2 22. 10. 2010 23:25 — Editoval piiity (22. 10. 2010 23:33)

Re: Matlab - Fibonacciho postupnost

#3 23. 10. 2010 17:21

Re: Matlab - Fibonacciho postupnost

#4 23. 10. 2010 18:51

Re: Matlab - Fibonacciho postupnost

#5 23. 10. 2010 19:36

Re: Matlab - Fibonacciho postupnost

#6 24. 10. 2010 13:15 — Editoval piiity (24. 10. 2010 13:30)

Re: Matlab - Fibonacciho postupnost

Code:

#7 24. 10. 2010 14:17 — Editoval gladiator01 (24. 10. 2010 16:09)

Re: Matlab - Fibonacciho postupnost

Code:

#8 24. 10. 2010 15:21

Re: Matlab - Fibonacciho postupnost

Zápatí