信息學(xué)奧賽教程指導(dǎo)

1、上海市控江中學(xué)上海市控江中學(xué) 王建德王建德6 6、20022002、20032003年分區(qū)聯(lián)賽復(fù)賽試年分區(qū)聯(lián)賽復(fù)賽試題解析題解析1 1、高精度運算、高精度運算2 2、圖的運算、圖的運算3 3、搜索算法、搜索算法4 4、構(gòu)造算法、構(gòu)造算法5 5、動態(tài)程序設(shè)計、動態(tài)程序設(shè)計題題 型型題題 目目與課內(nèi)知識相關(guān)與課內(nèi)知識相關(guān)自由落體、級數(shù)求和、乒乓球、自由落體、級數(shù)求和、乒乓球、麥森數(shù)麥森數(shù) 字符串處理字符串處理字符近似查找字符近似查找貪心法貪心法均分紙牌、傳染病控制均分紙牌、傳染病控制 回溯法回溯法選數(shù)、字串變換、棧、神經(jīng)網(wǎng)絡(luò)、選數(shù)、字串變換、棧、神經(jīng)網(wǎng)絡(luò)、偵探推理偵探推理 動態(tài)程序設(shè)計方法動態(tài)程序

2、設(shè)計方法過河卒、數(shù)字游戲、加分二叉樹過河卒、數(shù)字游戲、加分二叉樹 幾何計算幾何計算矩形覆蓋矩形覆蓋 雖然雖然2002、2003年全國奧林匹克信息學(xué)復(fù)賽中含許多可年全國奧林匹克信息學(xué)復(fù)賽中含許多可“一題多解一題多解” 的試題，但如果按照較優(yōu)算法標(biāo)準(zhǔn)分類的話，大致的試題，但如果按照較優(yōu)算法標(biāo)準(zhǔn)分類的話，大致可分為可分為 1、凸現(xiàn)信息學(xué)知識和學(xué)科知識整合的趨勢凸現(xiàn)信息學(xué)知識和學(xué)科知識整合的趨勢。為了考核學(xué)生運用學(xué)科知識的能力，激發(fā)學(xué)生為了考核學(xué)生運用學(xué)科知識的能力，激發(fā)學(xué)生的創(chuàng)造力，的創(chuàng)造力，2002、2003年全國奧林匹克信息聯(lián)年全國奧林匹克信息聯(lián)賽賽(NOIP)中學(xué)科類的試題增加，并且首次出現(xiàn)中

3、學(xué)科類的試題增加，并且首次出現(xiàn)了計算幾何類的試題了計算幾何類的試題。這說明信息學(xué)與學(xué)。這說明信息學(xué)與學(xué)科的依賴關(guān)系日益凸現(xiàn)，學(xué)科基礎(chǔ)好、尤其是科的依賴關(guān)系日益凸現(xiàn)，學(xué)科基礎(chǔ)好、尤其是數(shù)學(xué)素質(zhì)好的人雖然不一定會編程，但希望學(xué)數(shù)學(xué)素質(zhì)好的人雖然不一定會編程，但希望學(xué)習(xí)編程的人愈來愈多；編程解題能力強的人勢習(xí)編程的人愈來愈多；編程解題能力強的人勢必有數(shù)學(xué)的潛質(zhì)和愛好，他們中愈來愈多的人必有數(shù)學(xué)的潛質(zhì)和愛好，他們中愈來愈多的人也希望深造數(shù)學(xué)。各門學(xué)科的交融和整合是奧也希望深造數(shù)學(xué)。各門學(xué)科的交融和整合是奧林匹克信息學(xué)聯(lián)賽活動發(fā)展的一個大趨勢林匹克信息學(xué)聯(lián)賽活動發(fā)展的一個大趨勢（按照（按照2005年國家

4、教改方案，數(shù)學(xué)教材增加算法內(nèi)容，信息科技教材摻入語言知年國家教改方案，數(shù)學(xué)教材增加算法內(nèi)容，信息科技教材摻入語言知識）。識）。2、“構(gòu)造法構(gòu)造法” 或貪心策略類試題的引或貪心策略類試題的引入，使得入，使得算法知識的不確定性和不穩(wěn)定算法知識的不確定性和不穩(wěn)定性增加。性增加。這正體現(xiàn)了科學(xué)的本質(zhì)這正體現(xiàn)了科學(xué)的本質(zhì)知識知識是不斷推陳出新的。是不斷推陳出新的。3、試題的綜合性增加試題的綜合性增加，并不一定隨知，并不一定隨知識的分類而發(fā)生變化，有時幾乎找不識的分類而發(fā)生變化，有時幾乎找不到一個單一的經(jīng)典算法到一個單一的經(jīng)典算法，也找不到一個純粹的數(shù)據(jù)結(jié)，也找不到一個純粹的數(shù)據(jù)結(jié)構(gòu)問題構(gòu)問題，關(guān)鍵是你從

5、哪個角度去分析，關(guān)鍵是你從哪個角度去分析，也就是說能不能綜合所學(xué)的知識，應(yīng)也就是說能不能綜合所學(xué)的知識，應(yīng)用自如地解決問題。選手的綜合素質(zhì)用自如地解決問題。選手的綜合素質(zhì)愈高，得勝的機率愈大；愈高，得勝的機率愈大； 4、經(jīng)常面對著不知道算法的試題，經(jīng)常面對著不知道算法的試題，面對著誰都不知如何處置的情境面對著誰都不知如何處置的情境，因此必須使學(xué)生正確地理解問因此必須使學(xué)生正確地理解問題、深入問題的空間并形成解決問題、深入問題的空間并形成解決問題的意識、習(xí)慣和能力。能不能題的意識、習(xí)慣和能力。能不能創(chuàng)創(chuàng)造性地應(yīng)答沒有遇到過的挑戰(zhàn)造性地應(yīng)答沒有遇到過的挑戰(zhàn)，成成為培訓(xùn)的基本要求和目標(biāo)。為培訓(xùn)的基本

