教科版選修1《窮舉法》省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)

窮舉法

第1頁(yè)一、引入實(shí)例一：輸入繩子長(zhǎng)度n，將該繩子分成三段，每段長(zhǎng)度為正整數(shù)，輸出由該三段繩子組成三角形個(gè)數(shù)。

窮舉法算法分析：沒(méi)有公式直接求出三角形個(gè)數(shù),所以程序只能采取窮舉法,一一驗(yàn)證范圍內(nèi)數(shù)是否能組成三角形,若是則累計(jì)。

第2頁(yè)一、引入s:=0;fora:=1ton-2doforb:=aton-2doforc:=bton-2doif(a+b>c)and(b+c>a)and(c+a>b)and(a+b+c=n)thens:=s+1;窮舉法第3頁(yè)s:=0;fora:=1ton-2doforb:=aton-2dobeginc:=n-a-b;if(a+b>c)and(b+c>a)and(c+a>b)and(c>=b)thens:=s+1;end;

一、引入第4頁(yè)二、窮舉法基本概念窮舉法窮舉方法是基于計(jì)算機(jī)特點(diǎn)而進(jìn)行解題思維方法。普通是在一時(shí)找不出處理問(wèn)題更加好路徑（即從數(shù)學(xué)上找不到求解公式或規(guī)則）時(shí)，能夠依據(jù)問(wèn)題中部分條件（約束條件）將全部可能解情況列舉出來(lái)，然后經(jīng)過(guò)一一驗(yàn)證是否符合整個(gè)問(wèn)題求解要求，而得到問(wèn)題解。這么處理問(wèn)題方法我們稱之為窮舉算法。窮舉算法特點(diǎn)是算法簡(jiǎn)單，但運(yùn)行時(shí)所花費(fèi)時(shí)間量大。所以，我們?cè)谟酶F舉方法處理問(wèn)題時(shí)，應(yīng)盡可能將顯著不符合條件情況排除在外，以盡快取得問(wèn)題解。

第5頁(yè)三、窮舉算法模式窮舉法1、問(wèn)題解可能搜索范圍：用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實(shí)現(xiàn)

2、寫(xiě)出符合問(wèn)題解條件。

3、能使程序優(yōu)化語(yǔ)句，方便縮小搜索范圍，降低程序運(yùn)行時(shí)間。

第6頁(yè)四、窮舉法應(yīng)用窮舉法窮舉法應(yīng)用很多，比如一些密碼破譯軟件通常就是用窮舉算法。如在QQ上，OicqPassOver這個(gè)工具窮舉你口令，它依據(jù)機(jī)器性能最高能夠每秒測(cè)試0個(gè)口令，假如口令簡(jiǎn)單，一分鐘內(nèi)，密碼就會(huì)遭到破譯。下面我們來(lái)以三個(gè)例子說(shuō)明窮舉法基本應(yīng)用。

第7頁(yè)實(shí)例二：有形如：ax3+bx2+cx+d=0

這么一個(gè)一元三次方程。給出該方程中各項(xiàng)系數(shù)(a，b，c，d

均為實(shí)數(shù))，并約定該方程存在三個(gè)不一樣實(shí)根(根范圍在-100至100之間)，且根與根之差絕對(duì)值>=1。要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并準(zhǔn)確到小數(shù)點(diǎn)后2位。提醒：記方程f(x)=0，若存在2個(gè)數(shù)x1和x2，且x1<x2，f(x1)*(x2)<0，則在(x1，x2)之間一定有一個(gè)根。樣例輸入：1

-5

-4

20輸出：-2.00

2.00

5.00四、窮舉法應(yīng)用第8頁(yè)本題是年全國(guó)信息學(xué)奧林匹克競(jìng)賽高中組復(fù)賽第一題，假如考慮解方程話則比較麻煩。我們能夠換個(gè)角度思索問(wèn)題，在-100到100之間找三個(gè)滿足方程實(shí)數(shù)，因?yàn)楦F舉時(shí)必須用整型變量，題目又要求保留兩位小數(shù)，我們只需將循環(huán)變量擴(kuò)大100倍即可順利窮舉，最終只要將所求結(jié)果再縮小100倍即可。四、窮舉法應(yīng)用第9頁(yè)程序以下：Vara,b,c,d,x:real;i,x1,x2,x3:Integer;BeginRead(a,b,c,d);x1:=MaxInt;x2:=x1;x3:=x1;

