第5章搜索與回溯算法(C版)

1、第五章 搜索與回溯算法 搜索與回溯是計(jì)算機(jī)解題中常用的算法，很多問(wèn)題無(wú)法根據(jù)某種確定的計(jì)算法則來(lái)求解，可以利用搜索與回溯的技術(shù)求解?；厮菔撬阉魉惴ㄖ械囊环N控制策略。它的基本思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無(wú)解。 如迷宮問(wèn)題：進(jìn)入迷宮后，先隨意選擇一個(gè)前進(jìn)方向，一步步向前試探前進(jìn),如果碰到死胡同，說(shuō)明前進(jìn)方向已無(wú)路可走，這時(shí)，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無(wú)路可走，則返回一步，再看其它方向是否還有路可走；如果有路可走，則沿該方

2、向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無(wú)解為止。遞歸回溯法算法框架一int Search(int k)for (i=1;i=算符種數(shù);i+)if (滿足條件) 保存結(jié)果if (到目的地) 輸出解; else Search(k+1);恢復(fù)：保存結(jié)果之前的狀態(tài)回溯一步 遞歸回溯法算法框架二int Search(int k) if (到目的地) 輸出解;elsefor (i=1;i=算符種數(shù);i+)if (滿足條件) 保存結(jié)果; Search(k+1);恢復(fù)：保存結(jié)果之前的狀態(tài)回溯一步【例1】素?cái)?shù)環(huán):從1到20這20個(gè)數(shù)擺成一個(gè)環(huán)，要求相鄰的兩個(gè)數(shù)的和是一個(gè)素?cái)?shù)

3、?！舅惴ǚ治觥?非常明顯，這是一道回溯的題目。從1開(kāi)始，每個(gè)空位有20種可能，只要填進(jìn)去的數(shù)合法：與前面的數(shù)不相同；與左邊相鄰的數(shù)的和是一個(gè)素?cái)?shù)。第20個(gè)數(shù)還要判斷和第1個(gè)數(shù)的和是否素?cái)?shù)?！舅惴鞒獭?、數(shù)據(jù)初始化； 2、遞歸填數(shù)：判斷第i個(gè)數(shù)填入是否合法；A、如果合法：填數(shù)；判斷是否到達(dá)目標(biāo)（20個(gè)已填完）：是，打印結(jié)果；不是，遞歸填下一個(gè)；B、如果不合法：選擇下一種可能；【參考程序】#include#include#include#includeusing namespace std;bool b21=0;int total=0,a21=0;int search(int); /回溯過(guò)程in

