信息學(xué)競(jìng)賽3-4回溯法

1、回溯法Page 2用回溯法產(chǎn)生所有3位數(shù) n 從100到999n 設(shè)m為當(dāng)前指向的位置n 當(dāng)m1，回溯到上一個(gè)位置n即：m-;n每次都要am+；n 退出條件a1=10A1A2A3100101102103Page 3八皇后問(wèn)題n 十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。 n 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)有人用圖論的方法解出92種結(jié)果。n 計(jì)算機(jī)發(fā)明后，有多種方法可以解決此問(wèn)題。Page 4解決方案n 簡(jiǎn)化為四皇后n 確

2、定解的表示方法n右圖為2413n 確定解的特征2413Page 5四皇后問(wèn)題n 用數(shù)組表示解n 2413為A1=2A2=4A3=1A4=3n 不攻擊的條件1. AiAj，不在同一列2. Abs(Ai-Aj) i-k，不在同一斜線2413Page 61Page 71XXPage 81XX3Page 91XX3XXXXPage 101XX4Page 111XX4XXXPage 121XX4X2XXPage 131XX4X2XXXXXXPage 142Page 152XXXPage 162XXX4Page 172XXX41XXXPage 182XXX41XXX3Page 193Page 203XXX

3、Page 2131XXXPage 2231XXXXXXPage 2331XXXXXX4Page 2431XXXXXX42Page 254Page 264XXPage 2742XXPage 2842XXXXXXPage 2941XXPage 3041XXXX3XPage 3141XXXX3XXXXXPage 32回溯法的幾個(gè)關(guān)鍵條件n 初始條件m=1;am = 1;n 循環(huán)條件a1 N + 1n 繼續(xù)條件m 1/已經(jīng)測(cè)試完這一行的所有列/到達(dá)最后一列，且不是第1行n 調(diào)整am+; /右移1列Page 33回溯法基本流程初始條件While(循環(huán)條件) if(繼續(xù)條件) 繼續(xù) else while

4、(回溯條件) 回溯; 調(diào)整; Page 34回溯法演示n 用回溯法產(chǎn)生所有3位數(shù)n 初始條件m=1;am = 1;n 循環(huán)條件a1 10n 繼續(xù)條件m 1/已經(jīng)測(cè)試完這一行的所有數(shù)字/到達(dá)最后一列，且不是第1行n 調(diào)整am+; /右移1列Page 35用回溯法解決問(wèn)題n 八皇后n 橋本方程式Page 36橋本分?jǐn)?shù)式nPage 37八皇后問(wèn)題n 十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。 n 高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來(lái)

5、有人用圖論的方法解出92種結(jié)果。Page 38解決方案n 簡(jiǎn)化為四皇后n 確定解的表示方法n右圖為2413n 確定解的特征2413Page 39四皇后問(wèn)題n 用數(shù)組表示解n 2413為A1=2A2=4A3=1A4=3n 不攻擊的條件1. AiAj，不在同一列2. Abs(Ai-Aj) i-k，不在同一斜線2413Page 40神奇古尺有一個(gè)古尺，總長(zhǎng)36寸因年代久遠(yuǎn)，中間標(biāo)注的刻度只剩下8個(gè)但是這個(gè)尺子還是可以一次性度量136之間的任意長(zhǎng)度請(qǐng)確定這8個(gè)刻度的位置 Page 41神奇古尺可能刻度為1,3,6,13,20,27,31,35,可能刻度為1,5,9,16,23,30,33,35,Pag

6、e 42四大湖泊我國(guó)有4大淡水湖。 甲說(shuō)：洞庭湖最大，洪澤最小。鄱陽(yáng)湖第三。 乙說(shuō)：洪澤湖最大，洞庭湖最小，鄱陽(yáng)湖第二。太湖第三。 丙說(shuō)：洪澤湖最小，洞庭湖第三。 丁說(shuō)：鄱陽(yáng)湖最大，太湖最小，洪澤湖第二，洞庭湖第三。 4個(gè)人每人僅答對(duì)了一個(gè)，請(qǐng)你編程給出4個(gè)湖從大到小的順序Page 43四大湖泊甲：a=1,b=4,c=3乙：b=1,a=4,c=2,d=3丙：b=4,a=3?。篶=1,d=4,b=2,a=3洞庭湖洞庭湖 洪澤湖洪澤湖 鄱陽(yáng)湖鄱陽(yáng)湖太湖太湖abcdPage 44四大湖泊隱藏條件a b c d，并且a+b+c+d=10結(jié)果a=2,b=4,c=1,d=3洞庭湖洞庭湖 洪澤湖洪澤湖 鄱陽(yáng)

7、湖鄱陽(yáng)湖太湖太湖abcdPage 45裝錯(cuò)信封n 某人給5個(gè)朋友寫(xiě)信，同時(shí)寫(xiě)了5個(gè)朋友的信封，問(wèn)每個(gè)信封和信都不相符的情況有多少？Page 46別出心裁的情侶拍照n 8對(duì)情侶，參加聚會(huì)后拍照，主持人要求如下：1. 每對(duì)情侶不得相鄰2. 每對(duì)情侶都是男左女右排隊(duì)3. 編號(hào)為1的情侶之間有1個(gè)人，編號(hào)為2的情侶之間有2個(gè)人，依次類推，編號(hào)為8的情侶之間有8個(gè)人Page 47Page 48Page 49Page 50Page 51Page 52Page 53Page 54Page 55馬攔過(guò)河卒n 棋盤上A點(diǎn)有一個(gè)過(guò)河卒,需要走到目標(biāo)B點(diǎn).卒行走的規(guī)則:可以向下、或者向右。同時(shí)在棋盤上C點(diǎn)有一個(gè)對(duì)方

