1基礎(chǔ)題和串運(yùn)算重點課件

上海市控江中學(xué)王建德全國奧林匹克信息學(xué)聯(lián)賽最近三年全國分區(qū)聯(lián)賽復(fù)賽

雖然最近三年全國奧林匹克信息學(xué)復(fù)賽中含許多可“一題多解”的試題，但如果按照較優(yōu)算法標(biāo)準(zhǔn)分類的話，大致可分為

題型

題型與課內(nèi)知識和編程基礎(chǔ)相關(guān)自由落體、級數(shù)求和、乒乓球、麥森數(shù)、不高興的津津、花生采摘、津津的儲蓄計劃構(gòu)造法均分紙牌、傳染病控制、火星人數(shù)據(jù)結(jié)構(gòu)字符近似查找、合并果子（堆排序）、棧、FBI樹（二叉樹）、神經(jīng)網(wǎng)絡(luò)（圖）枚舉法蟲食算、偵探推理回溯法選數(shù)、字串變換動態(tài)程序設(shè)計方法過河卒、數(shù)字游戲、加分二叉樹、合唱隊形

幾何計算矩形覆蓋特點

1、凸現(xiàn)信息學(xué)知識和學(xué)科知識整合的趨勢。為了考核學(xué)生運(yùn)用學(xué)科知識的能力，激發(fā)學(xué)生的創(chuàng)造力，2002年全國奧林匹克信息聯(lián)賽(NOIP)中學(xué)科類的試題增加，并且首次出現(xiàn)了計算幾何類的試題(矩形覆蓋)。這說明信息學(xué)與學(xué)科的依賴關(guān)系日益凸現(xiàn)，學(xué)科基礎(chǔ)好、尤其是數(shù)學(xué)素質(zhì)好的人雖然不一定會編程，但希望學(xué)習(xí)編程的人愈來愈多；編程解題能力強(qiáng)的人勢必有數(shù)學(xué)的潛質(zhì)和愛好，他們中愈來愈多的人也希望深造數(shù)學(xué)。各門學(xué)科的交融和整合是奧林匹克信息學(xué)聯(lián)賽活動發(fā)展的一個大趨勢（有專家提議，數(shù)學(xué)教材講算法，信息科技教材講語言，上海的信息科技教材出現(xiàn)真值表（初中）和c語言（高中））。2、“構(gòu)造法”或貪心策略類試題的引入，使得算法知識的不確定性和不穩(wěn)定性增加。這正體現(xiàn)了科學(xué)的本質(zhì)—知識是不斷推陳出新的。3、試題的綜合性增加，并不一定隨知識的分類而發(fā)生變化，有時幾乎找不到一個單一的經(jīng)典算法(字串變換——回溯法中有字符串處理)，也找不到一個純粹的數(shù)據(jù)結(jié)構(gòu)問題（級數(shù)求和——需要為表達(dá)式的計算結(jié)果設(shè)計合適的數(shù)據(jù)類型），關(guān)鍵是你從哪個角度去分析，也就是說能不能綜合所學(xué)的知識，應(yīng)用自如地解決問題。選手的綜合素質(zhì)愈高，得勝的機(jī)率愈大；

4、經(jīng)常面對著不知道算法的試題，面對著誰都不知如何處置的情境（經(jīng)常出現(xiàn)許多選手在一題中得0分、優(yōu)秀選手表現(xiàn)失常的情況），因此必須使學(xué)生正確地理解問題、深入問題的空間并形成解決問題的意識、習(xí)慣和能力。能不能創(chuàng)造性地應(yīng)答沒有遇到過的挑戰(zhàn)，成為培訓(xùn)的基本要求和目標(biāo)。

1、培養(yǎng)問題意識和問題能力。創(chuàng)造始于問題。“有了問題才會思考，有了思考才有解決問題的方法，才有找到獨(dú)立思路的可能（陶行知）”。有問題雖然不一定有創(chuàng)造，但沒有問題一定沒有創(chuàng)造（想一想當(dāng)前的解法有沒有缺陷，有沒有更好的算法，它與哪些問題有聯(lián)系，與哪些知識相關(guān)聯(lián)，還可以拓延出哪些問題，要解決這些問題還需要哪些知識）；