四、窮舉法應(yīng)用第10頁(yè)Fori:=-10000To10000DoBeginx:=i/100;IfAbs(a*x*x*x+b*x*x+c*x+d)<0.000001ThenIfi<x1Thenx1:=iElseIfi<x2Thenx2:=iElseIfi<x3Thenx3:=i;{確保x1<x2<3}End;Writeln(x1/100:0:2,'',x2/100:0:2,'',x3/100:0:2);End.四、窮舉法應(yīng)用第11頁(yè)四、窮舉法應(yīng)用窮舉法實(shí)例三：學(xué)校名次。

問(wèn)題描述：有A，B，C，D，E5所學(xué)校。在一次檢驗(yàn)評(píng)選中，已知E校必定不是第2名或第3名，他們相互進(jìn)行推測(cè)。A校有些人說(shuō)，E校一定是第1名；B校有些人說(shuō)，我?？赡苁堑?名；C校有些人說(shuō)，A校最差；D校有些人說(shuō)，C校不是最好；E校有些人說(shuō)，D校會(huì)獲第1名。結(jié)果只有第1名和第2名學(xué)校人猜對(duì)了。編程指出這5所學(xué)校名次。第12頁(yè)四、窮舉法應(yīng)用窮舉法分析：本題是一個(gè)邏輯判斷題，普通邏輯判斷題都采取窮舉法進(jìn)行處理。我們對(duì)5所學(xué)校所得名次各種可能情況進(jìn)行窮舉。在每種情況中，為了預(yù)防不一樣學(xué)校取相同名次，設(shè)置了邏輯數(shù)組x，x[I]為false表示已經(jīng)有某校取第I名。此題難點(diǎn)在于確定判斷條件。我們?cè)O(shè)置邏輯變量b0來(lái)描述這一條件，主要有兩個(gè)條件：“E校不是第2名或第3名”與“只有第1名和第2名學(xué)校人猜對(duì)”，后一條件要判斷：1）是否只有兩人說(shuō)法正確？2）說(shuō)得正確人是否是取得第1名和第2名學(xué)校人？要判斷是否僅有兩人說(shuō)正確，須統(tǒng)計(jì)正確命題個(gè)數(shù)。為此，設(shè)置了函數(shù)bton，將邏輯量數(shù)值化。

第13頁(yè)四、窮舉法應(yīng)用窮舉法程序：programl3(output);vari,a,b,c,d,e,m:integer;x:array[1..5]ofboolean;b0,b1:boolean;functionbton(b:boolean):integer;beginifbthenbton:=-1elsebton:=0end;第14頁(yè)四、窮舉法應(yīng)用窮舉法beginfori:=1to5dox[i]:=true;fora:=1to5dobeginx[a]:=false;forb:=1to5doifx[b]thenbeginx[b]:=false;forc:=1to5doifx[c]thenbeginx[c]:=false;ford:=1to5doifx[d]then第15頁(yè)四、窮舉法應(yīng)用窮舉法begine:=15-a-b-c-d;b0:=(e<>2)and(e<>3);m:=bton(e=1)+bton(b=2)+bton(a=5)+bton(c<>1)+bton(d=1);b0:=b0and(m=-2);b1:=(e=1)and(a<>2);b1:=b1or(a=5)and(c<>1)and(c<>2);b1:=b1or(c<>1)and(d<>1)and(d<>2);b1:=b1or(d=1)and(e<>2);b0:=b0andnotb1;ifb0thenwriteln('a=',a:2,'b=',b:2,'c=',c:2,'d=',d:2,'e=',e:2);x[d]:=true;end;第16頁(yè)四、窮舉法應(yīng)用窮舉法

x[c]:=true;end;x[b]:=true;end;x[a]:=true;end;end.運(yùn)行結(jié)果：a=5b=2c=1d=3e=4第17頁(yè)窮舉法實(shí)例四：阿姆斯特朗數(shù)。問(wèn)題描述：編一個(gè)程序找出全部三位數(shù)到七位數(shù)中阿姆斯特朗數(shù)。阿姆斯特朗數(shù)也叫水仙花數(shù),它定義以下:若一個(gè)n位自然數(shù)各位數(shù)字n次方之和等于它本身,則稱這個(gè)自然數(shù)為阿姆斯特朗數(shù)。比如153(153=1*1*1+3*3*3+5*5*5)是一個(gè)三位數(shù)阿姆斯特朗數(shù),8208則是一個(gè)四位數(shù)阿姆斯特朗數(shù)。

