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

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

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

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

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

5、哪個(gè)角度去分析，關(guān)鍵是你從哪個(gè)角度去分析，也就是說能不能綜合所學(xué)的知識(shí)，應(yīng)也就是說能不能綜合所學(xué)的知識(shí)，應(yīng)用自如地解決問題。選手的綜合素質(zhì)用自如地解決問題。選手的綜合素質(zhì)愈高，得勝的機(jī)率愈大；愈高，得勝的機(jī)率愈大； 4、經(jīng)常面對(duì)著不知道算法的試題，經(jīng)常面對(duì)著不知道算法的試題，面對(duì)著誰都不知如何處置的情境面對(duì)著誰都不知如何處置的情境，因此必須使學(xué)生正確地理解問因此必須使學(xué)生正確地理解問題、深入問題的空間并形成解決問題、深入問題的空間并形成解決問題的意識(shí)、習(xí)慣和能力。能不能題的意識(shí)、習(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)問題意識(shí)和問題能力。培養(yǎng)問題意識(shí)和問題能力。創(chuàng)造始創(chuàng)造始于問題。于問題?！坝辛藛栴}才會(huì)思考，有了思有了問題才會(huì)思考，有了思考才有解決問題的方法，才有找到獨(dú)立考才有解決問題的方法，才有找到獨(dú)立思路的可能（陶行知）思路的可能（陶行知）”。有問題雖然。有問題雖然不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)造造； 2、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和、處理好前沿性與基礎(chǔ)性、直線培訓(xùn)和散點(diǎn)培訓(xùn)、循序漸進(jìn)與跳躍式的矛盾。散點(diǎn)培訓(xùn)、循序漸進(jìn)與跳躍式的矛盾。如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式學(xué)習(xí)，將離全國(guó)和國(guó)際奧林

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

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

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

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

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

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

13、或少一個(gè)字符，其余字符匹配； 第2類：?jiǎn)卧~僅有一個(gè)字符與待匹配單詞不匹配； 第3類：?jiǎn)卧~與待匹配單詞完全匹配；設(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= 其他情況相同與有一個(gè)字符不同與得到中添加或刪除一個(gè)字符在0321ilistwantilistwantilistwant1、匹配情況的計(jì)算、匹配情況的計(jì)算計(jì)算兩個(gè)等長(zhǎng)字串中不同字符的個(gè)

14、數(shù)計(jì)算兩個(gè)等長(zhǎng)字串中不同字符的個(gè)數(shù)function find(a,b:string):integer；輸入兩個(gè)等長(zhǎng)字串a(chǎn),b，計(jì)算和返回不同字符的個(gè)數(shù)vari,tot:integer；begintot0；for i1 to length(a) do if aibi then inc(tot)；findtot；end； find n判別一個(gè)字串是否比另一個(gè)字串多一個(gè)字符（其余字符匹配）判別一個(gè)字串是否比另一個(gè)字串多一個(gè)字符（其余字符匹配）n我們不知道長(zhǎng)度大1的字串究竟在哪個(gè)位置上多出一個(gè)字符，無奈，只能將該字串的每一個(gè)字符試插在另一個(gè)字串的對(duì)應(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ǔ)上添加一個(gè)字符得到的話，則返回上添加一個(gè)字符得到的話，則返回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、計(jì)算字典表中的每一類單詞、計(jì)算字典表中的每一類單詞首先，我們依次計(jì)算每一個(gè)單詞的類別序號(hào) 在單詞

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

18、(listi,want)；計(jì)算單詞i與待匹配單詞的不同字符個(gè)數(shù) if k=0 then ansi 3； 記下類別序號(hào) if k=1 then ansi 2； end；then若單詞i比待匹配單詞多或少一個(gè)字符（其余字符匹配），則單詞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)的序號(hào) k0； for j1 to n do if ansj=i then begin kj；break；end；thenhavehave or (k0)；writeln(notei,k)；end；for 第二題：級(jí)數(shù)求和第二題：級(jí)數(shù)求和 已知：Sn=1+1/2+1/3+.+1/n。顯然當(dāng)n.非常大的時(shí)候，Sn可大于任何一個(gè)整數(shù)K?，F(xiàn)給出一個(gè)整數(shù)K（1K15），要求計(jì)算出一個(gè)最小的n，使得SnK。輸入輸入 鍵盤輸入k 輸出輸出 屏幕輸出n 輸入輸出樣例輸入輸出樣例輸入: 1輸出: 2算法分析算法分析 該題考核選手的并不是編程能力，而

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

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

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

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

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

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

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

