網上找的一些算法窮舉法

1、窮舉法2011曹文信息學奧林匹克夏令營 江蘇省常州高級中學 吳濤（江蘇省信息學奧林匹克中級教練員）窮舉法概念窮舉的策略是直接基于計算機特點而使用的思維方法，在一時找不到解決問題的更好途徑（指從數學上找到求解公式或規(guī)則）時，可以根據問題中的部分條件（約束條件）將可能解的情況列舉出來，然后一一驗證是否符合整個問題的求解要求。例1：獲獎名次三位老師對參加信息學競賽的四名學生將獲得的名次預測如下：甲：學生c得第一名，學生d得第四名；乙：學生a得第一名，學生b得第三名；丙：學生d得第一名，學生b得第三名；競賽結果表明，每位老師都說對了一半，說錯了一半。試編寫程序排出學生的名次。例2：分魚a,b,c,d,

2、e五人合伙夜間捕魚，清晨時都疲倦不堪，各自在河邊的樹叢中找地方睡著了。a第一個醒來，他將魚平分成五份，把多余的一條扔回河中，拿著自己的一份回家了。b第二個醒來，也將魚平分成五份，扔掉多余的一條，拿走自己的一份。接著c、d、e依次醒來，也都這樣處理。問：五人至少捕到多少條魚？注：每人拿到的都是整條的魚例3：分西瓜小小詢問集市上賣西瓜的農民今天上午賣了幾個西瓜，這個農民回答說：我在第一個小時賣出了全部西瓜的1/2又1/2個；第二個小時賣出了剩余的1/3又1/3個；第三個小時賣出了剩余的1/4又1/4個；第四個小時賣出了剩余的1/5又1/5個.最后正好剩余11個西瓜。問：這個農民原來一共有多少個西瓜

3、？例4：百元買百雞百元買百雞問題（一只公雞5元，一只母雞3元，三只小雞1元）討論多種解法的優(yōu)劣性例5：數字分組19這9個數字平均分成三組，每組組成一個三位數，且使這三個三位數構成1：2：3的比例，試求所有滿足條件的三個三位數。例如：192，384，576這三個就滿足條件。例6：阿姆斯特朗數阿姆斯特朗數也叫水仙花數。153(153=1*1*1+3*3*3+5*5*5)是一個三位數的阿姆斯特朗數。如果要求37位的阿姆斯特朗數呢？例7：鋸木棍長短不一木棍共n根，現要求鋸成同樣長度的至少m根，你能求出鋸成的最長長度嗎？方法：最大公約數？窮舉？例8: 勾股數問題描述 設三個正整數a、b、c,滿足則稱a