五、窮舉算法深入應(yīng)用第18頁(yè)窮舉法算法分析：為了使得程序盡快運(yùn)行出正確結(jié)果,程序中使用了一個(gè)數(shù)組power存放全部數(shù)字各次冪之值,power[i,j]等于ij次方。變量currentnumber存放當(dāng)前要被驗(yàn)證數(shù),數(shù)組digit存放當(dāng)前數(shù)各位數(shù)字,開(kāi)始時(shí)digit[3]=1,其它元素均為0,此時(shí)表示當(dāng)前數(shù)為100。highest為當(dāng)前數(shù)位數(shù)。五、窮舉算法深入應(yīng)用第19頁(yè)窮舉法程序：programex3(input,outoutp);constmaxlen=7;vari,j,currentnumber,highest,sum,total:longint;digit:array[0..maxlen+1]ofinteger;power:array[0..9,0..maxlen]oflongint;beginfori:=0to9dobeginpower[i,0]:=1;forj:=1tomaxlendopower[i,j]:=power[i,j-1]*iend;

五、窮舉算法深入應(yīng)用第20頁(yè)窮舉法fori:=1tomaxlendodigit[i]:=0;digit[3]:=1;highest:=3;currentnumber:=100;total:=0;whiledigit[maxlen+1]=0dobeginsum:=0;fori:=1tohighestdosum:=sum+power[digit[i],highest];ifsum=currentnumberthenbegintotal:=total+1;write(currentnumber:maxlen+5);iftotalmod6=0thenwritelnend;五、窮舉算法深入應(yīng)用第21頁(yè)窮舉法digit[1]:=digit[1]+1;i:=1;whiledigit[i]=10dobegindigit[i+1]:=digit[i+1]+1;digit[i]:=0;i:=i+1end;ifi>highestthenhighest:=i;currentnumber:=currentnumber+1end;writelnend.五、窮舉算法深入應(yīng)用第22頁(yè)窮舉法優(yōu)化策略一：算法中時(shí)間和空間往往是矛盾，時(shí)間復(fù)雜性和空間復(fù)雜性在一定條件下也是能夠相互轉(zhuǎn)化,有時(shí)候?yàn)榱颂嵘绦蜻\(yùn)行速度,在算法空間要求不苛刻前提下,設(shè)計(jì)算法時(shí)可考慮充分利用有限剩下空間來(lái)存放程序中重復(fù)要計(jì)算數(shù)據(jù),這就是“用空間換時(shí)間”策略,是優(yōu)化程序一個(gè)慣用方法。五、窮舉算法深入應(yīng)用第23頁(yè)五、窮舉算法深入應(yīng)用窮舉法實(shí)例五：郵票面值。問(wèn)題描述：郵局發(fā)行一套票面有四種不一樣值郵票，假如每封信所貼郵票張數(shù)不超出三枚，存在整數(shù)Ｒ，使得用不超出三枚郵票，能夠貼出連續(xù)整數(shù)１、２、３，…，Ｒ來(lái)，找出這四種面值數(shù)，使得Ｒ值最大。第24頁(yè)五、窮舉算法深入應(yīng)用窮舉法分析：本題知道每封信郵票數(shù)范圍（<=3）,郵票有四種類型，編程找出能使面值最大郵票。其算法是：

(1)面值不一樣四種郵票，每封信所貼郵票不超出3張。(2)用這四種郵票貼出連序整數(shù)，而且使Ｒ值最大。(3)用窮舉法，找出全部符合條件解。(4)本題用集合方法統(tǒng)計(jì)郵票面值，提升判重速度。設(shè)四種郵票面值分別為：A,B,C,D，依據(jù)題意設(shè)：A<B<C<D，所以A=1，用循環(huán)語(yǔ)句完成搜索。

第25頁(yè)五、窮舉算法深入應(yīng)用窮舉法Programp12_3;vara,b,c,d：integer;