27、點(diǎn)，則輸出路徑數(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； 點(diǎn)點(diǎn)(i,j)(i,j)允許卒通行的標(biāo)志允許卒通行的標(biāo)志 馬的初始位置為（馬的初始位置為（x,yx,y）。我們按照下述方式計(jì)算）。我們按照下述方式計(jì)算cancan序列：序列：canx,y falsecanx,y false； 對(duì)方馬所在的點(diǎn)為控制點(diǎn)對(duì)方馬所在的點(diǎn)為控制點(diǎn) for i1 to 8 do b

29、eginfor i1 to 8 do begin從（從（x x，y y）出發(fā)，沿）出發(fā)，沿8 8個(gè)跳馬方向計(jì)算控制點(diǎn)個(gè)跳馬方向計(jì)算控制點(diǎn) jx+movei,1 jx+movei,1； 計(jì)算計(jì)算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)，則為控制點(diǎn)）在界內(nèi)，則為控制點(diǎn) 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) 若卒的起點(diǎn)和終點(diǎn)為控制點(diǎn)，則輸出路徑數(shù)若卒的起點(diǎn)和終點(diǎn)為控制點(diǎn)，則輸出路徑數(shù)00 then writeln(0) then writeln(0) else begin else begin 計(jì)算和輸出卒從（計(jì)算和輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點(diǎn)的路徑數(shù)）點(diǎn)的路徑數(shù)listn,mlistn,m；endend；elseelse2 2、計(jì)算和輸出卒從（計(jì)算和輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點(diǎn)的路徑條）點(diǎn)的路徑條數(shù)數(shù) 我們按照由上而下、由左而右的順

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

