1、典型的回溯算法問題一、購票問題有2n個人排隊購一件價為0.5元的商品，其中一半人拿一張1元人民幣，另一半人拿一張0.5元的人民幣，找出所有排隊的方案。問這2n個人應該如何排隊？(2)該問題可以用二進制數表示：用0表示持0.5元的人，么2n個人排隊問題化為2n個0、1的排列問題。這里我們用數組2n存放持幣情況。(3)設k是B數組下標指針，BK=0或BK=1,另用數組用1表示持1元的人，那B1.d0、d1記錄0與1的個數，且必須滿足：nd0=d1。要使售貨員在售貨中，不發生找錢困難，(售貨員一開始就沒有準備零錢)分析：(1)根據題意可以看出，要使售貨員在售貨中，不發生找錢困難，則在排隊中，應該是任

2、何情況下，持0.5元的排在前面的人數多于持1元的人數。(4)算法：回溯搜索。0，(a)先將B1、B2、B2n置1,從第一個元素開始搜索，每個元素先取再取1,即BK+1DBK,試探新的值，若符合規則，增加一個新元素；(b)若k2n,則k+1Dk,試探下一個元素，若k=2n則輸出B1、B2,B2n。(c)如果BK的值不符合要求，則BK再加1,試探新的值，若BK=2,表示第k個元素的所有值都搜索過,均不符合條件,只能返回到上一個元素BK1,即回溯。(d)返回到上一個元素(5)直到求出所有解。k：=k1,并修改D0、D1。二、騎士游歷問題在nDn的國際象棋上的某一位置上放置一個馬，規則，要求這個馬能不

3、重復地走完nDn個格子,試用計算機解決這個問題。分析：本題是典型的回溯算法問題,設騎士在某一位置,設步可以是如圖(n=5)所示的8個位置之一。然后采用象棋中“馬走日字”的(X,Y),按規則走,下一我們將重點考慮前進的方向：如果某一步可繼續走下去,就試探著走下去且考慮下一步的走法,若走不通則返回,考慮另選一個位置。三、四色問題設有如圖1的地圖，每個區域代表一個省，區域中的數字表示省的編號，現在要求給每個省涂上紅、藍、黃、白四種顏色之一，同時使相鄰的省份以不同的顏色區分。圖2圖1分析：（1）本題是圖論中的一個搜索問題，我們可以將該問題簡化：將每個省看著一個點，而將省之間的聯系看作一條邊，可以得到如

4、圖2所示圖形。（2）從圖2可以知道各省之間的相鄰關系，我們可以數據陣列表示矩陣，即用一個二維數組來表示：Rx，y=1表示省x與省y相鄰0表示省x與省y不相鄰由圖2可以得到如下矩陣0100001101111101010000110100010101001001011100010（3）從編號為1的省開始按四種顏色順序填色，當第一個省顏色與相鄰省顏色不同時，就可以確定第一個省的顏色，然后，再依次對第二、第三，進行處理，直到所有省份顏色都涂上為止。（4）問題關鍵在于在填色過程中，如果即將填的顏色與相鄰省的顏色相同，而且四種顏色都試探過，均不能滿足要求，則需要回溯到上一個點（即前一個省），修改上一個省的

5、顏色，重新試探下一個省的顏色。四、填數問題在n*n的棋盤上（1二n=10）填入1,2,3,n*n,共有n*n個數，使得任意兩個相鄰數的和為素數。例如：當n=2時，有：當n=4時，一種可以填寫的方案如下表，在這里我們約定：左上角的格子里必須填數字1。程序要求：輸入n；輸出：有多個解，則輸出第一行、第一列之和為最小的排列方案；若無解，則輸出“NO！”12111216158513491467103分析：（1）從問題可以看出這是一個搜索問題，是素數的任務。程序中必須完成判斷相鄰兩個數的和是否（2）如果一邊填數，一邊求和及判斷素數，程序運行速度將大大減慢，所以我們可以采用數組結構，將2Dn*n之間所有素數存放在一個數組中。由于問題中指出n=10,所以，最大的相鄰兩個數的和是：99+100200。我們只需要將2D200之間的素數存放在數組中就可以了。（3）按行、列填入數據，并求相鄰兩個數的和，將其與素數數組比較，若是素數，則當前格可以填數，繼續填數。若當前格沒有數據可以填，則要回溯到上一格，重新填寫上一格數據，再進行判斷。數據結構：T表示1Dn*n之間的數是否用過，false表示