典型的回溯算法問題

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

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

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

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

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