6、要求和目標(biāo)。 1 1、培養(yǎng)問題意識和問題能力。培養(yǎng)問題意識和問題能力。創(chuàng)造始創(chuàng)造始于問題。于問題?！坝辛藛栴}才會思考，有了思有了問題才會思考，有了思考才有解決問題的方法，才有找到獨立考才有解決問題的方法，才有找到獨立思路的可能（陶行知）思路的可能（陶行知）”。有問題雖然。有問題雖然不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)造造； 2、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和散點培訓(xùn)、循序漸進(jìn)與跳躍式的矛盾。散點培訓(xùn)、循序漸進(jìn)與跳躍式的矛盾。如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式學(xué)習(xí)，將離全國和國際奧林

7、匹克信息學(xué)活動的學(xué)習(xí)，將離全國和國際奧林匹克信息學(xué)活動的前沿、離世界程序設(shè)計知識的前沿愈來愈遠(yuǎn)。前沿、離世界程序設(shè)計知識的前沿愈來愈遠(yuǎn)。因此在進(jìn)行基礎(chǔ)課程學(xué)習(xí)的同時，必須有追逐因此在進(jìn)行基礎(chǔ)課程學(xué)習(xí)的同時，必須有追逐前沿的選擇性學(xué)習(xí)。這里，有時候心理的障礙前沿的選擇性學(xué)習(xí)。這里，有時候心理的障礙比科學(xué)上的障礙更難跨越，敢不敢的問題比能比科學(xué)上的障礙更難跨越，敢不敢的問題比能不能的問題更突出。其實在學(xué)習(xí)中或多或少地不能的問題更突出。其實在學(xué)習(xí)中或多或少地都有必要的跳躍，不少人還能夠?qū)崿F(xiàn)比較大的都有必要的跳躍，不少人還能夠?qū)崿F(xiàn)比較大的跳躍跳躍v學(xué)生必須學(xué)會從浩如煙海的信息中選擇最有價值的知識，構(gòu)建

8、個性化（符合自己能力結(jié)構(gòu)和興趣結(jié)構(gòu)）和競爭需要的知識結(jié)構(gòu)v培訓(xùn)內(nèi)容要有選擇性，因為除了出題者，誰也說不清楚在未來競賽中究竟什么知識是必要的，因此不可能把所有重要的東西都選擇好了給學(xué)生，而是應(yīng)該將直線培訓(xùn)與散點培訓(xùn)相結(jié)合，選擇部分重要的東西交給學(xué)生，讓他們自己去探索若干知識點之間的聯(lián)系，補充自己認(rèn)為需要補充的知識。3、參與活動的學(xué)生應(yīng)由競、參與活動的學(xué)生應(yīng)由競爭關(guān)系和獨立關(guān)系爭關(guān)系和獨立關(guān)系轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系學(xué)生的心理調(diào)適：學(xué)生的心理調(diào)適：v我掌握的知識僅不過是滄海一粟我掌握的知識僅不過是滄海一粟(進(jìn)取心進(jìn)取心)；v固守錯誤的概念比一無所知更可怕固守錯誤的概念比一無所知更可怕（

9、明智）（明智）；v三人之行必有我?guī)熑酥斜赜形規(guī)煟ㄖt虛）（謙虛）；v知識生產(chǎn)社會化條件下人的基本素質(zhì)之一知識生產(chǎn)社會化條件下人的基本素質(zhì)之一是合作精神（現(xiàn)在的重大科學(xué)發(fā)明需要成百是合作精神（現(xiàn)在的重大科學(xué)發(fā)明需要成百上千科學(xué)家進(jìn)行長期甚至跨國的合作，例如上千科學(xué)家進(jìn)行長期甚至跨國的合作，例如制作制作windows，人類基因工程），人類基因工程）（現(xiàn)代意識）（現(xiàn)代意識）；前提條件：前提條件：水平相當(dāng)?shù)耐|(zhì)成員水平相當(dāng)?shù)耐|(zhì)成員或各有所長（包括數(shù)學(xué)知識、編或各有所長（包括數(shù)學(xué)知識、編程能力和思維方式等解題所需的程能力和思維方式等解題所需的各種因素）的異質(zhì)成員是開展合各種因素）的異質(zhì)成員是開展合作

10、學(xué)習(xí)的組織基礎(chǔ)；作學(xué)習(xí)的組織基礎(chǔ)；合作學(xué)習(xí)的效應(yīng)：合作學(xué)習(xí)的效應(yīng)：v集思廣益容易出好的算法；集思廣益容易出好的算法；v群體設(shè)計的測試數(shù)據(jù)相對全面；群體設(shè)計的測試數(shù)據(jù)相對全面；v在群體活動中能比較客觀的反映自己在群體活動中能比較客觀的反映自己能力情況；能力情況；v每個學(xué)生在付出與給予中可提高合作每個學(xué)生在付出與給予中可提高合作精神和編程能力，成功者往往是那些相精神和編程能力，成功者往往是那些相容性好、容性好、 樂于幫助他人，并且善于取樂于幫助他人，并且善于取他人之長的學(xué)生他人之長的學(xué)生（符文杰、張一飛等）。（符文杰、張一飛等）。4、選手面對從未遇到過的、選手面對從未遇到過的挑戰(zhàn)應(yīng)調(diào)整好心態(tài)，挑戰(zhàn)

11、應(yīng)調(diào)整好心態(tài)，不要急不要急功近利，要只管耕耘、不問收獲、功近利，要只管耕耘、不問收獲、潛心鉆研、其樂無窮。那怕是一兩潛心鉆研、其樂無窮。那怕是一兩次失誤，也是砥礪之石，可從中汲次失誤，也是砥礪之石，可從中汲取有益的經(jīng)驗和教訓(xùn)。取有益的經(jīng)驗和教訓(xùn)。“不是一番不是一番寒徹骨，哪得梅花撲鼻香寒徹骨，哪得梅花撲鼻香”。 第一題：字符近似查找第一題：字符近似查找設(shè)有n個單詞的字典表（1n100）。計算某單詞在字典表中的四種匹配情況（字典表中的單詞和待匹配單詞的長度上限為255）： i：該單詞在字典表中的序號； Ei：在字典表中僅有一個字符不匹配的單詞序號； Fi：在字典表中多或少一個字符（其余字符匹配）