4、t print(); /輸出方案bool pd(int,int); /判斷素?cái)?shù) int main() search(1); couttotalendl; /輸出總方案數(shù)int search(int t) int i; for (i=1;i=20;i+) /有20個(gè)數(shù)可選 if (pd(at-1,i)&(!bi) /判斷與前一個(gè)數(shù)是否構(gòu)成素?cái)?shù)及該數(shù)是否可用 at=i; bi=1; if (t=20) if (pd(a20,a1) print(); else search(t+1); bi=0; int print() total+; couttotal; for (int j=1;j=20;j+

5、) coutaj ; coutendl; bool pd(int x,int y) int k=2,i=x+y; while (ksqrt(i) return 1; else return 0;【例2】設(shè)有n個(gè)整數(shù)的集合1,2,n，從中取出任意r個(gè)數(shù)進(jìn)行排列（rn），試列出所有的排列。#include#include#includeusing namespace std;int num=0,a10001=0,n,r;bool b10001=0;int search(int); /回溯過(guò)程int print(); /輸出方案int main() coutnr; search(1); coutnu

6、mber=numendl; /輸出方案總數(shù)int search(int k) int i; for (i=1;i=n;i+) if (!bi) /判斷i是否可用 ak=i; /保存結(jié)果 bi=1; if (k=r) print(); else search(k+1); bi=0; int print() num+; for (int i=1;i=r;i+) coutsetw(3)ai; coutendl; 【例3】任何一個(gè)大于1的自然數(shù)n，總可以拆分成若干個(gè)小于n的自然數(shù)之和。當(dāng)n=7共14種拆分方法：7=1+1+1+1+1+1+17=1+1+1+1+1+27=1+1+1+1+37=1+1+1

7、+2+27=1+1+1+47=1+1+2+37=1+1+57=1+2+2+27=1+2+47=1+3+37=1+67=2+2+37=2+57=3+4total=14【參考程序】#include#include#includeusing namespace std;int a10001=1,n,total;int search(int,int);int print(int);int main() cinn; search(n,1); /將要拆分的數(shù)n傳遞給s couttotal=totalendl; /輸出拆分的方案數(shù)int search(int s,int t) int i; for (i=a

8、t-1;i=s;i+) if (i0時(shí)，繼續(xù)遞歸 s+=i; /回溯：加上拆分的數(shù)，以便產(chǎn)分所有可能的拆分 int print(int t) coutn=; for (int i=1;i=t-1;i+) /輸出一種拆分方案 coutai+; coutatendl; total+; /方案數(shù)累加1【例4】八皇后問(wèn)題：要在國(guó)際象棋棋盤(pán)中放八個(gè)皇后，使任意兩個(gè)皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一對(duì)角線的任意棋子。）放置第個(gè)(行)皇后的算法為： int search(i)； int j;for (第i個(gè)皇后的位置j=1;j=8;j+ ) /在本行的8列中去試 if (本行本列允許放置

9、皇后) 放置第i個(gè)皇后； 對(duì)放置皇后的位置進(jìn)行標(biāo)記；if (i=8) 輸出 /已經(jīng)放完個(gè)皇后 else search(i+1)； /放置第i+1個(gè)皇后對(duì)放置皇后的位置釋放標(biāo)記，嘗試下一個(gè)位置是否可行； 【算法分析】 顯然問(wèn)題的關(guān)鍵在于如何判定某個(gè)皇后所在的行、列、斜線上是否有別的皇后；可以從矩陣的特點(diǎn)上找到規(guī)律，如果在同一行，則行號(hào)相同；如果在同一列上，則列號(hào)相同；如果同在斜線上的行列值之和相同；如果同在斜線上的行列值之差相同；從下圖可驗(yàn)證： 考慮每行有且僅有一個(gè)皇后，設(shè)一維數(shù)組1.8表示皇后的放置：第行皇后放在第列，用ij來(lái)表示，即下標(biāo)是行數(shù)，內(nèi)容是列數(shù)。例如：A3=5就表示第3個(gè)皇后在第3

10、行第5列上。 判斷皇后是否安全，即檢查同一列、同一對(duì)角線是否已有皇后，建立標(biāo)志數(shù)組1.8控制同一列只能有一個(gè)皇后，若兩皇后在同一對(duì)角線上，則其行列坐標(biāo)之和或行列坐標(biāo)之差相等，故亦可建立標(biāo)志數(shù)組1.16、-7.7控制同一對(duì)角線上只能有一個(gè)皇后。 如果斜線不分方向，則同一斜線上兩皇后的行號(hào)之差的絕對(duì)值與列號(hào)之差的絕對(duì)值相同。在這種方式下，要表示兩個(gè)皇后I和J不在同一列或斜線上的條件可以描述為：AIAJ AND ABS(I-J)ABS(AI-AJ)I和J分別表示兩個(gè)皇后的行號(hào)【參考程序】#include#include#include#includeusing namespace std;bool

11、d16=0,b9=0,c16=0;int sum=0,a9;int search(int);int print();int main() search(1); /從第1個(gè)皇后開(kāi)始放置int search(int i) int j; for (j=1;j=8;j+) /每個(gè)皇后都有8位置(列)可以試放if (!bj)&(!ci+j)&(!di-j+7) /尋找放置皇后的位置 /由于C+不能操作負(fù)數(shù)組，因此考慮加7 /放置皇后,建立相應(yīng)標(biāo)志值 ai=j; /擺放皇后 bj=1; /宣布占領(lǐng)第j列 ci+j=1; /占領(lǐng)兩個(gè)對(duì)角線 di-j+7=1; if (i=8) print(); /個(gè)皇后都放

12、置好,輸出 else search(i+1); /繼續(xù)遞歸放置下一個(gè)皇后 bj=0; /遞歸返回即為回溯一步,當(dāng)前皇后退出 ci+j=0; di-j+7=0; int print() int i; sum+; /方案數(shù)累加1 coutsum=sumendl; for (i=1;i=8;i+) /輸出一種方案 coutsetw(4)ai; cout2,1-3,3-1,4-3,5-2,7-4,8【算法分析】 如圖4（b）,馬最多有四個(gè)方向，若原來(lái)的橫坐標(biāo)為j、縱坐標(biāo)為i,則四個(gè)方向的移動(dòng)可表示為：1: （i,j）（i+2,j+1）； (i3,j8)2: （i,j）（i+1,j+2）； (i4,j0

13、,j1,j8) 搜索策略： S1:=(0,0); S2:從1出發(fā)，按移動(dòng)規(guī)則依次選定某個(gè)方向，如果達(dá)到的是（4,8）則轉(zhuǎn)向S3,否則繼續(xù)搜索下一個(gè)到達(dá)的頂點(diǎn)； S3:打印路徑?！緟⒖汲绦颉?include#include#includeusing namespace std;int a1003,t=0; /路徑總數(shù)和路徑int x4=2,1,-1,-2, /四種移動(dòng)規(guī)則 y4=1,2,2,1;int search(int); /搜索 int print(int); /打印int main() /主程序 a11=0;a12=0; /從坐標(biāo)(0,0)開(kāi)始往右跳第二步 search(2); ; in

14、t search(int i) for (int j=0;j=0&ai-11+xj=0&ai-12+yj=8) /判斷馬不越界 ai1=ai-11+xj; /保存當(dāng)前馬的位置 ai2=ai-12+yj; if (ai1=4&ai2=8) print(i); else search(i+1); /搜索下一步 int print(int ii) t+; coutt: ; for (int i=1;i=ii-1;i+) coutai1,ai2; cout4,8endl; 【例6】設(shè)有A，B，C，D，E五人從事J1，J2，J3，J4，J5五項(xiàng)工作，每人只能從事一項(xiàng)，他們的效益如下。 每人選擇五項(xiàng)工作中

15、的一項(xiàng)，在各種選擇的組合中，找到效益最高的的一種組合輸出?！舅惴ǚ治觥?用數(shù)組儲(chǔ)存工作選擇的方案；數(shù)組存放最優(yōu)的工作選擇方案；數(shù)組用于表示某項(xiàng)工作有沒(méi)有被選擇了。 (1)選擇(i)=0的第i項(xiàng)工作； (2)判斷效益是否高于max已記錄的效益，若高于則更新數(shù)組及max的值。 搜索策略: 回溯法（深度優(yōu)先搜索dfs）?！緟⒖汲绦颉?include#include#include#includeusing namespace std;int data66=0,0,0,0,0,0,0,13,11,10,4,7,0,13,10,10,8,5,0,5,9,7,7,4,0,15,12,10,11,5,0,1

16、0,11,8,8,4;int max1=0,g10,f10;bool p6=0;int go(int step,int t) / step是第幾個(gè)人，t是之前已得的效益 for (int i=1;i=5;i+) if (!pi) /判斷第i項(xiàng)工作沒(méi)人選擇 fstep=i; /第step個(gè)人，就選第i項(xiàng)工作 pi=1; /標(biāo)記第i項(xiàng)工作被人安排了 t+=datastepi; /計(jì)算效益值 if (stepmax1) /保存最佳效益值 max1=t; for (int j=1;j=5;j+) gj=fj; /保存最優(yōu)效益下的工作選擇方案 t-=datastepi; /回溯 pi=0; int ma

17、in() go(1,0); /從第1個(gè)人，總效益為0開(kāi)始 for (int i=1;i=5;i+) coutchar(64+i):Jgisetw(3); /輸出各項(xiàng)工作安排情況 coutendl; coutsupply:max1endl; /輸出最佳效益值【例7】選書(shū) 學(xué)校放寒假時(shí)，信息學(xué)競(jìng)賽輔導(dǎo)老師有A，B，C，D，E五本書(shū)，要分給參加培訓(xùn)的張、王、劉、孫、李五位同學(xué)，每人只能選一本書(shū)。老師事先讓每個(gè)人將自己喜歡的書(shū)填寫(xiě)在如下的表格中。然后根據(jù)他們填寫(xiě)的表來(lái)分配書(shū)本，希望設(shè)計(jì)一個(gè)程序幫助老師求出所有可能的分配方案，使每個(gè)學(xué)生都滿意?！舅惴ǚ治觥?可用窮舉法，先不考慮“每人都滿意” 這一條件，

18、這樣只?！懊咳诉x一本且只能選一本”這一條件。在這個(gè)條件下，可行解就是五本書(shū)的所有全排列，一共有5！=120種。然后在120種可行解中一一刪去不符合“每人都滿意”的解，留下的就是本題的解答。 為了編程方便，設(shè)1，2，3，4，5分別表示這五本書(shū)。這五個(gè)數(shù)的一種全排列就是五本書(shū)的一種分發(fā)。例如54321就表示第5本書(shū)（即E）分給張，第4本書(shū)（即D）分給王，第1本書(shū)（即A）分給李?！跋矏?ài)書(shū)表”可以用二維數(shù)組來(lái)表示，1表示喜愛(ài)，0表示不喜愛(ài)。算法設(shè)計(jì)：S1：產(chǎn)生5個(gè)數(shù)字的一個(gè)全排列； S2：檢查是否符合“喜愛(ài)書(shū)表”的條件，如果符合就打印出來(lái)； S3：檢查是否所有的排列都產(chǎn)生了，如果沒(méi)有產(chǎn)生完，則返回S1

19、； S4：結(jié)束。int Search(i) for (j=1;j=5;j+) if (第i個(gè)同學(xué)分給第j本書(shū)符合條件) 記錄第i個(gè)數(shù) if (i=5) 打印一個(gè)解; else Search(i+1); 刪去第i 個(gè)數(shù) 上述算法有可以改進(jìn)的地方。比如產(chǎn)生了一個(gè)全排列12345，從表中可以看出，選第一本書(shū)即給張同學(xué)的書(shū)，1是不可能的，因?yàn)閺堉幌矚g第3、4本書(shū)。這就是說(shuō)，1一類的分法都不符合條件。由此想到，如果選定第一本書(shū)后，就立即檢查一下是否符合條件，發(fā)現(xiàn)1是不符合的，后面的四個(gè)數(shù)字就不必選了，這樣就減少了運(yùn)算量。換句話說(shuō)，第一個(gè)數(shù)字只在3、4中選擇，這樣就可以減少3/5的運(yùn)算量。同理，選定了第一

