日韩黑丝制服一区视频播放|日韩欧美人妻丝袜视频在线观看|九九影院一级蜜桃|亚洲中文在线导航|青草草视频在线观看|婷婷五月色伊人网站|日本一区二区在线|国产AV一二三四区毛片|正在播放久草视频|亚洲色图精品一区

搜索
分享

遞歸算法

 日月桃子 2016-02-16

概述

程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設(shè)計語言中廣泛應(yīng)用。遞歸有直接遞歸和間接遞歸

·直接遞歸：函數(shù)在執(zhí)行過程中調(diào)用本身。
·間接遞歸：函數(shù)在執(zhí)行過程中調(diào)用其它函數(shù)再經(jīng)過這些函數(shù)調(diào)用本身。
·表達方式：

·遞歸算法有四個特性：

（1）必須有可最終達到的終止條件，否則程序?qū)⑾萑霟o窮循環(huán)；

（2）子問題在規(guī)模上比原問題小，或更接近終止條件；

（3）子問題可通過再次遞歸調(diào)用求解或因滿足終止條件而直接求解；

（4）子問題的解應(yīng)能組合為整個問題的解。


下面將從以下幾個典型的例子來講解遞歸算法：

漢諾塔問題

如圖，漢諾塔問題是指有三根桿子A,B,C。C桿上有若干碟子，把所有碟子從C桿上移到B桿上，每次只能移動一個碟子，大的碟子不能疊在小的碟子上面。求最少要移動多少次？

當(dāng)n=1時：
Move  1  from  A  to  C
當(dāng)n=2時：
Move  1  from  A  to  B
Move  2  from  A  to  C
Move  1  from  B  to  C
當(dāng)n=3時：
Move  1  from  A  to  C
Move  2  from  A  to  B
Move  1  from  C  to  B
Move  3  from  A  to  C
Move  1  from  B  to  A
Move  2  from  B  to  C
Move  1  from  A  to  C

源代碼

  1. static StringBuffer str = new StringBuffer();  
  2.     /** 
  3.      * //漢諾塔問題 
  4.      * @param n 盤子的個數(shù) 
  5.      * @param x 將要移動盤子柱子 
  6.      * @param y 要借用的柱子 
  7.      * @param z 要移動到的柱子 
  8.      * @return 
  9.      */  
  10.     public static String hanio(int n, Object x, Object y, Object z) {  
  11.         //String str ="";  
  12.         if(1 == n)   
  13.             str.append(move(x, n, z) + "\n");  
  14.         else {  
  15.             hanio(n-1, x, z, y);  
  16.             str.append(move(x, n, z) + "\n") ;  
  17.             hanio(n-1, y, x, z);  
  18.         }  
  19.         return str.toString();  
  20.     }  
  21.     private static String move(Object x, int n, Object y) {  
  22.         //System.out.println("Move  " + n + "  from  " + x + "  to  " + y);  
  23.         return "Move  " + n + "  from  " + x + "  to  " + y;  
  24.     }  

fibonacci數(shù)列

斐波納契數(shù)列，又稱黃金分割數(shù)列，指的是這樣一個數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*）

源代碼

  1. /** 
  2.      * fibonacci數(shù)列 
  3.      * @param n 
  4.      * @return 
  5.      */  
  6.     public static long fibonacci(int n) {  
  7.         if((0 == n) || (1 == n)) {  
  8.             return n;  
  9.         }else {  
  10.             return fibonacci(n-1) + fibonacci(n-2);  
  11.         }  
  12.     }  

1加到n累加

用遞歸實現(xiàn)從1加到n，即1+2+3+4+...+n。

源代碼

  1. /** 
  2.      * 累加,從1加到n，即1+2+3+4+...+n 
  3.      * @param n 要累加到的數(shù)值 
  4.      * @return 累加的結(jié)果 
  5.      */  
  6.     public static long total(int n) {  
  7.         if(1 == n) {  
  8.             return n;  
  9.         }else {  
  10.             return total(n-1) + n;  
  11.         }  
  12.     }  

從1到n累積

用遞歸實現(xiàn)，從1到n累積，即1*2*3*...*n

源代碼

  1. /** 
  2.      * 從1到n的累積，即1*2*3*...*n 
  3.      * @param n 要累乖到的數(shù)值 
  4.      * @return 
  5.      */  
  6.     public static long accumulate(int n) {   
  7.         if(1 == n) {  
  8.             return n;  
  9.         }else {  
  10.             return accumulate(n-1) * n;  
  11.         }  
  12.     }  

求數(shù)組中的最大值

用遞歸算法求數(shù)組中的最大值。

源代碼

  1. /** 
  2.      * 用遞歸算法求數(shù)組中的最大值 
  3.      * @param a 數(shù)組 
  4.      * @param low 數(shù)組下標(biāo) 
  5.      * @param heigh 數(shù)組上標(biāo) 
  6.      * @return 
  7.      */  
  8.     public static int Max(int[] a, int low, int heigh) {  
  9.         int max;  
  10.         if(low > heigh-2) {  
  11.             if(a[low] > a[heigh]) max = a[low];  
  12.             else max = a[heigh];  
  13.         }else {  
  14.             int mid = (low + heigh)/2;  
  15.             int max1 = Max(a, low, mid);  
  16.             int max2 = Max(a, mid+1, heigh);  
  17.             max = max1>max2 ? max1 : max2;  
  18.         }  
  19.         return max;  
  20.     }  

數(shù)字塔問題

用遞歸算法求解數(shù)字塔問題。
n=1時
1
n=2時
1      
2      2      
n=3時
1      
2      2      
3      3      3   
n=4時
1      
2      2      
3      3      3      
4      4      4      4    

源代碼

  1. /** 
  2.      * 用遞歸算法求解數(shù)字塔問題 
  3.      * @param n 數(shù)字塔的行數(shù) 
  4.      * @return 數(shù)字塔的字符串 
  5.      */  
  6.     public static String tourData(int n) {  
  7.         String str = new String();  
  8.         if(1 == n) {  
  9.             str = rowData(n) + "\n";  
  10.             return str;  
  11.         }  
  12.         else {  
  13.             str = tourData(n-1) + rowData(n) + "\n";  
  14.         }  
  15.         return str;  
  16.     }  
  17.     private static String rowData(int n) {  
  18.         String str = new String();  
  19.         for(int i=0; i<n; i++) {  
  20.             str = str+ n + "      ";  
  21.         }  
  22.         return str;  
  23.     }  

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多