啟示2、處理好基礎(chǔ)性與前沿性、直線培訓(xùn)和散點培訓(xùn)、循序漸進(jìn)與跳躍式的矛盾。如果恪守按部就班的培訓(xùn)程序，不謀求跳躍式學(xué)習(xí)，將離全國和國際奧林匹克信息學(xué)活動的前沿、離世界程序設(shè)計知識的前沿愈來愈遠(yuǎn)。因此在進(jìn)行基礎(chǔ)課程學(xué)習(xí)的同時，必須有追逐前沿的選擇性學(xué)習(xí)。這里，有時候心理的障礙比科學(xué)上的障礙更難跨越，敢不敢的問題比能不能的問題更突出。其實在學(xué)習(xí)中或多或少地都有必要的跳躍，不少人還能夠?qū)崿F(xiàn)比較大的跳躍（

愛笛生小學(xué)三年級退學(xué)、比爾.蓋茨大學(xué)三年級退學(xué)）學(xué)生必須學(xué)會從浩如煙海的信息中選擇最有價值的知識，構(gòu)建個性化（符合自己能力結(jié)構(gòu)和興趣結(jié)構(gòu)）和競爭需要的知識結(jié)構(gòu)培訓(xùn)內(nèi)容要有選擇性，因為除了出題者，誰也說不清楚在未來競賽中究竟什么知識是必要的（對基礎(chǔ)的理解是主觀的選擇。例如中國、美國和俄羅斯的理科教材大不相同，有的同年級同學(xué)科的教材相差三分之二），因此不可能把所有重要的東西都選擇好了給學(xué)生，而是應(yīng)該將直線培訓(xùn)與散點培訓(xùn)相結(jié)合，選擇部分重要的東西交給學(xué)生，讓他們自己去探索若干知識點之間的聯(lián)系，補(bǔ)充自己認(rèn)為需要補(bǔ)充的知識。

3、參與活動的學(xué)生應(yīng)由競爭關(guān)系和獨(dú)立關(guān)系（你做你的，我干我的，程序和算法互相保密，彼此津津樂道于對方的失敗和自己的成功）轉(zhuǎn)向合作學(xué)習(xí)的關(guān)系（通過研討算法、集中編程、互測數(shù)據(jù)等互相合作的方式完成學(xué)習(xí)任務(wù)）學(xué)生的心理調(diào)適：我掌握的知識僅不過是滄海一粟(進(jìn)取心)；固守錯誤的概念比一無所知更可怕（明智）；三人之行必有我?guī)煟ㄖt虛）；知識生產(chǎn)社會化條件下人的基本素質(zhì)之一是合作精神（現(xiàn)在的重大科學(xué)發(fā)明需要成百上千科學(xué)家進(jìn)行長期甚至跨國的合作，例如制作windows，人類基因工程）（現(xiàn)代意識）；前提條件：水平相當(dāng)?shù)耐|(zhì)成員或各有所長（包括數(shù)學(xué)知識、編程能力和思維方式等解題所需的各種因素）的異質(zhì)成員是開展合作學(xué)習(xí)的組織基礎(chǔ)；合作學(xué)習(xí)的效應(yīng)：集思廣益容易出好的算法；群體設(shè)計的測試數(shù)據(jù)相對全面；在群體活動中能比較客觀的反映自己能力情況；每個學(xué)生在付出與給予中可提高合作精神和編程能力，成功者往往是那些相容性好、樂于幫助他人，并且善于取他人之長的學(xué)生（符文杰、張一飛等）。4、選手面對從未遇到過的挑戰(zhàn)應(yīng)調(diào)整好心態(tài)，不要急功近利，要只管耕耘、不問收獲、潛心鉆研、其樂無窮。那怕是一兩次失誤，也是砥礪之石，可從中汲取有益的經(jīng)驗和教訓(xùn)。“不是一番寒徹骨，哪得梅花撲鼻香”?；A(chǔ)題串運(yùn)算基礎(chǔ)題有些基礎(chǔ)題雖然直接給出了計算公式或算法十分明顯（例如統(tǒng)計數(shù)和），但是，如果變量的數(shù)據(jù)類型選錯了，或者不會文件操作，同樣會做錯題，導(dǎo)致意外的失誤。因此作題必須強(qiáng)調(diào)兩基：基礎(chǔ)知識基本基能級數(shù)求和

已知：Sn=1+1/2+1/3+….+1/n。顯然當(dāng)n.非常大的時候，Sn可大于任何一個整數(shù)K。現(xiàn)給出一個整數(shù)K（1≤K≤15），要求計算出一個最小的n，使得Sn>K。

輸入

鍵盤輸入 k

輸出

屏幕輸出 n

輸入輸出樣例

輸入: 1

輸出: 2

算法分析