20、個(gè)數(shù)字后，也不應(yīng)該把其他4個(gè)數(shù)字一次選定，而是選擇了第二個(gè)數(shù)字后，就立即檢查是否符合條件。例如，第一個(gè)數(shù)選3，第二個(gè)數(shù)選4后，立即檢查，發(fā)現(xiàn)不符合條件，就應(yīng)另選第二個(gè)數(shù)。這樣就把34一類的分法在產(chǎn)生前就刪去了。又減少了一部分運(yùn)算量。 綜上所述，改進(jìn)后的算法應(yīng)該是：在產(chǎn)生排列時(shí)，每增加一個(gè)數(shù)，就檢查該數(shù)是否符合條件，不符合，就立刻換一個(gè)，符合條件后，再產(chǎn)生下一個(gè)數(shù)。因?yàn)閺牡贗本書(shū)到第I+1本書(shū)的尋找過(guò)程是相同的，所以可以用回溯算法。算法設(shè)計(jì)如下：【參考程序】#include#include#includeusing namespace std;int book6,c;bool flag6,lik

21、e66=0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1, 0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,0,0,1;int search(int);int print();int main() for (int i=1;i=5;i+) flagi=1; search(1); /從第1個(gè)開(kāi)始選書(shū)，遞歸。 int search(int i) /遞歸函數(shù) for (int j=1;j=5; j+) /每個(gè)人都有5本書(shū)可選 if (flagj&likeij) /滿足分書(shū)的條件 flagj=0; /把被選中的書(shū)放入集合flag中，避免重復(fù)被選 booki=j; /保

