2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法.doc
《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法.doc（4頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法 枚舉法，常常稱之為窮舉法，是指從可能的集合中一一枚舉各個(gè)元素，用題目給定的約束條件判定哪些是無用的，哪些是有用的。能使命題成立者，即為問題的解。 采用枚舉算法解題的基本思路： （1） 確定枚舉對象、枚舉范圍和判定條件； （2） 一一枚舉可能的解，驗(yàn)證是否是問題的解 下面我們就從枚舉算法的的優(yōu)化、枚舉對象的選擇以及判定條件的確定，這三個(gè)方面來探討如何用枚舉法解題。 枚舉算法應(yīng)用 例1：百錢買百雞問題：有一個(gè)人有一百塊錢，打算買一百只雞。到市場一看，大雞三塊錢一只，小雞一塊錢三只，不大不小的雞兩塊錢一只?，F(xiàn)在，請你編一程序，幫他計(jì)劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？ 算法分析：此題很顯然是用枚舉法，我們以三種雞的個(gè)數(shù)為枚舉對象（分別設(shè)為x,y,z）,以三種雞的總數(shù)（x+y+z）和買雞用去的錢的總數(shù)(x*3+y*2+z)為判定條件，窮舉各種雞的個(gè)數(shù)。 下面是解這個(gè)百雞問題的程序 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); {驗(yàn)證可能的解，并輸出符合題目要求的解} 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 次，時(shí)間復(fù)雜度為O(n3)；優(yōu)化后的程序只循環(huán)了（102*101/2）次 ，時(shí)間復(fù)雜度為O(n2)。從上面的對比可以看出，對于枚舉算法，加強(qiáng)約束條件，縮小枚舉的范圍，是程序優(yōu)化的主要考慮方向。 在枚舉算法中，枚舉對象的選擇也是非常重要的，它直接影響著算法的時(shí)間復(fù)雜度，選擇適當(dāng)?shù)拿杜e對象可以獲得更高的效率。如下例： 例2、將1,2...9共9個(gè)數(shù)分成三組,分別組成三個(gè)三位數(shù),且使這三個(gè)三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個(gè)三位數(shù). 例如:三個(gè)三位數(shù)192,384,576滿足以上條件.(NOIPxxpj) 算法分析：這是xx年全國分區(qū)聯(lián)賽普及組試題（簡稱NOIPxxpj，以下同）。此題數(shù)據(jù)規(guī)模不大，可以進(jìn)行枚舉，如果我們不加思地以每一個(gè)數(shù)位為枚舉對象，一位一位地去枚舉： 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為枚舉對象，窮舉的范圍就減少為９３，在細(xì)節(jié)上再進(jìn)一步優(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個(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. 在枚舉法解題中，判定條件的確定也是很重要的，如果約束條件不對或者不全面，就窮舉不出正確的結(jié)果，我們再看看下面的例子。 例３ 一元三次方程求解(noipxxtg) 問題描述 有形如：ax3+bx2+cx+d=0 這樣的一個(gè)一元三次方程。給出該方程中各項(xiàng)的系數(shù)(a，b，c，d 均為實(shí)數(shù))，并約定該方程存在三個(gè)不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。 要求由小到大依次在同一行輸出這三個(gè)實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后2位。 提示：記方程f(x)=0，若存在2個(gè)數(shù)x1和x2，且x1下載提示(請認(rèn)真閱讀)
- 1.請仔細(xì)閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點(diǎn)此認(rèn)領(lǐng)！既往收益都?xì)w您。
文檔包含非法信息？點(diǎn)此舉報(bào)后獲取現(xiàn)金獎(jiǎng)勵(lì)！
下載文檔到電腦，查找使用更方便
9.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計(jì)者僅對作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 2019-2020年高中信息技術(shù) 全國青少年奧林匹克聯(lián)賽教案 枚舉法 2019 2020 年高 信息技術(shù) 全國青少年 奧林匹克 聯(lián)賽 教案 枚舉
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
鏈接地址：http://www.820124.com/p-2589946.html