枚舉法、模擬法

1、專題一、枚舉法：所謂枚舉法，指的是從可能的解的集合中一一枚舉各元素，用題目給定的檢驗條件判定哪些是無用的，哪些是有用的，能使命題成立的就是正確的解。例0、最長公共子串（noi93第一題）文件名string.pas, string.in. string.out求N個字符串的最長公共子串，N20，字符串長度不超255。例如N3，由文件依次輸入3個字符串為What is locla bus ?Name some local buses .local bus is a high speed I/Obus close to the processor .則最長公共子串為“l(fā)ocal bus”長度為9輸入

2、：3What is local bus ?Name some local buses .local bus is a high speed I/Obus close to the processor .輸出：9例1、 斷開的項鏈（ioi93t1 usacogate/broken necklace）文件名necklace.pas,necklace.in,necklace.out有一條n（3<n<350）個珠子穿成的項鏈，珠子有紅（red）、藍(lán)（blue）、白（white）三種顏色，分別使用字母r,b,w來代表。如圖所示： 1 2 1 2 r b b r b r r b r b b b

3、 r r b r r r w r b r w w b b r r b b b b b b r b r r b r b r r r b r r r r r r b r b r r r w Figure A Figure B項鏈可以從某一個位置斷開，然后從斷開的位置沿著兩個方向收集珠子。相同顏色的珠子能被收集到一塊，白色的珠子能和藍(lán)色的收集成一堆也能和紅色的收集成一堆。問題：給定一個項鏈，問從哪里斷開收集的珠子總個數(shù)最多。輸入樣例：（第一行是一個數(shù)字，表示項鏈中的珠子數(shù)；第二行是每個珠子顏色）29wwwbbrwrbrbrrbrbrwrwwrbwrwrrb輸出樣例：（輸出結(jié)果是最多收集的珠子個數(shù)）1

4、1例2、Prime Palindromes 回文質(zhì)數(shù)pprime.pas因為151即是一個質(zhì)數(shù)又是一個回文數(shù)(從左到右和從右到左是看一樣的)，所以 151 號是回文質(zhì)數(shù)。寫一個程序來找出范圍a,b(5 <= a < b <= 100,000,000)間的所有回文質(zhì)數(shù);輸入格式：第 1 行: 二個整數(shù) a 和 b .樣例輸入pprime.in5 500輸出格式：輸出一個回文質(zhì)數(shù)的列表，一行一個。樣例輸出：file pprime.out5711101131151181191313353373383例3：一元三次方程求解equation.pas/equation.in/equati

5、on.out問題描述有形如：ax3+bx2+cx+d=0 這樣的一個一元三次方程。給出該方程中各項的系數(shù)(a，b，c，d 均為實(shí)數(shù))，并約定該方程存在三個不同實(shí)根(根的范圍在-100至100之間)，且根與根之差的絕對值>=1。要求由小到大依次在同一行輸出這三個實(shí)根(根與根之間留有空格)，并精確到小數(shù)點(diǎn)后2位。提示：記方程f(x)=0，若存在2個數(shù)x1和x2，且x1<x2，f(x1)*f(x2)<0，則在(x1，x2)之間一定有一個 根。樣例輸入：1 -5 -4 20輸出：-2.00 2.00 5.00例4：最大公約數(shù)與最小公倍數(shù)問題 gcdlcm.pas/gcdlcm.in/

6、gcdlcm.out問題描述 輸入二個正整數(shù)x0,y0(2x0100000，2y01000000)，求出滿足下列條件的P、Q的個數(shù)。 條件:1.P、Q是正整數(shù) 2要求P、Q以x0為最大公約數(shù)，以y0為最小公倍數(shù)。 試求，滿足條件的所有可能的兩個正整數(shù)的個數(shù)。樣例 輸入：x0=3 y0=60 輸出：4 說明：(不用輸出)此時的 P Q 分別為， 3 60 15 12 12 15 60 3所以，滿足條件的所有可能的兩個正整數(shù)的個數(shù)共4種。專題二、模擬法：在自然界和日常生活中，許多現(xiàn)象具有不確定的性質(zhì)，有些問題甚至很難建立數(shù)學(xué)模型，或者很難用計算機(jī)建立地推、遞歸、枚舉、回溯等算法。在這種情況下，一般