該題考核選手的并不是編程能力，而是選擇變量類型的能力。由于該數(shù)列是遞減的，而k的上限為15，因此項數(shù)很大，即便是longint也容納不下。但未必非高精度運(yùn)算不可。只要啟動浮點數(shù)運(yùn)算（{$n+}），將項數(shù)設(shè)為extended類型，便可以得出正確解。{$n+}{啟動浮點數(shù)運(yùn)算}vars,b,k:extended；{數(shù)列的和、項數(shù)、最接近sn(大于sn)的整數(shù)值}begin s←0；b←0；{數(shù)列的和、項數(shù)初始化} readln(k)；{讀最接近sn(大于sn)的整數(shù)值k} whiles<=kdo{若目前數(shù)列的和小于k，則項數(shù)b+1，計算sb}begin b←b+1；s←s+1/b；end；{while}輸出項數(shù)round(b)；end.{main}關(guān)鍵是s的類型。如果設(shè)為string，則增加了編程難度；如果設(shè)為除extended外的其它類型，則會失分！乒乓球（Table.pas）【問題背景】國際乒聯(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表示華華對手獲得一分）：WWWWWWWWWWWWWWWWWWWWWWLW在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)容。

【輸出格式】輸出由兩部分組成，每部分有若干行，每一行對應(yīng)一局比賽的比分（按比賽信息輸入順序）。其中第一部分是11分制下的結(jié)果，第二部分是21分制下的結(jié)果，兩部分之間由一個空行分隔。

算法分析

首先，對當(dāng)前輸入行計算11分制下每一局比賽的比分。設(shè)a為當(dāng)前局華華的得分，每輸入一個‘W’，a+1；b為當(dāng)前局對方的得分，每輸入一個‘L’，b+1。若輸入‘E’或者華華的得分a或者對方得分b達(dá)到11分且雙方的分?jǐn)?shù)差值大于1（((a≥11)or(b≥11))and(abs(a-b)>1)），則輸出當(dāng)前局的比分a：b。請注意，如果輸入的字符為‘E’，則標(biāo)志比賽結(jié)束，11分制計算完畢；否則，繼續(xù)讀下一個字符，計算新一局的比分。然后，對當(dāng)前輸入行計算21分制下每一局比賽的比分。計算方法基本如上。有所不同的是，若華華得分a或者對方得分b達(dá)到21分且雙方的分?jǐn)?shù)差值大于1（((a≥21)or(b≥21))and(abs(a-b)>1)），則輸出當(dāng)前局的比分a：b。按照上述方法對每一輸入行計算11分制和21分制的比賽結(jié)果，直至文件讀完（eof(input)）為止。assign(input,inp);reset(input);{輸入文件讀準(zhǔn)備}assign(output,out);rewrite(output);{輸出文件寫準(zhǔn)備}a:=0;b:=0;{當(dāng)前局雙方的比分初始化}whilenoteof(input)do{若文件未讀完，則循環(huán)}beginwhilenoteoln(input)do{若當(dāng)前行處理完，則11分制的比賽結(jié)束}beginread(ch);{讀一個字符}casechof{根據(jù)字符的種類分情形處理}'E':begin{若比賽結(jié)束，則輸出雙方比分}writeln(a,':',b);break;{退出11分制的計算過程}end;{'E'}'W',’L’:begin{華華或?qū)Ψ降靡环謢ifch=’W’theninc(a)elseinc(b);if((a>=11)or(b>=11))and(abs(a-b)>1)then{若有一方得分達(dá)到11分且雙方的分?jǐn)?shù)差值大于1，則輸出雙方比分}beginwriteln(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);{重新讀輸入行}whilenoteof(input)do{若文件未讀完且比賽未結(jié)束，則循環(huán)}beginwhilenoteoln(input)do{若當(dāng)前行處理完，則21分制的比賽結(jié)束}beginread(ch);{讀一個字符}