12、的單詞序號； N：其他情況 當(dāng)查找時有多個單詞符合條件，僅要求第一個單詞的序號即可。輸入文件輸入文件 輸入文件名為a.in，文件的格式如下： n（字典表的單詞數(shù)） n行，每行一個單詞 待匹配單詞 輸出文件輸出文件 輸出文件名a.out，格式如下： i Ei Fi其中i為字典表中符合條件的單詞序號（1in），若字典表中不存在符合條件的單詞，則對應(yīng)的i=0。若上述三種情況不存在，則輸出N。輸入輸出樣例輸入輸出樣例輸入1:5abcdeabcasdfasfdabcdaacdabcd輸出輸出1:4E5F1輸入輸入2:1ab輸出輸出2:0E0F0N我們將字典表中的單詞分成3類： 第1類：單詞與待匹配單詞多

13、或少一個字符，其余字符匹配； 第2類：單詞僅有一個字符與待匹配單詞不匹配； 第3類：單詞與待匹配單詞完全匹配；設(shè)constnote :array1.3 of string=(F,E,)； 匹配情況的標(biāo)志 var want:string； 待匹配單詞list:array1.100 of string； 字典表。其中l(wèi)isti為字典ians ：array1.100 of integer；單詞的類別序列。其中ansi= 其他情況相同與有一個字符不同與得到中添加或刪除一個字符在0321ilistwantilistwantilistwant1、匹配情況的計算、匹配情況的計算計算兩個等長字串中不同字符的個

14、數(shù)計算兩個等長字串中不同字符的個數(shù)function find(a,b:string):integer；輸入兩個等長字串a(chǎn),b，計算和返回不同字符的個數(shù)vari,tot:integer；begintot0；for i1 to length(a) do if aibi then inc(tot)；findtot；end； find n判別一個字串是否比另一個字串多一個字符（其余字符匹配）判別一個字串是否比另一個字串多一個字符（其余字符匹配）n我們不知道長度大1的字串究竟在哪個位置上多出一個字符，無奈，只能將該字串的每一個字符試插在另一個字串的對應(yīng)位置上。如果插入后使得兩串相同，則說明猜想成立。否則

15、猜想不成立。nfunction check(a,b:string):integerfunction check(a,b:string):integer； 輸入字串輸入字串a(chǎn),ba,b。若。若b b能夠在能夠在a a的基礎(chǔ)的基礎(chǔ)上添加一個字符得到的話，則返回上添加一個字符得到的話，則返回1 1；否則返回；否則返回00nvarvar i:integeri:integer；nbeginbeginncheck0check0；nfor i0 to length(a) do begin for i0 to length(a) do begin nacopy(a,1,i)+bi+1+copy(a,i+1,2

16、55)acopy(a,1,i)+bi+1+copy(a,i+1,255)； 在在aiai后插入后插入bi+1bi+1nif a=b if a=b 若插入后兩串相同，則成功退出若插入后兩串相同，則成功退出 nthen begin check1then begin check1；exitexit；endend；thenthenndelete(a,i+1,1)delete(a,i+1,1)； 刪去刪去a a中的插入字符中的插入字符 nendend；forfornendend；checkcheckn2 2、計算字典表中的每一類單詞、計算字典表中的每一類單詞首先，我們依次計算每一個單詞的類別序號 在單詞

17、i與待匹配單詞等長的情況下，若兩串相同，則單詞i的類別記為3；若兩串僅有一個字符不同，則單詞i的類別記為2； 若單詞i比待匹配單詞多或少一個字符（其余字符匹配），則單詞i的類別記為1；否則單詞i的類別記為0；然后根據(jù)ans序列在字典表中依次搜索類別3類別1的單詞，輸出對應(yīng)的單詞序號。如果在字典表中不存在上述3種類別的單詞，則輸出N。fillchar(ans,sizeof(ans),0)； 單詞的類別序列初始化for i1 to n do begin 對字典中的每個單詞進(jìn)行分類 if length(listi)=length(want) 若單詞i與待匹配單詞等長 then begin kfind

18、(listi,want)；計算單詞i與待匹配單詞的不同字符個數(shù) if k=0 then ansi 3； 記下類別序號 if k=1 then ansi 2； end；then若單詞i比待匹配單詞多或少一個字符（其余字符匹配），則單詞i的類別記為1；否則單詞i的類別記為0 if length(listi)+1=length(want) then ansi check(listi,want)； if length(listi)=length(want)+1 then ansi check(want,listi)；end；forhavefalse； 匹配情況存在的標(biāo)志初始化for i3 downto

19、 1 do begin 依次輸出每一類別的單詞在字典表最先出現(xiàn)的序號 k0； for j1 to n do if ansj=i then begin kj；break；end；thenhavehave or (k0)；writeln(notei,k)；end；for 第二題：級數(shù)求和第二題：級數(shù)求和 已知：Sn=1+1/2+1/3+.+1/n。顯然當(dāng)n.非常大的時候，Sn可大于任何一個整數(shù)K。現(xiàn)給出一個整數(shù)K（1K15），要求計算出一個最小的n，使得SnK。輸入輸入 鍵盤輸入k 輸出輸出 屏幕輸出n 輸入輸出樣例輸入輸出樣例輸入: 1輸出: 2算法分析算法分析 該題考核選手的并不是編程能力，而