7、采用模擬策略。所謂模擬策略就是模擬某個過程，通過改變數(shù)學(xué)模型的各種參數(shù)，進(jìn)而觀察變更這些參數(shù)引起的過程狀態(tài)的變化，由此展開算法。編程的人可以按照題意設(shè)計的方法進(jìn)行模擬，觀察模擬過程中參數(shù)變化和過程狀態(tài)的變化，模擬效果取決于過程模擬的真實(shí)性和算法的正確性。這一類題目在編程時要注意考慮問題的全面性，不能疏忽特殊條件、邊界條件等。例1：津津的儲蓄計劃(save.pas)【問題描述】津津的零花錢一直都是自己管理。每個月的月初媽媽給津津300元錢，津津會預(yù)算這個月的花銷，并且總能做到實(shí)際花銷和預(yù)算的相同。為了讓津津?qū)W習(xí)如何儲蓄，媽媽提出，津津可以隨時把整百的錢存在她那里，到了年末她會加上20%還給津津。

8、因此津津制定了一個儲蓄計劃：每個月的月初，在得到媽媽給的零花錢后，如果她預(yù)計到這個月的月末手中還會有多于100元或恰好100元，她就會把整百的錢存在媽媽那里，剩余的錢留在自己手中。例如11月初津津手中還有83元，媽媽給了津津300元。津津預(yù)計11月的花銷是180元，那么她就會在媽媽那里存200元，自己留下183元。到了11月月末，津津手中會剩下3元錢。津津發(fā)現(xiàn)這個儲蓄計劃的主要風(fēng)險是，存在媽媽那里的錢在年末之前不能取出。有可能在某個月的月初，津津手中的錢加上這個月媽媽給的錢，不夠這個月的原定預(yù)算。如果出現(xiàn)這種情況，津津?qū)⒉坏貌辉谶@個月省吃儉用，壓縮預(yù)算?，F(xiàn)在請你根據(jù)2004年1月到12月每個月

9、津津的預(yù)算，判斷會不會出現(xiàn)這種情況。如果不會，計算到2004年年末，媽媽將津津平常存的錢加上20%還給津津之后，津津手中會有多少錢?！据斎胛募枯斎胛募ave.in包括12行數(shù)據(jù)，每行包含一個小于350的非負(fù)整數(shù)，分別表示1月到12月津津的預(yù)算?！据敵鑫募枯敵鑫募ave.out包括一行，這一行只包含一個整數(shù)。如果儲蓄計劃實(shí)施過程中出現(xiàn)某個月錢不夠用的情況，輸出-X，X表示出現(xiàn)這種情況的第一個月；否則輸出到2004年年末津津手中會有多少錢?！緲永斎?】29023028020030017034050908020060【樣例輸出1】-7【樣例輸入2】290230280200300170330

10、50908020060【樣例輸出2】1580例2：貪婪的送禮者(Greedy Gift Giver)對于一群要互送禮物的朋友，你要確定每個人送出的禮物比收到的多多少(and vice versa for those who view gift giving with cynicism)。在這一個問題中，每個人都準(zhǔn)備了一些錢來送禮物，而這些錢將會被平均分給那些將收到他的禮物的人。然而，在任何一群朋友中，有些人將送出較多的禮物(可能是因為有較多的朋友)，有些人有準(zhǔn)備了較多的錢。給出一群朋友， 沒有人的名字會長于 14 字符，給出每個人將花在送禮上的錢，和將收到他的禮物的人的列表，請確定每個人收到的

