NOIP復(fù)賽輔導(dǎo)-模擬法2012-09模擬法有些問題難以找到公式與規(guī)律來解決，只能依舊問題的敘述一步一步不停地做下去，才能最終得到結(jié)果。這樣的問題用計算機(jī)來模擬解決是最有效的。所以計算機(jī)模擬算法，即使程序完整的按題目所敘述的方式運行，最終得出答案。其實，模擬算法也就是將整個過程完完整整的走一遍。題目怎么敘述的，程序就怎么運行。

在C語言中,rand()函數(shù)可以用來產(chǎn)生隨機(jī)數(shù)，但是這不是真真意義上的隨機(jī)數(shù)，是一個偽隨機(jī)數(shù)，是根據(jù)一個數(shù)，我們稱它為種子為基準(zhǔn)以某個遞推公式推算出來的一系數(shù)。(1)C語言的偽隨機(jī)數(shù)函數(shù)

rand(x);rand()產(chǎn)生一個從0到32767之間的偽隨機(jī)數(shù)。使用本函數(shù)應(yīng)使用#include<stdlib.h>。我們常常用(rand()%N)這樣的一個表達(dá)式來產(chǎn)生一個從0~N-1之間的整數(shù)。（曾經(jīng)說過%是求余運算符）(2)隨機(jī)數(shù)初始化函數(shù)

randomize();

用一個time不斷變化的時間函數(shù)對隨機(jī)數(shù)函數(shù)發(fā)生器進(jìn)行初始化。因此使用本函數(shù)應(yīng)使用#include<time.h>。

常用rand()%N這樣的一個表達(dá)式來產(chǎn)生一個從0~N-1之間的整數(shù)。假設(shè)我們希望產(chǎn)生一個在A到B之間的隨機(jī)數(shù)(A<B)，則我們可以這樣寫隨機(jī)數(shù)生成的式子：x=rand()%(B-A+1)+A;x=rand()%B+1產(chǎn)生的隨機(jī)數(shù)x是在0到B之間的整數(shù);x=rand()%(B-A+1)+A產(chǎn)生的隨機(jī)數(shù)x是在A到B之間的整數(shù)。隨機(jī)數(shù)生成舉例:

(1)產(chǎn)生1至6的隨機(jī)整數(shù)rr=rand()%6+1;(2)產(chǎn)生2000至2050的隨機(jī)整數(shù)rr=rand()%51+2000

[探索]

請依據(jù)下面給出的條件寫出隨機(jī)數(shù)生成的式子。(1)產(chǎn)生100至999的隨機(jī)整數(shù)r

_____________________________

(2)產(chǎn)生10以內(nèi)的隨機(jī)奇數(shù)r_____________________________(3)產(chǎn)生100以內(nèi)被5整除的隨機(jī)整數(shù)r

___________________________________

例題1:模擬七選三的彩票中獎機(jī)率(1)先隨機(jī)產(chǎn)生三個從1到7的數(shù)a,b,c為彩票中獎號碼。(2)再隨機(jī)產(chǎn)生1000組選號x,y,z(3)統(tǒng)計中獎的選號有多少。#include<stdio.h>#include<stdlib.h>#include<time.h>main(){inta,b,c,x,y,z,j,p=0;clrscr();randomize();a=random(7)+1;b=random(7)+1;c=random(7)+1;for(j=1;j<=1000;j++){x=random(7)+1;y=random(7)+1;z=random(7)+1;if(x==a&&y==b&&z==c){p++;printf(“(%d)%d%d%d\n”,p,x,y,z);}}}第一題：歡樂同慶（文件名：hltq.c）過年了，小明與鄰居的小伙伴們共5個人相約一起放鞭炮：他們同時放響了第一個，隨后5個人分別以A1、A2、A3、A4、A5秒的間隔繼續(xù)放鞭炮，每人都放了b個。問：總共可聽到多少聲鞭炮響？輸入：A1、A2、A3、A4、A5(每個數(shù)≤30)和B(b≤30，并滿足An*b≤255)。輸出一個整數(shù)，即聽到的鞭炮響聲數(shù)。輸入輸出示例：輸入：12345（5個人放鞭炮的間隔）

