三個齒輪嚙合問題

設有三個齒輪互相銜接，求當三個齒輪的某兩對齒互相銜接后到下一次這兩對齒再互相銜接，每個齒輪最少各轉多少圈。 解:這是求最小公倍數的問題。每個齒輪需轉圈數是三個齒輪齒數的最小公倍數除以自己的齒數。設三個齒輪的齒數分別為:na、nb、nc；嚙合最小圈數分別為:ma、mb、mc；三齒輪齒數的最小公倍數為k3。計算步驟表示為：開始讀入三齒輪齒數求三齒數的最小公倍數k3分別計算嚙合的最小圈數輸出結果結束計算三齒數的最小公倍數k3?？梢园言搯栴}分解成先求兩個齒數na與nb的最小公倍數k2，然后再求k2與第三個齒數nc的最小公倍數k3，

k3即為na、nb、nc三個齒輪齒數的最小公倍數。設已經有求兩個數的最小公倍數的函數

intlowestcm(intx,inty)則該過程可表示成。求三齒數的最小公倍數k3=lowestcm(lowestcm(na,nb),nc )結束求兩個數的最小公倍數的函數lowestcm。

x、y的最小公倍數是x、y的積除以x、y的最大公約數。設已經有求兩個數的最大公約數的函數

intgcd(intx,inty)則過程可表示成：

intlowestcm(intx,inty)returnx*y/gcd(x,y)結束def采用展轉相除法求兩個數的最大公約數，函數

intgcd(intx,inty)定義如下函數gcd可用一個遞歸函數實現：intgcd(intx,inty)結束y≠0returngcd(y,x%y)returnx最后，分別計算嚙合的最小圈數。開始ma=k3/namb=k3/nbmc=k3/nc結束受限排列組合——窮舉法與試探法

有這樣一類問題，從若干元素的所有排列(或組合)中選取符合某種條件的一些排列(或組合)。八皇后問題Debruijn問題解這類問題有兩條途徑:1.窮舉法;2.試探法。八皇后問題

這是一個古老而有趣的游戲。高斯(C.F.Gauss)最早在1850年提出并研究過這個問題，但是沒有完全解決。該問題是： 在一個8*8格的國際象棋棋盤上放置八個皇后，使任意兩個皇后都不能互相攻擊。按國際象棋規則，兩個皇后可以互相攻擊。若在同一行上，或在同一列上,或在同一條斜線上（包括左高右低、右高左低）********如圖放置的八個皇后便不能互相攻擊。編程序,求出所有符合要求的布局。共有92種滿足條件的布局，若除去對稱的等類同布局,完全不同者有12種。這里不考慮剔除類同布局，求出全部92種布局。八皇后問題的表示方法:用一個一維數組表示棋盤。A[i]表示棋盤的第i列，每列一個皇后，若A[i]中存放有數k表示第i列中第k行上放置了皇后。例: A[3]=6表示在棋盤的第3列第6行上放置一個皇后。A[0]不用

012345678A:八皇后窮舉法

本方法思路是，按某種順序枚舉出全部排列或組合。每當枚舉出一種排列或組合之后，便用給定條件判斷該種排列或組合是否符合條件。若符合條件，則本種排列或組合被選中，可以輸出或記錄下來。若不符合條件，則把本種排列或組合舍掉。八個皇后的排列問題，最簡單的方法是八重循環，可以編出如下窮舉法程序。

intmain(void){inta[9]，i1,i2,i3,i4,i5,i6,i7,i8;for(i1=1;i1<=8;i1++)for(i2=1;i2<=8;i2++)for(i3=1;i3<=8;i3++)for(i4=1;i4<=8;i4++)for(i5=1;i5<=8;i5++)for(i6=1;i6<=8;i6++)for(i7=1;i7<=8;i7++)for(i8=1;i8<=8;i8++){a[1]=i1;a[2]=i2;a[3]=i3;a[4]=i4;a[5]=i5;a[6]=i6;a[7]=i7;a[8]=i8;if(check())out();}}八皇后試探法按規律，從一滿足條件的初始狀態出發，逐步生成滿足條件的子排列,不斷增加子排列長度。增加子排列長度過程中，每增加一位,生成一個子排列后,便檢驗它是否滿足條件。不滿足條件,則換一個子排列－即修改當前位置滿足條件,則延長子排列,增加子排列長度。子排列的長度滿足要求長度,便找到了一個解。若要求找一個解即可，這時便可以結束。若要求找所有解，這時可以輸出或記錄本解，然后按前述思路，繼續修改排列，繼續試探，找下個解在上述試探過程中,修改當前位置時：若當前位置上還有沒被試探過的元素，則應該取下一個沒被試探過的元素進行試探若當前位置上所有元素都被試探過了，則在當前位置上沒辦法再修改了這說明前邊的某個位置有問題，放置的元素不對，顯然應該向回退一位?；厮莺?原來的上一個位置變成了當前位置,則又變成修改當前位置的問題了。這時,同樣還應該考慮取下一個沒被試探過的元素進行試探,以及是否所有元素在當前位置上都被試探過了并回溯的問題。如圖所示，設要生成一個n位的串A；在每個位置上可選擇的符號有K個；A應該滿足條件r；m表示當前試探位置。試探法的算法描述為：1.初始時，從第一個位置開始試探，令m=1;2.然后在第m位逐次取可選符號:B[1],B[2],...,