x,x0,x1,x2,x3,x4：integer;st1：setof1．．100;Functionnumber(a,b,c,d:integer)：integer;varn1,n2,n3,n4,sum:integer;beginst1:=[];forn1:=0to3do｛每種郵票所取張數(shù)｝

forn2:=0to3-n1doforn3:=0to3-n1-n2doforn4:=0to3-n1-n2-n3dobegin

第26頁(yè)五、窮舉算法深入應(yīng)用窮舉法

ifn1+n2+n3+n4<=3then

beginsum:=n1*a+n2*b+n3*c+n4*d;

｛計(jì)算信封郵票面值｝st1:=st1+[sum]end;end;sum:=1;whilesuminst1dosum:=sum+1;number:=sum-1;end;{函數(shù)結(jié)束}

第27頁(yè)五、窮舉算法深入應(yīng)用窮舉法

BEGIN{main}a:=1;x0:=0;forb:=a+1to3*a+1doforc:=b+1to3*b+1do｛每種郵票可取值范圍｝ford:=c+1to3*c+1dobeginx:=number(a,b,c,d);調(diào)用函數(shù)求每封信郵票總面值｝ifx>x0thenbeginx0:=x;x1:=a;x2:=b;x3:=c;x4:=d｛保留最大面值郵票｝write(x1：5,x2：5,x3：5,x4：5);writeln(‘‘:10,'x0=',x0);end;end;end.第28頁(yè)五、窮舉算法深入應(yīng)用窮舉法程序運(yùn)行后，其輸出結(jié)果是：{解答結(jié)果有11組}1234x0=121235x0=13…….13610x0=231478x0=24第29頁(yè)五、窮舉算法深入應(yīng)用窮舉法優(yōu)化思緒二：降低窮舉變量，在使用窮舉算法之前，先考慮一下解元素之間關(guān)聯(lián)，將一些非窮舉不可解元素列為窮舉變量，其它元素經(jīng)過(guò)計(jì)算和分析得出解元素可能值。優(yōu)化思緒三：降低窮舉變量值域，經(jīng)過(guò)和窮舉變量間數(shù)學(xué)關(guān)系定義解元素值域。

第30頁(yè)五、窮舉算法深入應(yīng)用窮舉法實(shí)例六：方格填數(shù)。問(wèn)題描述：如圖所表示8個(gè)格子中放入1～8八個(gè)數(shù)字，使得相鄰和對(duì)角線數(shù)字之差不為1。編程找出全部放法。第31頁(yè)五、窮舉算法深入應(yīng)用窮舉法分析：我們先不考慮后一條件，只考慮第一個(gè)條件，即把1～8八個(gè)數(shù)字放入8個(gè)格子中。這是輕易做到，就是8個(gè)數(shù)字全排列，共有8!=40320種放法。然后對(duì)這8!個(gè)可行解用后一個(gè)條件加以檢驗(yàn)，輸出符合條件解。對(duì)于后一個(gè)條件中“相鄰”判斷，能夠建立一個(gè)鄰接表來(lái)處理：112213314423525626734……13671478第32頁(yè)五、窮舉算法深入應(yīng)用窮舉法表中表示哪兩個(gè)格子是相鄰，link[i,1]和link[i,2]是相鄰格子編號(hào)。全排列產(chǎn)生，能夠用八重循環(huán)，也可以用專門算法，程序留給同學(xué)們自己去完成。利用窮舉策略編制程序，其運(yùn)算量普通是很大，所以怎樣提升算法效率是窮舉算法一個(gè)很主要問(wèn)題。普通應(yīng)盡可能降低可行解個(gè)數(shù)，使得第二步檢驗(yàn)運(yùn)算量盡可能地少。怎樣來(lái)優(yōu)化算法呢?第33頁(yè)五、窮舉算法深入應(yīng)用窮舉法假如注意到b3和b6兩個(gè)格子，與它們“相鄰”格子有6個(gè)，也就是說(shuō)，放入這兩個(gè)格子中數(shù)，必須和6個(gè)數(shù)不連續(xù)，僅能夠和一個(gè)數(shù)是連續(xù)，這么數(shù)只有2個(gè)，即1和8。這么，b1，b3，b6，b8；4個(gè)格子中數(shù)放法僅有兩種可能：2、8、1、7和7、1、8、2。而b2、b4、b5、b7四個(gè)格子中數(shù)僅需在3～6四個(gè)數(shù)中選擇。經(jīng)過(guò)上述優(yōu)化，可行解僅有：2×4?。?8個(gè)，大大降低了計(jì)算量。而且檢驗(yàn)是否符合要求，也只需檢驗(yàn)(1，2)，(1，4)，(2，5)，(4，7)，(5，8)，(7，8)這6對(duì)數(shù)之差就能夠了。