4（每人放鞭炮數(shù)b）輸出：12第二題：

接水問題(water.c)【問題描述】學(xué)校里有一個水房，水房里一共裝有m個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的供水量相等，均為1?，F(xiàn)在有n名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1到n編號，i號同學(xué)的接水量為wi。接水開始時，1到m號同學(xué)各占一個水龍頭，并同時打開水龍頭接水。當(dāng)其中某名同學(xué)j完成其接水量要求Wj后，下一名排隊等候接水的同學(xué)k馬上接替j同學(xué)的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即j同學(xué)第x秒結(jié)束時完成接水，則k同學(xué)第x+1秒立刻開始接水。若當(dāng)前接水人數(shù)n不足m，則只有n個龍頭供水，其它m-n個龍頭關(guān)閉。現(xiàn)在給出n名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒?！据斎敫袷健康?行2個整數(shù)n和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。第2行n個整數(shù)w1、w2、……、wn，每兩個整數(shù)之間用一個空格隔開，wi表示i號同學(xué)的接水量。1≤n≤10000，1≤m≤100且m≤n；1≤wi≤100?！据敵龈袷健績H一行，1個整數(shù)，表示接水所需的總時間?！緲永斎搿?/p>

53

44121【樣例輸出】

4【算法分析】

這是一道典型的模擬題，設(shè)置a[i]為第i個水龍頭已經(jīng)輸出的水量，那么每次某個人去接水量為ｗ的水時，就是在所有a[i]中最小的一個里面加上ｗ，由此，對于每個人都重復(fù)這一過程，最后輸出所有a[i]里最大的一個就是結(jié)果。想一想，本題采用模擬法，于是有了加或者減的方法。1．減法（純粹模擬）2．加法（更優(yōu)模擬）注：減法時最好不要時間一點一點的模擬，找最小得數(shù)減。

第三題：花生采摘(peanuts.pas/dpr/c/cpp)【問題描述】魯賓遜先生有一只寵物猴，名叫多多。這天，他們兩個正沿著鄉(xiāng)間小路散步，突然發(fā)現(xiàn)路邊的告示牌上貼著一張小小的紙條：“歡迎免費品嘗我種的花生！—熊字”。魯賓遜先生和多多都很開心，因為花生正是他們的最愛。在告示牌背后，路邊真的有一塊花生田，花生植株整齊地排列成矩形網(wǎng)格（如圖1）。有經(jīng)驗的多多一眼就能看出，每棵花生植株下的花生有多少。為了訓(xùn)練多多的算術(shù)，魯賓遜先生說：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此類推，不過你一定要在我限定的時間內(nèi)回到路邊?！蔽覀兗俣ǘ喽嘣诿總€單位時間內(nèi)，可以做下列四件事情中的一件：1)從路邊跳到最靠近路邊（即第一行）的某棵花生植株；2)從一棵植株跳到前后左右與之相鄰的另一棵植株；3)采摘一棵植株下的花生；4)從最靠近路邊（即第一行）的某棵花生植株跳回路邊?，F(xiàn)在給定一塊花生田的大小和花生的分布，請問在限定時間內(nèi)，多多最多可以采到多少個花生？注意可能只有部分植株下面長有花生，假設(shè)這些植株下的花生個數(shù)各不相同。例如在圖2所示的花生田里，只有位于(2,5),(3,7),(4,2),(5,4)的植株下長有花生，個數(shù)分別為13,7,15,9。沿著圖示的路線，多多在21個單位時間內(nèi)，最多可以采到37個花生。【輸入文件】輸入文件peanuts.in的第一行包括三個整數(shù)，M,N和K，用空格隔開；表示花生田的大小為M*N（1<=M,N<=20），多多采花生的限定時間為K（0<=K<=1000）個單位時間。接下來的M行，每行包括N個非負(fù)整數(shù)，也用空格隔開；第i+1行的第j個整數(shù)Pij（0<=Pij<=500）表示花生田里植株(i,j)下花生的數(shù)目，0表示該植株下沒有花生?！据敵鑫募枯敵鑫募eanuts.out包括一行，這一行只包含一個整數(shù)，即在限定時間內(nèi)，多多最多可以采到花生的個數(shù)?！緲永斎?】672100000000000130000000070150000000090000000000【樣例輸出1】37【樣例輸入2】672000000000000130000000070150000000090000000000【樣例輸出2】28【算法分析】