B[k]。對某一個B[i]有兩種可能:012n

A:…B:12…k若B[i]使A[1],A[2],...,A[m]滿足r,則進入A的下一個位置。

m=m+1012…mm+1nA:B:12…k若B[i]不能使A[1],A[2],...,A[m]滿足r,則有兩種情況:i<k，012……mnA:B[i]B:1…ii+1…k若B[i]不能使A[1],A[2],...,A[m]滿足r,則有兩種情況:i<k，取B中下一個符號繼續試探

i=i+1012……mnA:B[i+1]B:1…ii+1…k若i=k說明在當前位置上所有符號都已經被試探過012…m-2m-1mnA:B[w]B[k]B:1…imim+1…k若i=k說明在當前位置上所有符號都已經被試探過應該回溯到上一個位置,作m=m-1后繼續試探直到找到解、m=0結束012…m-2m-1mnA:B[i1]B[i2]…B[w+1]B:1…ww+1…k**************以四皇后問題為例，考察試探過程：12341234上述試探法思想描述如下:試探法初值

試探未結束結束

子排列合格夠長修正當前位置輸出延長修正當前位置修正當前位置取下一個沒被試探過的元素回溯結束本位置已經沒有沒被試探過的元素def延長當前位置賦值第一個元素下一個位置變成當前位置(m=m+1)返回程序如下: intA[9],m;boolcheck(intm);/*檢查某格局是否合格的函數*/voidout();/*輸出函數*/voidchange(void){/*修正*/while(A[m]==8)m=m-1;A[m]=A[m]+1;}voidextend(void){/*延長*/m=m+1;A[m]=1;}intmain(void){/*主程序*/A[0]=0;A[1]=1;m=1;while(m>0)if(check(m)){if(m==8){out();change();}else extend();}elsechange();}窮舉法與試探法的著眼點及主要區別在于:窮舉法是舉出全部可能的格局，對每種格局進行檢驗,使合格者入選，不合格者淘汰。試探法是從初始滿足條件的格局開始，逐步前進。每前進一步都判斷子格局是否合適。若當前子格局合適則進入下一級;若當前子格局不合適則選同一級的下一個子格局;但是若同級子格局已全部試探完畢,則回溯到上一級直到當前子格局夠長為止。

顯然窮舉法的運算量比試探法要大的多。因為它要考慮一切情況的排列，而試探法可以在中間丟掉大量的不合格排列。事實上許多問題的窮舉法是不適用的,把每一種情況都排出來，并檢驗其是否合格顯然是不可能的。不論窮舉法還是試探法都可以寫成遞歸形式:循環迭代遞歸

八皇后窮舉法的遞歸實現用窮舉法實現八皇后問題,可以抽象的描述為：在數組A的8個位置上分別排列一個1到8的整數。設想,如果有一個函數

queen(r)

能夠完成

“在數組A后部的r個位置（從第8-r+1到8）上,分別排列一個1到8的整數”。則八皇后問題便是

queen(8)“在數組A后部的r個位置上,分別排列一個1到8的整數”可以分解成:先在第8-r+1位上分別排列一個1到8的整數；然后再在剩余的后部的r-1個位置上分別排列一個1到8的整數。步驟2便是對queen的遞歸調用

queen(r-1)。最后考慮遞歸出口,顯然應該在r=1

時檢驗輸出并退出遞歸。由此得遞歸實現八皇后問題的窮舉算法及遞歸程序八皇后窮舉法結束queen(8)queen(r)結束for(i=1;i<=8;i++)queen(r-1)A[8-r+1]=i;r>1輸出檢驗intA[9];boolcheck();/*檢查某格局是否合格的函數*/voidout();/*輸出函數,分程序略*/voidqueen(intr){inti;for(i=1;i<=8;i++){A[8-r+1]=i;if(

r>1)queen(r-1);elseif(cheek())out();}}intmain(void){queen(8)}八皇后試探法的遞歸實現試探方法的思路是，按一定規律，從某一滿足條件的初始狀態出發，逐步試探生成滿足條件的子排列,不斷增加子排列長度,直到子排列的長度滿足問題的要求長度n為止,便找到了一個解。設想,如果有一個函數

