枚舉與模擬算法1枚舉與模擬算法1在前面幾章中我們用到了整型、實型、布爾型、字符型的數據。以上數據類型是由pascal規(guī)定的標準數據類型，只要寫integer、real、boolean、char，pascal編譯系統就能識別并按這些類型來處理。pascal還允許用戶定義一些類型，這是其它一些語言所沒有的，這就使得pascal使用靈活、功能豐富。編程是解決日常生活中所有問題，如加油站系統，超市購物系統，學校自助充電系統、學校的自助購買飲料系統等等，用以上學習知識就不能解決了？？？在前面幾章中我們用到了整型、實型、布爾型、字符型的數據。以上2一、枚舉類型隨著計算機的不斷普及，程序不僅只用于數值計算，還更廣泛地用于處理非數值的數據。例如：性別、月份、星期幾、顏色、單位名、學歷、職業(yè)等，都不是數值數據。在其它程序設計語言中，一般用一個數值來代表某一狀態(tài)，這種處理方法不直觀，易讀性差。如果能在程序中用自然語言中有相應含義的單詞來代表某一狀態(tài)，則程序就很容易閱讀和理解。也就是說，事先考慮到某一變量可能取的值，盡量用自然語言中含義清楚的單詞來表示它的每一個值，這種方法稱為枚舉方法，用這種方法定義的類型稱枚舉類型。枚舉類型是一種很有實用價值的數據類型，它是pascal一項重要創(chuàng)新。一、枚舉類型隨著計算機的不斷普及，程序不僅只用于數值計算，還3枚舉類型的定義:枚舉類型是一種自定義類型，要使用枚舉類型當然也要先說明枚舉類型，枚舉類型的一般格式：type <枚舉類型標識符>=(<標識符1>,<標識符2>,……<標識符n>)；

var <枚舉類型變量表>:<枚舉類型標識符>枚舉類型的定義:枚舉類型是一種自定義類型，要使用枚舉類型當然4說明：①括號中的每一個標識符都稱為枚舉元素或枚舉常量②定義枚舉類型時列出的所有枚舉元素構成了這種枚舉類型的值域（取值范圍），也就是說，該類型的變量所有可能的取值都列出了③枚舉元素只能是標識符（除系統標識符），不能是數值常量和字符常量例如，下列類型定義是合法的：

typedays=(sun,mon,tue,wed,thu,fri,sat);colors=(red,yellow,blue,white,black,green);

而下列類型定義是錯誤的(因為枚舉元素非標識符):typecolortype=('red','yellow','blue','white');

numbers=(1,3,5,7,9);

ty=(for,do,while);說明：①括號中的每一個標識符都稱為枚舉元素或枚舉常量5枚舉類型變量：定義了枚舉類型，就可以把某些變量說明成該類型。如：

varholiday,workday:day;

incolor:colors;

也可以把變量的說明與類型的定義合并在一起,如:varholiday,workday:(sun,mon,tue,wed,thu,fri,sat);

incolor:(red,yellow,blue,white,black,green);枚舉類型變量：定義了枚舉類型，就可以把某些變量說明成該類型。6枚舉類型的性質：１、枚舉類型屬于順序類型 根據定義類型時各枚舉元素的排列順序確定它們的序號，第一個枚舉元素的序號為0。例如：設有定義

typedays=(sun,mon,tue,wed,thu,fri,sat);則:ord(sun)=0,ord(mon)=1,ord(sat)=6;succ(sun)=mon,succ(mon)=tue,succ(fri)=sat;pred(mon)=sun,pred(tue)=mon,pred(sat)=fri。應注意的是：枚舉類型中的第一個元素無前趨，最后一個元素無后繼，卻pred(sun)和succ(sat)皆是錯誤的枚舉類型的性質：１、枚舉類型屬于順序類型7枚舉類型的性質2：對枚舉類型只能進行賦值運算和關系運算：一旦定義了枚舉類型及這種類型的變量，則在語句部分只能對枚舉類型變量賦值，或進行關系運算，不能進行算術運算和邏輯運算。在枚舉元素比較時，實際上是對其序號的比較。當然，賦值或比較時，應注意類型一致。例如，設程序有如下說明：