第34頁(yè)五、窮舉算法深入應(yīng)用窮舉法programexampleb;constlink:array[1..6,1..2]ofinteger=((1,2),(1,4),(2,5),(4,7),(5,8),(7,8));varb:array[1..8]ofinteger;procedureprint;beginwriteln('',b[1]:2);writeln(b[2]:2,b[3]:2,b[4]:2);writeln(b[5]:2,b[6]:2,b[7]:2);writeln('',b[8]:2)end;第35頁(yè)五、窮舉算法深入應(yīng)用窮舉法functionchoose:boolean;vari:integer;beginchoose:=false;fori:=1to6doifabs(b[link[i,1]]-b[link[i,2]])=1thenexit;choose:=trueend;第36頁(yè)五、窮舉算法深入應(yīng)用窮舉法proceduretry;beginforb[2]:=3to6doforb[4]:=3to6doifb[2]<>b[4]thenforb[5]:=3to6doif(b[5]<>b[2])and(b[5]<>b[4])thenbeginb[7]:=18-b[2]-b[4]-b[5];ifchoosethenprint;end;end;第37頁(yè)五、窮舉算法深入應(yīng)用窮舉法beginb[1]:=2;b[3]:=8;b[6]:=1;b[8]:=7;try;b[1]:=7;b[3]:=1;b[6]:=8;b[8]:=2;try;readlnend.第38頁(yè)五、窮舉算法深入應(yīng)用窮舉法優(yōu)化思緒四：分解約束條件，將拆分約束條件嵌套在對(duì)應(yīng)循環(huán)體間，盡可能降低可行解數(shù)目，也稱為“剪枝”，即把顯著不符合條件可行解盡可能地剪去，降低窮舉計(jì)算量。第39頁(yè)六、窮舉算法代碼實(shí)現(xiàn)方法：實(shí)例七：4皇后問(wèn)題。問(wèn)題描述：在4×4棋盤上安置4個(gè)皇后，要求任意兩個(gè)皇后不在同一行、不在同一列、不在同一對(duì)角線上，輸出全部方案。第40頁(yè)窮舉法分析：1）

本題是一個(gè)搜索問(wèn)題，搜索范圍44，找出符合條件方案；2）方案必須滿足條件：任意兩個(gè)不在同一行、同一列和同一對(duì)角線。

六、窮舉算法代碼實(shí)現(xiàn)方法：第41頁(yè)窮舉法方法一程序：constn=4;typestack=array[1..n]ofinteger;vari1,i2,i3,i4:integer;s:stack;functioncheck:boolean;vari,j:integer;beginfori:=1ton-1doforj:=i+1tondoif(s[i]=s[j])or(s[i]-i=s[j]-j)or(s[i]+i=s[j]+j)thenbegincheck:=false;exitend;check:=trueend;六、窮舉算法代碼實(shí)現(xiàn)方法：第42頁(yè)窮舉法procedureprint;vari:integer;beginfori:=1tondowrite(s[i]:2);writelnend;beginfori1:=1tondofori2:=1tondofori3:=1tondofori4:=1tondobegins[1]:=i1;s[2]:=i2;s[3]:=i3;s[4]:=i4;ifcheckthenprint;end;end.第43頁(yè)窮舉法方法二程序：constn=4;typestack=array[1..n]ofinteger;vari1,i2,i3,i4:integer;s:stack;functioncheck:boolean;vari,j:integer;beginfori:=1ton-1doforj:=i+1tondoif(s[i]=s[j])or(s[i]-i=s[j]-j)or(s[i]+i=s[j]+j)thenbegincheck:=false;exitend;check:=trueend;六、窮舉算法代碼實(shí)現(xiàn)方法：第44頁(yè)procedureprint;vari:integer;beginfori:=1tondowrite(s[i]:2);writelnend;beginwhiles[0]=1dobeginj:=n;

