2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 枚舉法.doc
《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 枚舉法.doc》由會員分享，可在線閱讀，更多相關《2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 枚舉法.doc（4頁珍藏版）》請在裝配圖網(wǎng)上搜索。
2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 枚舉法 枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。 采用枚舉算法解題的基本思路： （1） 確定枚舉對象、枚舉范圍和判定條件； （2） 一一枚舉可能的解，驗證是否是問題的解 下面我們就從枚舉算法的的優(yōu)化、枚舉對象的選擇以及判定條件的確定，這三個方面來探討如何用枚舉法解題。 枚舉算法應用 例1：百錢買百雞問題：有一個人有一百塊錢，打算買一百只雞。到市場一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩塊錢一只?，F(xiàn)在，請你編一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？ 算法分析：此題很顯然是用枚舉法，我們以三種雞的個數(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 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,y=,y,z=,z); end; end. 未經(jīng)優(yōu)化的程序循環(huán)了1013 次，時間復雜度為O(n3)；優(yōu)化后的程序只循環(huán)了（102*101/2）次 ，時間復雜度為O(n2)。從上面的對比可以看出，對于枚舉算法，加強約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。 在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時間復雜度，選擇適當?shù)拿杜e對象可以獲得更高的效率。如下例： 例2、將1,2...9共9個數(shù)分成三組,分別組成三個三位數(shù),且使這三個三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個三位數(shù). 例如:三個三位數(shù)192,384,576滿足以上條件.(NOIPxxpj) 算法分析：這是xx年全國分區(qū)聯(lián)賽普及組試題（簡稱NOIPxxpj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進行枚舉，如果我們不加思地以每一個數(shù)位為枚舉對象，一位一位地去枚舉： for a:=1 to 9 do for b:=1 to 9 do ……… for i:=1 to 9 do 這樣下去，枚舉次數(shù)就有9９次，如果我們分別設三個數(shù)為x,2x,3x，以x為枚舉對象，窮舉的范圍就減少為９３，在細節(jié)上再進一步優(yōu)化，枚舉范圍就更少了。程序如下： var t,x:integer; s,st:string; c:char; begin for x:=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. 在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(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
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞：
- 2019-2020年高中信息技術 全國青少年奧林匹克聯(lián)賽教案 枚舉法 2019 2020 年高 信息技術 全國青少年 奧林匹克 聯(lián)賽 教案 枚舉
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學習交流，未經(jīng)上傳用戶書面授權，請勿作他用。
鏈接地址：http://m.appdesigncorp.com/p-2589946.html