基級班講稿簡單算法應(yīng)用

簡單算法勝利第二中學(xué)周恒一、概念枚舉法，常常稱之為窮舉法，是指在一個(gè)有窮的可能的解的集合中，枚舉出集合中的每一個(gè)元素，用問題給定的解的檢驗(yàn)條件去判斷其是否符合條件。若滿足條件，該元素即為問題的一個(gè)解；若不滿足，該元素就不是這一問題的解。（可通過循環(huán)和條件判斷語句完成）一一列舉出某問題所有可能的解，并在逐一列舉的過程中，檢查每個(gè)可能的解是否是問題的真正解，若是，就采納這個(gè)解，否則拋棄它。(在列舉過程中，既不能遺漏，也不應(yīng)重復(fù))枚舉法注：①適用于問題的可能解的規(guī)模（個(gè)數(shù)）不是特別大，其解變量的值的變化具有一定規(guī)律時(shí)。②減少枚舉量，提高枚舉效率（適當(dāng)使用條件語句，排除無效解）二、特點(diǎn)枚舉法特點(diǎn)是算法簡單，但運(yùn)行時(shí)所花費(fèi)等待運(yùn)行結(jié)果的時(shí)間也將使人無法忍受。另外，窮舉出的情況如何存儲在計(jì)算機(jī)中的也是一個(gè)棘手的問題。因此，我們在用枚舉法解決問題時(shí)，應(yīng)盡可能將明顯的不符合條件的情況排除在外，以盡快取得問題的解。三、枚舉法的模式①問題解的可能搜索的范圍：用循環(huán)或循環(huán)嵌套結(jié)構(gòu)實(shí)現(xiàn)；②寫出符合問題解的條件；③能使程序優(yōu)化的語句，以便縮小搜索范圍，減少程序運(yùn)行時(shí)間。四、枚舉法的優(yōu)缺點(diǎn)枚舉法的優(yōu)點(diǎn)：①由于枚舉算法一般是現(xiàn)實(shí)生活中問題的“直譯”，因此比較直觀，易于理解；②由于枚舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。枚舉法的缺點(diǎn)：枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)，因此效率比較低。五、枚舉的優(yōu)化枚舉算法的時(shí)間復(fù)雜度可以用狀態(tài)總數(shù)*考察單個(gè)狀態(tài)的耗時(shí)來表示，因此優(yōu)化主要是:(1)減少狀態(tài)總數(shù)（即減少枚舉變量和枚舉變量的值域）(2)降低單個(gè)狀態(tài)的考察代價(jià)優(yōu)化過程從幾個(gè)方面考慮。具體講:(1)提取有效信息(2)減少重復(fù)計(jì)算(3)將原問題化為更小的問題(4)根據(jù)問題的性質(zhì)進(jìn)行截枝(5)引進(jìn)其他算法三位數(shù)問題問題描述將1,2...9共9個(gè)數(shù)分成三組,分別組成三個(gè)三位數(shù),且使這三個(gè)三位數(shù)構(gòu)成1:2:3的比例,試求出所有滿足條件的三個(gè)三位數(shù).輸入:無輸出:192384576219438657273546819327654981枚舉算法及其應(yīng)用vari:integer;s,ss:string;c:char;beginfori:=123to329dobeginstr(i,ss);str(i*2,s);ss:=ss+s;str(i*3,s);ss:=ss+s;forc:='1'to'9'doifpos(c,ss)=0thenbreak;ifpos(c,ss)=0thencontinue;writeln(i,'',i*2,'',i*3);end;end.百錢百雞(m1.pas)問題描述一只公雞值5元，一只母雞值3元，3只小雞值1元，現(xiàn)用一百元要買一百只雞，問有什么方案(可以買0只)？輸入:無輸出:分別為公雞、母雞、小雞的個(gè)數(shù)，中間隔一空格，最后無空格。02575418788118112484作業(yè)一模擬算法用計(jì)算機(jī)語言模擬人處理某個(gè)事件過程的方法，根據(jù)模擬對象的不同特點(diǎn)，可以把計(jì)算機(jī)模擬分為決定性模擬和隨機(jī)性模擬兩大類。決定性模擬是對決定性現(xiàn)象進(jìn)行的模擬，其所模擬的事件按照固有的規(guī)律發(fā)生發(fā)展，并且最終有明確的結(jié)果。如方塊下落問題。隨機(jī)模擬是模擬隨機(jī)現(xiàn)象，由于隨機(jī)現(xiàn)象中至少有一個(gè)不確定的因素，因此在模擬中，必須建立一個(gè)用隨機(jī)數(shù)表示的數(shù)學(xué)模型才能進(jìn)行模擬。如：抓火柴問題。隨機(jī)模擬要用到的兩個(gè)函數(shù)：（1）randomize過程。隨機(jī)數(shù)種子，在使用隨機(jī)函數(shù)以前運(yùn)行它，可以使每次產(chǎn)生的隨機(jī)數(shù)都不同。（2）random(X)函數(shù)。產(chǎn)生一個(gè)范圍在[0，X）的隨機(jī)數(shù)。抓火柴問題一、問題描述甲乙兩方抓N個(gè)火柴,誰抓最后的棋子誰就贏.每次只能抓1或2個(gè)火柴,但不許不抓.試設(shè)計(jì)一程序,使計(jì)算機(jī)(甲)總是勝.二、算法解析不論N是奇數(shù)還是偶數(shù)，甲取火柴的原則是在甲取火柴之后，使余下的火柴是3的倍數(shù)，則對方就必然會輸。測試數(shù)據(jù)n=10

(1)computerfirst(2)youfirst:1

computerfirsttake=1

youtake=2

computertake=1

youtake=2

computertake=1

youtake=2

computertake=1

computerwin!programaa;usescrt;varn,m,a,r:integer;c:string;beginclrscr;repeatwrite('n=');readln(n);untiln>0;repeatwrite('(1)computerfirst(2)youfirst:');readln(r);until(r>0)and(r<3);c:='first';a:=0;randomize;ifr=2thenbeginwrite('you',c,'take=');readln(a);c:=''end;whilen>0dobeginn:=n-a;ifn=0thenbeginwriteln('youwin!');haltend;m:=nmod3;ifm=0thenm:=1+random(2);writeln('computer',c,'take=',m);n:=n-m;c:='';ifn<>0thenbeginwrite('youtake=');readln(a)end;end;writeln('computerwin!');end.不高興的津津(m2.pas)一、問題描述津津上初中了。媽媽認(rèn)為津津應(yīng)該更加用功學(xué)習(xí)，所以津津除了上學(xué)之外，還要參加?jì)寢尀樗龍?bào)名的各科復(fù)習(xí)班。另外每周媽媽還會送她去學(xué)習(xí)朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個(gè)小時(shí)就會不高興，而且上得越久就會越不高興。假設(shè)津津不會因?yàn)槠渌虏桓吲d，并且她的不高興不會持續(xù)到第二天。請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興。作業(yè)二【輸入】輸入包括七行數(shù)據(jù)，分別表示周一到周日的日程安排。每行包括兩個(gè)小于10的非負(fù)整數(shù)，用空格隔開，分別表示津津在學(xué)校上課的時(shí)間和媽媽安排她上課的時(shí)間?！据敵觥枯敵鲆恍?，這一行只包含一個(gè)數(shù)字。如果不會不高興則輸出0，如果會則輸出最不高興的是周幾（用1,2,3,4,5,6,7分別表示周一，周二，周三，周四，周五，周六，周日）。如果有兩天或兩天以上不高興的程度相當(dāng)，則輸出時(shí)間最靠前的一天?！緲永斎搿?3627253540406【樣例輸出】3算法解析解題方法：采用模擬。當(dāng)天不高興程度=當(dāng)天上午不高