32、經(jīng)過每一個(gè)可行點(diǎn)的路徑數(shù)。若（i i，j j）為可）為可行點(diǎn)，則卒可由上側(cè)的（行點(diǎn)，則卒可由上側(cè)的（i-1,ji-1,j）和左側(cè)的（）和左側(cè)的（i,j-1i,j-1）進(jìn)入該點(diǎn)。將這兩點(diǎn)）進(jìn)入該點(diǎn)。將這兩點(diǎ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）非控制點(diǎn)）非控制點(diǎn)依次類推，最后得出的依次類推，最后得出的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對(duì)于每個(gè)可行點(diǎn)對(duì)于每個(gè)可行點(diǎn), ,小兵要么從左側(cè)、要么從上方走到小兵要么從左側(cè)、要么從上方走到, ,由此由此計(jì)算從計(jì)算從(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）點(diǎn)的路徑條數(shù)）點(diǎn)的路徑條數(shù)listn,mlistn,m；問題描述問題描述 有N堆紙牌，編號(hào)分別為1，2，.N。每堆上有若干張， 但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮疲缓笠苿?dòng)。移牌規(guī)則為：在編號(hào)為：在編號(hào)為1 1堆上取的紙牌，只能移到編號(hào)為堆上取的紙牌，只能移到編號(hào)為2 2的堆上；在編號(hào)為的堆上；在編

35、號(hào)為N N的堆上的堆上取的紙牌，只能移到編號(hào)為取的紙牌，只能移到編號(hào)為N-1N-1的堆上；其他堆上取的紙牌，可以移到相鄰的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上。左邊或右邊的堆上。現(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為： 9 8 17 6移動(dòng)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í)的最少移動(dòng)次數(shù)。輸入輸出樣例輸入輸出樣例輸入：輸入： 4 9 8 17 6 輸出：輸出： 3設(shè)list為紙牌序列，其中l(wèi)isti為第i堆紙牌的張數(shù)（1in），ave為均分后每堆紙牌的張數(shù)，即 ；ans為最少移動(dòng)次數(shù)。nilistni1我們按照由左而右的順序移動(dòng)紙牌。若第i堆紙牌的張數(shù)listi超出平均值，則移動(dòng)一次(ans+1)，將超出部分留給下一堆，既第i+1堆紙牌的張數(shù)增加listi-ave；若第i堆紙牌的張數(shù)listi少于平均值，則移動(dòng)一次(ans+1)，由下一堆補(bǔ)充不足部分，既第i+1堆紙牌的張數(shù)減少ave-listi； 右鄰堆取的牌問題是，在從第i

37、+1堆中取出紙牌補(bǔ)充第i堆的過程中，可能會(huì)出現(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的一個(gè)待匹配子串。由于匹配過程的由左而右進(jìn)行的，因此設(shè)j為now的指針，即從now的第j個(gè)字符開始匹配rulei,1。now適用第i條規(guī)則的條件是vnow中的子串被第i條規(guī)則替換后的長(zhǎng)度小于255，即 length(now)+length(rulei,2)-length(rulei,1)255vrulei,1是now的一個(gè)子串（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中可能有多個(gè)子串被第i條規(guī)則替換，因此每替換一次后，為了方便地找出下一個(gè)替換位置，我們將當(dāng)前被替換串前（包括被替換串）的子串刪除。 由于原串a(chǎn)、目標(biāo)串b和規(guī)則rule是隨機(jī)輸入的，因此不可能找出直接計(jì)算最少替換次數(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ī)則替換后的長(zhǎng)度小于255；由此得出計(jì)算過程： 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個(gè)小球，體積不計(jì)，位置分別為0，1，2，n-1。在地面上有一個(gè)小車(長(zhǎng)為L(zhǎng)，高為K，距原點(diǎn)距離為S1)。已知小球下落距離計(jì)算公式為 S=1/2*g*t2，其中 g=10， t為下落時(shí)間。地面上的小車以速度 V 前進(jìn)。如下圖： 小車與所有小球同時(shí)開始運(yùn)動(dòng)，當(dāng)小球距小車的距離小車與

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

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

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

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

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

47、best，now:longint；兩個(gè)獨(dú)立矩形的最小面積和、當(dāng)前方案中兩個(gè)獨(dú)立矩形的面積和枚舉過程如下： 計(jì)算tac和tdc序列； bestmaxlongint； 最小矩形面積初始化 for i1 to 2 do begin 依次分析x軸向和y軸向 k=3時(shí)順序?qū)ふ襥軸向上第一個(gè)未被矩形1覆蓋的點(diǎn)j； while jn do枚舉i軸向上所有可能的兩個(gè)獨(dú)立矩形，從中找出最佳方案 begin 記下i軸向上點(diǎn)j的坐標(biāo)h； 順序?qū)ふ襥軸向上最接近h點(diǎn)(k=3時(shí)，該點(diǎn)未被矩形1覆蓋)的點(diǎn)j； if 點(diǎn)j存在并且k=2，或者k=3時(shí)以點(diǎn)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)；則計(jì)算兩個(gè)獨(dú)立矩形的面積和 if nowbest then bestnow； 若面積和為目前最小，則記下 end；thenend；whileend；for if best=maxlongint 若找不到的兩個(gè)獨(dú)立矩形 then返回失敗標(biāo)志-1 else返回兩個(gè)矩形的最小面積和best；end；getans 我們先枚舉第一個(gè)矩形，該矩形覆蓋x軸向上的點(diǎn)1、點(diǎn)i、點(diǎn)j、點(diǎn)h（1in, ijn, jhn）,求出覆蓋它們的最小

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

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

