Рекурсия и ряд Фибоначчи - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток, господа! Имеется код (приложенный ниже) в котором как вы можете заметить находится ряд фибоначчи (да рекурсией, а не циклом, так нужно!) и необходимо реализовать вывод на экран этого ряда, причём именно в рекурсии и именно тут я и столкнулся с проблемой. В моём коде он конечно же выводит члены ряда, но выводит каждый вычисленный поэтому множество раз одни и теже члены повторяются множество раз, очень бы хотелось увидеть ваши советы\решения этой проблемы.
#include <stdio.h>
#include <stdlib.h>
 
int fib(int n,int f1, int f2)
{
    int f;
    if(n==0) return f1;
    else if(n==1) return f2;
    else
    {
        f=fib(n-1,f1,f2)+fib(n-2,f1,f2);
        printf("f[%d]=%d\n", n, f);
        return f;
    }
}
int main()
{
    int n;
    while(1)
    {
        printf("Enter the number of the Fibonacci number\n");
        if (!scanf("%d", &n) || (n<=2 || n>2000000))
        {
            printf("Invalid number\n ");
            fflush(stdin);
            continue;
        }
        fflush(stdin);
        break;
    }
    fib(n, 0, 1);
    return 0;
}

Решение задачи: «Рекурсия и ряд Фибоначчи»

textual
Листинг программы
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int *chk;
 
int fib(int n)
{
    int r;
    if (n<=2) 
      r=1;       
    else
      r=fib(n-2)+fib(n-1);
 
    if ((n==2) && chk[1]==0) return r;
 
    if (chk[n]==0)
    { 
      printf("n=%d f=%d\n",n,r);
      chk[n]=1;
    }  
    return r;
}              
 
int main(int argc, char *argv[])
{
    int i,n;
    cout << "n=";
    cin >> n;
    chk=new int[n+1];
    for (i=0; i<n; i++) chk[i]=0;
    i=fib(n);   
    delete [] chk;
    system("PAUSE");
    return EXIT_SUCCESS;
}

Объяснение кода листинга программы

Код представляет собой функцию fib, которая вычисляет число Фибоначчи для заданного числа n. Вектор chk используется для хранения информации о том, было ли уже вычислено число Фибоначчи для каждого из чисел от 0 до n. При запуске программы пользователем вводится число n, для которого необходимо вычислить число Фибоначчи. Затем в цикле вычисляются числа Фибоначчи от 0 до n, и в каждом шаге выводится на экран текущее число и его результат. После завершения вычислений программа завершается.

Оцени полезность:

7   голосов , оценка 4.286 из 5
Похожие ответы