typedays=(sun,mon,tue,wed,thu,fri,sat);

colors=(red,yellow,blue,white,black,green);

varcolor:colors;

weekday:days;則下列語句是合法的:

weekday:=mon;

ifweekday=sunthenwrite('rest');

weekday<>sun

而下面語句是不合法的:

mon:=weekday;

mon:=1;

ifweekday=sunorsatthenwrite('rest');

sun>red

weekday<>color枚舉類型的性質2：對枚舉類型只能進行賦值運算和關系運算：一旦8枚舉類型的性質3：枚舉變量的值只能用賦值語句來獲得也就是說，不能用read(或readln)讀一個枚舉型的值。同樣，也不能用write(或writeln)輸出一個枚舉型的值。如write(red)是非法的，會發(fā)生編譯錯誤。千萬不要誤認為，該語句的結果是輸出"red"三個字符。但對枚舉數據的輸入與輸出可通過間接方式進行。輸入時，一般可輸入一個代碼，通過程序進行轉換，輸出時，也只是打印出與枚舉元素相對應的字符串。這在后面的例題中將有使用示例。枚舉類型的性質3：枚舉變量的值只能用賦值語句來獲得9枚舉類型的性質4同一個枚舉元素不能出現在兩個或兩個以上的枚舉類型定義中，如：typecolor1=(red,yellow,white);

color2=(blue,red,black);是不允許的，因為red屬于兩個枚舉類型。枚舉類型的性質4同一個枚舉元素不能出現在兩個或兩個以上的枚舉10枚舉類型的應用：【問題描述】

暑假期間數學老師布置了一道有趣的題目，意思是：九頭鳥(傳說中的一種怪鳥，它有九個頭、兩只腳)、雞和兔子關在一個籠子里。數數它們的頭正好是100，數數它們的腳也正好是100。老師讓學生編程計算其中九頭鳥、雞和兔子各有多少只？你能幫助他嗎？

【輸出格式】

共三個數，分別表示九頭鳥、雞和兔子的只數。枚舉類型的應用：【問題描述】

暑假期間數學老師布置了11動手完成數學建模!動手完成數學建模!12一．問題的簡單分析

基本題意與已知條件，設九頭鳥有M只，雞有N只，兔子有K只，則有：

9M+N+K=100（1）

2M+2N+4K=100（2）

題目的要求就是要找出符合條件的M、N和L。該如何入手來解決這個問題呢？

一．問題的簡單分析

基本題意與已知條件，設九頭鳥有M13二．算法：直接枚舉三個變量

由于M、N和K的變化范圍都是1～100，因此，可以采用枚舉法的思想與做法，讓M、N和K分別從1變化到100，看看它們的每一組取值是否能滿足上面兩個等式的要求。如果滿足要求，則將M、N、K的值打印出來；否則，繼續(xù)枚舉。二．算法：直接枚舉三個變量

由于M、N和K的變化14主要程序段如下：

t:=0{記錄共有多少組滿足條件的數據}

form:=1to100do{枚舉各種可能的取值}

forn:=1to100do

fork:=1to100do

if(9*m+n+k=100)and(2*m+2*n+4*k=100)then

begin

writeln(m,’’,n,’’,k);

t:=t+1；

end;

writeln(t);

主要程序段如下：

15有沒有其它好的辦法？思考！有沒有其它好的辦法？思考！16三．算法：縮小變量的枚舉范圍

仍然采用枚舉法，只是先做一些預先的分析，從而可以達到一定的優(yōu)化效果。由題意可知：如果100個頭都是九頭鳥的話，那九頭鳥最多有？只；如果100只腳都是雞的話，則最多有？只雞。同理，兔子最多有？

只。如果100個頭都是九頭鳥的話，那九頭鳥最多有100div9=11只；如果100只腳都是雞的話，則最多有50只雞。同理，兔子最多有25只。三．算法：縮小變量的枚舉范圍

仍然采用枚舉法，只17主要程序段如下：

t:=0;

form:=1to11do

forn:=1to50do

fork:=1to25do

