Java遞歸例子

1、實(shí)用文檔Java中的經(jīng)典遞歸/漢諾塔問題（遞歸）（古代有一個梵塔，塔內(nèi)有三個座 A、B、C, A座上有64個盤子，盤子大小不等，大的在下， 小的在上（如圖）。有一個和尚想把這64個盤子從A座移到B座，但每次只能允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在上。在移動過程中可以利用B座，要求打印移動的步驟。如果只有一個盤子，則不需要利用B座，直接將盤子從A移動到Co*如果有2個盤子，可以先將盤子 1上的盤子2移動到B;將盤子1移動到c;將盤子 2移動到Co這說明了：可以借助 B將2個盤子從A移動到C,當(dāng)然，也可以借助 C 將2個盤子從A移動到Bo*如果有3個盤子，那么

2、根據(jù) 2個盤子的結(jié)論，可以借助 c將盤子1上的兩個盤子從A 移動到B;將盤子1從A移動到C, A變成空座；借助 A座，將B上的兩個盤子移動 到Co這說明：可以借助一個空座，將3個盤子從一個座移動到另一個。*如果有4個盤子，那么首先借助空座 C,將盤子1上的三個盤子從 A移動到B;將盤 子1移動到C, A變成空座；借助空座 A,將B座上的三個盤子移動到 Co）package org;import java.util.Sca nner;public class Tower public static void main(String args) System.out.pri ntl n(”輸入盤子

3、的個數(shù)：”)；Scanner sc=new Sca nn er(System.i n);int n=sc. nextl nt(); tower( n, A,B,C);public static void tower(i nt n ,char a, char b, char c)if(n !=0)tower( n-1,a,c,b);System.out.println(move disk +n+t+from+a+t+to +c);c=a;tower( n-1,b,a,c);/ 斐波那契級數(shù)(遞歸，當(dāng)n比較大時，效率比較低)package org;import java.util.Scanner;