20、是選擇變量類型的能力。由于該數(shù)列是遞減的，而k的上限為15，因此項數(shù)很大，即便是longint也容納不下。但未必非高精度運算不可。只要啟動浮點數(shù)運算（$n+），將項數(shù)設(shè)為extended類型，便可以得出正確解。$n+ 啟動浮點數(shù)運算vars,b,k:extended； 數(shù)列的和、項數(shù)、最接近sn(大于sn)的整數(shù)值begins0； 數(shù)列的和初始化b0； 項數(shù)初始化readln(k)； 讀最接近sn(大于sn)的整數(shù)值kwhile s=k do 若目前數(shù)列的和小于k，則項數(shù)b+1，計算sb beginbb+1；ss+1/b； end；while 輸出項數(shù)round(b)；end.main第三題：

21、選數(shù)第三題：選數(shù) 已知n個整數(shù) x1,x2,.xn, 以及一個整數(shù)k (kn)。從 n 個整數(shù)中任選k個整數(shù)組合相加，可分別得到一系列的和。例如當(dāng) n=4, k=3，4個整數(shù)分別為3，7，12，19 時，可得全部的組合為： 3+7+12=22 3+7+19=29 7+12+19=38 3+12+19=34。 現(xiàn)在，要求你計算出和為素數(shù)的組合數(shù)有多少種。例如上例，只有一種組合的和為素數(shù)：（3+7+19=29）。輸入輸入 輸入文件名為c.in。文件格式n, k（1n20，ka，則說明a不可能分解出比primei大的素數(shù)了，a本身為素數(shù)。由于primei表的最大素數(shù)接近10000，其平方遠(yuǎn)大于xi的

22、上限5000000，因此是一個比較可行的方法：function check(a:longint):boolean； 判斷a是否是素數(shù)beginchecktrue； 素數(shù)標(biāo)志初始化for i1 to tot do begin 搜索素數(shù)表 if primei*primeia then exit；若超出搜索范圍的上限，則說明a是素數(shù)，返回true if a mod primei=0 then begin checkfalse；exit；end；thenend；forend； check 2 2、遞歸搜索方案數(shù)、遞歸搜索方案數(shù) 由于數(shù)列是隨機和無序的，因此只能通過搜索的辦法求解。設(shè) 狀態(tài)(left,n

23、ow,all)：目前組合為all，還需要從xnowxn中選出left個數(shù)； 約束條件(leftn-now+1)：xnowxn中數(shù)的個數(shù)大于等于left； 邊界條件（(left=0) and (now=n+1)）和目標(biāo)狀態(tài)（check(all)=true）：從x1xn中選出k個數(shù)為邊界。在這種情況下，若k個數(shù)的和為素數(shù)，則滿足條件的種數(shù)+1。到達(dá)邊界后，應(yīng)回溯； 搜索范圍為兩種選擇： 當(dāng)前組合不選xnow,遞歸計算子狀態(tài)(left,now+1,all)； 在還有數(shù)需要選的情況下（left0），xnow選入組合，遞歸計算子狀態(tài)(left-1,now+1,all+listnow)；由此得出子程序Pr

24、ocedure solve(left,now,all:longint)；遞歸計算選數(shù)情況beginif (leftn-now+1)then exit；若xnowxn中不足left個數(shù)，則回溯 if (left=0) and (now=n+1) 若從x1xn中選出了k個數(shù) then begin if check(all) then inc(ans)；若k個數(shù)的和為素數(shù)，則滿足條件的種數(shù)+1 exit； 回溯 end；then solve(left,now+1,all)；當(dāng)前組合不選xnow,遞歸計算子狀態(tài)if left0 在還有數(shù)需要選的情況下，xnow選入組合，遞歸計算子狀態(tài) then sol

25、ve(left-1,now+1,all+listnow)；end； solve顯然，遞歸調(diào)用solve(k,1,0)后得出的ans即為問題的解。過河卒過河卒如圖，A點有一個過河卒，需要走到目標(biāo)B點。卒行走的規(guī)則：可以向下、或者向右。 同時在棋盤上的任一點有一個對方的馬（如上圖的C點）,該馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點。例如上圖C點上的馬可以控制8個點（圖中的P1，P2.P8）。卒不能通過對方馬的控制點。 棋盤用坐標(biāo)表示，A點（0，0）、B點（n，m）(n,m為不超過20的整數(shù),并由鍵盤輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定：CA，同時CB）?，F(xiàn)在要求你計算出卒從A 點能

26、夠到達(dá)B點的路徑的條數(shù)。輸輸 入：入： 鍵盤輸入B點的坐標(biāo)(n,m)以及對方馬的坐標(biāo)（X，Y）輸輸 出：出： 屏幕輸出一個整數(shù)（路徑的條數(shù)）。輸入輸出樣例：輸入輸出樣例： 輸入：3 3 2 2 輸出：01 1、計算對方馬的控制點、計算對方馬的控制點 按照題意，對方的馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點，按照題意，對方的馬所在的點和所有跳躍一步可達(dá)的點稱為對方馬的控制點，卒不能通過對方馬的控制點。在卒出發(fā)之前，必須計算對方馬的所有控制點。卒不能通過對方馬的控制點。在卒出發(fā)之前，必須計算對方馬的所有控制點。顯然，若（顯然，若（0，0）或（）或（n,m）為控制點，則輸出路徑數(shù)為）為控制

27、點，則輸出路徑數(shù)為0。設(shè)。設(shè)constconst move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(- move:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)2,1),(-2,-1)； movek movek，1.21.2為馬沿為馬沿k k方向跳躍一步的水平增量和垂直增量方向跳躍一步的水平增量和垂直增量 varvar list:array-1.20,-1.20 of comp list:array-

28、1.20,-1.20 of comp； 路徑數(shù)序列，其中路徑數(shù)序列，其中l(wèi)isti,jlisti,j為卒從為卒從(0,0)(0,0)到到(i,j)(i,j)的路徑數(shù)的路徑數(shù) can:array0.20,0.20 of boolean can:array0.20,0.20 of boolean； 點點(i,j)(i,j)允許卒通行的標(biāo)志允許卒通行的標(biāo)志 馬的初始位置為（馬的初始位置為（x,yx,y）。我們按照下述方式計算）。我們按照下述方式計算cancan序列：序列：canx,y falsecanx,y false； 對方馬所在的點為控制點對方馬所在的點為控制點 for i1 to 8 do b