while

(s[j]=4)

do

j:=j-1;

s[j]:=s[j]+1;

for

I:=j+1

to

n

do

s[I]：=1;

ifcheckthenprint;

end;end.窮舉法第45頁(yè)窮舉法方法三程序：constn=8;typestack=array[1..n]ofinteger;varcount:integer;s:stack;functioncheck:boolean;vari,j:integer;beginfori:=1ton-1doforj:=i+1tondoif(s[i]=s[j])or(s[i]-i=s[j]-j)or(s[i]+i=s[j]+j)thenbegincheck:=false;exitend;check:=trueend;六、窮舉算法代碼實(shí)現(xiàn)方法：第46頁(yè)procedureprint;vari:integer;beginfori:=1tondowrite(s[i]:2);writelnend;proceduresearch(k:integer);vari:integer;beginifk>nthenbeginifcheckthenbegincount:=count+1;print;end;endelsefori:=1tondobegins[k]:=i;search(k+1);endend;begincount:=0;search(1);write(count);end.第47頁(yè)窮舉法方法四程序：constn=8;typestack=array[0..n]ofinteger;vartop,count:integer;s:stack;functioncheck:boolean;vari,j:integer;beginfori:=1ton-1doforj:=i+1tondoif(s[i]=s[j])or(s[i]-i=s[j]-j)or(s[i]+i=s[j]+j)thenbegincheck:=false;exitend;check:=trueend;六、窮舉算法代碼實(shí)現(xiàn)方法：第48頁(yè)begin fillchar(s,sizeof(s),0);count:=0; top:=1; repeatinc(s[top]);ifs[top]<=ntheniftop=nthenbeginifcheckthenbegins[top]:=0;dec(top);count:=count+1;endendelseinc(top)elsebegins[top]:=0;dec(top);end; untiltop=0;write(count);end.第49頁(yè)七、實(shí)例分析：窮舉法實(shí)例八：巧妙填數(shù)。問(wèn)題描述：將1～9這九個(gè)數(shù)字填入九個(gè)空格中。每一橫行三個(gè)數(shù)字組成一個(gè)三位數(shù)。假如要使第二行三位數(shù)是第一行兩倍，第三行三位數(shù)是第一行三倍，應(yīng)怎樣填數(shù)。如圖所表示。192384576第50頁(yè)七、實(shí)例分析：窮舉法分析：本題目有9個(gè)格子，要求填數(shù)，假如不考慮問(wèn)題給出條件，共有9！=362880種方案，在這些方案中符合問(wèn)題條件即為解。所以能夠采取窮舉法。但仔細(xì)分析問(wèn)題，顯然第一行數(shù)不會(huì)超出400，實(shí)際上只要確定第一行數(shù)就能夠依據(jù)條件算出其它兩行數(shù)了。這么僅需窮舉400次。第51頁(yè)七、實(shí)例分析：窮舉法programex_8(input,output);vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;{sum}functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;{mul}第52頁(yè)七、實(shí)例分析：窮舉法Beginfori:=1to3doforj:=1to9doifj<>ithenfork:=1to9doif(k<>j)and(k<>i)thenbegins:=i*100+j*10+k;if3*s<1000thenif(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)thenbeginwriteln(s);writeln(2*s);writeln(3*s);writeln;end;end;end.第53頁(yè)實(shí)例九：數(shù)塔問(wèn)題問(wèn)題描述：有形以下列圖所表示數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)能夠選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上數(shù)值和最靠近零。七、實(shí)例分析：第54頁(yè)輸入數(shù)據(jù)：輸入文件是numbertap.dat。該文件有若干行，第一行是一個(gè)正整數(shù)n(n<=20)，下面共有n行整數(shù)，每行整數(shù)個(gè)數(shù)依次是1，2，……n個(gè)，行首行末無(wú)多出空格。而且每個(gè)數(shù)字絕對(duì)值不超出1000000。輸出數(shù)據(jù)：輸出文件是numbertap.out。文件輸出一行，代表最靠近零數(shù)值絕對(duì)值。七、實(shí)例分析：第55頁(yè)constn=4;typestack=array[0..n]ofinteger;vari,j,k,sum,min:integer;s:stack;a:array[1..n,1..n]ofinteger;beginfori:=0tondos[i]:=0;fori:=1tondoforj:=1toidobeginread(a[i,j]);end;min:=10000;第56頁(yè)whiles[1]=0dobeginj:=n;while(s[j]=1)doj:=j-1;s[j]:=s[j]+1;forI:=j+1tondos[I]:=0;k:=1;sum:=0;fori:=1tondobegink:=k+s[i];write('k',k);sum:=sum+a[I,k];write(a[i,k],sum);readln;end;ifabs(sum)<abs(min)thenmin:=sum;end;end.第57頁(yè)實(shí)例十：選數(shù)