4、b c 為一組勾股數。求所有C=N的勾股數（1000)問題分析算法設計參考程序勾股數參考程序var n,a,b,c:longint;function f(a,b:longint):longint;a2+b2完全平方數判斷 var x,y:longint; begin x:=a*a+b*b; y:=trunc(sqrt(y); if (y=n)and(y*y=x) then f:=y else f:=0 end;勾股數參考程序begin write(n=);readln(n); for a:=1 to n-2 do for b:=a+1 to n-1 do begin c:=f(a,b); if

5、 c0 then writeln(a, ,b, ,c); end; Readln;end.例9直尺刻度問題描述一長厘米的尺子，只允許在上面刻個刻度，就能用它直接量出厘米的長度。求這個刻度的位置。問題分析算法設計參考程序直尺刻度問題分析 (1) 從 129 厘米中選擇七個刻度的所有可能情況數是:C（29，7） = （29*28*27*26*25*24*23）/（1*2*3*4*5*6*7） = 1560780(2) 對于每一組刻度的選擇都需要判斷是否能將 129 厘米的各種刻度量出來, 例如選擇的刻度為: a1,a2,a3,a4,a5a,6,a7 那么能量出的刻度為： a1, 29-a1; 2

6、a2, a2-a1, 29-a2; 3 a3, a3-a1 ,a3-a2, 29-a3 ; 4 a4, a4-a1, a4-a2, a4-a3, 29-a4; 5 a5,a5-a1,a5-a2, a5-a3, a5-a4, 29-a5; 6 a6,a6-a1,a6-a2,a6-a3,a6-a4, a6-a5, 29-a6; 7 a7,a7-a1, a7-a2, a7-a2, a7-a3, a7-a4, a7-a5, a7-a6, 29-a7； 8 共可量出 2+3+4+5+6+7+8 種刻度, 即 35 種刻度 。事實上其中有許多刻度是重復的, 不可能復蓋 129。例如： 取 a1, a2,

7、a3, a4, a5, a6, a7為1, 3, 6, 10, 15, 21, 28能量出的刻度為：直尺刻度問題分析 1 , 28 3, 2, 26 6, 5, 3, 23 10, 9, 7, 4, 19 15, 14, 12, 9, 5, 14 21, 20, 18, 15, 11, 6, 8 28, 27, 25, 22, 18, 13, 7, 1 缺 16,17,24 ( 29 即尺子長度 ) 問題的解必須使所有的刻度是否都能量得。(3)顯然要使1,28 兩種刻度能量出來, 則在七個刻度就必須有 1 或 28; 這樣就可設a1=1 ( 或 a1=28 )。本題就變成了只要在 227 中選

8、取六個刻度問題了。其刻度選擇的數目為 C（26，6） = （26*25*24*23*22*21）/（1*2*3*4*5*6）=230230直尺刻度參考程序1直尺刻度問題const n=29;m=1;var a:array1.7 of byte; b:array1.n of 0.1; i,j:byte;begin a1:=m; for a2:=2 to n-7 do for a3:=a2+1 to n-6 do for a4:=a3+1 to n-5 do for a5:=a4+1 to n-4 do for a6:=a5+1 to n-3 do for a7:=a6+1 to n-2 do b

9、egin直尺刻度參考程序2 for i:=1 to n do bi:=0; bn:=1; for i:=1 to 7 do begin bai:=1;bn-ai:=1; for j:=i+1 to 7 do babs(aj-ai):=1; end; j:=0; for i:=1 to n do inc(j,bi); if j=n then begin for i:=1 to 7 do write(ai:4);writeln;end; end;forEnd.例10 郵票面值問題【問題描述】郵局發(fā)行一套票面有四種不同值的郵票，如果每封信所貼郵票張數不超過三枚，存在整數，使得用不超過三枚的郵票，可以

10、貼出連續(xù)的整數、，來，找出這四種面值數，使得值最大?！舅惴ǚ治觥?設四種郵票的面值分別為： A , B , C , D ，根據題意設： A B C x0 then begin 保存最大面值郵票 x0:=x; x1:=a ; x2:=b ; x3:=c ; x4:=d end end; writeln( x1：5, x2：5, x3：5, x4：10, R=, x0 );End. 例11：分棋子1【問題描述】今有甲、乙、丙三堆棋子，先將甲堆棋子分給另外兩堆，使另外兩堆棋子數各增加1倍，再把乙堆棋子照這樣分配一次，最后把丙堆棋子也這樣分配。結果甲堆棋子數是丙堆棋子數的4/5，乙堆棋子數是丙堆棋子數

11、的1又7/15。求三堆中原來的棋子各有多少個？【輸入】: 無【輸出】: 輸出到屏幕。三個整數，分別表示甲、乙、丙堆棋子原來有的數量。分棋子2var i,j,k,x,y,z:longint;begin for i:=1 to 1000 do for j:=1 to i do for k:=1 to i do begin x:=i;y:=j;z:=k; x:=x-y-z;y:=y*2;z:=z*2; y:=y-x-z;x:=x*2;z:=z*2; z:=z-x-y;x:=x*2;y:=y*2; if (5*x=4*z)and(15*y=22*z) then begin writeln(i, ,j,

12、 ,k);halt;end; end;end.例12：冪十全數1【問題描述】如果一個數包含了09這十個數字，就稱為十全數。給定N，找一個最小的正整數M，使NM(表示連續(xù)M個N連乘，如23=2*2*2)為十全數?！据斎搿? 一個整數，即N(0=N0 do begin ai:=x mod 10; x:=x div 10; inc(i); end; a0:=i-1;end;冪十全數3function check:boolean;檢查0-9是否都出現var s:set of 0.9; i,t:longint;begin s:=;t:=0;i:=1; while (t10)and(i=0）3. n根火柴

13、棍必須全部用上【輸入】共一行，又一個整數n（n0 do begin inc(ai,hcx mod 10); x:=x div 10; end; end; t:=0; for i:=0 to 1000 do for j:=0 to 1000 do if ai+aj+ai+j=n-4 then inc(t); writeln(t);end.例14：代數和問題描述自然數從左到右排列，在相鄰兩個數之間添加一個“”或“”，使所得式子的代數和等于自然數。= ,N=16例如n=5、k=3時，得到下列等式：任務：輸入n k,輸出所有符合要求的等式。問題分析算法設計參考程序代數和參考程序11到N的代數和cons

14、t maxn=16;type btype=array1.maxn-1 of 0.1;var n,k,i:longint; m:word; b:btype;procedure ntob(n1:longint;var b:btype);整數化為二進制數 var i:longint; begin fillchar(b,sizeof(b),0); i:=0; while (i0) do begin inc(i); bi:=n1 mod 2; n1:=n1 div 2; end;end;代數和參考程序2function sum(b:btype):longint;求代數和var i,s:longint;b

15、egin s:=1; for i:=n-1 downto 1 do if bi=1 then s:=s+(n-i+1) else s:=s-(n-i+1); sum:=send;代數和參考程序3代數和參考程序4procedure print(b:btype);輸出var i:longint;begin write(1); for i:=2 to n do if bn-i+1=1 then write(+,i) else write(-,i); writeln(=,k);end;begin write(n,k=);readln(n,k); fillchar(b,sizeof(b),0); m:=

16、1; for i:=1 to n-1 do m:=m*2; m:=m-1; if sum(b)=k then print(b); for i:=1 to m do begin ntob(i,b); if sum(b)=k then print(b); end; readlnend.代數和參考程序5根據處理對象狀態(tài)的構造特點,以及不同狀態(tài)之間的生成關系,利用簡單操作,從當前狀態(tài)轉變?yōu)橄乱粋€新的狀態(tài),實現所有狀態(tài)的枚舉.例如例14代數和問題中N-1位二進制數b的狀態(tài)共有 2n-1個,兩個相鄰的狀態(tài)可以通過加1或減1的操作實現轉變，從最初的000逐個“加1”，依次轉變?yōu)?01、00.10、1110、

17、1111。下面的算法實現從當前的二進制數通過“加1”轉變?yōu)橄乱粋€二進制數。算法描述如下：構造法簡介Procedure next(var b:btype);Var i,c:longint;Begin c:=1;i:=0; Repeat inc(i);bi:=bi+c; if bi=2 then begin bi:=0; c:=1;end else c:=0; Until c=0;End;二進制數加1例15：構造法求N個元素全排列問題描述N盆不同顏色的鮮花擺成一排，求所有不同的擺法。問題分析算法設計參考程序構造法求全排列參考程序1const maxn=9; var x:array1.maxn of

