fibonaccin sarja

jormamietti 26.03.08 19:16

fibonaccin sarjan rekursiivinen funktio, alustava versio lausunnolle.

 Tekstiversio  Arvo: 0 (4 ääntä)  Äänestä: +  -
/* FIBONANACCIn sarjan käsittely */
/* Alustava koeversio  lausunnolle 26.03.2008 JVM  */
/* http://fi.wikipedia.org/wiki/Fibonaccin_lukujono */
#include <stdheaders.h>

int fibonac( int );

int main(void )
{
        int intluku;
        printf( "LASKEE N:N LUVUN FIBONACCIN SARJASTA\n" );
        printf( "Anna etsittävän luvun positio, max 12, 0 lopettaa:" );
        scanf( "%d", &intluku );
        while( intluku > 0 && intluku < 13 )
        {
                fibonac( intluku);
                printf( "\n Sarjan %d. luku on %d \n", intluku, fibonac( intluku ));
                printf( "Paina Enter" ); getch();       clrscr();
                printf( "Anna etsittävän luvun positio, max 12, 0 lopettaa:" );
                scanf( "%d", &intluku );
        }

        return 0;
}

int fibonac( int n )
{
        printf( "Lasketaan fib(%d)...", n);
        if( n < 3)
        {
                printf( "Palautetaan 1:\n" );
                return 1;
        }
        else
        {
                printf( "Tehdään kutsut: fib(%d) ja fib(%d) \n", n-2, n-1 );
                printf( "\n  fib(n-2)+fib(n-1) %d \n", (fibonac(n-2) + fibonac(n-1)));
                return (fibonac(n-2) + fibonac(n-1));
        }
}

/* End of File */

jormamietti 13:40 27.3.08 
Toimii nopeammin, kun jättää välitulostuksia pois. Lisäilin niitä yrittäessäni selvittää, mitenkä rekursio oikein toimii. JVM.
jormamietti 15:11 27.3.08 
Turhaan rupesin tätä itse pähkäilemään. Netti näyttää olevan täynnä rekursion ja Fibonaccin selityksiä ohjelmineen. JVM.
Esko 23:00 27.3.08 
Mutta eikös se itse oivaltaminen ole kuitenkin sitä parhainta oppimisen kannalta?

...joskin samastaoloisesta syystä tein potenssirekursion, Fibonaccia käytetään ihan liikaa esimerkkinä.
jormamietti 14:27 28.3.08 
Binomikerroin n!/(k!(n-k)!) rekursiolla toteutettuna voisi olla haastavampi kohde. Varmaan tämäkin löytyy valmiina, jos osaa etsiä. JVM
Enec 19:37 29.3.08 
                fibonac( intluku);
                printf( "\n Sarjan %d. luku on %d \n", intluku, fibonac( intluku ));

Eikös tämä nyt laske kys. luvun kahdesti? Eka itsekseen tallettamatta tulosta minnekkään, ja sen jälkeen ton printf sisällä.

#include <stdhearders.h>

En ole koskaan nähnyt tällaista käytettävän, eikä gcc:n mukaan ainakaan ole mikään kirjasto. Mahdollisesti jotain kääntäjäkohtasia epästandardeja?

                printf( "Paina Enter" ); getch();       clrscr();
getch(); ja clrscr(); on varmoja tapoja rikkoa portattavuus mm. Linuxille. Molemmat taitaa nimittäin tulla epästandardista conio.h -headeristä, mitä ainakin Borland muistaakseni tyrkyttää Windowsin puolella.

Tämähän olisi hyvä myös tehdä isommilla luvuilla kun int, nii saisi pidemmällekkin laskettua. long long unsigned int sai muistaakseni fib(92) asti laskettua oikein kun joskus kokeilin. Siitä pidemmälle niin tarvittaisiin jo jotain bigint -kirjastoja.
editoitu: 13:00 30.3.08
jormamietti 09:31 30.3.08 
Näin on. lcc-win32 on vanha kääntäjä, jonka kirjastossa on <conio.h>. <stdheaders.h> sisältää tukun #include käskyjä, jotta ohjelmoijan ei tarvitsisi muistella, mitä tarvitaan. JVM
Esko 21:37 30.3.08 
jormamietti kirjoitti:
Binomikerroin n!/(k!(n-k)!) rekursiolla toteutettuna voisi olla haastavampi kohde. Varmaan tämäkin löytyy valmiina, jos osaa etsiä. JVM


Yritin kovasti miettiä miten tuon saa revittyä rekursioksi mutten keksinyt. Eli ratkaisu kiinnostaisi kyllä.
editoitu: 21:45 3.4.08
harja 22:50 2.4.08 
*muokkail* Pois, alhaalla lyhyempi versio.

:)M
jormamietti 08:24 3.4.08 

C
int binker( int n, int k )
{
        if( n == k && k > 0 )
                return 1;
        else
                return binker( n-1, k )* n /( n-k);
}
 

Tämä ratkaisi ainakin matikan kirjan esimerkin: 25 oppilaan luokasta koottavien 4 oppilaan lähetystöjen määrän 12650 oikein. JVM
Esko 20:19 4.4.08 
Noniin, aivot niksahtavat :) Eli hyvä hyvä, voisi päivittää Wikiin ihan kiusallaan näitä rekursioesimerkkejä tästä nyt.