8、的馬，該馬所在的點(diǎn)和所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。因此稱之為“馬攔過(guò)河卒”。 n 棋盤用坐標(biāo)表示，A點(diǎn)（0，0）、B點(diǎn)（m,n)(n,m =15），同樣馬的位置坐標(biāo)是需要給出的。現(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定不動(dòng)的，并不是卒走一步馬走一步。 Page 56馬攔過(guò)河卒Page 57組合的輸出n 從n個(gè)元素中抽出r個(gè)元素（r=n）,可以簡(jiǎn)單地將n個(gè)元素理解為自然數(shù)1，2，n，從中任取r個(gè)數(shù)。 n 要求：不用遞歸的方法輸出所有組合。 n 例如n=5，r=3，所有組合為r1r2r3： n 1 2 3 , 1 2 4 , 1 2 5, 1 3 4

9、, 1 3 5, 1 4 5 , 2 3 4 ,2 3 5,2 4 5 ,3 4 5 Page 58走迷宮n 有一個(gè)m*n格的迷宮(表示有m行、n列)，其中有可走的也有不可走的，如果用1表示可以走，0表示不可走，文件讀入這m*n個(gè)數(shù)據(jù)和起始點(diǎn)、結(jié)束點(diǎn)（起始點(diǎn)和結(jié)束點(diǎn)都是用兩個(gè)數(shù)據(jù)來(lái)描述的，分別表示這個(gè)點(diǎn)的的行號(hào)和列號(hào)）。現(xiàn)在要你編程找出所有可行的道路總數(shù)，要求所走的路中沒(méi)有重復(fù)的點(diǎn)，走時(shí)只能是上下左右四個(gè)方向。如果一條路都不可行，則輸出相應(yīng)信息（用 -1表示無(wú)路）Page 59走迷宮n Inputn第一行是兩個(gè)數(shù) m、n（1 m,n 15），接下來(lái)是m行n列由10組成的數(shù)據(jù)，最后兩行是起始點(diǎn)和

10、結(jié)束點(diǎn)。n Outputn所有可行的路徑總數(shù)。如果沒(méi)有一條可行的路則輸出 -1.Page 60數(shù)字排列問(wèn)題n 列出所有從數(shù)字式1到數(shù)字n的連續(xù)自然數(shù)的排列,要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。Page 61郵票問(wèn)題n 設(shè)有已知面額的郵票m種,每種有n張。問(wèn)：用總數(shù)不超過(guò)n張的郵票進(jìn)行組合，能組合的郵票面額中可以連續(xù)出現(xiàn)面額數(shù)最多有多少？（1=m=100,1=n=100,1=郵票面額=255）Page 62郵票問(wèn)題n Inputn第一行：m和n的值，中間用一空格隔開(kāi)。 n第二行：a1.m(面額)，每個(gè)數(shù)中間用一空格隔開(kāi)。 n Outputn連續(xù)面額數(shù)的最大長(zhǎng)度。Page 63郵票問(wèn)題

11、n Sample Inputn3 4n1 2 4n Sample Outputn14n 輸出說(shuō)明： n假設(shè)組合結(jié)果有：1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 n則其連續(xù)面額數(shù)的最大長(zhǎng)度為14（即1-14一直連續(xù)且長(zhǎng)度最長(zhǎng)）.Page 64置棋問(wèn)題n 在mn的方格中任意指定x個(gè)格子構(gòu)成一個(gè)棋盤(如圖)，在任一個(gè)構(gòu)成的棋盤上放置k個(gè)棋子，要求任意兩個(gè)棋子不得位于同一行或同一列上，要求輸出滿足條件的所有方案。 （注意棋盤是稀疏的，即x(m*n)/2,1 m、n 10） Page 65置棋問(wèn)題n 編程要求： 1、對(duì)給定的一個(gè)棋盤，求出該棋盤可放置的最多的棋子數(shù)p。 2、記di為該棋盤上放置i個(gè)棋子時(shí)的方案總數(shù)（1=i=p），其中經(jīng)旋轉(zhuǎn)和鏡面反射而得到的方案記為不同的方案，對(duì)每一個(gè)i，求出相應(yīng)的di。 3、對(duì)每一個(gè)棋盤，輸出p和d1，d2，dp，只需輸出數(shù)字，不必輸出具體的棋盤方案。 Page 66置棋問(wèn)題n Inputn第一行是兩個(gè)數(shù)字，代表第一個(gè)棋盤的m和n，以下m行為一個(gè)僅由0、1組成的mn的矩陣，某一個(gè)位置值為1表示相應(yīng)的格子在這個(gè)棋盤上，為0表示相應(yīng)的格子不在棋盤上。n