Рекурсия и ряд Фибоначчи - 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
, и в каждом шаге выводится на экран текущее число и его результат.
После завершения вычислений программа завершается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д