18、 byte; n,i,k,l,r,temp:longint; b:boolean; begin write(n=);readln(n); for i:=1 to n do xi:=i; for i:=1 to n do write(xi); writeln; 第一個排列 b:=true; while b do begin k:=n-1; 找最靠右的數字變大的位置 while (k0) and (xkxk+1) do dec(k); if k=0 then b:=false終止 else begin i:=n; while xkxi do dec(i); temp:=xk;xk:=xi;xi:=

19、temp;構造法求全排列參考程序2 l:=k+1;r:=n; while lr do begin temp:=xl;xl:=xr;xr:=temp; inc(l);dec(r); end; for i:=1 to n do write(xi);writeln; end;else end;while readlnend.構造法求全排列參考程序3例16：求數組問題描述 給出任意一個自然數N (N100)，數組滿足下列條件： 1.數組元素由各不相同自然數組成； 2.數組元素的最后一個元素必為N； 3.每一個數組元素都不小于它前面一個元素的平方 (第一個元素除外)； 4.數組中包含的元素個數可不相同，

20、但至少要有一個元素。求符合上述條件的不同數組個數例如： N=1 有1個 數組 (1) N=5 有4個 數組 (5)、(1，5)、(1，2，5)、(2，5) 例17： NOIP2001P_1數的計算問題描述我們要求找出具有下列性質數的個數(包含輸入的自然數n):先輸入一個自然數n(n0 then cacu:=ax else begin s:=1; for i:=1 to x div 2 do s:=s+cacu(i); ax:=s; cacu:=s; end;end;begin readln(n); fillchar(a,sizeof(a),0); writeln(cacu(n); close(

21、input);close(output);end.例18：完全平方數拆分1【問題描述】一個整數，如果是另一個整數的平方，那么這個數就被稱為完全平方數，如4（=2*2）、36（=6*6）都是完全平方數?，F在給你一個數N，要把N拆成某些完全平方數的和，例如：23=1+4+9+9。我們希望N拆成的數越少越好，請你找到這種拆分。 【輸入】:一個整數N（n=1000），表示待拆分的數?！据敵觥? 輸出到屏幕。一個整數，表示N最少可以被拆成幾個完全平方數的和?！緲永浚狠斎耄?3輸出：4完全平方數拆分2var a:array0.40of longint; n,min:longint;procedure i

22、nitu; 預處理求出小于等于n的完全平方數var i:longint;begin i:=1; while i*i=n do begin ai:=i*i; inc(i); end; a0:=i-1;end;完全平方數拆分3procedure dg(rem,ceng,fen:longint); 遞歸求解最小份數var i,gs:longint;begin if fen1 then begin gs:=rem div aceng; for i:=0 to gs do dg(rem-i*aceng,ceng-1,fen+i); end;end;完全平方數拆分4begin readln(n); initu; 預處理求出小于等于n的完全平方數 min:=n; dg(n,a0,0);遞歸求解最小份數 writeln(min);end.例19： NOIP2001P_4裝箱問題問題描述有一個箱子容量為V（正整數，0V20000），同時有n個物品（0n30，每個物品有一個體積（正整數）。要求n個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。樣例輸入：24 一個整數，表示箱子容量6 一個整數，表示有n個物品8 接下來n行，分別表示這n 個物品的各自體積312797輸出：0一個整數，表示箱子剩余空間。例20： NOIP2004T_3合唱隊形【問題描述】N位同學