29、eginfor i1 to 8 do begin從（從（x x，y y）出發(fā)，沿）出發(fā)，沿8 8個跳馬方向計算控制點個跳馬方向計算控制點 jx+movei,1 jx+movei,1； 計算計算i i方向的跳馬位置方向的跳馬位置(j(j，k)k) ky+movei,2 ky+movei,2； if (j=0) and (k=0) and (j=n) and (k=0) and (k=0) and (j=n) and (k=m) 若（若（j,kj,k）在界內(nèi)，則為控制點）在界內(nèi)，則為控制點 then canj,k false then canj,k false；endend；forforif (n

30、ot can0,0)or(not cann,m) if (not can0,0)or(not cann,m) 若卒的起點和終點為控制點，則輸出路徑數(shù)若卒的起點和終點為控制點，則輸出路徑數(shù)00 then writeln(0) then writeln(0) else begin else begin 計算和輸出卒從（計算和輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點的路徑數(shù)）點的路徑數(shù)listn,mlistn,m；endend；elseelse2 2、計算和輸出卒從（計算和輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點的路徑條）點的路徑條數(shù)數(shù) 我們按照由上而下、由左而右的順

31、序，將卒可能到達(dá)的每一個位置（我們按照由上而下、由左而右的順序，將卒可能到達(dá)的每一個位置（i,ji,j）(0in(0in，0jm)0jm)設(shè)為階段設(shè)為階段, ,顯然這樣做，可以取消對狀態(tài)的枚舉。顯然這樣做，可以取消對狀態(tài)的枚舉。 首先，將卒的出發(fā)點（首先，將卒的出發(fā)點（0 0，0 0）的路徑數(shù)設(shè)為）的路徑數(shù)設(shè)為1 1（list0,01list0,01），并將該），并將該位置設(shè)為控制點（位置設(shè)為控制點（can0,0 falscan0,0 fals）。然后從（）。然后從（0 0，0 0）出發(fā)，按照由上而）出發(fā)，按照由上而下、由左而右的順序計算卒經(jīng)過每一個可行點的路徑數(shù)。若（下、由左而右的順序計算卒

32、經(jīng)過每一個可行點的路徑數(shù)。若（i i，j j）為可）為可行點，則卒可由上側(cè)的（行點，則卒可由上側(cè)的（i-1,ji-1,j）和左側(cè)的（）和左側(cè)的（i,j-1i,j-1）進(jìn)入該點。將這兩點）進(jìn)入該點。將這兩點的路徑數(shù)加起來，即為從（的路徑數(shù)加起來，即為從（0 0，0 0）走到（）走到（i i，j j ）的路徑數(shù)，即）的路徑數(shù)，即 listi,j=listi-1,j+listi,j-1listi,j=listi-1,j+listi,j-1（i i，j j）非控制點）非控制點依次類推，最后得出的依次類推，最后得出的listn,mlistn,m即為問題的解。由此得出算法：即為問題的解。由此得出算法： f

33、illchar(list,sizeof(list),0)fillchar(list,sizeof(list),0)； 路徑數(shù)序列初始化路徑數(shù)序列初始化 list0,01 list0,01； 卒從（卒從（0 0，0 0）出發(fā)的路徑數(shù)為）出發(fā)的路徑數(shù)為1 1，該位置不再允許卒通行，該位置不再允許卒通行 can0,0 false can0,0 false； for i0 to n dofor i0 to n do對于每個可行點對于每個可行點, ,小兵要么從左側(cè)、要么從上方走到小兵要么從左側(cè)、要么從上方走到, ,由此由此計算從計算從(0,0)(0,0)到到(i,j)(i,j)的路徑數(shù)的路徑數(shù) for

34、j0 to m do if cani,j for j0 to m do if cani,j then listi,jlisti-1,j+listi,j-1 then listi,jlisti-1,j+listi,j-1；輸出卒從（輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點的路徑條數(shù)）點的路徑條數(shù)listn,mlistn,m；問題描述問題描述 有N堆紙牌，編號分別為1，2，.N。每堆上有若干張， 但紙牌總數(shù)必為N的倍數(shù)。可以在任一堆上取若干張紙牌，然后移動。移牌規(guī)則為：在編號為：在編號為1 1堆上取的紙牌，只能移到編號為堆上取的紙牌，只能移到編號為2 2的堆上；在編號為的堆上；在編

35、號為N N的堆上的堆上取的紙牌，只能移到編號為取的紙牌，只能移到編號為N-1N-1的堆上；其他堆上取的紙牌，可以移到相鄰的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為： 9 8 17 6移動3次可達(dá)到目的：從取4張牌放到（9 8 13 10）從取3張牌放到（9 11 10 10）從取1張牌放到（10 10 10 10）。 輸輸 入入 ： N （ N 堆紙牌，1N100） A1，A2，.An (N 堆紙牌，每堆紙牌初始數(shù)，1Ai10000

36、) 輸輸 出出 ：所有堆均達(dá)到相等時的最少移動次數(shù)。輸入輸出樣例輸入輸出樣例輸入：輸入： 4 9 8 17 6 輸出：輸出： 3設(shè)list為紙牌序列，其中l(wèi)isti為第i堆紙牌的張數(shù)（1in），ave為均分后每堆紙牌的張數(shù)，即 ；ans為最少移動次數(shù)。nilistni1我們按照由左而右的順序移動紙牌。若第i堆紙牌的張數(shù)listi超出平均值，則移動一次(ans+1)，將超出部分留給下一堆，既第i+1堆紙牌的張數(shù)增加listi-ave；若第i堆紙牌的張數(shù)listi少于平均值，則移動一次(ans+1)，由下一堆補充不足部分，既第i+1堆紙牌的張數(shù)減少ave-listi； 右鄰堆取的牌問題是，在從第i

