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

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

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

2、一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？ 算法分析：此題很顯然是用枚舉法，我們以三種雞的個數(shù)為枚舉對象（分別設(shè)為x,y,z）,以三種雞的總數(shù)（x+y+z）和買雞用去的錢的總數(shù)(x*3+y*2+z)為判定條件，窮舉各種雞的個數(shù)。 下面是解這個百雞問題的程序 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); {驗證可能的解，并輸出符合題目要求的解} end. 上面的條件還有優(yōu)化的空間，三種雞的和是固定的，我們只要枚舉二種雞（x,y），第三種雞就可以根據(jù)約束條件求得（z=100-x-y），這樣就縮小了枚舉范圍，請看下面的程序： 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 次，時間復(fù)雜度為O(n3)；優(yōu)化后的程序只循環(huán)了（102*101/2）次 ，時間復(fù)雜度為O(n2)。從上面的對比可以看出，對于枚舉算法，加強(qiáng)約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。 在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時間復(fù)雜度，選擇適當(dāng)?shù)拿杜e對象可以獲得更高的效率。如下例： 例2、將1,2...9共9個數(shù)分成三組,分別組成三個三位數(shù),且使這三個三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個三位數(shù). 例如:三個三位數(shù)192,384,576滿足以上條件.(N

5、OIPxxpj) 算法分析：這是xx年全國分區(qū)聯(lián)賽普及組試題（簡稱NOIPxxpj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進(jìn)行枚舉，如果我們不加思地以每一個數(shù)位為枚舉對象，一位一位地去枚舉： for a:=1 to 9 do for b:=1 to 9 do ……… for i:=1 to 9 do 這樣下去，枚舉次數(shù)就有9９次，如果我們分別設(shè)三個數(shù)為x,2x,3x，以x為枚舉對象，窮舉的范圍就減少為９３，在細(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個字符，判斷是否都在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、舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(jié)果，?我們再看看下面的例子。 例３ 一元三次方程求解(noipxxtg) 問題描述 有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d 均為實數(shù))，并約定該方程存在三個不同實根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。 要求由小到大依次在同一行輸出這三個實根(根與根之間留有空格)，并精確到小數(shù)點后2位。 提示：記方程f(x)=0，若存在2個數(shù)x1和x2，且x1

8、根。 樣例 輸入：1 -5 -4 20 輸出：-2.00 2.00 5.00 算法分析：由題目的提示很符合二分法求解的原理，所以此題可以用二分法。用二分法解題相對于枚舉法來說很要復(fù)雜很多。此題是否能用枚舉法求解呢？再分析一下題目，根的范圍在-100到100之間，結(jié)果只要保留兩位小數(shù)，我們不妨將根的值域擴(kuò)大100倍（-10000<=x<=10000），再以根為枚舉對象，枚舉范圍是-10000到10000，用原方程式進(jì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. 用這種方法，很快就可以把程序編出來，再將樣例數(shù)據(jù)代入測試也是對的，等成績下來才發(fā)現(xiàn)這題沒有全對，只得了一半的分。 這種解法為什么是錯的呢？錯在哪里？前面的分析好象也沒錯啊，難道這題不能用枚舉法做嗎？ 看到這里大家可能有點迷惑了。 在上面的解法中，枚舉范圍和枚舉對象都沒有錯，而是在驗證枚舉結(jié)果時，判定條件用錯了。因為要保留二

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

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