Здравствуйте, гаврилова анастасия вячеславовна.
Вот Ваша программа. Правда, на таких маленьких числах на моём компьютере время выполнения каждой функции - 0 мс. Если хотите увидеть разницу, продлите выполнение цикла хотя бы до 31, или до 51.
Описание алгоритмов можете посмотреть
здесь, функции я взяла оттуда.
Проверено на Visual Studio 2005.
Удачи!
Приложение:
#include <time.h>
#include <iostream>
using namespace std;
//Внимание: функция имеет экспоненциальное время выполнения и неэффективно использует стек.
//Функция возвращает n-e число Фибоначчи по данному n.
int fib_r(int n) //рекурсивная функция
{
if (n <= 2) return 1;
else
{
return fib_r(n - 1) + fib_r(n - 2);
}
}
//возвращает n-е число Фибоначчи
int fib_n(int n) //нерекурсивная функция
{
if (n <= 2) return 1;
//F(n-2)
int x = 1;
//F(n-1)
int y = 1;
//F(n)
int ans = 0;
for (int i = 3; i <= n; i++)
{
ans = x + y;
x = y;
y = ans;
}
return ans;
}
void main()
{
clock_t beg, tm1, tm2; //время
int f;
printf (" i Recursive Non-recursive Value\n");
for (int i=4; i<13; i+=2) {
beg = clock (); //засекаем
f = fib_r (i);
tm1 = clock ()-beg; //вычисляем, сколько прошло
beg = clock ();
fib_n (i);
tm2 = clock ()-beg;
printf ("%4d %5d ms %9d ms %d\n", i, tm1, tm2, f);
}
}