37、+1堆中取出紙牌補充第i堆的過程中，可能會出現(xiàn)第i+1堆的紙牌數(shù)小于零(listi+1-(ave-listi)xu ud-yy-yzA.out文件：文件： 3設(shè)規(guī)則序列為rule，其中第i條規(guī)則為rulei，1rulei，2；當(dāng)前串為now，其中tmp為now的一個待匹配子串。由于匹配過程的由左而右進(jìn)行的，因此設(shè)j為now的指針，即從now的第j個字符開始匹配rulei,1。now適用第i條規(guī)則的條件是vnow中的子串被第i條規(guī)則替換后的長度小于255，即 length(now)+length(rulei,2)-length(rulei,1)255vrulei,1是now的一個子串（k=pos

38、(rulei,1,tmp)0）在使用了第i條規(guī)則后，now變換為now= copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多個子串被第i條規(guī)則替換，因此每替換一次后，為了方便地找出下一個替換位置，我們將當(dāng)前被替換串前（包括被替換串）的子串刪除。 由于原串a(chǎn)、目標(biāo)串b和規(guī)則rule是隨機輸入的，因此不可能找出直接計算最少替換次數(shù)best的數(shù)學(xué)規(guī)律，只能采用回溯搜索的辦法。設(shè)v 狀態(tài)（need,now）:替換次數(shù)為need，替換結(jié)果為now；v 邊界條件（needbest）和目標(biāo)狀態(tài)（now=b）：替換次數(shù)達(dá)到

39、或超過目前得出的最小值為邊界；已經(jīng)替換出目標(biāo)串為目標(biāo)狀態(tài)；v 搜索范圍i：嘗試每一條規(guī)則,即1i規(guī)則數(shù)n；v約束條件（length(now)+length(rulei,2)-length(rulei,1)255）：now中的子串被第i條規(guī)則替換后的長度小于255；由此得出計算過程： procedure solve(need；now)；從當(dāng)前串now出發(fā)，遞歸第need次替換vari,k,j:integer；tmp:string；beginif need=best then exit； 若到達(dá)邊界，則回溯if now=b then begin若達(dá)到目標(biāo)狀態(tài)，則記下替換次數(shù)，并回溯 bestnee

40、d； exit； end；thenfor i1 to n do 搜索每一條規(guī)則 if length(now)+length(rulei,2)-length(rulei,1)0 do 反復(fù)在tmp 中尋找子串rulei,1 begin solve(need+1，copy(now,1,j+k-1)+rulei,2+copy(now，j+k+length(rulei，1)，255)； 遞歸下一次替換 delete(tmp,1,k)；將當(dāng)前被替換串前（包括被替換串）的子串刪除 jj+k； 右移匹配指針 kpos(rulei,1,tmp)； 繼續(xù)嘗試第i條規(guī)則 end；while end；thenend

41、； solve 由此得出主程序：讀入初始串a(chǎn)和目標(biāo)串；讀入替換規(guī)則rule；best31； 設(shè)定替換次數(shù)的上限solve(0,a)； 回溯搜索最少的替換次數(shù)if best=30 輸出最少替換次數(shù) then writeln(best) else writeln(ERROR!)；、問題描述問題描述: 在高為H 的天花板上有n個小球，體積不計，位置分別為0，1，2，n-1。在地面上有一個小車(長為L，高為K，距原點距離為S1)。已知小球下落距離計算公式為 S=1/2*g*t2，其中 g=10， t為下落時間。地面上的小車以速度 V 前進(jìn)。如下圖： 小車與所有小球同時開始運動，當(dāng)小球距小車的距離小車與

42、所有小球同時開始運動，當(dāng)小球距小車的距離0.000010.00001時，即認(rèn)為時，即認(rèn)為小球被小車接受小球被小車接受（小球落到地面后不能被接受）。請你計算出小車能接受到多少個小球。輸入輸入：H，S1，v，L，k，n （1H，S1，v，L，k，n100000）輸出輸出：小車能接受到的小球個數(shù)。 由題意可知，車頂與天花板的距離為h-k，小球由天花板落至車頂所花費的時間為t1= ，由天花板落至地面的時間為t2= 。小車與所有小球同時開始運動，當(dāng)小球距小車的距離0.00001時，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。10)(*2kh10*2 h00001. 0*1lvts5 . 00000

43、1. 0*2vts顯然，若n1n2，則小車接受的小球數(shù)為n1-n2+1；否則小車未接受任何一個小球。 小車在行駛了t1*v-0.00001路程后接受了第一個小球，其編號為n1=minn-1, 小車在行駛了t2*v+0.00001路程后小球落地，小車接受最后一個小球的編號為n2=max0， 。問題描述問題描述：在平面上有n個點 (n100)，每個點用一對整數(shù)坐標(biāo)表示。例如：當(dāng)n=4 時，4 個點的坐標(biāo)分別為： p1(1，1)， p2(2，2)， p3 (6，3)， p4(7，0)這些點可以用這些點可以用 k k 個矩形個矩形( k4) ( k4) 全部覆蓋，矩形的邊平行于坐標(biāo)軸全部覆蓋，矩形的邊

44、平行于坐標(biāo)軸。如圖一，當(dāng) k=2時，可用如圖二的兩個矩形s1，s2覆蓋， s1，s2面積和為4。問題是當(dāng) n個點坐標(biāo)和 k 給出后，怎樣才能使得覆蓋所有點的k個矩形的面積之和為最小呢。約定：v 覆蓋一個點的矩形面積為覆蓋一個點的矩形面積為0 0；v覆蓋平行于坐標(biāo)軸直線上點的矩形面積也為覆蓋平行于坐標(biāo)軸直線上點的矩形面積也為0 0；v各個矩形間必須完全分開（邊線也不能重合）；各個矩形間必須完全分開（邊線也不能重合）； 平面上的點由坐標(biāo)（x,y）表示。由于計算過程是按照由下而上、由左而右進(jìn)行的，因此我們按照x坐標(biāo)遞增的順序和y坐標(biāo)遞增的順序?qū)個點存入a序列。矩形由2條平行于x軸的邊界線和2條平行

45、于y軸的邊界線圍成。為了計算最小矩形的方便，我們將空矩形的左邊界設(shè)為、右邊界為設(shè)-、下邊界設(shè)為、上邊界設(shè)為-。 2、計算覆蓋所有點的一個最小矩形、計算覆蓋所有點的一個最小矩形設(shè)目前最小矩形的四條邊界為maxx，maxy，minx，miny。如何按照面積最小的要求將a點加入矩形呢？顯然需要調(diào)整邊界顯然需要調(diào)整邊界線，使線，使a a點位于對應(yīng)的邊界線上。點位于對應(yīng)的邊界線上。初始時，我們設(shè)最小矩形為空，即左邊界left為、右邊界right為-、下邊界top為、上邊界bottom為-。然后由左而右，依次往矩形放入n個點，調(diào)整對應(yīng)的邊界線。最后得出的矩形為最小矩形，其面積為（右邊界-左邊界）*（上邊界

46、-下邊界） 我們稱彼此完全分開的矩形是獨立的。兩個覆蓋所有點的獨立矩形有兩種形態(tài)： 我們將覆蓋x軸左方點集a1,1.j的最小獨立矩形存入tac1,j；將覆蓋x軸右方點集a1,j.n的最小獨立矩形存入tdc1,j；將覆蓋y軸下方點集a2,1.j的最小獨立矩形存入tac2,j；將覆蓋y軸上方點集a2,j.n的最小獨立矩形存入tdc2,j（注意：當(dāng)k=3時，對應(yīng)的點集不包括被矩形1覆蓋的點（1j n ）。 Tac1,j-1Tdc1,jTac2,j-1Tdc2,j問題是面積和最小的兩個獨立矩形究竟取哪一個形態(tài)，區(qū)分兩個矩形的分界線j為何值，我們無法確定。不得已，只能將所有可能的情況枚舉出來。設(shè)var

47、best，now:longint；兩個獨立矩形的最小面積和、當(dāng)前方案中兩個獨立矩形的面積和枚舉過程如下： 計算tac和tdc序列； bestmaxlongint； 最小矩形面積初始化 for i1 to 2 do begin 依次分析x軸向和y軸向 k=3時順序?qū)ふ襥軸向上第一個未被矩形1覆蓋的點j； while jn do枚舉i軸向上所有可能的兩個獨立矩形，從中找出最佳方案 begin 記下i軸向上點j的坐標(biāo)h； 順序?qū)ふ襥軸向上最接近h點(k=3時，該點未被矩形1覆蓋)的點j； if 點j存在并且k=2，或者k=3時以點j為分界線的左矩形和右矩形與矩形1沒有交集 then begin no

