动态规划与分治法 — 求解Fibonacci数列

 

Fibonacci数列

无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为：

1. 分治法求Fibonacci数列   
分治法将具有最优子结构性质的原问题分解成若干个子问题, 子问题相互独立.

分治法通常采用递归操作实现.

 

/*
@author: jarg
@TODO: 分治法求Fibonacci数列
*/

import java.io.InputStreamReader;

public class Fibonacci
{
	public static void main(String[] args)
	{
		InputStreamReader ir = new InputStreamReader(System.in);
		try
		{
			System.out.print("输入参数n: ");
			int n = Integer.parseInt("" + (char)ir.read());
			System.out.println("Fibonacci(" + n +")=" + fibonacci(n));
		}
		catch(Exception e)
		{
			System.out.println("invalid input.");
		}
	}

	/* 求Fibonacci数列 */
	public static int fibonacci(int n)
	{
		if(n<2)
		{
			return 1;
		}
		return fibonacci(n-1) + fibonacci(n-2);
	}
}

 

 

2. 动态规划求Fibonacci数列

 动态规划也将具有最优子结构性质的原问题分解成若干个子问题, 且原问题具有重叠子问题性质.

 

/*
@author: jarg
@TODO: 动态规划求Fibonacci数列
*/

import java.io.InputStreamReader;

public class Fibonacci
{
	public static void main(String[] args)
	{
		InputStreamReader ir = new InputStreamReader(System.in);
		try
		{
			System.out.print("输入参数n: ");
			int n = Integer.parseInt("" + (char)ir.read());
			System.out.println("Fibonacci(" + n +")=" + fibonacci(n));
		}
		catch(Exception e)
		{
			System.out.println("invalid input.");
		}
		
	}

	/* 求Fibonacci数列 */
	public static int fibonacci(int n)
	{
		int result = 1,f1 = 1,f2 = 1;

		/* 边界条件: n<2 */
		if(n<2)
		{
			return 1;
		}
		for(int i=2;i<=n;i++)
		{
			result = f1 + f2;
			f1 = f2;
			f2 = result;
		}
		return result;
	}
}

 

 

当递归分解得到的子问题不互相独立时，若用分治法求解，则有些子问题会被重复计算多次。 例如:

fibonacci(5) = fibonacci(4) + fibonacci(3);

fibonacci(4) = fibonacci(3) + fibonacci(2);

分治法求解时fibonacci(3)被计算至少二次.

而动态规划法通过保存已解决的子问题的解，在需要时再找出已求得的解，可以避免大量重复计算。

评论

3 楼 jiji879 2011-07-13  

yeshaoting 写道

sd6733531 写道

恕我愚笨。
我感觉第一个是用递归解。
第二个不是用递归解。
其他区别就看不出了。- -！

我也是最近才捡起的算法设计与分析.分析不准确的地方谅解.

确实这二个程序的区别之一是: 第一个用递归解,第二个用非递归解.
不过这只是分治法和动态规划具体实现的区别.

分治法与动态规划实现方法:
① 分治法求解几乎都要用到递归.
② 动态规划既可以用自底向上的迭代法(动态规划求解问题常用的方法),也能用具有记忆功能的递归法自顶向下求解.

分治法与动态规划主要共同点:
都是就是将原问题分而治之,分成若干个子问题.然后将子问题的解合并,形成原问题的解.

分治法与动态规划主要区别:
① 分治法将分解后的子问题看成相互独立的.
② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分.

例如: 求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).而求解fibonacci(4)时又得重新求解fibonacci(3).
在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),也就是说求解了二次子问题fibonacci(3).
动态规划为了避免子问题fibonacci(3)的重复求解,将其解保存下来.

分治法与动态规划适用条件:
① 原问题具有最优子结构性质的前提下,分解出的子问题都绝对相互独立.
② 原问题具有最优子结构性质的前提下,分解出的子问题并不相互独立,求解一个子问题可能要用到已经求解过的子问题的解.子问题间具有重叠性,即要求原问题具有重叠子结构性质.

分治法与动态规划复杂度分析:
① 分治法因为对子问题进行了多次求解,所以效率比动态规划低一点.(时间复杂度相对高)
② 动态规划求解需要将子问题的解保存下来,所以会比分治法多用一些空间.(空间复杂度相对高)
其实,算法世界里,要么用时间换空间,要么用空间换时间.

int fibonacci(Integer n){
		if(list.get(n-1)!=0){
			return list.get(n-1);
		}
		list.add(n-1,fibonacci(n-1)+fibonacci(n-2));
		return list.get(n-1);
	}

貌似这才是动态规划的解。

2 楼 yeshaoting 2011-01-07  

sd6733531 写道

恕我愚笨。
我感觉第一个是用递归解。
第二个不是用递归解。
其他区别就看不出了。- -！

我也是最近才捡起的算法设计与分析.分析不准确的地方谅解.

确实这二个程序的区别之一是: 第一个用递归解,第二个用非递归解.
不过这只是分治法和动态规划具体实现的区别.

分治法与动态规划实现方法:
① 分治法求解几乎都要用到递归.
② 动态规划既可以用自底向上的迭代法(动态规划求解问题常用的方法),也能用具有记忆功能的递归法自顶向下求解.

分治法与动态规划主要共同点:
都是就是将原问题分而治之,分成若干个子问题.然后将子问题的解合并,形成原问题的解.

分治法与动态规划主要区别:
① 分治法将分解后的子问题看成相互独立的.
② 动态规划将分解后的子问题理解为相互间有联系,有重叠部分.

例如: 求解fibonacci(5)时,得求解fibonacci(4)和fibonacci(3).而求解fibonacci(4)时又得重新求解fibonacci(3).
在分治法中,求解完fibonacci(4)后还得重新求解fibonacci(3),也就是说求解了二次子问题fibonacci(3).
动态规划为了避免子问题fibonacci(3)的重复求解,将其解保存下来.

分治法与动态规划适用条件:
① 原问题具有最优子结构性质的前提下,分解出的子问题都绝对相互独立.
② 原问题具有最优子结构性质的前提下,分解出的子问题并不相互独立,求解一个子问题可能要用到已经求解过的子问题的解.子问题间具有重叠性,即要求原问题具有重叠子结构性质.

分治法与动态规划复杂度分析:
① 分治法因为对子问题进行了多次求解,所以效率比动态规划低一点.(时间复杂度相对高)
② 动态规划求解需要将子问题的解保存下来,所以会比分治法多用一些空间.(空间复杂度相对高)
其实,算法世界里,要么用时间换空间,要么用空间换时间.

1 楼 sd6733531 2011-01-07  

恕我愚笨。
我感觉第一个是用递归解。
第二个不是用递归解。
其他区别就看不出了。- -！