遞歸解決八皇后以及漢諾塔迷宮源碼

1、假設(shè)欲計算出13*4，則：13 * 4 = 13 + ( 13 * 3 )= 13 + ( 13 + ( 13 * 2 ) )= 13 + ( 13 + ( 13 + ( 13 * 1 ) ) )= 13 + ( 13 + ( 13 + 13 ) )= 13 + ( 13 + 26 )= 13 + 39 = 52程序源代碼：010203040506070809101112131415161718192021222324252627282930313233343536373839/* = Program Description =*/* 程序名稱： multiply.c */* 程序目的： 設(shè)計

2、一個可計算兩數(shù)相乘，但僅用加法運算， */* 不使用乘法運算的程序。 */* Written By (WANT Studio.) */* = */* - */* 遞歸乘法運算 */* - */int Multiply(int M,int N)intResult; /*運算結(jié)果*/if ( N = 1)Result = M; /* 遞歸結(jié)束條件*/ElseResult = M + Multiply(M,N-1);/* 遞歸執(zhí)行部分 */returnResult;/* - */* 主程序 */* - */void main ()intNumA;/* 乘數(shù)變量*/intNumB;/* 被乘數(shù)變量*/

3、intProduct;/* 乘積變量 */printf("Please enter Number A:");/* 輸入乘數(shù)*/scanf("%d",&NumA);printf("Please enter Number B:");/* 輸入被乘數(shù)*/scanf("%d",&NumB);Product = multiply(NumA,NumB);printf("%d * %d = %d",NumA,NumB,Product);運行結(jié)果：C:DS>multiplyPlease e

4、nter Number A:13Please enter Number B:413 * 4 = 52C:DS>我們由題意可知每次執(zhí)行的過程相似，唯一的不同點為其中一個傳入?yún)?shù)，每次執(zhí)行都遞減。遞歸結(jié)束條件為當被乘數(shù)為1時返回乘數(shù)的值。否則繼續(xù)調(diào)用程序并遞減傳入被乘數(shù)值。其結(jié)構(gòu)如下：int Multiply(int M,int N)intResult;if ( N = 1)Result = M;/* 遞歸結(jié)束條件(Stopping Case) */else Result = M + Multiply(M,N-1);/* 遞歸執(zhí)行部分(Recursive Step) */ returnRes

5、ult;處理遞歸問題，常采用if語句來判斷是否符合遞歸結(jié)束條件，其算法格式如下：if (符合遞歸結(jié)束條件)then返回 答案else使用遞歸將程序分割為更簡單的小程序。在C語言中，我們采用堆棧這個數(shù)據(jù)結(jié)構(gòu)來記錄函數(shù)調(diào)用后的返回地址。例如有一個程序如下：intProcedureA ()/*子程序A*/ProcedureB();/*調(diào)用子程序B*/*返回地址2 */intProcedureB()/*子程序B */void main ()/*主程序 */ProcedureA();/*調(diào)用子程序A */*返回地址1 */程序源代碼：01020304050607080910111213141516171

