斐波那契数：动态规划法和分治法

这个学期开了一门叫算法的课，为了今天的ＩＴＡＴ复赛，这两天研究了一下这门课。感觉算法真的是太神奇了。就比如说今天学了动态规划（小小的入门）。用它实现了斐波那契数，和原来的用分治法的一比较，差距出来了。相差十几几万倍（要算的数越大相差的倍数越多）。下面是实现：

#include <iostream>
#include <ctime>

using namespace std;

/*
* 动态规划法实现
*/
int f(int n, int a[])
{
	if (n < 0)
	{
		return 0;
	}
	if (n == 0 || n == 1)
	{
		return n;
	}
	else
	{
		/* 计算f(n-1) 与已经计算过的f(n-2)=a[n-2]*/
		// 如果febonacci函数中没有for语句的事先填表
		// 可以用a[n] = a[n-1] + a[n-2];实现动态填表
		return f(n-1,a) + a[n-2];
	}
}

/*
* 填表函数
*/
int febonacci(int n)
{
	int a[1000] = {0};
	a[0] = 0;
	a[1] = 1;
	/* 自底向上填表 */
	for (int i = 2; i <= n; i++)
	{
		a[i] = a[i-1] + a[i-2];
	}

	int sum = f(n,a);

	return sum;
}

/*
* 分治法实现
*/
int f2(int n)
{
	if (n == 0 || n == 1)
	{
		return n;
	}
	else
	{
		return f2(n-1) + f2(n-2);
	}
}

int main()
{
	time_t begin1,end1;
	time_t begin2,end2;

	// 斐波那契数的阶数
	int i = 33;

	begin1 = time(NULL);
	int sum1 = 0;
	// 计算100万次
	for(int k = 0; k < 1000000; k++)
	{
		sum1 = febonacci(i);
	}
		
	cout<<"sum1:"<<sum1<<endl;
	end1 = time(NULL);
	cout<<"Time:"<<end1 - begin1<<endl<<endl;
	
	begin2 = time(NULL);
	int sum2 = 0;
	// 计算100次
	for (int m = 0; m < 100; m++)
	{
		sum2 = f2(i);
	}	
	cout<<"sum2:"<<sum2<<endl<<endl;
	end2 = time(NULL);
	cout<<"Time:"<<end2 - begin2<<endl;

	return EXIT_SUCCESS;
}

运行结果：