if(9*m+n+k=100)and(2*m+2*n+4*k=100)then

beginwriteln(m,’’,n,’’,k);

t:=t+1

end;

writeln(t);主要程序段如下：

t:=0;

form:=1to18有沒有其它更好的辦法？思考！在上面的算法里，采用的是縮短循環(huán)變量的初值和終值之間距離的方法，來減少循環(huán)的次數，以減少程序的運行時間。信息學的最高境界：更少、更快、更優(yōu)！有沒有其它更好的辦法？思考！在上面的算法里，采用19三．算法：減少枚舉的變量（2個）

由上面算法可知，雞的循環(huán)變量范圍最大，最值得進一步優(yōu)化以縮小其取值范圍。根據等式(1)，將N用M和K來表示，得到：

N=100-9M-K(3)

這樣一來，就又可以做進一步的優(yōu)化了：將原來的三重循環(huán)降低到了兩重循環(huán)(減少了一個循環(huán)變量)。

但是，(3)式根據M和L計算出來的N值可能會出現負數，這是不允許的。所以，在循環(huán)體中判斷(2)式是否成立時，還要加上N>0

這一條件。三．算法：減少枚舉的變量（2個）

由上面算法可知，雞的20主要程序段如下：

t:=0;

form:=1to11do

fork:=1to25do

begin

n:=100-9*m-k

if(n>0)and(2*m+2*n+4*k=100)then

beginwriteln(m,’’,n,’’,k);

t:=t+1;end;

end;

writeln(t);

主要程序段如下：

t:=0;

for21有沒有其它更好的辦法？思考！信息學的最高境界：更少、更快、更優(yōu)！有沒有其它更好的辦法？思考！信息學的最高境界：更少、更快、更22四．算法4：減少枚舉的變量（1個）

進一步的優(yōu)化，消去N9M+N+K=100（1）推出N=100-K-9M代入（2）式2M+2N+4K=100（2）

得到：16M–2K=100

整理上式可得：K=8M–50(4)這樣就可以將兩重循環(huán)進一步簡化成一重循環(huán)。但是，(4)式由M計算出來的L也可能會出現負數，這是不允許的，故在循環(huán)體中要加上K>0的條件。

表達式(4)應寫在表達式(3)的前面，即必須先求出K，才能求n。四．算法4：減少枚舉的變量（1個）

進一步的優(yōu)化，消23主要程序段如下：

t:=0;

form:=1to11do

begin

k:=8*m–50;

n:=100-9*m-k;

if(k>0)and(n>0)then

beginwriteln(m,’’,n,’’,k);

t:=t+1;end;

end;

writeln(t);主要程序段如下：

t:=0;

form:=1to24上面的四種算法都能給出正確的結果，但所需循環(huán)次數分別是100*100*100、11*50*25、11*25、11次，通過一系列優(yōu)化措施，以及將不必要的循環(huán)去掉，使得程序的效率不斷地提高。總結：提高枚舉法效率的方法有：

1）在算式長值不變的情況下，減少循環(huán)變量的初值和終值的差距；

2）在初值、終值不變的情況下，增大算式長；

3）減少循環(huán)嵌套的層數。

具體使用時，應根據題目的條件，靈活運用。上面的四種算法都能給出正確的結果，但所需循環(huán)次數25【例2】：巧妙填數將1～9這九個數字填入九個空格中。每一橫行的三個數字組成一個三位數。如果要使第二行的三位數是第一行的兩倍,第三行的三位數是第一行的三倍,應怎樣填數。1923845761.枚舉算法策略26【例2】：巧妙填數將1～9這九個數字填入九個空格中【算法分析】9個格子,不考慮問題給出的條件，共有9!=362880中方案。通過分析，第一行的3位數不會大于400；確定第一行的數，可以根據條件算出其他兩行的數嗎？通過限定條件：枚舉400次就可以求解。1.枚舉算法策略【算法分析】9個格子,不考慮問題給出的條件，共有9!=36227programqmts;vari,j,k,s:integer;functionsum(s:integer):integer;beginsum:=sdiv100+sdiv10mod10+smod10end;functionmul(s:integer):longint;beginmul:=(sdiv100)*(sdiv10mod10)*(smod10)end;【參考程序】programqmts;【參考程序】28beginfori:=1to3doforj:=1to9doifj<>ithen fork:=1to9do begin s:=i*100+j*10+k; if3*s<1000then if(sum(s)+sum(2*s)+sum(3*s)=45)and(mul(s)*mul(2*s)*mul(3*s)=362880)then begin writeln(s); writeln(2*s);