48、w(taci，j-1，1-taci，j-1，3)*(taci，j-1，2-taci，j-1，4)+(tdci，j，1-tdci，j，3)*(tdci，j，2-tdci，j，4)；則計算兩個獨立矩形的面積和 if nowbest then bestnow； 若面積和為目前最小，則記下 end；thenend；whileend；for if best=maxlongint 若找不到的兩個獨立矩形 then返回失敗標(biāo)志-1 else返回兩個矩形的最小面積和best；end；getans 我們先枚舉第一個矩形，該矩形覆蓋x軸向上的點1、點i、點j、點h（1in, ijn, jhn）,求出覆蓋它們的最小

49、矩形。該矩形的上邊界、下邊界、左邊界和右邊界分別記為bottom、top、left、right。顯然其面積為(bottom-top)*(right-left)。我們將該矩形稱為矩形1。那么，平面上還有哪些點未在矩形1內(nèi)，這些點將被另外兩個獨立的矩形所覆蓋。 (xleft) and (xright) and (ybottom) and (ytop) (min(x1,right) max(x2,left) and (min(y1,bottom) max(y2,top)我們在得出矩形1的基礎(chǔ)上，直接調(diào)用上述算法計算與矩形1分開的另外兩個獨立矩形的面積和，加上矩形1的面積便是三個獨立矩形的面積和。問題

50、是矩形1究竟覆蓋了哪些點才能得出最優(yōu)解呢？我們無法得知。無奈之下，只能通過枚舉法搜索所有的可能情況for i1 to n do 枚舉x軸向上三個點（點i、點j、點h）的所有可能組合 for ji to n do for hj to n do begin 計算覆蓋點1、點i、點j、點h的最小矩形（矩形1）的四條邊界right、bottom、left、top； now(bottom-top)*(right-left)； 計算矩形1的面積 計算未被矩形1覆蓋的點集u； 計算覆蓋u且與矩形1不相交的兩個獨立矩形的最小面積和g； if (g0) and (g+now1)），則輸出當(dāng)前局的比分a：b。請注

51、意，如果輸入的字符為E，則標(biāo)志比賽結(jié)束，11分制計算完畢；否則，繼續(xù)讀下一個字符，計算新一局的比分。然后，對當(dāng)前輸入行計算21分制下每一局比賽的比分。計算方法基本如上。有所不同的是，若華華得分a或者對方得分b達(dá)到21分且雙方的分?jǐn)?shù)差值大于1（(a21) or(b21)and (abs(a-b)1)），則輸出當(dāng)前局的比分a：b。 按照上述方法對每一輸入行計算11分制和21分制的比賽結(jié)果，直至文件讀完（eof(input)）為止。a s s i g n ( i n p u t , i n p ) ; reset(input);輸入文件讀準(zhǔn)備 assign(output,out);rewrite(o

52、utput);輸出文件寫準(zhǔn)備 a:=0;b:=0; 當(dāng)前局雙方的比分初始化 while not eof (input) do若文件未讀完，則循環(huán) begin while not eoln(input) do若當(dāng)前行處理完，則11分制的比賽結(jié)束 begin read(ch);讀一個字符 case ch of根據(jù)字符的種類分情形處理 E: begin若比賽結(jié)束，則輸出雙方比分 writeln(a,:,b); break;退出11分制的計算過程 end; E W,L: begin華華或?qū)Ψ降靡环?if ch=Wthen inc(a)else inc(b); if(a=11)or(b=11) and