22、存第i個(gè)人選中的第j本書(shū) if (i=5) print(); /i=5時(shí)，所有的人都分到書(shū)，輸出結(jié)果 else search(i+1); /i5時(shí)，繼續(xù)遞歸分書(shū) flagj=1; /回溯：把選中的書(shū)放回，產(chǎn)生其他分書(shū)的方案 booki=0; int print() c+; /方案數(shù)累加1 cout answer c :n; for (int i=1;i=5;i+) cout i : char(64+booki) endl; /輸出分書(shū)的方案輸出結(jié)果：answer 11: C2: A3: B4: D5: E【例8】跳馬問(wèn)題。在5*5格的棋盤(pán)上，有一只中國(guó)象棋的馬，從（1,1）點(diǎn)出發(fā)，按日字跳馬，

23、它可以朝8個(gè)方向跳，但不允許出界或跳到已跳過(guò)的格子上，要求在跳遍整個(gè)棋盤(pán)。輸出前5個(gè)方案及總方案數(shù)。輸出格式示例： 116 21 10 2520 11 24 15 2217 2 19 6 912 7 423 14 318 13 8 5#include#include#include#includeusing namespace std;int u8=1,2,2,1,-1,-2,-2,-1, /8個(gè)方向上的x,y增量 v8=-2,-1,1,2,2,1,-1,-2;int a100100=0,num=0; /記每一步走在棋盤(pán)的哪一格和棋盤(pán)的 /每一格有沒(méi)有被走過(guò)bool b100100=0;int