casechof{根據(jù)字符的種類分情形處理}‘E’:begin{若比賽結(jié)束，則輸出雙方比分，退出21分制的計算過程}writeln(a,':',b);break;end;{'E'}'W',’L’:begin{華華或?qū)Ψ降靡环謢ifch=’W’theninc(a)elseinc(b);if((a>=21)or(b>=21))and(abs(a-b)>1){若有一方得分達(dá)到21分且雙方的分?jǐn)?shù)差值大于1，則輸出雙方比分}thenbeginwriteln(a,':',b);a:=0;b:=0;{新一局的比分初始化}end;{then}end;{'W',’L’}end;{case}end;{while}readln;end;{while}close(input);close(output);{關(guān)閉輸入文件和輸出文件}關(guān)鍵是文件操作。如果在計算21分制的得分前，不會通過reset(input)將讀頭移到文件首，則會出錯！串是由零個或多個字符組成的有限序列。一個串中包含的字符個數(shù)稱為這個串的長度。長度為零的串稱為空串，它不包含任何字符。串運(yùn)算1.連接運(yùn)算——函數(shù)concat(s1，[，s2，…，sn])：其中值參s1，‥，sn為string類型，函數(shù)值為string類型。若連接后的串長大于255，則自動截斷超出部分。2.求子串——函數(shù)copy(s，i，l)：其中值參s為string類型，i和l為integer類型。函數(shù)返回s串中第i個字符開始、長度為l的子串（string類型）。若i大于s的長度，則回送一個空串；若l大于第i個字符開始的余串長度，則僅回送余串。3.刪子串——過程delete(vars，i，l)：其中變量參數(shù)s為string類型，值參i、l為ingteger類型。該過程刪去s中第i個字符開始的長度為l的子串，并返回剩余串s。若i大于原串s的長度，則不刪任何字符；若l大于第i個字符開始的余串長度，則刪去余串。在串運(yùn)算中充分利用系統(tǒng)的庫函數(shù)4.插入子串——過程insert(s1，vars，i)：變量參數(shù)s為string類型，值參s1為string類型。該過程將s1子串插入空串s的第i個字符位置處，并返回插入后的結(jié)果s。若插入后s的串長大于255個字符，則截斷超出部分。5.求串長——函數(shù)length(s)：值參s為string類型。該函數(shù)返回s串的實際長度值（integer類型）。6.搜索子串位置——函數(shù)pos(s1，s2)：值參s1和s2為string類型。若s1是s2的一個子串，則返回s1中第1個字符在s2串中的位置（integer類型）；若s1非s2的一個子串，則返回0。7.數(shù)值轉(zhuǎn)換為數(shù)串——過程str(x，vars)：值參x為integer類型或real類型，變量參數(shù)s為string類型。該過程將返回數(shù)值x對應(yīng)的數(shù)串s。

8.數(shù)串轉(zhuǎn)換為數(shù)值——過程val(s，varv，varc)：值參s為string類型，變量參數(shù)v為integer類型或real類型，變量參數(shù)c為integer類型。該過程試將s串轉(zhuǎn)換成數(shù)值v。若轉(zhuǎn)換成功，則c為0，并返回對應(yīng)的數(shù)值v；否則c為無效字符的序數(shù)。9.字符的大寫轉(zhuǎn)換——函數(shù)upcase(ch)：值參ch為char類型。該函數(shù)返回ch字符的大寫體（char類型）數(shù)碼排序設(shè)有n個正整數(shù)，將他們連接成一排，組成一個最大的多位整數(shù).例如：n=3時，3個整數(shù)13，312，343，連成的最大整數(shù)為：34331213。又如：n=4時，4個整數(shù)7，13，4，246連接成的最大整數(shù)為7424613。程序輸入：N N個數(shù)程序輸出：連接成的多位數(shù)

由于連接后的字串長度不變，我們可以利用字符串的大小順序和十進(jìn)制的進(jìn)位關(guān)系，對n個數(shù)串s進(jìn)行排序fori←1ton-1do{順序排定s1…sn-1}forj←i+1tondoifs[i]+s[j]<s[j]+s[i]thenbegins1←s[i]；s[i]←s[j]；s[j]←s1；end；{then}fori←1tondowrite(s[i])；{輸出最大的多位整數(shù)}字符串編輯

