2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 枚舉法

《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 枚舉法》由會(huì)員分享，可在線閱讀，更多相關(guān)《2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 枚舉法（4頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2022年高中信息技術(shù) 全國(guó)青少年奧林匹克聯(lián)賽教案 枚舉法 枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個(gè)元素，用題目給定的約束條件判定哪些是無(wú)用的，哪些是有用的。能使命題成立者，即為問(wèn)題的解。 采用枚舉算法解題的基本思路： （1） 確定枚舉對(duì)象、枚舉范圍和判定條件； （2） 一一枚舉可能的解，驗(yàn)證是否是問(wèn)題的解 下面我們就從枚舉算法的的優(yōu)化、枚舉對(duì)象的選擇以及判定條件的確定，這三個(gè)方面來(lái)探討如何用枚舉法解題。 枚舉算法應(yīng)用 例1：百錢買百雞問(wèn)題：有一個(gè)人有一百塊錢，打算買一百只雞。到市場(chǎng)一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩塊錢一只?，F(xiàn)在，請(qǐng)你編

2、一程序，幫他計(jì)劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？ 算法分析：此題很顯然是用枚舉法，我們以三種雞的個(gè)數(shù)為枚舉對(duì)象（分別設(shè)為x,y,z）,以三種雞的總數(shù)（x+y+z）和買雞用去的錢的總數(shù)(x*3+y*2+z)為判定條件，窮舉各種雞的個(gè)數(shù)。 下面是解這個(gè)百雞問(wèn)題的程序 var x,y,z:integer; begin for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do{枚舉所有可能的解} if (x+y+z=100)and(x*3+y*2+z div 3=100)and(z mod 3=0)then

3、 writeln('x=',x,'y=',y,'z=',z); {驗(yàn)證可能的解，并輸出符合題目要求的解} end. 上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞（x,y），第三種雞就可以根據(jù)約束條件求得（z=100-x-y），這樣就縮小了枚舉范圍，請(qǐng)看下面的程序： var x,y,z:integer; begin for x:=0 to 100 do for y:=0 to 100-x do begin z:=100-x-y; if (x*3+y*2+z div 3=100)and(z mod 3=0)then writeln('x=',x

4、,'y=',y,'z=',z); end; end. 未經(jīng)優(yōu)化的程序循環(huán)了1013 次，時(shí)間復(fù)雜度為O(n3)；優(yōu)化后的程序只循環(huán)了（102*101/2）次 ，時(shí)間復(fù)雜度為O(n2)。從上面的對(duì)比可以看出，對(duì)于枚舉算法，加強(qiáng)約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。 在枚舉算法中，枚舉對(duì)象的選擇也是非常重要的，它直接影響著算法的時(shí)間復(fù)雜度，選擇適當(dāng)?shù)拿杜e對(duì)象可以獲得更高的效率。如下例： 例2、將1,2...9共9個(gè)數(shù)分成三組,分別組成三個(gè)三位數(shù),且使這三個(gè)三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個(gè)三位數(shù). 例如:三個(gè)三位數(shù)192,384,576滿足以上條件.(N

5、OIPxxpj) 算法分析：這是xx年全國(guó)分區(qū)聯(lián)賽普及組試題（簡(jiǎn)稱NOIPxxpj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進(jìn)行枚舉，如果我們不加思地以每一個(gè)數(shù)位為枚舉對(duì)象，一位一位地去枚舉： for a:=1 to 9 do for b:=1 to 9 do ……… for i:=1 to 9 do 這樣下去，枚舉次數(shù)就有9９次，如果我們分別設(shè)三個(gè)數(shù)為x,2x,3x，以x為枚舉對(duì)象，窮舉的范圍就減少為９３，在細(xì)節(jié)上再進(jìn)一步優(yōu)化，枚舉范圍就更少了。程序如下： var t,x:integer; s,st:string; c:char; begin for x:

6、=123 to 321 do{枚舉所有可能的解} begin t:=0; str(x,st);{把整數(shù)x轉(zhuǎn)化為字符串，存放在st中} str(x*2,s); st:=st+s; str(x*3,s); st:=st+s; for c:='1' to '9' do{枚舉9個(gè)字符，判斷是否都在st中} if pos(c,st)<>0 then inc(t) else break;{如果不在st中，則退出循環(huán)} if t=9 then writeln(x,' ',x*2,' ',x*3); end; end. 在枚

