遞歸分類
- 分解為直接量+小規(guī)模子問題
- 不伴隨著參數(shù)角色的變化
- 伴隨著參數(shù)角色的變化（調(diào)用遞歸時除了縮小參數(shù)腻格，還要調(diào)換參數(shù)的位子）
- 分解為多個小規(guī)模子問題
- 子問題不等價(jià) f(M)+f(N)
- 子問題等價(jià) f(N/k)+...+f(N/k)
- 不分解，但是規(guī)模不斷縮小
例1：求階乘
【#分解為直接量+小規(guī)模子問題啥繁，不伴隨著參數(shù)角色的變化】
【思考】這道題典型的"切蛋糕",在前面切一刀菜职，并且只有一個參數(shù)。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
System.out.println(jieCheng(n));
}
static int jieCheng(int n){
if(n==1)
return 1;
return n*jieCheng(n-1);
}
}
例2：數(shù)組求和
【#分解為直接量+小規(guī)模子問題旗闽，不伴隨著參數(shù)角色的變化】
【思考】這道題典型的"切蛋糕",在前面切一刀些楣，但是有兩個參數(shù)，兩個參數(shù)沒有角色交換宪睹，只是其中一個參數(shù)不斷縮小規(guī)模愁茁。
import java.util.*;
public class Main{
public static void main(String args[]){
//先創(chuàng)建一個儲存0~n-1的數(shù)組
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=i;
}
//調(diào)用函數(shù)
System.out.println(sum_arr(0,arr));
}
static int sum_arr(int i,int[] arr){
if(i==arr.length-1)
return arr[i];
return arr[i]+sum_arr(i+1,arr);
}
}
例3：字符串翻轉(zhuǎn)
【#分解為直接量+小規(guī)模子問題，不伴隨著參數(shù)角色的變化】
【思考】這道題典型的"切蛋糕",但是在后面切一刀亭病，有兩個參數(shù)鹅很，兩個參數(shù)沒有角色交換，其中一個參數(shù)不斷縮小規(guī)模罪帖。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
String s=in.next();
System.out.println(reverse(s,s.length()-1));
}
static String reverse(String s,int end){
if(end==0){
return ""+s.charAt(end);
}
return s.charAt(end)+reverse(s,end-1);
}
}
例4：漢諾塔
在印度促煮，有這么一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針整袁。印度教的主神梵天在創(chuàng)造世界的時候菠齿，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔坐昙。不論白天黑夜绳匀，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面疾棵。僧侶們預(yù)言戈钢，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅是尔，而梵塔殉了、廟宇和眾生也都將同歸于盡。
假設(shè)三根針分別是A,B,C拟枚，用戶輸入金片個數(shù)N薪铜，起初這N個金片全部在A針上，那么漢諾塔金片全部移動到B針上時需要移動的最少步數(shù)是多少恩溅？
【#分解為直接量+小規(guī)模子問題隔箍，伴隨著參數(shù)角色的變化（調(diào)用遞歸時除了縮小參數(shù)，還要調(diào)換參數(shù)的位子）】
【思考】
1暴匠、為什么選擇先把最大（放在最底下）的金片放在目標(biāo)針鞍恢，再把剩下的挪到目標(biāo)針？因?yàn)榇蟮姆藕靡院缶涂梢圆挥脛恿嗣拷眩疫@根針還可以放其它金片帮掉，因?yàn)槠渌鹌急确藕玫慕鹌 ?br>
2、最開始所有金片都在A上窒典，要把金片移動到B上蟆炊，C作為輔助針。挪動最底下的金片之前要先把上面的所有金片挪到輔助針上瀑志，再挪動最底下的金片到目標(biāo)針涩搓，然后把當(dāng)前輔助針上的金片挪到目標(biāo)針上。假如有N個金片需要挪動劈猪，那么剛剛已經(jīng)完成了N個金片的挪動昧甘，但忽略了前N-1個金片的挪動細(xì)節(jié)。當(dāng)我們要移動前N-1個金片時战得，可以把它想象成是挪動N個金片充边，但是參數(shù)對應(yīng)的角色變了，對于第1~N-1個金片常侦，當(dāng)它們從A到C時浇冰，它們的目標(biāo)針是C，A是起始針聋亡，B是輔助針肘习；第N個金片放好以后，要把其它金片從C挪到B坡倔，這個時候A成為了輔助針漂佩，而B是目標(biāo)針脖含，C是起始針。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
hanNuoTa(N,"A","B","C");
}
static void hanNuoTa(int N,String from,String to,String help){
if(N==1){
System.out.println("把"+N+"從"+from+"移到"+to);
}
else{
hanNuoTa(N-1,from,help,to); //參數(shù)角色變化
System.out.println("把"+N+"從"+from+"移到"+to);
hanNuoTa(N-1,help,to,from); //參數(shù)角色變化
}
}
}
例5:斐波拉契數(shù)列求和
【#分解為多個小規(guī)模子問題,f(M)+f(N)】
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
System.out.println(fib(in.nextInt()));
}
static int fib(int n){
if(n==1||n==2)
return 1;
return fib(n-1)+fib(n-2);
}
}
例6：輾轉(zhuǎn)相除法求最大公約數(shù)
【 #不分解仅仆，但是規(guī)模不斷縮小】
【知識點(diǎn)】輾轉(zhuǎn)相除法求最大公約數(shù)的原理：舉個例子器赞，求511和292的最大公約數(shù)垢袱。511/292=1......219; 292/219=1......73; 219/73=3; 最大公約數(shù)為73墓拜。
import java.util.*;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
System.out.println(gcd(in.nextInt(),in.nextInt()));
}
static int gcd(int m,int n){
if(m%n==0)
return n;
return gcd(n,m%n);
}
}
