日志
动态规划与分治法 — 求解Fibonacci数列
||
http://dl.iteye.com/upload/attachment/381194/3e8ad765-2fd9-3aaa-a99b-187cd4d30527.jpg
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)被计算至少二次.
而动态规划法通过保存已解决的子问题的解，在需要时再找出已求得的解，可以避免大量重复计算。
/2 
