首页 > Java开发 > 动态规划-斐波那契数列

动态规划-斐波那契数列

动态规划是什么?如果不知道这个算法规则,我们一样可以解决问题相关,甚至天马行空的时候,更是状态无限,

但是,掌握很多的解法,却不知道这个问题怎么归类,是不是有更好的解决方式,或者一系列的算法题中是否可以提出规律呢?

这个宝贝的定义,我放在后边,看看随心所欲的编程带来的是什么样的结果。

斐波那契数列(Fibonacci polynomial),又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、……

    要求编程输出这样的一组数,比如输出10个数的序列。

源码:

[java]
  1. /**
  2.      * @param i 第n个数
  3.      * @param j 第n+1个数
  4.      * @param n 输出个数
  5.      */
  6.     public static void DynPFibonacci(int i,int j,int n) {
  7.         int ii=1;
  8.         System.out.print(i+",");
  9.         while(ii++<n){
  10.         System.out.print(j+",");
  11.               int k=j;
  12.               j=i+j;
  13.               i=k;
  14.         }

main函数中 DynPFibonacci(0,1,10);

输出:0,1,1,2,3,5,8,13,21,34,

这样的做法是完全的解决了问题,效率还行!如果没有看过动态规划算法规则,下一次相同类型的问题,有可能还是不能一下就搞定。

 

 动态规划的规则如下:

是一种在数学、计算机科学和经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。

简单地说,问题能够分解成子问题来解决。

即使这么看书上说的,还是有些晕!用白话解释最好!

存在这样一数组,可以提炼出一个通项公式(高中数学),重复的用这个公式计算结果。

比如,斐波那契数列的通项公式为:F0=0,F1=1,F(n)=F(n-1)+F(n-2) ,(n>2) 或者 a(n)=a(n-1)+a(n-2),(a(0)=0,a(1)=2)

该公式就是最优子结构或子问题,重复的运用这个公式就可以计算出该序列。

源码:

[java]
  1. /**
  2.  * @param arr 存放序列的数组
  3.  * @param n 需要计算的第n的数
  4.  * @return 计算结果
  5.  */
  6. public static int DynPFibonacci(int[] arr,int n) {
  7.         return arr[n-1]+arr[n-2];
  8.     }

随便的调用下,生成结果

[java]
  1. int n=10;
  2. int[] arr=new int[n];
  3. arr[0]=0;
  4. arr[1]=1;
  5. for(int i=2;i<n;i++){
  6.     arr[i]=DynPFibonacci(arr,i);
  7. }
  8. for(int k=0;k<n;k++){
  9.     System.out.print(arr[k]+", ");
  10. }System.out.print("...... ");

输出:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ......

即使这样,动态规划的强大之处还没有完全挖掘,所以需要继续完善,并不断的补充。


本文固定链接: http://www.devba.com/index.php/archives/5133.html | 开发吧

报歉!评论已关闭.