問(wèn)題描述：已知n（1<=n<=20）個(gè)整數(shù)x1,x2,…,xn（1<=xi<=5000000），以及一個(gè)整數(shù)k（k<n）。從n個(gè)整數(shù)中任選k個(gè)整數(shù)相加，可分別得到一系列和?，F(xiàn)在，要求你計(jì)算出和為素?cái)?shù)共有多少種。七、實(shí)例分析：第58頁(yè)本題無(wú)數(shù)學(xué)公式可尋，1<=n<=20這個(gè)約束條件暗示我們本題窮舉搜索是有希望。第二個(gè)問(wèn)題就是判斷素?cái)?shù)，判斷一個(gè)整數(shù)P(P>1)是否為素?cái)?shù)最簡(jiǎn)單方法就是看是否存在一個(gè)素?cái)?shù)a(a<=sqrt(P))是P約數(shù)，假如不存在，該數(shù)就為素?cái)?shù)，因?yàn)樵诖祟}中1<=xi<=5000000,n<=20,所以要判斷數(shù)P不會(huì)超出100000000，sqrt(p)<=10000，所以，為了加緊速度，我們能夠用篩選法將2…10000之間素?cái)?shù)保留到一個(gè)數(shù)組里（共1229個(gè)），這么速度預(yù)計(jì)將提升好幾倍。第59頁(yè)窮舉法小結(jié):窮舉法窮舉思想往往是最輕易想到一個(gè)解題策略，窮舉算法從本質(zhì)上說(shuō)，它是一個(gè)搜索算法。適合窮舉策略求解問(wèn)題，首先必須滿足其問(wèn)題規(guī)模和可能解規(guī)模（個(gè)數(shù)）不是尤其大，且解變量值改變含有一定規(guī)律性。實(shí)際應(yīng)用中，許多復(fù)雜問(wèn)題求解策略不止使用一個(gè)算法，窮舉算法在這類問(wèn)題求解過(guò)程中起到相當(dāng)關(guān)鍵作用。如圓桌騎士問(wèn)題。假如問(wèn)題規(guī)模很大，而又能找到其它算法處理，則不宜采取窮舉法，如全排列問(wèn)題，可用結(jié)構(gòu)法處理。第60頁(yè)圓桌騎士問(wèn)題:窮舉法很多世紀(jì)以前，阿瑟王和他圓桌武士常在每年元旦聚會(huì)慶賀他們情誼。我們用一個(gè)單人玩棋盤游戲去紀(jì)念這個(gè)史實(shí)：一個(gè)國(guó)王和多個(gè)武士被隨機(jī)放在8X8正方形棋盤不一樣方格上。只要不越出棋盤，國(guó)王能夠移至與之相鄰方格內(nèi)，只要不越出棋盤，武士能夠跳日字，在棋局當(dāng)中，選手能夠在同一方格內(nèi)擺放多個(gè)棋子，選手目標(biāo)是在盡可能少步數(shù)內(nèi)把全部棋子集中到同一方格。為此，他必須按前述方法去移動(dòng)棋子。另外，當(dāng)國(guó)王和一個(gè)或多個(gè)武士位于同一方格內(nèi)時(shí)，選手能夠選擇今后讓國(guó)王跟隨其中一個(gè)武士一同向聚會(huì)終點(diǎn)移動(dòng)，就象移動(dòng)單個(gè)武士一樣。任務(wù)：寫(xiě)出一個(gè)程序去計(jì)算選手要實(shí)現(xiàn)聚會(huì)所