24、 search(int,int,int); /以每一格為階段，在每一階段中試遍8個(gè)方向int print(); /打印方案int main() a11=1;b11=1; /從(1,1)第一步開(kāi)始走 search(1,1,2); /從(1,1)開(kāi)始搜第2步該怎樣走 coutnum25) print();return 0; /達(dá)到最大規(guī)模打印、統(tǒng)計(jì)方案 for (k=0;k=7;k+) /試遍8個(gè)方向 x=i+uk;y=j+vk; /走此方向，得到的新坐標(biāo) if (x=1&y=1&(!bxy) /如果新坐標(biāo)在棋盤(pán)上，并且這一格可以走 bxy=1; axy=n; search(x,y,n+1); /

25、從(x,y)去搜下一步該如何走 bxy=0; axy=0; int print() num+; /統(tǒng)計(jì)總方案 if (num=5) /打印出前5種方案 for (int k=1;k=5;k+) /打印本次方案 for (int kk=1;kk=5;kk+) coutsetw(5)akkk; coutendl; 【例9】數(shù)的劃分(NOIP2001)【問(wèn)題描述】 將整數(shù)n分成k份，且每份不能為空，任意兩種分法不能相同(不考慮順序)。例如:n=7,k=3,下面三種分法被認(rèn)為是相同的。 1，1，5； 1，5，1； 5，1，1；問(wèn)有多少種不同的分法?！据斎敫袷健?n,k (6n200，2k6)【輸出格式

26、】 一個(gè)整數(shù)，即不同的分法?！据斎霕永?7 3【輸出樣例】 44種分法為：1,1,5；1,2,4；1,3,3; 2,2,3 說(shuō)明部分不必輸出【算法分析】方法1、回溯法，超時(shí)，參考程序如下。#include#include#includeusing namespace std;int n,i,j,k,rest,sum,total;int s7;int main() cout n k; total = 0; s1 = 0; i = 1; while (i) si+; if (si n) i-; else if (i = k) sum = 0; for (j = 1; j = k; j+) sum

27、 += sj; if (n = sum) total+; else rest -= si; i+; si = si-1 - 1; cout total; return 0;方法2、遞歸，參考程序如下。#include#include#includeusing namespace std;int n,k;int f(int a,int b,int c) int g = 0,i; if (b = 1) g = 1; else for (i = c; i = a/b; i+) g += f(a-i,b-1,i); return g;int main() cout n k; cout f(n,k,1)

28、; return 0;方法3、用動(dòng)態(tài)循環(huán)窮舉所有不同的分解，要注意剪枝，參考程序如下。#include#include#includeusing namespace std;int n,k,total;int min(int x,int y) if (x = rest/dep; i-) select(dep-1,rest-i,i);int main() cout n k; total = 0; select(k,n,n); cout total; return 0;方法4、遞推法首先將正整數(shù)n分解成k個(gè)正整數(shù)之和的不同分解方案總數(shù)等于將正整數(shù)n-k分解成任意個(gè)不大于k的正整數(shù)之和的不同分解方案

29、總數(shù)(可用ferror圖證明之),后者的遞推公式不難得到,參考程序如下。#include#include#include#includeusing namespace std;int i,j,k,n,x;int p2017; int main() cin n k; memset(p,0,sizeof(p); p00 = 1; for (i = 1; i = n; i+) pi1 = 1; for (i = 1; i = n - k; i+) for (j = 2; j = min(i,k); j+) for (x = 1; x = min(i,j); x+) pij += pi-xmin(i-

30、x,x); cout pn-kk; return 0;【課堂練習(xí)】 1、輸出自然數(shù)1到n所有不重復(fù)的排列，即n的全排列?！緟⒖歼^(guò)程】 int Search(int i) Int j; for (j=1;j=n;j+) if (bj) ai=j; bj=false; if (In) Search(i+1); else print(); bj=true; 2、找出n個(gè)自然數(shù)(1,2,3,n)中r個(gè)數(shù)的組合。例如，當(dāng)n=,r=3時(shí)，所有組合為：1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5total=10 /組合的總數(shù)【分析】：設(shè)在b1,b2,b