51、意，如果輸入的字符為E，則標(biāo)志比賽結(jié)束，11分制計(jì)算完畢；否則，繼續(xù)讀下一個(gè)字符，計(jì)算新一局的比分。然后，對(duì)當(dāng)前輸入行計(jì)算21分制下每一局比賽的比分。計(jì)算方法基本如上。有所不同的是，若華華得分a或者對(duì)方得分b達(dá)到21分且雙方的分?jǐn)?shù)差值大于1（(a21) or(b21)and (abs(a-b)1)），則輸出當(dāng)前局的比分a：b。 按照上述方法對(duì)每一輸入行計(jì)算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);讀一個(gè)字符 case ch of根據(jù)字符的種類分情形處理 E: begin若比賽結(jié)束，則輸出雙方比分 writeln(a,:,b); break;退出11分制的計(jì)算過程 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、讀一個(gè)字符 case ch of根據(jù)字符的種類分情形處理 E: begin若比賽結(jié)束，則輸出雙方比分，退出21分制的計(jì)算過程 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） 丁丁最近沉迷于一個(gè)數(shù)字游戲之中。這個(gè)游戲看似簡(jiǎn)單，但丁丁在研究了許多天之后卻發(fā)覺原來在簡(jiǎn)單的規(guī)則下想要贏得這個(gè)游戲并不那么容易。游戲是這樣的，在你面前有一圈整數(shù)（一共n個(gè)），你要按順序?qū)⑵浞譃閙個(gè)部分，各部分內(nèi)的數(shù)字相加，相加所得的m個(gè)結(jié)果對(duì)10取模后再相乘，最終得到一個(gè)數(shù)k。游戲的要求是使你所得的k最大或者最小。例如，對(duì)于下面這圈數(shù)字（n=4，m=2）：當(dāng)要求最小值時(shí)，(2-1) mod 10)(4+3) mod 10)=17=7，要求

56、最大值時(shí)，為(2+4+3) mod 10)(-1 mod 10)=99=81。特別值得注意的是，無論是負(fù)數(shù)還是正數(shù)，對(duì)10取模的結(jié)果均為非負(fù)值。丁丁請(qǐng)你編寫程序幫他贏得這個(gè)游戲。 【輸入格式】輸入文件第一行有兩個(gè)整數(shù)，n（1n50）和m（1m9）。以下n行每行有個(gè)整數(shù)，其絕對(duì)值不大于104，按順序給出圈中的數(shù)字，首尾相接。 【輸出格式】輸出文件有兩行，各包含一個(gè)非負(fù)整數(shù)。第一行是你程序得到的最小值，第二行是最大值。算法分析算法分析 設(shè)圓周上的n個(gè)數(shù)字為a1、a2、an。按照模運(yùn)算的規(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ù)和對(duì)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時(shí)，程序得到的最小值和最大值為g1,n；fmax1p,I,j為ai、ai+1、aj分為p個(gè)部分，各部分內(nèi)的數(shù)字相加，相加所得的p個(gè)結(jié)果對(duì)10取模后 再 相 乘 ， 最 終 得 到 最 大 數(shù) 。 顯 然 ，fmax11,i,j= gi，j；fmin1p,I,j為ai、ai+1、aj分為p個(gè)部分，各部分內(nèi)的數(shù)字相加，相加所得的p個(gè)結(jié)果對(duì)10取模后再相

58、乘，最終得到最小數(shù)。顯然，fmin11,i,j= gi，j；(1pm)問題是當(dāng)ai、ai+1、aj劃分成的部分?jǐn)?shù)p大于1時(shí)，怎么辦。我們采用動(dòng)態(tài)程序設(shè)計(jì)的方法計(jì)算。設(shè) 階段p：劃分成的部分?jǐn)?shù),2pm-1； 狀態(tài)（i，j）:將ai、ai+1、aj劃分成p個(gè)部分，1in，ijn； 決策k: 將ai、ai+1、ak劃分成p-1個(gè)部分，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ù)字個(gè)數(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依次讀入每個(gè)數(shù)，一個(gè)數(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計(jì)算一部分內(nèi)的數(shù)和對(duì)10的模的所有可能情況 for j:=i+1 to n do begin gi,j:=(gi,j-1+gj,j) mod mask; fmax1i,j:=gi,j; fmin1i,j:=