writeln(3*s); writeln; end;end; end.【參考程序】begin【參考程序】292.模擬算法策略模擬法：有些問題的描述和解決方法已經很清楚，只需要按照描述去一步一步的執(zhí)行即可，這種方法就是計算機解決問題的一種最普遍最直接的方法------模擬法。

模擬法并不是程序，只是我們依賴計算機的運算速度解決問題的一種方法或模式，針對具體問題要設計具體的程序。

模擬法適用于問題求解清晰、運算規(guī)模較小的問題。如果問題求解的時空代價很大，就要考慮是否有其它更好的解決方案。2.模擬算法策略模擬法：30例題1、酗酒的獄警。某監(jiān)獄里有個很長的走廊，走廊中一個接一個地有n個房間。每個房間中鎖著一個犯人。一天夜里，獄警決定玩一個無聊的游戲。第一輪中，他喝了一口威士忌，然后打開每個房間。第2輪，他喝了一口威士忌，然后按2的倍數遍歷每個房間。第3輪，他又喝了一口威士忌，遍歷所有3的倍數的房間，以此類推。在遍歷中，如果房間是鎖著的，則打開；否則鎖上。他這樣重復n輪，最后醉酒。這時有些囚犯看到自己的房間所被打開了，他們立即逃跑。對于有n個房間的走廊，最終會有多少個囚犯逃脫？例題1、酗酒的獄警。某監(jiān)獄里有個很長的走廊，走廊中一個接一個31programyujing;varnum,s,n,m,i,k,j:integer;

a:array[0..200]ofboolean;begin

readln(num);

fori:=1tonumdo

begin

readln(n);

fillchar(a,sizeof(a),true);

forj:=1tondo

fork:=1tondo

ifkmodj=0

thena[k]:=nota[k];

s:=0;

forj:=1tondo

ifa[j]=falsetheninc(s);

writeln('thelastis:',s);

end;end.programyujing;322.模擬算法策略【例2】：有一個圓盤，盤內存有36個槽，當一個小球在盤內滾動時，可能落入任一槽內，這些槽的編號分別為1-36，其中槽號為奇數時為紅色，槽號為偶數時為黃色，編一個程序模擬球滾動100次，計算落入每個槽中的次數及落入紅槽、黃槽各有多少次。算法分析：數組a[1]…a[36]落入每個槽中的次數；X：隨機落入槽號T:落入黃槽的次數S：落入紅槽的次數X:=random(36)+12.模擬算法策略【例2】：有一個圓盤，盤內存有36個槽，當33【參考程序】programmoni1;vara:array[1..36]ofinteger;x,t,s,i:integer;f:boolean;beginrandomize;t:=0;s:=0;fori:=1to36doa[i]:=0;fori:=1to36do beginx:=random(36)+1;f:=odd(x);iffthens:=s+1elset:=t+1; a[x]:=a[x]+1;end;fori:=1to36dowriteln(i,a[i]:5); writeln('red=',s,'yelllow=',t);end.【參考程序】programmoni1;fori:=1t34例3、分發(fā)糖果。一些學生圍繞老是坐著，每人手里都有偶數個糖。現在老師吹一聲哨子，所有同學同時將自己的一半糖果給他右邊的同學，如果某個同學手里的糖果個數是奇數，則老師給他一個糖果，重復這個過程直到所有同學手中的糖果數一致。寫一個程序判斷老師要吹多少下哨子，每人手中的糖果數才能一致，并給出結束后每人手里的糖果數。例3、分發(fā)糖果。一些學生圍繞老是坐著，每人手里都有偶數個糖。35programfatang;

constmaxn=100000;

typearr=array[0..maxn]