31、i-1中已固定地取了某一組值且bi-1=k的前提下，過(guò)程Search(i,k)能夠列出所有可能的組合。由于此時(shí)bi只能取k+1至n-r+i，對(duì)j=k+1,k+2,n-r+i，使bi:=j，再調(diào)用過(guò)程Search(i+1,j)，形成遞歸調(diào)用。直至i的值大于r時(shí)，就可以在b中構(gòu)成一種組合并輸出。3、輸出字母a、b、c、d，4個(gè)元素全排列的每一種排列。4、顯示從前m個(gè)大寫(xiě)英文字母中取n個(gè)不同字母的所有種排列。5、有A、B、C、D、E五本書(shū)，要分給張、王、劉、趙、錢(qián)五位同學(xué)，每人只能選一本，事先讓每人把自已喜愛(ài)的書(shū)填于下表，編程找出讓每人都滿意的所有方案?！敬鸢浮克姆N方案張 王 劉 趙 錢(qián) C A B

32、 D E D A C B E D B C A E D E C A B6、有紅球4個(gè)，白球3個(gè)，黃球3個(gè)，將它們排成一排共有多少種排法？【分析】：可以用回溯法來(lái)生成所有的排法。用數(shù)組b1.3表示尚未排列的這3種顏色球的個(gè)數(shù)。設(shè)共有I-1個(gè)球已參加排列，用子程序Search(i)生成由第I個(gè)位置開(kāi)始的以后n-I+1位置上的各種排列。對(duì)于第I個(gè)位置，我們對(duì)3種顏色的球逐一試探，看每種顏色是否還有未加入排序的球。若有，則選取一個(gè)放在第I個(gè)位置上，且將這種球所剩的個(gè)數(shù)減1，然后調(diào)用Search(I+1),直至形成一種排列后出。對(duì)第I個(gè)位置上的所有顏色全部試探完后，則回溯至前一位置?！旧蠙C(jī)練習(xí)】1、全排列

