Fibonacci C++

[em]

Scrieti un cod care calculeaza (si afiseaza)

a) Termenii din sirul lui Fibonacci mai mici ca 40000 folosind doar 2 variabile.

Primii n termeni din sirul lui Fibonnaci folosind doar doua variabile.

c) Primii n termeni din sirul lui Fibonacci folosind doar o variabila. (n)

Nu imi bagati sirul intr-un vector si il afisati, nu imi folositi recursivitati sau stive, n<20 (citit de la tastatura).

Obs: Daca folositi un contor (int i) se pune ca o variabila!

Fibonacci number - Wikipedia, the free encyclopedia

[cmiN]

Daca am un v[3] si un i sunt 2 variabile sau 4 ?

[em]

Daca am un v[3] si un i sunt 2 variabile sau 4 ?

Sunt 4.

[cmiN]

a)

#include <iostream>
using namespace std;

int main()
{
    unsigned int a = 0, b = 1;
    while (b < 40000) {
        cout << a << ", " << b << ", ";
        a += b;
        b += a;
    }
    system("pause >nul");
    return 0;
}

[em]

@cmiN

E bine. Bravo. Astept o solutie pentru si c).

P.S. Ca sa fie mai usor de verificat pe net rezolvarea (pe codepad de exemplu) puteti pune la inceputul programului int n=20; (e tot aia cu cititul lui n pana la urma..). Ideea de baza la si c) este cum ati face sa va opriti dupa un anumit numar de pasi, nu dupa o anumita valoare a ultimului termen.

[cmiN]

Singurele idei care le mai am sunt matricea Q sau matricea cealalta pe prima linie si coloana 0 restul 1 (e de 2 pe 2). Sigur nu am voie sa folosesc recursivitate, nici macar daca folosesc recurenta ca f(n) = f(n-1) + f(n-2) ?

[En0mis]

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n = 0;
    double f = 0.0;
    while(n<20)	{
        f=(1/sqrt(5))*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n));
        cout << f << " ";
        n++;
    }
    return 0;
}

c)

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n = 0;
    while(n<20)	{
        cout << (1/sqrt(5))*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n)) << " ";
        n++;
    }
    return 0;
}

[cmiN]

o.O wtf ... vazusem eu ceva cu radical din 5 pe undeva da nici chiar asa ) gege.

[AlStar]

Foarte faina faza cu radicalii. Am banuit ca tre' sa fie o formula matematica;))

[em]

E frumos si asa dar hai sa ne limitam la f(n)=f(n-1)+f(n-2).

P.S. : Sau ca sa nu mai faci asa, hai sa presupunem ca eu vreau ca sirul sa inceapa cu 1, 3 si sa respecte doar regula constructiei...sau ca ii introduc eu de la tastatura.. (nu prea ar mai fi respectat enuntul ca as mai citi inca 2 variabile asa..)

L.E.:

Chiar asa fiind nu e rezolvat calumea. Avem n,f,20 - acesta ar fi trebuit citit deci mai manca o variabila. => 3

Doar rezolvarea care ai propus-o la c) ar fi buna pentru . Avem n, 20 - care ar fi trebuit citit. => 2

[cmiN]

Recurenta foloseste recursivitatea si ai zis ca recursiv nu avem voie ... oricum daca se poate

#include <iostream>
using namespace std;

unsigned long fib(unsigned int n)
{
    if (n > 3) {
        return fib(n - 1) + fib(n - 2);
    } else if (n == 3 || n == 2) {
        return 1;
    } else {
        return 0;
    }
}

int main()
{
    unsigned int n;
    cout << "n: ";
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cout << fib(i) << ", ";
    }
    system("pause >nul");
    return 0;
}

[em]

@cmiN Hint pentru

Gandeste-te ca int are 10 cifre, pe cand fib(21) abia atinge 5

[En0mis]

c) (Pentru b se poate folosi inca o variabila "i" ca si contor)

#include <stdio.h>
#include <iostream>
using namespace std;

int main()
{
    long long n = 20;
    n = n << 56;
    n++;
    while( 0 != ((n >> 56 )&0xFF)) {
        cout <<  ((n >> 32) & 0xFFFFFF) << " " << (n & 0xFFFFFF) << " ";
        n += (n & 0xFFFFFF) << 32;
        n += (n >> 32) & 0xFFFFFF;
        n -= ((long long)2) << 56;
        }
    return 0;
}

P.S. Compilat cu succes in Visual C++ 2010 Express (posibil ca alte compilatoare sa nu suporte "long long").

[em]

E corect. Bravo. Oricum pentru numerele pana la 20 ajungea si un int.

[totti93]

Am scris in openoffice.org un mic guide pentru calcularea termenului general al sirului Fibonacci:

[nightkhaos]

Scrieti un cod care calculeaza (si afiseaza)

a) Termenii din sirul lui Fibonacci mai mici ca 40000 folosind doar 2 variabile.

Primii n termeni din sirul lui Fibonnaci folosind doar doua variabile.

c) Primii n termeni din sirul lui Fibonacci folosind doar o variabila. (n)

Nu imi bagati sirul intr-un vector si il afisati, nu imi folositi recursivitati sau stive, n<20 (citit de la tastatura).

Obs: Daca folositi un contor (int i) se pune ca o variabila!

Fibonacci number - Wikipedia, the free encyclopedia

Deci daca am voie sa folosesc o variabila in c++ si tu ai spus ca numerele sunt mai mici decat 40000 adik 2 bytes .. folosesc un tip de data pe 64 de bits adica 8 bytes si am asa:

long long variabila;//sau double sau orice alt tip de data

#define var1 variabila>>8;

#define var2 variabila>>16;

#define var3 variabila>>24;

#define var4 variabila>>32;

.....................................

si am facut rost de 8 variabile in felul asta folosind doar 1 variabila de tip long long;

asta e 1 varianta;

-------------------------------

varianta 2:

la nivel de assembler imi iau un registru(1 variabila) exemplu: eax care are 32 de bits, si o impart in ax bx (2 variabile de 16 bits) iar astea la randul lor le impart in (al, ah, bl ,bh)

si ma pot lafai in variabile:D si pot sa aplic cel mai lame algoritm a lui fibbonaci;