» »

Fibonaccijevo zaporedje v C

Fibonaccijevo zaporedje v C

prix ::

Pozdrav!

Imam nekaj težav z domačo nalogo za programiranje. Do sedaj mi je uspelo napisati kodo, ki sicer racuna clene fibonacijevega zaporedja vendar so zgleda ti cleni od 30 navzgor preveliki, in računalnik računa full dolgo, nato pa že meče zraven neke predznake ipd.... Verjetno tudi tip spremenljivke int ni pravi...

koda:
#include <stdio.h>

int main()
{
    int i, vrednost;
    
    for(i=1; i<100; i++)
    {
             int stevilo(int n)
             {
             if((n==1)||(n==2))
             {
                 return 1;
             }
             else
             {
                 return (stevilo(n-1) + stevilo(n-2));
             }
    }
    vrednost=stevilo(i);
    printf("%d\n", vrednost);
    }
}


Mi lahko nekdo pomaga kaj delam narobe... in kako te vrednosti spravim v vektor.

ps. Se naloga od profesorja:

Napišite program, ki bo izračunal prvih 100 mest Fibonaccijevega zaporedja in jih shranil v vektor F. Izpis ni potreben.

Fibonaccijevo zaporedje člen zaporedja je vsota prejšnjih dveh členov, pri čemer sta prva dva člena 1:

1, 1, 2, 3, 5, 8, ... ,an=an-1+an-2, ...

Narišite tudi pripadajoči diagram poteka.
-------------------------------------------------
Errare humanum est, in errore perservare stultum.
-------------------------------------------------
  • spremenil: prix ()

arjan_t ::

počasi ti dela ker računaš rekurzivno in vsakič na novo ...

čidne stvari ti prikazuje ker prekoračiš mejo tipa int, čeprav prvih 100 členov je malo dosti, nevem če bo največji tudi v double prišel

Senitel ::

1. Nauči se LEPO pisat kodo (začetki blokov naj bodo logično zamaknjeni, ne pa tako kot imaš sedaj).
2. Zakaj funkcija v funkciji?
3. Odvisno od prevajalnika ampak za zaporedja do 100 boš potreboval večji podatkovni tip kot je int. Skratka nek 64 biten tip, ki ga tvoj prevajalnik ponuja (recimo long).
4. Če rešuješ problem rekurzivno je narava tega problema taka, da boš potreboval ogromno CPU časa.
5. Ker potrebuješ izračunat 100 števil se je stvar veliko bolj enostavno lotiti z vektorjem (google std::vector). Daš v vektor dve številki (1, 1), potem pa narediš zanko od 2 do 100 v kateri vzameš i - 1 in i - 2 elementa iz vektorja, ju sešteješ in vpišeš na i-to mesto.

Gundolf ::

A pišeš v C (kot izgleda iz tvoje kode in naslova) ali v C++? Ker ravno omenjaš vektor (in senitel isto), to je totalno C++ zadeva.

Glede 100 števil - takole na pamet, vsak naslednji člen rabi približno 1 bit več kot prejšnji, tako da jih boš verjetno težko spravil tudi v long int spremenljivko. Double bi tu deloval, vendar na račun natančnosti največjih števil.

Za hitrost je pa že razumljivo razloženo.

blaz_ ::

kot je že arjan_t omenil, je tista rekurzivna rešitev zelo naivna, časovne primerjave lahko najdeš tule: http://www.brpreiss.com/books/opus5/htm...
http://www.mcs.surrey.ac.uk/Personal/R....


očitno sem imel malo preveč časa ;) , tole je tut rekurzivna verzija, samo da računa dokler ne pride do recimo stotega zaporednega števila, hkrati pa vmesne tudi izpisuje (kar pomeni, da ko računaš 100 števil, moraš tako ali tako izračunati že vse do tega stotega), proti koncu (od 92.tega dalje), je long long int že premajen in se posledično tam pojavijo minusi, če daš namesto inta double tam pri typedef, bo sicer delovalo, ampak kot je že Gundolf omenil, na račun natančnosti ni več pravilen rezultat, pri stotem je tudi z double že pramajhen tip in posledično ponovno dobiš minus, tako da bi rabil kakšen sestavljen tip

#include <stdio.h>

typedef long long int lint;

lint stevilo(lint val1, lint val2, int step, int counter, lint result) {
	if(step == counter) {
		result = val1 + val2;
		printf("%d: %lld\n", counter, val1+val2);
		return result;
	}

	if((step==1)||(step==2)) {
		return 1;
	}else{
		printf("%d: %lld\n", counter, val1+val2);
		return stevilo(val2, val1 + val2, step, counter+1, result);
	}
}

int main()
{
	lint vrednost;

	printf("%d: %d\n", 1, 1);
	printf("%d: %d\n", 2, 1);
	vrednost=stevilo(1, 1, 100, 3, vrednost);
	printf("konec: %d\n", vrednost);
	return 0;
}




hmm, zakaj mi ignorira tabulatorje? :X (Senitel: Ker ne uporabljaš st.koda tagov :P)

Lp
Ko tehnologija odpove, uporabi macolo.

Zgodovina sprememb…

  • spremenil: Senitel ()

Gundolf ::

Hmm, blaz_, double ti ne bi smel nagajat z minusi.

P.S. Kodo se vpiše takole: [st.koda c] izvorna koda [/st.koda c]

Zgodovina sprememb…

  • spremenil: Gundolf ()

Senitel ::

Mnja blaz_ uporablja long long int, torej 64 bitni integer, ne pa double precision float. Tako da to se še vedno lahko obrne.

blaz_ ::

Gundolf ja res ni minusa tam, očitno sem imel spremenjeno kodo oz. morda drugačen izpis? no nima veze, uglavnem pri double se izgubi natančnost :)
Senitel, Gundolf je mislil, ko sem imel double, da sem dobil minus
Ko tehnologija odpove, uporabi macolo.

Zgodovina sprememb…

  • spremenil: blaz_ ()

prix ::

hvala za pomoč, mogoče so nekatere stvari zame še preveč komplicirane sem pa na dobri poti... :)

HF
-------------------------------------------------
Errare humanum est, in errore perservare stultum.
-------------------------------------------------


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Java in reference (strokovno vprašanje)

Oddelek: Programiranje
8810 (639) marjan_h
»

Pomoč z C++ nalogo

Oddelek: Programiranje
101424 (1231) denis123
»

[C++] Pomoč pri osnovnih nalogah

Oddelek: Programiranje
171992 (1992) angello
»

[Naloga][C++] vsota vrste

Oddelek: Programiranje
71954 (1794) bozjak
»

Zna kdo rešiti nalogo v C ++ ?

Oddelek: Programiranje
121560 (1416) OwcA

Več podobnih tem