33、問(wèn)題(Form.cpp)【問(wèn)題描述】 輸出自然數(shù)1到n所有不重復(fù)的排列，即n的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字?！据斎敫袷健?n(1n9)【輸出格式】 由1n組成的所有不重復(fù)的數(shù)字序列，每行一個(gè)序列。【輸入樣例】Form.in 3【輸出樣例】Form.out1 2 31 3 22 1 32 3 13 1 23 2 12、組合的輸出(Compages.cpp)【問(wèn)題描述】 排列與組合是常用的數(shù)學(xué)方法，其中組合就是從n個(gè)元素中抽出r個(gè)元素(不分順序且rn)，我們可以簡(jiǎn)單地將n個(gè)元素理解為自然數(shù)1，2，n，從中任取r個(gè)數(shù)。 現(xiàn)要求你用遞歸的方法輸出所有組合。 例如n5，r3，所

34、有組合為： l 2 3 l 2 4 1 2 5 l 3 4 l 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5【輸入】 一行兩個(gè)自然數(shù)n、r(1n21，1rn)?！据敵觥?所有的組合，每一個(gè)組合占一行且其中的元素按由小到大的順序排列，每個(gè)元素占三個(gè)字符的位置，所有的組合也按字典順序。【樣例】compages.in compages.out5 3 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 53、N皇后問(wèn)題(Queen.cpp)【問(wèn)題描述】在N*N的棋盤(pán)上放置N個(gè)皇后（n=10）而彼此不受攻擊（即在棋盤(pán)的

35、任一行，任一列和任一對(duì)角線上不能放置2個(gè)皇后），編程求解所有的擺放方法。八皇后的兩組解【輸入格式】 輸入：n【輸出格式】每行輸出一種方案，每種方案順序輸出皇后所在的列號(hào)，各個(gè)數(shù)之間有空格隔開(kāi)。若無(wú)方案，則輸出no solute!【輸入樣例】Queen.in 4【輸出樣例】Queen.out2 4 1 33 1 4 24、有重復(fù)元素的排列問(wèn)題【問(wèn)題描述】 設(shè)R= r1, r2 , , rn是要進(jìn)行排列的n個(gè)元素。其中元素r1, r2 , , rn可能相同。試設(shè)計(jì)一個(gè)算法，列出R的所有不同排列?！揪幊倘蝿?wù)】 給定n 以及待排列的n 個(gè)元素。計(jì)算出這n 個(gè)元素的所有不同排列?！据斎敫袷健?由perm

36、.in輸入數(shù)據(jù)。文件的第1 行是元素個(gè)數(shù)n，1n500。接下來(lái)的1 行是待排列的n個(gè)元素?！据敵龈袷健?計(jì)算出的n個(gè)元素的所有不同排列輸出到文件perm.out中。文件最后1行中的數(shù)是排列總數(shù)。【輸入樣例】4aacc【輸出樣例】多解aaccacacaccacaaccacaccaa65、子集和問(wèn)題【問(wèn)題描述】 子集和問(wèn)題的一個(gè)實(shí)例為S,t。其中，S= x1， x2， xn是一個(gè)正整數(shù)的集合，c是一個(gè)正整數(shù)。子集和問(wèn)題判定是否存在S的一個(gè)子集S1，使得子集S1和等于c?！揪幊倘蝿?wù)】 對(duì)于給定的正整數(shù)的集合S= x1， x2， xn和正整數(shù)c，編程計(jì)算S 的一個(gè)子集S1，使得子集S1和等于c?！据斎?/p>