4、public class Fib public static long fib(int n) if(n=1 | n=2) return 1;elsereturn fib(n-1)+fib(n-2);/* 測試 */public static void main(String args) System.out.println( 輸入一個整數(shù)： ); Scanner sc=new Scanner(System.in); int n=sc.nextInt();System.out.println( 結(jié)果為： +fib(n);/ 最大公約數(shù) ( 遞歸 )package org;import java.

5、util.Scanner;public class MaxGcd /* 遞歸實(shí)現(xiàn) */public static int gcd(int m， int n) if(n=0)return m;else if(m=n) while(n!=0) int rem=m % n; m=n; n=rem;else gcd2(n,m);return m;/* 測試 */ public static void main(String args) System.out.println(”請輸入兩個整數(shù) m和 n);Scanner sc=new Scanner(System.in);int m=sc.nextInt

6、();int n=sc.nextInt();System.out.println(m+和+n+的最大公約數(shù)為：+gcd(m,n);/ 簡單的 0/1 背包問題 ( 遞歸) ：設(shè)一背包可容物品的最大質(zhì)量為m,現(xiàn)有n件物品，質(zhì)量為 m1, m2 . , mn, mi均為正整數(shù)，要從 n 件物品中挑選若干件，/ 使背包的質(zhì)量之和正好為 mpackage org;public class Bag01 public static boolean knap(int weight, int a, int n)if(n=an-1) / 能放 if(knap(weight-an-1,a,n-1) return

7、true;else/ 不放/ 不放return knap(weight,a,n-1);else / 不能放return knap(weight,a,n-1);/* 測試 */public static void main(String args) int weight=68;int a=16,21,6,31,2,5,7,8,10,15; boolean flag=knap(weight,a,10); System.out.println(flag);/ 求 n!package org;import java.util.Scanner;public class Factorial /* 遞歸實(shí)現(xiàn)

8、 */ public static long fac(int n) if(n=0 | n=1) return 1;else return (n * fac(n-1);/* 非遞歸實(shí)現(xiàn) */ public static long fac2(int n) int sum=1;if(n=0 | n=1) return 1;for(int i=2;i=n;i+) sum*=i;return sum;/* 測試 */ public static void main(String args) System.out.println( 輸入一個整數(shù)： ); Scanner sc=new Scanner(Sys

9、tem.in); int n=sc.nextInt();System.out.println(n+ ！ =+fac(n);/ 求 n 個數(shù)的排列 ( 遞歸 )package org;/* permutation: 排列 */public class Permutation public static void perm(int data, int start, int end) if(start=end-1)for(int i=0;iend;i+)System.out.print(datai);System.out.println();elsefor(int i=start;irightMax

10、 ? leftMax : rightMax;public static int findMin(int srcData, int left, int right) if(left=right)return srcDataleft;int mid=(left+right)/2;int leftMin=findMin(srcData, left, mid);int rightMin=findMin(srcData,mid+1,right); return leftMin right | left a.length) return -1;int low = left;int high = right

11、 - 1;while (low 1; /與 int mid=(low+high)/2 等價， 但執(zhí)行效率高int midVal = amid;if (midVal key) high = mid - 1;else return mid; / key foundreturn -(low + 1); / key not found./* 測試 */public static void main(String args) int a=-9,-1,1,2,3,4,5,6,7;System.out.println(search(a, 0, 8,-1); / 快速排序package org;public

12、class QuickSort public static int sortASC(int array) if(array=null)return null;int srcData=(int)array.clone();return quickSort(srcData, 0, srcData.length-1);/* srcData: 待排序的數(shù)組 first: 起始下標(biāo) last: 終止下標(biāo) */ private static int quickSort(int srcData, int first, int last) if(firstlast)int pos=partition(srcD

13、ata,first,last); quickSort(srcData, first, pos-1); quickSort(srcData, pos+1, last);return srcData;/* 根據(jù)數(shù)組的第一個數(shù)分治，把比數(shù)組第一個數(shù)大的往后排，把比數(shù)組第一個數(shù)小的 往前排 */private static int partition(int srcData, int first, int last)int temp=srcDatafirst;int pos=first;for(int i=first+1;i=last;i+)if(srcDataitemp)pos+; swap(src

14、Data,pos,i);swap(srcData,first,pos);return pos;/* 交換數(shù)組中下標(biāo)為 src 和 dest 的值 */ private static void swap(int data,int src,int dest) int temp=datasrc; datasrc=datadest;datadest=temp;/* 測試 */public static void main(String args) int array=22,13,-5,-8,15,60,17,31,47; System.out.println( 排序前： );for(int i=0;i

15、array.length;i+)System.out.print(arrayi+ );System.out.println();System.out.println( 排序后： );int afterSortArray=sortASC(array);for(int i=0;iafterSortArray.length;i+)System.out.print(afterSortArrayi+ );/ 歸并排序package org;public class MergeSort private static void mergeSort(int a, int temp, int left, int

16、 right) if (left right) int center = (left + right) / 2;mergeSort(a, temp, left, center);mergeSort(a, temp, center + 1, right); merge(a, temp, left, center + 1, right);public static void mergeSort(int a) int temp = new inta.length;mergeSort(a, temp, 0, a.length - 1);private static void merge(int a,

17、int temp, int leftPos, int rightPos, int rightEnd) int leftEnd = rightPos - 1;int tmpPos = leftPos;int numElements = rightEnd - leftPos + 1;while (leftPos = leftEnd & rightPos = rightEnd)if (aleftPos = arightPos) temptmpPos+ = aleftPos+;else temptmpPos+ = arightPos+;while (leftPos = leftEnd) temptmp

18、Pos+ = aleftPos+;while (rightPos = rightEnd) temptmpPos+ = arightPos+;for (int i = 0; i numElements; i+, rightEnd-) arightEnd = temprightEnd;/* 測試 */public static void main(String args) int a = 1, 13, 24, 26, 2, 15, 27, 38 ;System.out.println( 排序前： );for (int i = 0; i a.length; i+)System.out.print(a

19、i + );System.out.println();mergeSort(a);System.out.println( 排序后： );for (int i = 0; i a.length; i+)System.out.print(ai + ); /LCS 問題：( 給出兩個字符串，求出兩個字符串的最長公共子序列)package org;public class LCS public static void main(String args) char left = abcbdab.toCharArray(); /21232523311324char right = bdcaba.toCharA

20、rray(); /312123223445 char result = delLGS(left, right);String strResult=;for(int index = 0;indexresult.length;index+)strResult = strResult+ resultindex+;System.out.println(strResult);public static char delLGS(char left, char right) int lenLeft = left.length;int lenRight = right.length;int c = new i

21、ntlenLeftlenRight;char p;int start, end, len, i, j = 0;end = len = 0;for (i = 0; i = 0; j-) if (lefti = rightj) if (i = 0 | j = 0) cij = 1;else cij = ci - 1j - 1 + 1; else cij = 0;if (cij len) len = cij; end = j;start = end - len + 1;p = new charlen;for (i = start; i = end; i+)pi - start = righti;re

22、turn p;/* LCS 問題就是求兩個字符串最長公共子串的問題。* 解法就是用一個矩陣來記錄兩個字符串中所有位置的兩個字符之間的匹配情況，* 若是匹配則為 1，否則為 0。然后求出對角線最長的 1 序列，* 其對應(yīng)的位置就是最長匹配子串的位置*/ 矩陣鏈乘積問題：(給定n個矩陣A1,A2,.,An,其中Ai與Ai+1是可乘的，i=1,2,n-1./ 如何確定計(jì)算矩陣鏈乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的次數(shù)最少)package org;import java.util.ArrayList;import java.util.Date;import java.util.List;i

23、mport java.util.Random;public class MatrixChainOrder private double m;private int s;public MatrixChainOrder(MatrixArray p) int n, i, j, k, l;double q;n = p.getMatrixArrayLength();m = new doublenn;s = new intnn;for (i = 0; i n; i+) for (j = 0; j n; j+) sij = 0;for (i = 0; i n; i+) mii = 0;for (l = 2;

24、 l n; l+) for (i = 1; i (n - l + 1); i+) j = i + l - 1;mij = 99999999999999999999.0; for (k = i; k j; k+) + p.getMatrixArray(i - 1)*q = mik + mk + 1j p.getMatrixArray(k) * p.getMatrixArray(j);if (q mij) mij = q; sij = k;/ end of MatrixChainOrderpublic double getM(int i, int j) return mij;public int

25、getS(int i, int j) return sij;public static void main(String args) Date date1, date2, date3; long d1, d2, d3; MatrixArray p; int i, j;double sum = 1.0, k = 0.0;p = new MatrixArray(100); p.ranMakeMatrixArray(100); p.makeMatrixChain(); MatrixChainOrder newOrder; newOrder = new MatrixChainOrder(p); Mat

26、rix A, B; date1 = new Date(); d1 = date1.getTime(); System.out.println(d1); A = p.matrixMultiply(p); date2 = new Date(); d2 = date2.getTime(); System.out.println(d2);B = p.matrixChainMultiply(newOrder); date3 = new Date(); d3 = date3.getTime();System.out.println(d3);d1 = d2 - d1;毫秒); 毫秒);d2 = d3 - d

27、2;System.out.println( 普通相乘用時 + d1 + System.out.println( 優(yōu)化相乘用時 + d2 + class Matrix private int i, j;private double matrix;/ 初始化矩陣public void makeMatrix(int i, int j) this.i = i;this.j = j; matrix = new doubleij;/ 隨機(jī)生成矩陣元素public void ranFillMatrix(int random) int s, t;Random ran = new Random(); for (

28、s = 0; s i; s+) for (t = 0; t j; t+) matrixst = ran.nextDouble() * random;/ 獲取矩陣元素public double getMatrix(int i, int j) return matrixij;/ 取得矩陣的列數(shù) public int getMatrixI() return i;/ 取得矩陣的行數(shù) public int getMatrixJ() return j;/ 設(shè)定矩陣中某個元素的值public void setMatrix(int i, int j, double value) matrixij = valu

29、e;/ 矩陣相乘實(shí)用文檔public Matrix multiplyMatrix(Matrix matrix) int s, t;/ 記錄傳入矩陣的維數(shù) int start, middle, end;/ 矩陣運(yùn)算游標(biāo) double sum;s = matrix.getMatrixI();t = matrix.getMatrixJ();this.matrixstartmiddle*Matrix matrixResult = new Matrix(); matrixResult.makeMatrix(i, t); for (start = 0; start i; start+) for (end

30、= 0; end t; end+) sum = 0; for (middle = 0; middle j; middle+) sum = sum + matrix.getMatrix(middle, end);matrixResult.setMatrix(start, end, sum);return matrixResult;class MatrixArray private int matrixnum;private int array;private List matrixobjectarray;/ 獲取矩陣public Matrix getMatrix(int i) return (M

31、atrix) matrixobjectarray.get(i);public MatrixArray(int i) int j;matrixnum = i;array = new intmatrixnum;/ 隨機(jī)生成鏈乘矩陣public void ranMakeMatrixArray(int random) int j;Random ran = new Random();for (j = 0; j matrixnum; j+) arrayj = ran.nextInt(random) + 1;/ 獲取鏈乘陣的維數(shù) public int getMatrixArray(int i) return

32、 arrayi;public int getMatrixArrayLength() return matrixnum;/ 產(chǎn)生具體的矩陣 public void makeMatrixChain() int i, j;matrixobjectarray = new ArrayList(); Matrix x;for (i = 0; i matrixnum - 1; i+) x = new Matrix(); x.makeMatrix(arrayi, arrayi + 1); x.ranFillMatrix(100); matrixobjectarray.add(i, x);/ 矩陣基礎(chǔ)乘publ

33、ic Matrix matrixMultiply(MatrixArray p) Matrix A; int i;A = p.getMatrix(0);for (i = 1; i i) x = mCM(A, S, i, S.getS(i, j); y = mCM(A, S, S.getS(i, j) + 1, j); return x.multiplyMatrix(y);實(shí)用文檔/N皇后問題在一個N*N的棋盤上放置 N個皇后，每行一個并使其不能互相攻擊（同一行、同一列、同一斜線上的皇后都會自動攻擊）。問有多少種擺法。package org;public class Quee nN private

34、 final int size; /private int location; /private in t colsOccupied; /private in t cross1Occupied; /private in t cross2Occupied; /private static int count; /棋盤的大小，也表示皇后的數(shù)目皇后在棋盤的每行上的列的位置皇后在棋盤上占據(jù)的列皇后在棋盤上占據(jù)的正對角線皇后在棋盤上占據(jù)的反對角線解決方案的個數(shù)private static final int STATUS_OCCUPIED = 1; /占領(lǐng)狀態(tài)private static final i

35、nt STATUS_OCCUPY_CANCELED = 0; /未占領(lǐng)狀態(tài)public Quee nN (i nt size) this.size = size;locati on = new in tsize;colsOccupied = new in tsize;cross1Occupied = new in t2 * size; cross2Occupied = new in t2 * size;public void printLocation() System.out.println(”以下是皇后在棋盤上的第 ” + count + 種擺放位置);for (int i = 0; i

36、size; i+)System.out.println(”行：” + i + 列：” + locationi);/判斷位置(i,j)是否被占領(lǐng)private boolean isOccupied(int i, int j) return (colsOccupiedj = STATUS_OCCUPIED)| (cross1Occupiedi - j + size - 1 = STATUS_OCCUPIED)| (cross2Occupiedi + j = STATUS_OCCUPIED);/如果參數(shù)flag為1，表示占領(lǐng)位置(i,j);/如果參數(shù)flag為0，表示取消占領(lǐng)位置(i,j);priv

37、ate void setStatus(int i, int j, int flag) colsOccupiedj = flag; /宣布占領(lǐng)或取消占領(lǐng)第j列；實(shí)用文檔cross1Occupiedi - j + size - 1 = flag; /宣布占領(lǐng)或取消占領(lǐng)正對角線cross2Occupiedi + j = flag; /宣布占領(lǐng)或取消占領(lǐng)反對角線/ 從第 i 行開始擺放皇后public void place(int i) for (int j = 0; j size; j+)/ 在第 i 行分別嘗試把皇后放在每一列上if (!isOccupied(i, j) / 判斷該位置是否被占領(lǐng)l

38、ocationi = j; /擺放皇后，在第 i 行把皇后放在你 j 列setStatus(i, j, STATUS_OCCUPIED); /宣布占領(lǐng) (i,j) 位置if (i size - 1)place(i + 1); / 如果所有皇后沒有擺完，遞歸擺放下一行皇后 else count+; / 統(tǒng)計(jì)解決方案的個數(shù)printLocation(); / 完成任務(wù)，打印所有皇后的位置/ 回溯，取消占領(lǐng)位置 (i,j)setStatus(i, j, STATUS_OCCUPY_CANCELED);public void start() place(0); / 從第 0 行開始放置皇后public

39、 static void main(String args) new QueenN(8).start(); / 開始執(zhí)行 8 皇后/0/1 背包問題(給定n種物品和一個容量為C的背包，物品i的重量是wi,其價值為vi ,背包問題是如何選擇裝入背包的物品，/ 使得裝入背包中物品的總價值最大 ?)package org;import java.util.*;public class KnapSack1 public static void main(String args) 實(shí)用文檔Scanner in = new Scanner(System.in);System.out.println( 請輸

40、入物品的數(shù)量 :); int n = in.nextInt();int w = new intn; int v = new intn; System.out.println( for (int i = 0; i n; i+) wi = in.nextInt();System.out.println( for (int i = 0; i n; i+) vi = in.nextInt();System.out.println( int c = in.nextInt();現(xiàn)在請輸入這些物品的重量 :)現(xiàn)在請輸入這些物品的價值 :)現(xiàn)在請輸入背包的容量 :);/* * 按單位重量價值 ri=vi/wi

41、 降序排列 */ double startTime = System.currentTimeMillis(); double r = new doublen;int index = new intn;for (int i = 0; i n; i+) ri = (double) vi / (double) wi; indexi = i;double temp = 0;for (int i = 0; i n - 1; i+) for (int j = i + 1; j n; j+) if (ri rj) temp = ri; ri = rj; rj = temp; int x = indexi; indexi = indexj; indexj = x;/*排序后的重量和價值分別存到w1和v1中*/int w1 = new intn;int v1 = new intn;for (int i = 0; i n; i+) 實(shí)用文檔w1i = windexi; v1i = vindexi;System.out.println(Array