7、舉法解題中，判定條件的確定也是很重要的，如果約束條件不對(duì)或者不全面，就窮舉不出正確的結(jié)果，?我們?cè)倏纯聪旅娴睦印? 例３ 一元三次方程求解(noipxxtg) 問(wèn)題描述 有形如：ax3+bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d 均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對(duì)值>=1。 要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后2位。 提示：記方程f(x)=0，若存在2個(gè)數(shù)x1和x2，且x1

8、根。 樣例 輸入：1 -5 -4 20 輸出：-2.00 2.00 5.00 算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法。用二分法解題相對(duì)于枚舉法來(lái)說(shuō)很要復(fù)雜很多。此題是否能用枚舉法求解呢？再分析一下題目，根的范圍在-100到100之間，結(jié)果只要保留兩位小數(shù)，我們不妨將根的值域擴(kuò)大100倍（-10000<=x<=10000），再以根為枚舉對(duì)象，枚舉范圍是-10000到10000，用原方程式進(jìn)行一一驗(yàn)證，找出方程的解。 有的同學(xué)在比賽中是這樣做 var k:integer; a,b,c,d,x :real; begin

9、read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if a*x*x*x+b*x*x+c*x+d=0 then write(x:0:2,' '); end; end. 用這種方法，很快就可以把程序編出來(lái)，再將樣例數(shù)據(jù)代入測(cè)試也是對(duì)的，等成績(jī)下來(lái)才發(fā)現(xiàn)這題沒(méi)有全對(duì)，只得了一半的分。 這種解法為什么是錯(cuò)的呢？錯(cuò)在哪里？前面的分析好象也沒(méi)錯(cuò)啊，難道這題不能用枚舉法做嗎？ 看到這里大家可能有點(diǎn)迷惑了。 在上面的解法中，枚舉范圍和枚舉對(duì)象都沒(méi)有錯(cuò)，而是在驗(yàn)證枚舉結(jié)果時(shí)，判定條件用錯(cuò)了。因?yàn)橐Ａ舳?/p>

10、位小數(shù)，所以求出來(lái)的解不一定是方程的精確根，再代入ax3+bx2+cx+d中，所得的結(jié)果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作為判斷條件是不準(zhǔn)確的。 我們換一個(gè)角度來(lái)思考問(wèn)題，設(shè)f(x)=ax3+bx2+cx+d，若x為方程的根，則根據(jù)提示可知，必有f(x-0.005)*(x+0.005)<0，如果我們以此為枚舉判定條件，問(wèn)題就逆刃而解。另外，如果f(x-0.005)=0，哪么就說(shuō)明x-0.005是方程的根，這時(shí)根據(jù)四舍5入，方程的根也為x。所以我們用(f(x-0.005)*f(x+0.005)<0) 和 (f(x-0.005)=0)作為判定條件。為了程序設(shè)計(jì)的方便，我

11、們?cè)O(shè)計(jì)一個(gè)函數(shù)f(x)計(jì)算ax3+bx2+cx+d的值，程序如下： {$N+} var k:integer; a,b,c,d,x:extended; function f(x:extended):extended; {計(jì)算ax3+bx2+cx+d的值} begin f:=((a*x+b)*x+c)*x+d; end; begin read(a,b,c,d); for k:=-10000 to 10000 do begin x:=k/100; if (f(x-0.005)*f(x+0.005)<0) or (f(x-0.005)=0) then write(x:0:2,' '); {若x兩端的函數(shù)值異號(hào)或x-0.005剛好是方程的根，則確定x為方程的根} end; end. 用枚舉法解題的最大的缺點(diǎn)是運(yùn)算量比較大，解題效率不高，如果枚舉范圍太大（一般以不超過(guò)兩百萬(wàn)次為限），在時(shí)間上就難以承受。但枚舉算法的思路簡(jiǎn)單，程序編寫和調(diào)試方便，比賽時(shí)也容易想到，在競(jìng)賽中，時(shí)間是有限的，我們競(jìng)賽的最終目標(biāo)就是求出問(wèn)題解，因此，如果題目的規(guī)模不是很大，在規(guī)定的時(shí)間與空間限制內(nèi)能夠求出解，那么我們最好是采用枚舉法，而不需太在意是否還有更快的算法，這樣可以使你有更多的時(shí)間去解答其他難題。