37、格式】 由文件subsum.in提供輸入數(shù)據(jù)。文件第1行有2個(gè)正整數(shù)n和c，n表示S的個(gè)數(shù)，c是子集和的目標(biāo)值。接下來(lái)的1 行中，有n個(gè)正整數(shù)，表示集合S中的元素?！据敵龈袷健?程序運(yùn)行結(jié)束時(shí)，將子集和問(wèn)題的解輸出到文件subsum.out中。當(dāng)問(wèn)題無(wú)解時(shí)，輸出“No solution!”。【輸入樣例】5 102 2 6 5 4【輸出樣例】2 2 66、工作分配問(wèn)題【問(wèn)題描述】 設(shè)有n件工作分配給n個(gè)人。將工作i分配給第j個(gè)人所需的費(fèi)用為cij。試設(shè)計(jì)一個(gè)算法，為每一個(gè)人都分配一件不同的工作，并使總費(fèi)用達(dá)到最小?！揪幊倘蝿?wù)】 設(shè)計(jì)一個(gè)算法，對(duì)于給定的工作費(fèi)用，計(jì)算最佳工作分配方案，使總費(fèi)用達(dá)到

38、最小?！据斎敫袷健?由文件job.in給出輸入數(shù)據(jù)。第一行有1個(gè)正整數(shù)n (1n20)。接下來(lái)的n行，每行n個(gè)數(shù)，第i行表示第i個(gè)人各項(xiàng)工作費(fèi)用?！据敵龈袷健?將計(jì)算出的最小總費(fèi)用輸出到文件job.out?！据斎霕永?4 2 52 3 63 4 5【輸出樣例】97、裝載問(wèn)題【問(wèn)題描述】 有一批共n個(gè)集裝箱要裝上艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優(yōu)裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。【輸入格式】 由文件load.in給出輸入數(shù)據(jù)。第一行有2個(gè)正整數(shù)n和c。n是集裝箱數(shù)，c是輪船的載重量。接下來(lái)的1行中有n個(gè)正整數(shù)，表示集裝

39、箱的重量?！据敵龈袷健?將計(jì)算出的最大裝載重量輸出到文件load.out?！据斎霕永? 107 2 6 5 4【輸出樣例】 108、字符序列(characts)【問(wèn)題描述】從三個(gè)元素的集合A，B，C中選取元素生成一個(gè)N個(gè)字符組成的序列，使得沒(méi)有兩個(gè)相鄰字的子序列（子序列長(zhǎng)度=2）相同。例：N = 5時(shí)ABCBA是合格的，而序列ABCBC與ABABC是不合格的，因?yàn)槠渲凶有蛄蠦C，AB是相同的。對(duì)于由鍵盤(pán)輸入的N(1=N=12)，求出滿足條件的N個(gè)字符的所有序列和其總數(shù)?！据斎霕永?【輸出樣例】729、試卷批分(grade)【問(wèn)題描述】某學(xué)校進(jìn)行了一次英語(yǔ)考試，共有10道是非題，每題為10分，解答用1表示“是”，用0表示“非”的方式。但老師批完卷后，發(fā)現(xiàn)漏批了一張?jiān)嚲?，而且?biāo)準(zhǔn)答案也丟失了，手頭只剩下了3張標(biāo)有分?jǐn)?shù)的試卷。試卷一： 0 0 1 0 1 0 0 1 0 0 得分：70試卷二： 0 1 1 1 0 1 0 1 1 1 得分：50試卷三： 0 1 1 1 0 0 0 1 0 1 得分：30待批試卷：