Rekurencja w funkcji

0

Tresc zadania
Napisz funkcje rekurencyjna wypisujaca n kolejnych liczb ciagu.
f(0)=0
f(1)=1
f(n)= f(n-1)+f(n-2) dla (n=>2)

Naskrobałem takie coś:

#include <iostream>
#include <math.h>
#include <stdlib.h>

using namespace std;

int TestPierwsza(long long p)
{
    if (p == 0) return 0;
    else if (p == 1) return 1;
    else return TestPierwsza(p - 1) + TestPierwsza(p - 2);
}

int main()
{
    long long n;

    cout << "ile liczb ciagu wyswietlic? : " << endl;

    cin >> n;
    cout << endl;

    cout << TestPierwsza(n);

    return 0;
}

teraz pytanie, jak wyswietlic kazda po kolei?

1

Nie używaj tyle razy instrukcji return. Przypisz wynik do zmiennej np. result i zastanów się kiedy musisz go wyświetlić. Chodzi mi o funkcję TestPierwsza.
I zmień jej nazwę na bo ona nic nie testuje tylko liczy ciąg Fibonacciego :)

0

Generalnie, taką prosta rekurencją nie da się wydrukować n kolejnych liczb ciągu Fibonacciego, można tą funkcję, po prostu wydrukować w pętli:

long fibonacciNumber(long n) {
    if (n == 0) 
        return 0;
    else if (n == 1) 
        return 1;
    else 
        return fibonacciNumber(n - 1) + fibonacciNumber(n - 2);  
}

void printNthFibonacciNumbers(long n) {
    for (long i = 0; i < n; ++i)
        std::cout << fibonacciNumber(i)<<" ";
}

Jest to głupie, bo kompletnie nie efektywne, prawidłowe rozwiązanie problemu jest imperatywne:

void printNthFibonacciIterative(long n) {
    long a = 1;
    long b = 0;
    long tmp = 0;
    while (n > 0) {
        std::cout << b <<" ";
        tmp = a;
        a = a + b;
        b = tmp;
        --n;
    }
}

Ale na upartego, korzystając z powyższego kodu, da się wydrukować rekurencyjnie, optymalizując rekurencję do TCO (gdyby kompilator C++ tak robił, to poniższy kod, byłby równoważny powyższemu):

long printNthFibonacciRecursive(long a, long b, long n) {
    if (n == 1) {
        std::cout << b <<" ";
        return b;
    }
    else {
        std::cout << b <<" ";
        return printNthFibonacciRecursive(a + b, a, n - 1);
    }
}

I main:

int main(){
    printNthFibonacciNumbers(7); // -> 0 1 1 2 3 5 8
    std::cout << "\n";
    printNthFibonacciIterative(7); // -> 0 1 1 2 3 5 8
    std::cout <<"\n";
    printNthFibonacciRecursive(1, 0, 7); // -> 0 1 1 2 3 5 8
    std::cout << "\n";
    return 0;
}
0

Strasznie komplikujesz, zbędne zmienne, nieścisłe typy:

void printNthFibonacciIterative(unsigned n) 
{
    for(unsigned long long a=1,b=0,tmp;n--;)
    {
        std::cout<<b<<" ";
        tmp=a;
        a+=b;
        b=tmp;
    }
}
1
lion137 napisał(a):

Generalnie, taką prosta rekurencją nie da się wydrukować n kolejnych liczb ciągu Fibonacciego, można tą funkcję, po prostu wydrukować w pętli:

Da się po prostej zmianie

#include <iostream>
#include <math.h>
#include <stdlib.h>

using namespace std;

long long TestPierwsza(long long p, bool ifShow)
{
    long long result;
    if (p == 0) result = 0;
    else if (p == 1) result = 1;
    else result = TestPierwsza(p - 1, ifShow) + TestPierwsza(p - 2, false);

    if (ifShow) cout << result << endl;

    return result;
}

int main()
{
    long long n;

    cout << "ile liczb ciagu wyswietlic? : " << endl;

    cin >> n;
    cout << endl;

    TestPierwsza(n, true);

    return 0;
}
2

Po kiego tak komplikować?

#include <iostream>
using namespace std;