從鍵盤輸入一個字符串(長度≤40個字符)，并以字符’.’結(jié)束.例如：’Thisisabook.’，現(xiàn)對該字符串進(jìn)行編輯，編輯功能有：D：刪除一個字符，命令的方式為：Da。其中a為被刪除的字符。例如：Ds表示刪除字符’s’，若字符串中有多個’s’，則刪除第一次出現(xiàn)的，如上例中刪除的結(jié)果為’Thiisabook.’I：插入一個字符，命令的格式為：Ia1a2。其中a1表示插入到指定字符前面，a2表示將要插入的字符。例如：Isd表示在指定字符’s’的前面插入字符’d’，若原串中有多個’s’，則插入在最后一個字符的前面。如上例中，原串：’Thisisabook.’，插入后：’Thisidsabook.’R：替換一個字符，命令格式為：Ra1a2。其中a1為被替換的字符，a2為替換的字符，若在原串中有多個a1，則應(yīng)全部替換。例如：原串：’Thisisabook.’。輸入命令：Roe，替換后：’Thisisabeek.’。在編輯過程中，若出現(xiàn)被指定的字符不存在時，則給出提示信息設(shè)s—原串和目標(biāo)串；que—命令串。其中que[1]為命令字，que[2]和que[4]為空格。que[3]和que[5]的定義如下：在D命令中，que[3]為被刪字符；在I命令中，que[3]為插入位置字符，que[5]為被插入字符；在R命令中，que[3]為被替換字符，que[5]為替換字符；刪除操作：字串S中尋找que[3]。若找不到，則失敗退出；否則，將該字符刪去：i←pos(que[3]，s)；ifi=0thenbeginwriteln(’Error!’)；halt；end{then}elsedelete(s，i，1)；插入操作：從S串尾出發(fā)，由右而左尋找que[3]字符的位置。若找不到，失敗退出；否則將que[5]字符插在該位置前

i←length(s)；{由右而左尋找que[3]字符的位置i}while(i>0)and(s[i]≠que[3])doi←i-1；ifi≠0theninsert(que[5]，s，i){將que[5]字符插在i位置前}elsebeginwriteln(’Error!’)；halt；end；{else}替換操作：從串首出發(fā)，由左而右尋找que[3]字符的位置。若找不到，失敗退出；否則將que[5]替換所有的que[3]字符：error←true；fori←1tolength(s)do{由左而右替換que[3]字符}ifs[i]=que[3]thenbeginerror←false；s[i]←que[5]；end；{then}iferrorthen{若找不到，失敗退出}beginwriteln(’Error!’)；halt；end{then}主程序輸入原串s和命令串que；caseque[1]of’D’：begin刪除操作；end；{’D’}’I’：begin插入操作；end；{’I’}’R’：begin替換操作；end；{’R’}end；{case}輸出s；字符近似查找設(shè)有n個單詞的字典表（1≤n≤100）。計算某單詞在字典表中的四種匹配情況（字典表中的單詞和待匹配單詞的長度上限為255）：i：該單詞在字典表中的序號；Ei：在字典表中僅有一個字符不匹配的單詞序號；Fi：在字典表中多或少一個字符（其余字符匹配）的單詞序號；N：其他情況當(dāng)查找時有多個單詞符合條件，僅要求第一個單詞的序號即可。輸入文件

輸入文件名為a.in，文件的格式如下：n（字典表的單詞數(shù)）n行，每行一個單詞待匹配單詞輸出文件

輸出文件名a.out，格式如下：iEiFi其中i為字典表中符合條件的單詞序號（1≤i≤n），若字典表中不存在符合條件的單詞，則對應(yīng)的i=0。若上述三種情況不存在，則輸出N。輸入輸出樣例輸入1:5abcdeabcasdfasfdabcdaacdabcd輸出1:4E5F1輸入2:1ab輸出2:0E0F0N我們將字典表中的單詞分成3類：第1類：單詞與待匹配單詞多或少一個字符，其余字符匹配；第2類：單詞僅有一個字符與待匹配單詞不匹配；第3類：單詞與待匹配單詞完全匹配；設(shè)constnote:array[1..3]ofstring=('F','E','')；{匹配情況的標(biāo)志}

varwant :string；{待匹配單詞}list :array[1..100]ofstring；{字典表。其中l(wèi)ist[i]為字典i}ans：array[1..100]ofinteger；{單詞的類別序列。其中ans[i]=}1、匹配情況的計算⑴計算兩個等長字串中不同字符的個數(shù)functionfind(a,b:string):integer；{輸入兩個等長字串a(chǎn),b，計算和返回不同字符的個數(shù)}var i,tot:integer；begin tot←0； fori←1tolength(a)doifa[i]<>b[i]theninc(tot)； find←tot；end；{find}

⑵判別一個字串是否比另一個字串多一個字符（其余字符匹配）我們不知道長度大1的字串究竟在哪個位置上多出一個字符，無奈，只能將該字串的每一個字符試插在另一個字串的對應(yīng)位置上。如果插入后使得兩串相同，則說明猜想成立。否則猜想不成立。functioncheck(a,b:string):integer；{輸入字串a(chǎn),b。若b能夠在a的基礎(chǔ)上添加一個字符得到的話，則返回1；否則返回0}var i:integer；begincheck←0；fori←0tolength(a)dobegina←copy(a,1,i)+b[i+1]+copy(a,i+1,255)；{在a[i]后插入b[i+1]}ifa=b