53、(abs(a-b)1) then若有一方得分達(dá)到11分且雙方的分?jǐn)?shù)差值大于1，則輸出雙方比分 begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln; end; while a:=0; b:=0; 新一局的比分初始化 writeln; reset(input);重新讀輸入行 while not eof(input) do若文件未讀完且比賽未結(jié)束，則循環(huán) begin while not eoln(input) do若當(dāng)前行處理完，則21分制的比賽結(jié)束 begin read(ch);

54、讀一個字符 case ch of根據(jù)字符的種類分情形處理 E: begin若比賽結(jié)束，則輸出雙方比分，退出21分制的計算過程 writeln(a,:,b); break; end; E W,L: begin華華或?qū)Ψ降靡环?if ch=Wthen inc(a) else inc(b); if (a=21)or(b=21) and (abs(a-b)1) 若有一方得分達(dá)到21分且雙方的分?jǐn)?shù)差值大于1，則輸出雙方比分 then begin writeln(a,:,b); a:=0;b:=0;新一局的比分初始化 end;then end; W,L end;case end;while readln;

55、 end;while close(input); close(output);關(guān)閉輸入文件和輸出文件 數(shù)字游戲（數(shù)字游戲（Game.pasGame.pas） 丁丁最近沉迷于一個數(shù)字游戲之中。這個游戲看似簡單，但丁丁在研究了許多天之后卻發(fā)覺原來在簡單的規(guī)則下想要贏得這個游戲并不那么容易。游戲是這樣的，在你面前有一圈整數(shù)（一共n個），你要按順序?qū)⑵浞譃閙個部分，各部分內(nèi)的數(shù)字相加，相加所得的m個結(jié)果對10取模后再相乘，最終得到一個數(shù)k。游戲的要求是使你所得的k最大或者最小。例如，對于下面這圈數(shù)字（n=4，m=2）：當(dāng)要求最小值時，(2-1) mod 10)(4+3) mod 10)=17=7，要求

56、最大值時，為(2+4+3) mod 10)(-1 mod 10)=99=81。特別值得注意的是，無論是負(fù)數(shù)還是正數(shù)，對10取模的結(jié)果均為非負(fù)值。丁丁請你編寫程序幫他贏得這個游戲。 【輸入格式】輸入文件第一行有兩個整數(shù)，n（1n50）和m（1m9）。以下n行每行有個整數(shù)，其絕對值不大于104，按順序給出圈中的數(shù)字，首尾相接。 【輸出格式】輸出文件有兩行，各包含一個非負(fù)整數(shù)。第一行是你程序得到的最小值，第二行是最大值。算法分析算法分析 設(shè)圓周上的n個數(shù)字為a1、a2、an。按照模運算的規(guī)則（a1+a2+ +ak）mod 10=(a1 mod 10+a2 mod 10+ ak mod 10)mod

57、10；gi，j為ai、ai+1、aj的數(shù)和對10的模，即 gi，j=（ai+ai+1+ +aj）mod 10顯然 gi，i=（ai mod 10+10）mod 10 gi，j= (gi,j-1+gj,j) mod 10 (1in，i+1jn)當(dāng)m=1時，程序得到的最小值和最大值為g1,n；fmax1p,I,j為ai、ai+1、aj分為p個部分，各部分內(nèi)的數(shù)字相加，相加所得的p個結(jié)果對10取模后 再 相 乘 ， 最 終 得 到 最 大 數(shù) 。 顯 然 ，fmax11,i,j= gi，j；fmin1p,I,j為ai、ai+1、aj分為p個部分，各部分內(nèi)的數(shù)字相加，相加所得的p個結(jié)果對10取模后再相

58、乘，最終得到最小數(shù)。顯然，fmin11,i,j= gi，j；(1pm)問題是當(dāng)ai、ai+1、aj劃分成的部分?jǐn)?shù)p大于1時，怎么辦。我們采用動態(tài)程序設(shè)計的方法計算。設(shè) 階段p：劃分成的部分?jǐn)?shù),2pm-1； 狀態(tài)（i，j）:將ai、ai+1、aj劃分成p個部分，1in，ijn； 決策k: 將ai、ai+1、ak劃分成p-1個部分，ak+1、aj為第p部分，ikj-1；顯然，狀態(tài)轉(zhuǎn)移方程為 fmin1p,i,j= fmin1p-1,i,k*gk+1,j fmax1p,i,j= fmax1p-1,i,k*gk+1,j2pm-11minjki1maxjkimax=min= 由于p-1階段僅和p階段發(fā)生

59、聯(lián)系，因此我們將p-1階段的狀態(tài)轉(zhuǎn)移方程fmin1p-1,i,j設(shè)為fmin1i,j、fmax1p-1,i,j 設(shè)為fmax1i,j，將p階段的狀態(tài)轉(zhuǎn)移方程fmin1p,i,j設(shè)為fmini,j、fmax1p,i,j設(shè)為fmaxi,j。 )() 1( , 1 1max*10mod), 1 1, 1 (max1njorijimfnjgignjini )() 1( , 1 1min*10mod), 1 1, 1 (min1njorijimfnjgignjini read(n,m);讀數(shù)字個數(shù)和劃分的部分?jǐn)?shù) fillchar(fmax1,sizeof(fmax1),0); fillchar(fmin

60、1,sizeof(fmin1),$FF);狀態(tài)轉(zhuǎn)移方程初始化 fillchar(g,sizeof(g),0); for i:=1 to n do依次讀入每個數(shù)，一個數(shù)組成一部分 begin read(gi,i); gi,i:=(gi,imod mask+mask) mod mask; min1i,i:=gi,i;fmax1i,i:=gi,i; end;for for i:=1 to n do計算一部分內(nèi)的數(shù)和對10的模的所有可能情況 for j:=i+1 to n do begin gi,j:=(gi,j-1+gj,j) mod mask; fmax1i,j:=gi,j; fmin1i,j:=