unsigned long long fib(unsigned p,bool show)
{
    unsigned long long result=p<2?p:fib(p-1,show)+fib(p-2,false);
    if(show)cout<<result<<endl;
    return result;
}

int main() 
{
    fib(13,true);
    return 0;
}

https://ideone.com/ZXyhJO

1

Rozwiązanie szybsze i nie ograniczająca się tylko do kilkudziesięciu pierwszych wyników.

#include <iostream>
#include <vector>

using namespace std;

string operator+( string&& a , string&& b )
{
    string result {};

    int sum {0};
    int offset {0};
    size_t index_a {a.size()};
    size_t index_b {b.size()};

    do
    {
        sum = 0;
        if( index_a>0 ) sum += a[--index_a]-48;
        if( index_b>0 ) sum += b[--index_b]-48;

        sum += offset;

        if( sum>9 )
        {
            offset = 1;
            sum -= 10;
        }
        else offset = 0;

        result.insert(0,1,static_cast<char>(sum+48));
    }
    while( index_a!=0 || index_b!=0 );

    if( offset==1 ) result.insert(0,1,'1');

    return result;
}

string Fib( int n )
{
    if( n==0 ) return "0";
    if( n==1 ) return "1";

    static vector<string> cache(100,"");
    if( n>=cache.size() ) cache.resize(2*n);

    if( cache[n]=="" )
    {
        cache[n] = Fib(n-1) + Fib(n-2);
    }

    return cache[n];
}

int main()
{
    for( int i=0 ; i<16000 ; ++i ) cout << i << " : " << Fib(i) << "\n";
    return 0;
}
0

chciałbym zaznaczyć, że chcę ten kod co mam, bo go rozumiem i potrafię go obronić.
tylko pytanie, czy jest mozliwosc zapisania w tym kodzie( który podałem wyżej) zapisywania każdego wyniku a potem jego wyświetlenia
np. uzytkownik podaje liczbę 6 ( mam mu podać 6 kolejnych wyrazów ciagu)
mój kod wyświetla rekurencją 6 wyraz, ale bez pozostałych 1,2,3,4,5.
jak to zrobic?

1

Tego kodu który masz nie da się sensownie zmusić do wyświetlania kolejnych wartości w trakcie liczenia bez bawienia się we flagi "show" ( dodaj sobie w pierwszej linijce cout << "licze fib" << p <<endl to sam zauważysz dlaczego).

Podpowiem Ci pewną sztuczkę...

long long fib2(long long p, long long a=0, long long b=1)
{
  if (!p) return a;
  return fib2 ( p-1, b, a+b );
}
0
#include <iostream>
using namespace std;

bool juzWTablicy(long long p, long long* arr) {
    return arr[p]!=(-500);
}
long long TestPierwsza(long long p, long long* juzObliczone)
{
    long long first=0;
    long long second=0;
    if (p == 0) return 0;
    else if (p == 1) return 1;
    else {

        if (juzWTablicy(p-1,juzObliczone)) first=juzObliczone[p-1];
        else {
            first=TestPierwsza(p-1,juzObliczone);
            juzObliczone[p-1]=first;
        }
        if (juzWTablicy(p-2,juzObliczone)) second=juzObliczone[p-2];
        else {
            second=TestPierwsza(p-2,juzObliczone);
            juzObliczone[p-2]=second;
        }
        return first + second;
    }
}

int main()
{
    long long n;

    cout << "ile liczb ciagu wyswietlic? : " << endl;

    cin >> n;
    cout << endl;
    long long juzObliczone[n+1];
    for(int i=0;i<n+1;i++) juzObliczone[i]=(-500);
    for(int i=0;i<n+1;i++) cout << TestPierwsza(i, juzObliczone) << endl;

    return 0;
}

programowanie dynamiczne mordko. Ten kod jest zbugowany bo jestem slaba w C++ ale chyba da sie zrozumiec o co chodzi i w czym ta metoda jest lepsza
edit: w sumie nie jest tak zle, po prostu trzeba zmienic typ zwracany na long long, nie wiem dlaczego jest overflow dla n<200 i nie wiem czy to sie da naprawic

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0