С++: Числа Фиббоначи (рекурсия и не рекурсия)

Задание:

Написать программу, которая реализует рекурсивную и нерекурсивную функцию, которая выводит на экран число Фиббоначи с индексом N
Последовательность Фиббоначи: x[n]=x[n-2]+x[n-1],x[0]=0;x[1]=1;

Не рекурсивный вариант:


int FibbonachiNotRecursion(int N)//нерекурсивная функция
{
int mas[255];
mas[0]=0;
mas[1]=1;
for (int i=2;i<=N;i++)
{
mas[i]=mas[i-2]+mas[i-1];
}
return mas[N];
}

Рекурсией:


int FibbonachiRecursion(int N)//рекурсивная функция
{
int sum;
if (N==0)
{
return 0;
}
else if (N==1)
{
return 1;
}
else
{
sum=Rec(N-2)+Rec(N-1);
return sum;
}
}

Использование:


#include "stdafx.h"
#include <conio.h>
#include <locale.h>

int main()
{
setlocale(LC_ALL, "Russian");
int N;
printf("Введите число\n");
scanf_s("%d",&N);
printf("Не рекурсивная %d\n",FibbonachiNotRecursion(N));
printf("Рекурсивная %d\n",FibbonachiRecursion(N));
return 0;
}

3 Responses

  1. expert 14.01.2012 / 11:36

    FibbonachiNotRecursion более правильно вычислять без использования массива, поскольку не требуется память под все N элементов:
    int fib(int N) {
    int x0=0;
    int x1=1;
    for (int i=0; i<N; i++) {
    int temp = x1;
    x1=x0+x1;
    x0=temp;
    }
    return x0;

    }

Добавить комментарий