11、比送出的錢多的數(shù)目。 PROGRAM NAME: gift1 INPUT FORMAT 第 1 行: 人數(shù)NP,2<= NP<=10 第 2到 NP+1 行: 這NP個在組里人的名字一個名字一行第NP2到最后： 這里的NP段內(nèi)容是這樣組織的：第一行是將會送出禮物人的名字。第二行包含二個數(shù)字:第一個是原有的錢的數(shù)目（在0到2000的范圍里），第二個NGi是將收到這個送禮者禮物的人的個數(shù) 如果 NGi 是非零的, 在下面 NGi 行列出禮物的接受者的名字，一個名字一行。 SAMPLE INPUT (file gift1.in) 5davelauraowenvickamrdave200

12、3lauraowenvickowen500 1daveamr150 2vickowenlaura0 2amrvickvick0 0 OUTPUT FORMAT 輸出 NP 行每行是一個的名字加上空格再加上收到的比送出的錢多的數(shù)目。對于每一個人，他名字的打印順序應(yīng)和他在輸入的2到NP1行中輸入的順序相同。所有的送禮的錢都是整數(shù)。每個人把相同數(shù)目的錢給每位要送禮的朋友，而且盡可能多給，不能給出的錢被送禮者自己保留。 SAMPLE OUTPUT (file gift1.out) dave 302laura 66owen -359vick 141amr -150例3：題一、乒乓球（Table.pas）

13、【問題背景】國際乒聯(lián)現(xiàn)在主席沙拉拉自從上任以來就立志于推行一系列改革，以推動乒乓球運(yùn)動在全球的普及。其中11分制改革引起了很大的爭議，有一部分球員因為無法適應(yīng)新規(guī)則只能選擇退役。華華就是其中一位，他退役之后走上了乒乓球研究工作，意圖弄明白11分制和21分制對選手的不同影響。在開展他的研究之前，他首先需要對他多年比賽的統(tǒng)計數(shù)據(jù)進(jìn)行一些分析，所以需要你的幫忙。【問題描述】華華通過以下方式進(jìn)行分析，首先將比賽每個球的勝負(fù)列成一張表，然后分別計算在11分制和21分制下，雙方的比賽結(jié)果（截至記錄末尾）。比如現(xiàn)在有這么一份記錄，（其中W表示華華獲得一分，L表示華華對手獲得一分）：WWWWWWWWWWWWW

14、WWWWWWWWWLW在11分制下，此時比賽的結(jié)果是華華第一局11比0獲勝，第二局11比0獲勝，正在進(jìn)行第三局，當(dāng)前比分1比1。而在21分制下，此時比賽結(jié)果是華華第一局21比0獲勝，正在進(jìn)行第二局，比分2比1。如果一局比賽剛開始，則此時比分為0比0。你的程序就是要對于一系列比賽信息的輸入（WL形式），輸出正確的結(jié)果?！据斎敫袷健棵總€輸入文件包含若干行字符串（每行至多20個字母），字符串有大寫的W、L和E組成。其中E表示比賽信息結(jié)束，程序應(yīng)該忽略E之后的所有內(nèi)容?！据敵龈袷健枯敵鲇蓛刹糠纸M成，每部分有若干行，每一行對應(yīng)一局比賽的比分（按比賽信息輸入順序）。其中第一部分是11分制下的結(jié)果，第二部分

15、是21分制下的結(jié)果，兩部分之間由一個空行分隔?！据斎霕永縒WWWWWWWWWWWWWWWWWWWWWLWE【輸出樣例】11:011:01:121:02:1例4：題一 均分紙牌playcard.pas/playcard.in/playcard.out問題描述有 N 堆紙牌，編號分別為 1，2，, N。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)?？梢栽谌我欢焉先∪粲趶埣埮?，然后移動。移牌規(guī)則為：在編號為 1 堆上取的紙牌，只能移到編號為 2 的堆上；在編號為 N 的堆上取的紙牌，只能移到編號為 N-1 的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動