乍一看此題，就會發(fā)現(xiàn)，窮舉、搜索的方法對此題都不適用，因為題目中已明確給出了摘豆子的規(guī)則。其實，我們只需要根據(jù)題目給出的規(guī)則，編程序模擬摘豆子的過程就可以了。首先，定義一個整型的二維數(shù)組a存儲每個格子中的豆子數(shù)目，然后進(jìn)行摘豆子。

設(shè)置一個二層循環(huán)求出含有最多豆子的格子的坐標(biāo)，由數(shù)學(xué)知識可知，從(x1,y1)到(x2,y2)需要的單位時間為|x1-x2|+|y1-y2|，因此由當(dāng)前位置（x，y）跳到含有最多豆子的格子（x1，y1）內(nèi)摘下豆子并回到路邊所需的時間為step=|x-x1|+|y-y1|+1+x1，接下來判斷step與剩余的時間p的大小關(guān)系。若step<=p則說明有足夠的時間去摘豆子，則去摘：具體步驟（剩余時間p：=p-|x-x1|+|y-y1|-1；當(dāng)前點的坐標(biāo)跳入（x1，y1）；摘下的總豆子數(shù)sum：=sum+a[x，y]，a[x，y]：=0；表示此格子內(nèi)的豆子已被摘沒）；若step>p，說明沒有足夠多的時間跳過去摘下豆子再回到路邊，因此只能回到路邊而不能去摘豆子了。

重復(fù)此摘法即可得出最后結(jié)果。

第二題：

接水問題(water.c)【問題描述】學(xué)校里有一個水房，水房里一共裝有m個龍頭可供同學(xué)們打開水，每個龍頭每秒鐘的供水量相等，均為1。現(xiàn)在有n名同學(xué)準(zhǔn)備接水，他們的初始接水順序已經(jīng)確定。將這些同學(xué)按接水順序從1到n編號，i號同學(xué)的接水量為wi。接水開始時，1到m號同學(xué)各占一個水龍頭，并同時打開水龍頭接水。當(dāng)其中某名同學(xué)j完成其接水量要求wj后，下一名排隊等候接水的同學(xué)k馬上接替j同學(xué)的位置開始接水。這個換人的過程是瞬間完成的，且沒有任何水的浪費。即j同學(xué)第x秒結(jié)束時完成接水，則k同學(xué)第x+1秒立刻開始接水。若當(dāng)前接水人數(shù)n不足m，則只有n個龍頭供水，其它m?n個龍頭關(guān)閉?，F(xiàn)在給出n名同學(xué)的接水量，按照上述接水規(guī)則，問所有同學(xué)都接完水需要多少秒?！据斎敫袷健康?行2個整數(shù)n和m，用一個空格隔開，分別表示接水人數(shù)和龍頭個數(shù)。第2行n個整數(shù)w1、w2、……、wn，每兩個整數(shù)之間用一個空格隔開，wi表示i號同學(xué)的接水量。1≤n≤10000，1≤m≤100且m≤n；1≤wi≤100。【輸出格式】僅一行，1個整數(shù)，表示接水所需的總時間?！?/p>