queen(r)

能夠“合理的排列數組A后部的r個(從第n-r+1到n)元素” 并保證序列滿足給定條件,則八皇后問題便是對queen的調用

queen(8)“合理的排列數組A后部的r個（從第n-r+1到n）元素”可以分解成:首先在第n-r+1位上排列一個合格的元素,然后在合理的排列從n-(r-1)+1開始的后部的r-1個元素。步驟1“在第n-r+1位上排列一個合格的元素”，即是把8個元素順次的排列在第n-r+1位上,并對每個元素檢驗是否合格，使合格者入選。步驟2“合理的排列后部的r-1個元素”顯然與“合理的排列后部的r個元素”具有相同的特征屬性,只是排列的元素個數減少了,也就是說它表現為對queen的遞歸調用。queen(r)結束for(i=1;i<=8;i++)queen(r-1)A[8-r+1]=i;合理輸出r>1

在該算法中,試探法的“延長”體現在繼續遞歸調用上；“修正本位”體現在從1到8作i的循環上；“回溯”則體現在遞歸出口的返回上。intA[9];boolcheck(intm);/*檢查某格局是否合格的函數*/voidout(void);/*輸出函數*/voidqueen(intr){/*試探法*/inti;for(i=1;i<=8;i++){A[8-r+1]=i;if(check(8-r+1))if(r>1)queen(r-1);elseout();}}intmain(void){ /*主程序*/queen(8)}分析檢驗條件:縱向,每列只有一個皇后:由數據結構保證每列只能放一個皇后。橫向，每行放置一個皇后:顯然要求數組A中不能有重復的數值。設當前為第m步，由于前m-1步是合格的,所以只要檢驗A[m]不等于所有的A[1]、...、A[m-1]。左高右低對角線(共有2*n-1即15條)：這樣對角線上不同位置的行列號之差相等。設當前為第m步，由于前m-1步是合格的，所以只要對一切i<m檢驗：

A[m]-m≠A[i]-i。左高右低對角線:與左高右低對角線類似。只不過這里該檢查

A[m]+m≠A[i]+i。試探法檢驗函數check如下，

boolcheck(intm){inti;for(i=1;i<m;i++){if(A[m]==A[i])returnfalse;if(A[m]-m==A[i]-i)returnfalse;if(A[m]+m==A[i]+i)returnfalse;}returntrue;}

窮舉法的檢驗函數應該多加一層循環。

boolcheck(){inti,j;for(i=1;i<8;i++){ for(j=i+1;j<=8;j++){if(A[j]==A[i])returnfalse;if(A[j]-j==A[i]-i)returnfalse;if(A[j]+j==A[i]+i)returnfalse;}}returntrue;}

Debruijn問題如圖由８個二進制數字0、1組成一個環。使８個3位的二進制數:0000

0011010201131004

1015

11061117正好在環中各出現一次。本例目前的順序是：0、1、2、5、3、7、6、4。設計生成這樣環的程序。環由2n個二進制數字組成，恰好包含2n個互不相同的n位二進制數。00001111

6.6迷宮問題

問題的提出迷宮問題是指在一個m*n的矩陣當中，其中”0”代表可以行走的區域，”1”代表不可行走的區域，當你處在迷宮的任何一個位置，除了不可行走的區域外，其余皆可以往上、下、左、右、左上、左下、右上、右下八個方向行走來找尋迷宮出口。程序實現程序目的運用遞歸來解迷宮問題程序構思遞歸結束條件：當已經走到出口時(當出口(6,5),標記為2時)遞歸執行部分：判斷傳入坐標是否可走如果可以走的話，則遞歸調用往上,往右上,往右,往右下,往下,往左下,往左,往左上坐標是否可走。可走的話，返回1。不可走的話，標記改為3(已走過,但為能有通路)。

6.6迷宮問題

程序源代碼importConsoleReader.*;//引入已定義的數據輸入類

publicclassmaze{publicstaticintMaze[][]={//聲明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}};

6.6迷宮問題

publicstaticvoidmain(Stringargs[]){inti,j;//循環計數變量

System.out.println(“==ProblemofMaze==”);System.out.println(“TheMazesourceis(1,1).”);System.out.println(“TheMazeDestinationis(6,5).”);Way(1,1);

System.out.println(“ThegraphofMaze.”);System.out.println(“0123456“);System.out.println(“+---+---+---+---+---+---+---+”);

for(i=0;i<8;i++){

6.6迷宮問題

System.out.print(“

“+i+”|“);for(j=0;j<7;j++)System.out.print(“-“+Maze[i][j]+”-|”);System.out.println(“

”);System.out.println(“+---+---+---+---+---+---+---+”);}}

//-----------------------------