16、次數(shù)使每堆上紙牌數(shù)都一樣多。例如 N=4，4 堆紙牌數(shù)分別為：98176移動3次可達(dá)到目的：從 取 4 張牌放到 （9 8 13 10） -> 從 取 3 張牌放到 （9 11 10 10）-> 從 取 1 張牌放到（10 10 10 10）。輸 入：鍵盤輸入文件名。文件格式：N（N 堆紙牌，1 <= N <= 100）A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l<= Ai <=10000）輸 出：輸出至屏幕。格式為：所有堆均達(dá)到相等時的最少移動次數(shù)。輸入輸出樣例a.in：49 8 17 6屏慕顯示：3例5：神經(jīng)網(wǎng)絡(luò)【問題背景】 人工神經(jīng)網(wǎng)絡(luò)（Arti

17、ficial Neural Network）是一種新興的具有自我學(xué)習(xí)能力的計算系統(tǒng)，在模式識別、函數(shù)逼近及貸款風(fēng)險評估等諸多領(lǐng)域有廣泛的應(yīng)用。對神經(jīng)網(wǎng)絡(luò)的研究一直是當(dāng)今的熱門方向，蘭蘭同學(xué)在自學(xué)了一本神經(jīng)網(wǎng)絡(luò)的入門書籍后，提出了一個簡化模型，他希望你能幫助他用程序檢驗這個神經(jīng)網(wǎng)絡(luò)模型的實(shí)用性。【問題描述】 在蘭蘭的模型中，神經(jīng)網(wǎng)絡(luò)就是一張有向圖，圖中的節(jié)點(diǎn)稱為神經(jīng)元，而且兩個神經(jīng)元之間至多有一條邊相連，下圖是一個神經(jīng)元的例子： 神經(jīng)元編號為1） 圖中，X1X3是信息輸入渠道，Y1Y2是信息輸出渠道，C1表示神經(jīng)元目前的狀態(tài)，Ui是閾值，可視為神經(jīng)元的一個內(nèi)在參數(shù)。 神經(jīng)元按一定的順序排列，構(gòu)成

18、整個神經(jīng)網(wǎng)絡(luò)。在蘭蘭的模型之中，神經(jīng)網(wǎng)絡(luò)中的神經(jīng)無分為幾層；稱為輸入層、輸出層，和若干個中間層。每層神經(jīng)元只向下一層的神經(jīng)元輸出信息，只從上一層神經(jīng)元接受信息。下圖是一個簡單的三層神經(jīng)網(wǎng)絡(luò)的例子。蘭蘭規(guī)定，Ci服從公式：（其中n是網(wǎng)絡(luò)中所有神經(jīng)元的數(shù)目） 公式中的Wji（可能為負(fù)值）表示連接j號神經(jīng)元和 i號神經(jīng)元的邊的權(quán)值。當(dāng) Ci大于0時，該神經(jīng)元處于興奮狀態(tài)，否則就處于平靜狀態(tài)。當(dāng)神經(jīng)元處于興奮狀態(tài)時，下一秒它會向其他神經(jīng)元傳送信號，信號的強(qiáng)度為Ci。 如此在輸入層神經(jīng)元被激發(fā)之后，整個網(wǎng)絡(luò)系統(tǒng)就在信息傳輸?shù)耐苿酉逻M(jìn)行運(yùn)作?，F(xiàn)在，給定一個神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（Ci），要求你的程序運(yùn)算出最后網(wǎng)絡(luò)輸出層的狀態(tài)?！据斎敫袷健枯斎胛募谝恍惺莾蓚€整數(shù)n（1n20）和p。接下來n行，每行兩個整數(shù)，第i1行是神經(jīng)元i最初狀態(tài)和其閾值（Ui），非輸入層的神經(jīng)元開始時狀態(tài)必然為0。再下面P行，每行由兩個整數(shù)i，j及一個整數(shù)Wi