6、81920212223242526272829303132333435/* = Program Description = */* 程序名稱： reverse.c */* 程序目的： 運用遞歸設(shè)計一個將字符串反轉(zhuǎn)的程序。 */* Written By . (WANT Studio.) */* = */charString30;/* 聲明字符串變量*/intLength;/* 字符串長度變量 */* - */* 遞歸字符串反轉(zhuǎn) */* - */void Reverse(int N)if ( N < Length)Reverse(N+1);/* 遞歸執(zhí)行部分 */printf("%

7、c",StringN);/* - */* 主程序 */* - */void main ()printf("Please enter string : "); /* 輸入原字符串*/scanf("%s",&String);Length = strlen(String); /* 取得字符串長度*/printf("The reverse string : ");Reverse(0); /* 調(diào)用遞歸函數(shù)*/printf("n");運行結(jié)果：C:DS>reversePlease enter stri

8、ng : ABCThe reverse string : CBAC:DS>程序源代碼：01020304050607080910111213141516171819202122232425262728293031/* = Program Description = */* 程序名稱： factor.c */* 程序目的： 運用遞歸設(shè)計一個做階乘運算的程序。 */* Written By . (WANT Studio.) */* =*/* - */* 遞歸階層運算 */* - */int Factor(int N)if ( N <= 1) /* 遞歸結(jié)束條件 */return 1;el

9、sereturn N * Factor(N-1);/* 遞歸執(zhí)行部分 */* - */* 主程序 */* - */void main ()intNumber; /* 運算數(shù)值變量*/intFactorial; /* 階乘數(shù)值變量*/printf("Please enter a number : "); /* 輸入數(shù)值*/scanf("%d",&Number);Factorial = Factor(Number); /* 調(diào)用遞歸函式*/printf("%d! = %dn",Number,Factorial);/* 輸出運算結(jié)果

10、*/運行結(jié)果：C:DS>factorPlease enter a number : 77! = 5040C:DS>程序源代碼：0102030405060708091011121314151617181920212223242526272829303132333435/* = Program Description =*/* 程序名稱： gcd.c */* 程序目的： 運用遞歸設(shè)計一個求兩數(shù)之最大公因子的程序 */* Written By. (WANT Studio.) */* =*/* - */* 遞歸求最大公因子 */* - */int GCD(int M,int N)if (N

11、 = 0)/* 遞歸結(jié)束條件 */return M;elsereturn GCD(N,M % N);/* 遞歸執(zhí)行部分 */* - */* 主程序 */* - */void main ()intNumberA;/* 運算數(shù)值變量*/intNumberB;/* 運算數(shù)值變量 */intResult;/* 運算結(jié)果變量 */printf("The Great Common Divisor of Number A, Number Bn");printf("Please enter number A : ");/* 輸入數(shù)值*/scanf("%d&qu

12、ot;,&NumberA);printf("Please enter number B : ");/* 輸入數(shù)值*/scanf("%d",&NumberB);Result = GCD(NumberA,NumberB);/* 調(diào)用遞歸函式*/printf("GCD(%d,%d) = %dn",NumberA,NumberB,Result);運行結(jié)果：C:DS>gcdThe Great Common Divisor of Number A, Number BPlease enter number A : 2545Pl

13、ease enter number B : 3155GCD(2545,3155) = 5C:DS>程序源代碼：0102030405060708091011121314151617181920212223242526272829303132/* = Program Description = */* 程序名稱： fib.c */* 程序目的： 運用遞歸設(shè)計一個求費氏級數(shù)的程序。 */* Written . (WANT Studio.) */* = */* - */* 遞歸求費氏級數(shù) */* - */int Fib(int N)if (N <= 1) /* 遞歸結(jié)束條件 */retur

14、n N;elsereturn Fib(N-1) + Fib(N-2);/* 遞歸執(zhí)行部分 */* - */* 主程序 */* - */void main ()intNumber; /* 運算數(shù)值變量*/intResult; /* 運算結(jié)果變量 */printf("The Fibonacci Numbers n");printf("Please enter a number : ");/* 輸入數(shù)值*/scanf("%d",&Number);Result = Fib(Number); /* 調(diào)用遞歸函式*/printf(&quo

15、t;Fibonacci Numbers of %d = %dn",Number,Result);運行結(jié)果：C:DS>fibThe Fibonacci NumbersPlease enter a number : 10Fibonacci Numbers of 10 = 55C:DS>程序源代碼：01020304050607080910111213141516171819202122232425262728293031323334353637383940/* = Program Description = */* 程序名稱： comb.c */* 程序目的： 運用遞歸設(shè)計一個

16、求組合公式的程序。 */* Written By . (WANT Studio.) */* = */* - */* 遞歸求組合公式 */* - */int Comb(int N,int M)if ( (N = M) | (M = 0) )/* 遞歸結(jié)束條件 */return 1;else /* 遞歸執(zhí)行部分 */return Comb(N-1,M) + Comb(N-1,M-1);/* - */* 主程序 */* - */void main ()intNumberN;/* 運算數(shù)值變量*/intNumberM;/* 運算數(shù)值變量*/intResult; /* 運算結(jié)果變量 */printf(&

17、quot;The Combination Number of two Numbers.n");printf("Please enter number N: ");/* 輸入數(shù)值*/scanf("%d",&NumberN);printf("Please enter number M: ");/* 輸入數(shù)值*/scanf("%d",&NumberM);if (NumberN >= NumberM)Result = Comb(NumberN,NumberM);/* 調(diào)用遞歸函式*/prin

18、tf("Comb(%d,%d) = %dn",NumberN,NumberM,Result);elseprintf("Error: N < M !n");運行結(jié)果：C:DS>combThe Combination Number of two Numbers.Please enter number N: 9Please enter number M: 3Comb(9,3) = 84C:DS>combThe Combination Number of two Numbers.Please enter number N: 3Please en

19、ter number M: 9Error: N < M !C:DS>程序源代碼：0102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556/* = Program Description = */* 程序名稱： hanoi.c */* 程序目的： 運用遞歸來解漢諾塔問題。 */* Written By . (WANT Studio.) */* = */#include <stdio.h>intCounter

20、;/* 計數(shù)器變量*/* - */* 遞歸解漢諾塔問題 */* - */int Hanoi(char From,char To,char Auxiliary,int N)if ( N = 1 )/* 遞歸結(jié)束條件 */Counter+;/* 計數(shù)器遞增*/printf("Step %d : ",Counter);printf("Move disk 1 from peg-%c to peg-%c.n",From,To);else/* 遞歸執(zhí)行部分 */* 將目的樁和輔助樁交換*/Hanoi(From,Auxiliary,To,N-1);Counter+;/

21、* 計數(shù)器遞增*/printf("Step %d : ",Counter);printf("Move disk %d from peg-%c to peg-%c.n",N,From,To);/* 將來源樁和輔助樁交換*/Hanoi(Auxiliary,To,From,N-1);/* - */* 主程序 */* - */void main ()intNumber;/* 鐵盤數(shù)目變量*/charSource;charDestination;charAuxiliary;Counter = 0;printf("The Tower of Hanoi pr

22、ogram.n");printf("Please enter the number of disks : ");scanf("%d",&Number);/* 輸入鐵盤數(shù)*/printf("The Source peg : ");Source = getche();/* 輸入來源樁 */printf("nThe Auxiliary : ");Auxiliary = getche();/* 輸入輔助樁*/printf("nThe Destination : ");Destinati

23、on = getche();/* 輸入目的樁*/printf("n");Hanoi(Source,Destination,Auxiliary,Number);/* 調(diào)用遞歸函數(shù)*/運行結(jié)果：C:DS>hanoiThe Tower of Hanoi program.Please enter the number of disks : 4The Source peg : AThe Auxiliary : BThe Destination : CStep 1 : Move disk 1 from peg-A to peg-B.Step 2 : Move disk 2 fro

24、m peg-A to peg-C.Step 3 : Move disk 1 from peg-B to peg-C.Step 4 : Move disk 3 from peg-A to peg-B.Step 5 : Move disk 1 from peg-C to peg-A.Step 6 : Move disk 2 from peg-C to peg-B.Step 7 : Move disk 1 from peg-A to peg-B.Step 8 : Move disk 4 from peg-A to peg-C.Step 9 : Move disk 1 from peg-B to pe

25、g-C.Step 10 : Move disk 2 from peg-B to peg-A.Step 11 : Move disk 1 from peg-C to peg-A.Step 12 : Move disk 3 from peg-B to peg-C.Step 13 : Move disk 1 from peg-A to peg-B.Step 14 : Move disk 2 from peg-A to peg-C.Step 15 : Move disk 1 from peg-B to peg-C.C:DS>程序源代碼：010203040506070809101112131415

26、161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117/* = Program Description = */* 程序名稱： queen.c */* 程序目的： 運用遞歸來解N皇后問題 */* Written

27、 . (WANT Studio.) */* = */charChessboard88;/* 聲明8*8的空白棋盤*/* -*/* 遞歸解N皇后問題 */* -*/int N_Queens(int LocX,int LocY,int Queens)inti,j;/* 循環(huán)計數(shù)變量*/intResult=0;if ( Queens = 8 ) /* 遞歸結(jié)束條件 */return 1;else/* 遞歸執(zhí)行部分 */if ( QueenPlace(LocX,LocY) )ChessboardLocXLocY = 'Q'for (i=0;i<8;i+)for (j=0;j<

28、;8;j+)Result += N_Queens(i,j,Queens+1);if (Result > 0)break;if (Result > 0)return 1;elseChessboardLocXLocY = 'X'Return 0;elsereturn 0;/* - */* 判斷傳入坐標是否可放置皇后 */* - */int QueenPlace(int LocX,int LocY)inti,j;if (ChessboardLocXLocY != 'X')/* 判斷是否有皇后*/return 0; for (j=LocY-1;j>=0

29、;j-)/* 判斷上方是否有皇后*/if (ChessboardLocXj != 'X')return 0;for (j=LocY+1;j<8;j+)/* 判斷下方是否有皇后*/if (ChessboardLocXj != 'X')return 0; for (i=LocX-1;i>=0;i-)/* 判斷左方是否有皇后*/if (ChessboardiLocY != 'X')return 0;for (i=LocX+1;i<8;i+)/* 判斷右方是否有皇后*/if (ChessboardiLocY != 'X'

30、)return 0;i = LocX - 1;j = LocY - 1;while ( i>=0 && j>=0 )/* 判斷左上方是否有皇后*/if (Chessboardi-j- != 'X')return 0;i = LocX + 1;j = LocY - 1;while ( i<8 && j>=0 )/* 判斷右上方是否有皇后*/if (Chessboardi+j- != 'X')return 0;i = LocX - 1;j = LocY + 1;while ( i>=0 &&

31、; j<8 )/* 判斷左下方是否有皇后*/if (Chessboardi-j+ != 'X')return 0;i = LocX + 1;j = LocY + 1;while ( i<8 && j<8 )/* 判斷右下方是否有皇后*/if (Chessboardi+j+ != 'X')return 0;return 1;/* - */* 主程序 */* - */void main ()inti,j;/* 循環(huán)計數(shù)變量*/for (i=0;i<8;i+)for (j=0;j<8;j+)Chessboardij = &

32、#39;X'N_Queens(0,0,0);printf("The graph of 8 Queens on the Chessboard.n");printf(" 0 1 2 3 4 5 6 7 n");printf(" +-+-+-+-+-+-+-+-+n");for (i=0;i<8;i+)printf(" %d |",i);for (j=0;j<8;j+)printf("-%c-|",Chessboardij);printf("n +-+-+-+-+-+-+

33、-+-+n");運行結(jié)果：C:DS>queenThe graph of 8 Queens on the Chessboard. 0 1 2 3 4 5 6 7 +-+-+-+-+-+-+-+-+ 0 |-Q-|-X-|-X-|-X-|-X-|-X-|-X-|-X-| +-+-+-+-+-+-+-+-+ 1 |-X-|-X-|-X-|-X-|-Q-|-X-|-X-|-X-| +-+-+-+-+-+-+-+-+ 2 |-X-|-X-|-X-|-X-|-X-|-X-|-X-|-Q-| +-+-+-+-+-+-+-+-+ 3 |-X-|-X-|-X-|-X-|-X-|-Q-|-X-|-

34、X-| +-+-+-+-+-+-+-+-+ 4 |-X-|-X-|-Q-|-X-|-X-|-X-|-X-|-X-| +-+-+-+-+-+-+-+-+ 5 |-X-|-X-|-X-|-X-|-X-|-X-|-Q-|-X-| +-+-+-+-+-+-+-+-+ 6 |-X-|-Q-|-X-|-X-|-X-|-X-|-X-|-X-| +-+-+-+-+-+-+-+-+ 7 |-X-|-X-|-X-|-Q-|-X-|-X-|-X-|-X-| +-+-+-+-+-+-+-+-+C:DS>程序源代碼：0102030405060708091011121314151617181920212223242

35、526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677/* = Program Description = */* 程序名稱： maze.c */* 程序目的： 運用遞歸來解迷宮問題 */* Written B. (WANT Studio.) */* = */intMaze87 = /* 聲明5*4的迷宮，外圍不可走*/1, 1, 1, 1, 1, 1, 1,1, 0, 1, 0, 0, 0, 1,1, 1, 0, 1, 1, 0, 1,1, 1, 0, 1, 1, 0, 1,1, 1, 1, 0, 1, 1, 1,1, 0, 0, 1, 0, 1, 1,1, 1, 1, 1, 0, 0, 1,1, 1, 1, 1, 1, 1, 1