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

信息學(xué)奧賽教程指導(dǎo)第1頁，課件共227頁，創(chuàng)作于2023年2月6、2002、2003年分區(qū)聯(lián)賽復(fù)賽試題解析1、高精度運算2、圖的運算3、搜索算法4、構(gòu)造算法5、動態(tài)程序設(shè)計第2頁，課件共227頁，創(chuàng)作于2023年2月2002、2003年全國分區(qū)聯(lián)賽復(fù)賽試題解析第3頁，課件共227頁，創(chuàng)作于2023年2月題

型題目與課內(nèi)知識相關(guān)自由落體、級數(shù)求和、乒乓球、麥森數(shù)字符串處理字符近似查找貪心法均分紙牌、傳染病控制回溯法選數(shù)、字串變換、棧、神經(jīng)網(wǎng)絡(luò)、偵探推理動態(tài)程序設(shè)計方法過河卒、數(shù)字游戲、加分二叉樹幾何計算矩形覆蓋

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

第4頁，課件共227頁，創(chuàng)作于2023年2月特點

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

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

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

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

愛笛生小學(xué)三年級退學(xué)、比爾.蓋茨大學(xué)三年級退學(xué)）第7頁，課件共227頁，創(chuàng)作于2023年2月學(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)系，補充自己認為需要補充的知識。

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

10、數(shù)字游戲

11、棧

12、麥森數(shù)

13、神經(jīng)網(wǎng)絡(luò)

14、偵探推理

15、加分二叉樹

16、傳染病控制第11頁，課件共227頁，創(chuàng)作于2023年2月第一題：字符近似查找設(shè)有n個單詞的字典表（1≤n≤100）。計算某單詞在字典表中的四種匹配情況（字典表中的單詞和待匹配單詞的長度上限為255）：

i：該單詞在字典表中的序號；

Ei：在字典表中僅有一個字符不匹配的單詞序號；

Fi：在字典表中多或少一個字符（其余字符匹配）的單詞序號；

N：其他情況當(dāng)查找時有多個單詞符合條件，僅要求第一個單詞的序號即可。輸入文件

輸入文件名為a.in，文件的格式如下：

n（字典表的單詞數(shù)）

n行，每行一個單詞待匹配單詞

第12頁，課件共227頁，創(chuàng)作于2023年2月輸出文件

輸出文件名a.out，格式如下：

iEiFi其中i為字典表中符合條件的單詞序號（1≤i≤n），若字典表中不存在符合條件的單詞，則對應(yīng)的i=0。若上述三種情況不存在，則輸出N。輸入輸出樣例輸入1:5abcdeabcasdfasfdabcdaacdabcd輸出1:4E5F1輸入2:1ab輸出2:0E0F0N第13頁，課件共227頁，創(chuàng)作于2023年2月我們將字典表中的單詞分成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]=}第14頁，課件共227頁，創(chuàng)作于2023年2月1、匹配情況的計算⑴計算兩個等長字串中不同字符的個數(shù)functionfind(a,b:string):integer；{輸入兩個等長字串a(chǎn),b，計算和返回不同字符的個數(shù)}var i,tot:integer；begintot←0；fori←1tolength(a)doifa[i]<>b[i]theninc(tot)；find←tot；end；{find}

第15頁，課件共227頁，創(chuàng)作于2023年2月⑵判別一個字串是否比另一個字串多一個字符（其余字符匹配）我們不知道長度大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{若插入后兩串相同，則成功退出}thenbegincheck←1；exit；end；{then}delete(a,i+1,1)；{刪去a中的插入字符}end；{for}end；{check}

第16頁，課件共227頁，創(chuàng)作于2023年2月2、計算字典表中的每一類單詞首先，我們依次計算每一個單詞的類別序號?

在單詞i與待匹配單詞等長的情況下，若兩串相同，則單詞i的類別記為3；若兩串僅有一個字符不同，則單詞i的類別記為2；?

若單詞i比待匹配單詞多或少一個字符（其余字符匹配），則單詞i的類別記為1；否則單詞i的類別記為0；然后根據(jù)ans序列在字典表中依次搜索類別3‥類別1的單詞，輸出對應(yīng)的單詞序號。如果在字典表中不存在上述3種類別的單詞，則輸出‘N’。fillchar(ans,sizeof(ans),0)；{單詞的類別序列初始化}fori←1tondobegin{對字典中的每個單詞進行分類}iflength(list[i])=length(want){若單詞i與待匹配單詞等長}thenbegink←find(list[i],want)；{計算單詞i與待匹配單詞的不同字符個數(shù)}

ifk=0thenans[i]←3；{記下類別序號}ifk=1thenans[i]←2；

end；{then}第17頁，課件共227頁，創(chuàng)作于2023年2月{若單詞i比待匹配單詞多或少一個字符（其余字符匹配），則單詞i的類別記為1；否則單詞i的類別記為0} iflength(list[i])+1=length(want)thenans[i]←check(list[i],want)；

iflength(list[i])=length(want)+1thenans[i]←check(want,list[i])；

end；{for} have←false；{匹配情況存在的標(biāo)志初始化} fori←3downto1dobegin{依次輸出每一類別的單詞在字典表最先出現(xiàn)的序號} k←0；

forj←1tondoifans[j]=ithenbegink←j；break；end；{then} have←haveor(k>0)；

writeln(note[i],k)；

end；{for}第18頁，課件共227頁，創(chuàng)作于2023年2月

第二題：級數(shù)求和

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

輸入

鍵盤輸入 k

輸出

屏幕輸出 n

輸入輸出樣例

輸入: 1

輸出: 2

第19頁，課件共227頁，創(chuàng)作于2023年2月算法分析

該題考核選手的并不是編程能力，而是選擇變量類型的能力。由于該數(shù)列是遞減的，而k的上限為15，因此項數(shù)很大，即便是longint也容納不下。但未必非高精度運算不可。只要啟動浮點數(shù)運算（{$n+}），將項數(shù)設(shè)為extended類型，便可以得出正確解。{$n+}{啟動浮點數(shù)運算}var s,b,k:extended；{數(shù)列的和、項數(shù)、最接近sn(大于sn)的整數(shù)值}begin s←0；{數(shù)列的和初始化} b←0；{項數(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}第20頁，課件共227頁，創(chuàng)作于2023年2月第三題：選數(shù)

已知n個整數(shù)x1,x2,…..xn,以及一個整數(shù)k(k<n)。從n個整數(shù)中任選k個整數(shù)組合相加，可分別得到一系列的和。例如當(dāng)n=4,k=3，4個整數(shù)分別為3，7，12，19時，可得全部的組合為：

3+7+12=223+7+19=297+12+19=383+12+19=34?，F(xiàn)在，要求你計算出和為素數(shù)的組合數(shù)有多少種。例如上例，只有一種組合的和為素數(shù)：（3+7+19=29）。第21頁，課件共227頁，創(chuàng)作于2023年2月輸入輸入文件名為c.in。文件格式

n,k（1≤n≤20，k<n）

x1,x2,…xn（1≤xi≤5000000）輸出：輸出文件名為c.out。文件格式一個整數(shù)（滿足條件的種數(shù)）。輸入輸出樣例：輸入：

4371219

輸出：

1第22頁，課件共227頁，創(chuàng)作于2023年2月1、判別一個數(shù)是否為素數(shù)由于整數(shù)xi的上限為5000000，k的上限為19，這就使得判別k個整數(shù)的和是否為素數(shù)的問題變得似乎有點困難。為了保證在該范圍內(nèi)能正確出解，我們首先通過篩選法，將1―10000間的素數(shù)存入素數(shù)表prime。設(shè)varmap:array[1..10000]ofboolean；{篩}prime:array[1..5000]oflongint；素數(shù)表。其中第i個素數(shù)為prime[i]}list:array[1..20]oflongint；{待選數(shù)字集合。其中l(wèi)ist[i]為xi}tot,ans:longint；{tot為素數(shù)表的長度；和為素數(shù)的組合的個數(shù)為ans}構(gòu)造素數(shù)表prime的過程如下：tot←0；{素數(shù)表的長度初始化}fillchar(map,sizeof(map),true)；{初始時所有數(shù)在篩中}fori←2to10000do{順序搜索篩中的最小數(shù)i}ifmap[i]thenbegin forj←2to10000dividomap[i*j]←false；{將i的倍數(shù)從篩中刪去}inc(tot)；prime[tot]←i；{i進入素數(shù)表}end；{then}第23頁，課件共227頁，創(chuàng)作于2023年2月

我們在素數(shù)表prime的基礎(chǔ)上判別某數(shù)a是否為素數(shù)。任何數(shù)都可以分解成素因子的乘積形式。按照遞增方向?qū)rime表中的每一個素數(shù)去試除a。若某個素數(shù)能被a整除，則說明a為合數(shù)；若prime[i]*prime[i]>a，則說明a不可能分解出比prime[i]大的素數(shù)了，a本身為素數(shù)。由于prime[i]表的最大素數(shù)接近10000，其平方遠大于xi的上限5000000，因此是一個比較可行的方法：functioncheck(a:longint):boolean；{判斷a是否是素數(shù)}begincheck←true；{素數(shù)標(biāo)志初始化}fori←1tototdobegin{搜索素數(shù)表} ifprime[i]*prime[i]>athenexit；{若超出搜索范圍的上限，則說明a是素數(shù)，返回true} ifamodprime[i]=0thenbegincheck←false；exit；end；{then} end；{for}end；{check}

第24頁，課件共227頁，創(chuàng)作于2023年2月2、遞歸搜索方案數(shù)由于數(shù)列是隨機和無序的，因此只能通過搜索的辦法求解。設(shè)

狀態(tài)(left,now,all)：目前組合為all，還需要從xnow‥xn中選出left個數(shù)；

約束條件(left≤n-now+1)：xnow‥xn中數(shù)的個數(shù)大于等于left；

邊界條件（(left=0)and(now=n+1)）和目標(biāo)狀態(tài)（check(all)=true）：從x1‥xn中選出k個數(shù)為邊界。在這種情況下，若k個數(shù)的和為素數(shù)，則滿足條件的種數(shù)+1。到達邊界后，應(yīng)回溯；

搜索范圍為兩種選擇：

當(dāng)前組合不選xnow,遞歸計算子狀態(tài)(left,now+1,all)；

在還有數(shù)需要選的情況下（left>0），xnow選入組合，遞歸計算子狀態(tài)(left-1,now+1,all+list[now])；由此得出子程序第25頁，課件共227頁，創(chuàng)作于2023年2月Proceduresolve(left,now,all:longint)；{遞歸計算選數(shù)情況}beginif(left>n-now+1)thenexit；{若xnow‥xn中不足left個數(shù)，則回溯}if(left=0)and(now=n+1){若從x1‥xn中選出了k個數(shù)}thenbegin ifcheck(all)theninc(ans)；{若k個數(shù)的和為素數(shù)，則滿足條件的種數(shù)+1}exit；{回溯} end；{then}solve(left,now+1,all)；{當(dāng)前組合不選xnow,遞歸計算子狀態(tài)} ifleft>0{在還有數(shù)需要選的情況下，xnow選入組合，遞歸計算子狀態(tài)}thensolve(left-1,now+1,all+list[now])；end；{solve}顯然，遞歸調(diào)用solve(k,1,0)后得出的ans即為問題的解。第26頁，課件共227頁，創(chuàng)作于2023年2月過河卒如圖，A點有一個過河卒，需要走到目標(biāo)B點。卒行走的規(guī)則：可以向下、或者向右。

第27頁，課件共227頁，創(chuàng)作于2023年2月

同時在棋盤上的任一點有一個對方的馬（如上圖的C點）,該馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點。例如上圖C點上的馬可以控制8個點（圖中的P1，P2….P8）。卒不能通過對方馬的控制點。棋盤用坐標(biāo)表示，A點（0，0）、B點（n，m）(n,m為不超過20的整數(shù),并由鍵盤輸入)，同樣馬的位置坐標(biāo)是需要給出的（約定：C≠A，同時C≠B）?，F(xiàn)在要求你計算出卒從A點能夠到達B點的路徑的條數(shù)。輸入：鍵盤輸入B點的坐標(biāo)(n,m)以及對方馬的坐標(biāo)（X，Y）輸出：屏幕輸出一個整數(shù)（路徑的條數(shù)）。輸入輸出樣例：輸入：3322

輸出：0第28頁，課件共227頁，創(chuàng)作于2023年2月1、計算對方馬的控制點按照題意，對方的馬所在的點和所有跳躍一步可達的點稱為對方馬的控制點，卒不能通過對方馬的控制點。在卒出發(fā)之前，必須計算對方馬的所有控制點。顯然，若（0，0）或（n,m）為控制點，則輸出路徑數(shù)為0。設(shè)constmove:array[1..8,1..2]ofinteger=((1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1))；{move[k，1..2]為馬沿k方向跳躍一步的水平增量和垂直增量}varlist:array[-1..20,-1..20]ofcomp；{路徑數(shù)序列，其中l(wèi)ist[i,j]為卒從(0,0)到(i,j)的路徑數(shù)}can:array[0..20,0..20]ofboolean；{點(i,j)允許卒通行的標(biāo)志}馬的初始位置為（x,y）。我們按照下述方式計算can序列： can[x,y]←false；{對方馬所在的點為控制點}fori←1to8dobegin{從（x，y）出發(fā)，沿8個跳馬方向計算控制點}j←x+move[i,1]；{計算i方向的跳馬位置(j，k)}k←y+move[i,2]；

if(j>=0)and(k>=0)and(j<=n)and(k<=m){若（j,k）在界內(nèi)，則為控制點}thencan[j,k]←false；end；{for}if(notcan[0,0])or(notcan[n,m]){若卒的起點和終點為控制點，則輸出路徑數(shù)0}thenwriteln(0)elsebegin計算和輸出卒從（0，0）走到（n,m）點的路徑數(shù)list[n,m]；end；{else}第29頁，課件共227頁，創(chuàng)作于2023年2月2、 計算和輸出卒從（0，0）走到（n,m）點的路徑條數(shù)我們按照由上而下、由左而右的順序，將卒可能到達的每一個位置（i,j）(0≤i≤n，0≤j≤m)設(shè)為階段,顯然這樣做，可以取消對狀態(tài)的枚舉。首先，將卒的出發(fā)點（0，0）的路徑數(shù)設(shè)為1（list[0,0]←1），并將該位置設(shè)為控制點（can[0,0]←fals）。然后從（0，0）出發(fā)，按照由上而下、由左而右的順序計算卒經(jīng)過每一個可行點的路徑數(shù)。若（i，j）為可行點，則卒可由上側(cè)的（i-1,j）和左側(cè)的（i,j-1）進入該點。將這兩點的路徑數(shù)加起來，即為從（0，0）走到（i，j）的路徑數(shù)，即

list[i,j]=list[i-1,j]+list[i,j-1]∣（i，j）非控制點依次類推，最后得出的list[n,m]即為問題的解。由此得出算法：

fillchar(list,sizeof(list),0)；{路徑數(shù)序列初始化}list[0,0]←1；{卒從（0，0）出發(fā)的路徑數(shù)為1，該位置不再允許卒通行}can[0,0]←false；

fori←0tondo{對于每個可行點,小兵要么從左側(cè)、要么從上方走到,由此計算從(0,0)到(i,j)的路徑數(shù)}forj←0tomdoifcan[i,j]thenlist[i,j]←list[i-1,j]+list[i,j-1]；輸出卒從（0，0）走到（n,m）點的路徑條數(shù)list[n,m]；第30頁，課件共227頁，創(chuàng)作于2023年2月題一均分紙牌[問題描述]

有N堆紙牌，編號分別為1，2，….N。每堆上有若干張，但紙牌總數(shù)必為N的倍數(shù)?？梢栽谌我欢焉先∪舾蓮埣埮?，然后移動。移牌規(guī)則為：在編號為1堆上取的紙牌，只能移到編號為2的堆上；在編號為N的堆上取的紙牌，只能移到編號為N-1的堆上；其他堆上取的紙牌，可以移到相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動方法，用最少的移動次數(shù)使每堆上紙牌數(shù)都一樣多。例如N=4，4堆紙牌數(shù)分別為：①9②8③17④6移動3次可達到目的：從③取4張牌放到④（981310）→從③取3張牌放到②（9111010）→從②取1張牌放到①（10101010）。[輸入]：N

（N堆紙牌，1≤N≤100）

A1，A2，….An(N堆紙牌，每堆紙牌初始數(shù)，1≤Ai≤10000)[輸出]：所有堆均達到相等時的最少移動次數(shù)。[輸入輸出樣例]第31頁，課件共227頁，創(chuàng)作于2023年2月輸入：

498176

輸出：

3設(shè)list為紙牌序列，其中l(wèi)ist[i]為第i堆紙牌的張數(shù)（1≤i≤n），ave為均分后每堆紙牌的張數(shù)，即；ans為最少移動次數(shù)。我們按照由左而右的順序移動紙牌。若第i堆紙牌的張數(shù)list[i]超出平均值，則移動一次(ans+1)，將超出部分留給下一堆，既第i+1堆紙牌的張數(shù)增加list[i]-ave；若第i堆紙牌的張數(shù)list[i]少于平均值，則移動一次(ans+1)，由下一堆補充不足部分，既第i+1堆紙牌的張數(shù)減少ave-list[i]；右鄰堆取的牌第32頁，課件共227頁，創(chuàng)作于2023年2月問題是，在從第i+1堆中取出紙牌補充第i堆的過程中，可能會出現(xiàn)第i+1堆的紙牌數(shù)小于零(list[i+1]-(ave-list[i])<0)的情況，這時可以理解為一個“先出后進”的棧。由于紙牌的總數(shù)是n的倍數(shù)，因此后面的堆會補充第i+1堆ave-list[i]-list[i+1]+ave張紙牌，使其達到均分的要求。

第四堆補充第三堆第三堆補充第二堆第二堆補充第一堆在枚舉分牌方案時，是否可以利用上述計數(shù)方法呢？第33頁，課件共227頁，創(chuàng)作于2023年2月題二字串變換[問題描述]：已知有兩個字串A$，B$及一組字串變換的規(guī)則：

A1$→B1$A2$→B2$………規(guī)則的含義為：在A$中的子串A1$可以變換為B1$、A2$可以變換為B2$…..。例如：A$=‘a(chǎn)bcd’B$=‘xyz’變換規(guī)則為：‘a(chǎn)bc’→‘xu’‘ud’→‘y’‘y’→‘yz’則此時，A$可以經(jīng)過一系列的變換變?yōu)锽$，其變換的過程為：‘a(chǎn)bcd’→‘xud’→‘xy’→‘xyz’共進行了三次變換，使得A$變換為B$。第34頁，課件共227頁，創(chuàng)作于2023年2月[輸入]：輸入文件名為A.in。文件格式如下：

A$，B$A1$→B1$A2$→B2$變換規(guī)則

………所有字符串長度的上限為255。[輸出]：輸出文件名為A.out。若在30步（包含30步）以內(nèi)能將A$變換為B$，則向A.out輸出最少的變換步數(shù)；否則向A.out輸出‘ERROR！’。[輸入輸出樣例]A.in文件：abcd,xyzabc->xuud->yy->yzA.out文件：

3第35頁，課件共227頁，創(chuàng)作于2023年2月1、分析變換規(guī)則設(shè)規(guī)則序列為rule，其中第i條規(guī)則為rule[i，1]→rule[i，2]；當(dāng)前串為now，其中tmp為now的一個待匹配子串。由于匹配過程的由左而右進行的，因此設(shè)j為now的指針，即從now的第j個字符開始匹配rule[i,1]。now適用第i條規(guī)則的條件是now中的子串被第i條規(guī)則替換后的長度小于255，即

length(now)+length(rule[i,2])-length(rule[i,1])≤255rule[i,1]是now的一個子串（k=pos(rule[i,1],tmp)≠0）在使用了第i條規(guī)則后，now變換為now=copy(now,1,j+k-1)+rule[i,2]+copy(now,j+k+length(rule[i,1]),255)由于now中可能有多個子串被第i條規(guī)則替換，因此每替換一次后，為了方便地找出下一個替換位置，我們將當(dāng)前被替換串前（包括被替換串）的子串刪除。第36頁，課件共227頁，創(chuàng)作于2023年2月2、使用回溯法計算最少替換次數(shù)由于原串a(chǎn)、目標(biāo)串b和規(guī)則rule是隨機輸入的，因此不可能找出直接計算最少替換次數(shù)best的數(shù)學(xué)規(guī)律，只能采用回溯搜索的辦法。設(shè)

狀態(tài)（need,now）:替換次數(shù)為need，替換結(jié)果為now；

邊界條件（need≥best）和目標(biāo)狀態(tài)（now=b）：替換次數(shù)達到或超過目前得出的最小值為邊界；已經(jīng)替換出目標(biāo)串為目標(biāo)狀態(tài)；

搜索范圍i：嘗試每一條規(guī)則,即1≤i≤規(guī)則數(shù)n；約束條件（length(now)+length(rule[i,2])-length(rule[i,1])≤255）：now中的子串被第i條規(guī)則替換后的長度小于255；由此得出計算過程：第37頁，課件共227頁，創(chuàng)作于2023年2月proceduresolve(need；now)；{從當(dāng)前串now出發(fā)，遞歸第need次替換}vari,k,j:integer；tmp:string；beginifneed>=bestthenexit； {若到達邊界，則回溯}ifnow=bthenbegin{若達到目標(biāo)狀態(tài)，則記下替換次數(shù)，并回溯} best←need；exit；

end；{then}fori←1tondo{搜索每一條規(guī)則}

第38頁，課件共227頁，創(chuàng)作于2023年2月iflength(now)+length(rule[i,2])-length(rule[i,1])<=255thenbegin{若使用了第i條規(guī)則后，串長不會超過上限}j←0；tmp←now；{匹配指針初始化和待匹配子串初始化}k←pos(rule[i,1],tmp)；{嘗試第i條規(guī)則}whilek>0do{反復(fù)在tmp中尋找子串rule[i,1]}beginsolve(need+1，copy(now,1,j+k-1)+rule[i,2]+copy(now，j+k+length(rule[i，1])，255))；{遞歸下一次替換}delete(tmp,1,k)；{將當(dāng)前被替換串前（包括被替換串）的子串刪除}j←j+k；{右移匹配指針}k←pos(rule[i,1],tmp)；{繼續(xù)嘗試第i條規(guī)則}end；{while}end；{then}end；{solve}第39頁，課件共227頁，創(chuàng)作于2023年2月由此得出主程序： 讀入初始串a(chǎn)和目標(biāo)串； 讀入替換規(guī)則rule；

best←31；{設(shè)定替換次數(shù)的上限} solve(0,a)； {回溯搜索最少的替換次數(shù)} ifbest<=30{輸出最少替換次數(shù)}thenwriteln(best)elsewriteln('ERROR!')；、第40頁，課件共227頁，創(chuàng)作于2023年2月題三自由落體[問題描述]:在高為H的天花板上有n個小球，體積不計，位置分別為0，1，2，…n-1。在地面上有一個小車(長為L，高為K，距原點距離為S1)。已知小球下落距離計算公式為

S=1/2*g*t2，其中

g=10，

t為下落時間。地面上的小車以速度

V前進。如下圖：

小車與所有小球同時開始運動，當(dāng)小球距小車的距離≤0.00001時，即認為小球被小車接受（小球落到地面后不能被接受）。請你計算出小車能接受到多少個小球。[輸入]：H，S1，v，L，k，n（1≤H，S1，v，L，k，n≤100000）[輸出]：小車能接受到的小球個數(shù)。

這是分區(qū)聯(lián)賽最容易失誤的一道試題，關(guān)鍵是弄清小車行程的物理意義和計算的精度誤差！第41頁，課件共227頁，創(chuàng)作于2023年2月算法分析由題意可知，車頂與天花板的距離為h-k，小球由天花板落至車頂所花費的時間為t1=，由天花板落至地面的時間為t2=。小車與所有小球同時開始運動，當(dāng)小球距小車的距離≤0.00001時，即認為小球被小車接受（小球落到地面后不能被接受）。顯然，若n1≥n2，則小車接受的小球數(shù)為n1-n2+1；否則小車未接受任何一個小球。

小車在行駛了t1*v-0.00001路程后接受了第一個小球，其編號為n1=min{n-1,}小車在行駛了t2*v+0.00001路程后小球落地，小車接受最后一個小球的編號為n2=max{0，}。為什么在n1的公式中加上L？為什么在n2的公式中加上0.5？為什么n1取下整、n2取上整？第42頁，課件共227頁，創(chuàng)作于2023年2月矩形覆蓋[問題描述]：在平面上有n個點(n≤100)，每個點用一對整數(shù)坐標(biāo)表示。例如：當(dāng)n=4時，4個點的坐標(biāo)分別為：p1(1，1)，p2(2，2)，p3(6，3)，p4(7，0)這些點可以用k個矩形(k<4)全部覆蓋，矩形的邊平行于坐標(biāo)軸。如圖一，當(dāng)k=2時，可用如圖二的兩個矩形s1，s2覆蓋，s1，s2面積和為4。問題是當(dāng)n個點坐標(biāo)和k給出后，怎樣才能使得覆蓋所有點的k個矩形的面積之和為最小呢。約定：覆蓋一個點的矩形面積為0；覆蓋平行于坐標(biāo)軸直線上點的矩形面積也為0；各個矩形間必須完全分開（邊線也不能重合）；

本試題是高中組復(fù)賽中最難的一道試題，對選手的幾何基礎(chǔ)和編程能力是一個比較嚴峻的考驗。

第43頁，課件共227頁，創(chuàng)作于2023年2月算法分析

1、點和矩形的描述和關(guān)系

平面上的點由坐標(biāo)（x,y）表示。由于計算過程是按照由下而上、由左而右進行的，因此我們按照x坐標(biāo)遞增的順序和y坐標(biāo)遞增的順序?qū)個點存入a序列。矩形由2條平行于x軸的邊界線和2條平行于y軸的邊界線圍成。為了計算最小矩形的方便，我們將空矩形的左邊界設(shè)為∞、右邊界為設(shè)-∞、下邊界設(shè)為∞、上邊界設(shè)為-∞。第44頁，課件共227頁，創(chuàng)作于2023年2月2、計算覆蓋所有點的一個最小矩形設(shè)目前最小矩形的四條邊界為maxx，maxy，minx，miny。如何按照面積最小的要求將a點加入矩形呢？顯然需要調(diào)整邊界線，使a點位于對應(yīng)的邊界線上。初始時，我們設(shè)最小矩形為空，即左邊界left為∞、右邊界right為-∞、下邊界top為∞、上邊界bottom為-∞。然后由左而右，依次往矩形放入n個點，調(diào)整對應(yīng)的邊界線。最后得出的矩形為最小矩形，其面積為（右邊界-左邊界）*（上邊界-下邊界）第45頁，課件共227頁，創(chuàng)作于2023年2月3、計算覆蓋所有點的兩個面積和最小的獨立矩形

我們稱彼此完全分開的矩形是獨立的。兩個覆蓋所有點的獨立矩形有兩種形態(tài)：

我們將覆蓋x軸左方點集a[1,1..j]的最小獨立矩形存入tac[1,j]；將覆蓋x軸右方點集a[1,j..n]的最小獨立矩形存入tdc[1,j]；將覆蓋y軸下方點集a[2,1..j]的最小獨立矩形存入tac[2,j]；將覆蓋y軸上方點集a[2,j..n]的最小獨立矩形存入tdc[2,j]（注意：當(dāng)k=3時，對應(yīng)的點集不包括被矩形1覆蓋的點（1≤j≤n）。Tac[1,j-1]Tdc[1,j]Tac[2,j-1]Tdc[2,j]為什么一定要考慮兩個軸向,如果僅考慮一個軸向的話,有什么反例?第46頁，課件共227頁，創(chuàng)作于2023年2月問題是面積和最小的兩個獨立矩形究竟取哪一個形態(tài)，區(qū)分兩個矩形的分界線j為何值，我們無法確定。不得已，只能將所有可能的情況枚舉出來。設(shè)varbest，now:longint；{兩個獨立矩形的最小面積和、當(dāng)前方案中兩個獨立矩形的面積和}枚舉過程如下：計算tac和tdc序列；

best←maxlongint；{最小矩形面積初始化}fori←1to2dobegin{依次分析x軸向和y軸向}k=3時順序?qū)ふ襥軸向上第一個未被矩形1覆蓋的點j；

whilej≤ndo{枚舉i軸向上所有可能的兩個獨立矩形，從中找出最佳方案}begin

記下i軸向上點j的坐標(biāo)h；順序?qū)ふ襥軸向上最接近h點(k=3時，該點未被矩形1覆蓋)的點j；

第47頁，課件共227頁，創(chuàng)作于2023年2月if點j存在并且k=2，或者k=3時以點j為分界線的左矩形和右矩形與矩形1沒有交集

thenbeginnow←(tac[i，j-1，1]-tac[i，j-1，3])*(tac[i，j-1，2]-tac[i，j-1，4])+(tdc[i，j，1]-tdc[i，j，3])*(tdc[i，j，2]-tdc[i，j，4])；{則計算兩個獨立矩形的面積和}ifnow<bestthenbest←now；{若面積和為目前最小，則記下}end；{then}end；{while}end；{for}ifbest=maxlongint{若找不到的兩個獨立矩形}then返回失敗標(biāo)志-1else返回兩個矩形的最小面積和best；end；{getans}

第48頁，課件共227頁，創(chuàng)作于2023年2月4、計算覆蓋所有點的三個面積和最小的獨立矩形

我們先枚舉第一個矩形，該矩形覆蓋x軸向上的點1、點i、點j、點h（1≤i≤n,i≤j≤n,j≤h≤n）,求出覆蓋它們的最小矩形。該矩形的上邊界、下邊界、左邊界和右邊界分別記為bottom、top、left、right。顯然其面積為(bottom-top)*(right-left)。我們將該矩形稱為矩形1。那么，平面上還有哪些點未在矩形1內(nèi)，這些點將被另外兩個獨立的矩形所覆蓋。判斷（x,y）是否在矩形1內(nèi)的條件

(x≥left)and(x≤right)and(y≤bottom)and(y≥top)

判斷矩形是否與矩形1相交的條件(min(x1,right)≥max(x2,left))and(min(y1,bottom)≥max(y2,top))第49頁，課件共227頁，創(chuàng)作于2023年2月我們在得出矩形1的基礎(chǔ)上，直接調(diào)用上述算法計算與矩形1分開的另外兩個獨立矩形的面積和，加上矩形1的面積便是三個獨立矩形的面積和。問題是矩形1究竟覆蓋了哪些點才能得出最優(yōu)解呢？我們無法得知。無奈之下，只能通過枚舉法搜索所有的可能情況 fori←1tondo{枚舉x軸向上三個點（點i、點j、點h）的所有可能組合}forj←itondoforh←jtondobegin

計算覆蓋點1、點i、點j、點h的最小矩形（矩形1）的四條邊界right、bottom、left、top；

now←(bottom-top)*(right-left)；{計算矩形1的面積}

計算未被矩形1覆蓋的點集u；計算覆蓋u且與矩形1不相交的兩個獨立矩形的最小面積和g；

if(g≥0)and(g+now<best)thenbest←g+now；{若三個獨立矩形的面積和為目前最小，則記下}end；{for}

輸出最小面積和best；

第50頁，課件共227頁，創(chuàng)作于2023年2月由此得出主程序：讀點數(shù)n和矩形數(shù)k；讀平面上的n個點；分別沿x軸和y軸對n個點進行排序；casekof1:

計算和輸出覆蓋所有點的一個最小矩形面積；2:

計算和輸出覆蓋所有點的兩個最小獨立矩形的面積和；3:

計算和輸出覆蓋所有點的三個最小獨立矩形的面積和；end；{case}

如果k≥4，則算法將如何修改？第51頁，課件共227頁，創(chuàng)作于2023年2月一、NOIP2003普及組復(fù)賽試題

題一、乒乓球（Table.pas）【問題背景】國際乒聯(lián)現(xiàn)在主席沙拉拉自從上任以來就立志于推行一系列改革，以推動乒乓球運動在全球的普及。其中11分制改革引起了很大的爭議，有一部分球員因為無法適應(yīng)新規(guī)則只能選擇退役。華華就是其中一位，他退役之后走上了乒乓球研究工作，意圖弄明白11分制和21分制對選手的不同影響。在開展他的研究之前，他首先需要對他多年比賽的統(tǒng)計數(shù)據(jù)進行一些分析，所以需要你的幫忙。

【問題描述】華華通過以下方式進行分析，首先將比賽每個球的勝負列成一張表，然后分別計算在11分制和21分制下，雙方的比賽結(jié)果（截至記錄末尾）。比如現(xiàn)在有這么一份記錄，（其中W表示華華獲得一分，L表示華華對手獲得一分）：第52頁，課件共227頁，創(chuàng)作于2023年2月WWWWWWWWWWWWWWWWWWWWWWLW在11分制下，此時比賽的結(jié)果是華華第一局11比0獲勝，第二局11比0獲勝，正在進行第三局，當(dāng)前比分1比1。而在21分制下，此時比賽結(jié)果是華華第一局21比0獲勝，正在進行第二局，比分2比1。如果一局比賽剛開始，則此時比分為0比0。你的程序就是要對于一系列比賽信息的輸入（WL形式），輸出正確的結(jié)果。

【輸入格式】每個輸入文件包含若干行字符串（每行至多20個字母），字符串有大寫的W、L和E組成。其中E表示比賽信息結(jié)束，程序應(yīng)該忽略E之后的所有內(nèi)容。

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

第53頁，課件共227頁，創(chuàng)作于2023年2月算法分析

首先，對當(dāng)前輸入行計算11分制下每一局比賽的比分。設(shè)a為當(dāng)前局華華的得分，每輸入一個‘W’，a+1；b為當(dāng)前局對方的得分，每輸入一個‘L’，b+1。若輸入‘E’或者華華的得分a或者對方得分b達到11分且雙方的分數(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達到21分且雙方的分數(shù)差值大于1（((a≥21)or(b≥21))and(abs(a-b)>1)），則輸出當(dāng)前局的比分a：b。按照上述方法對每一輸入行計算11分制和21分制的比賽結(jié)果，直至文件讀完（eof(input)）為止。第54頁，課件共227頁，創(chuàng)作于2023年2月assign(input,inp);reset(input);{輸入文件讀準備}assign(output,out);rewrite(output);{輸出文件寫準備}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{若有一方得分達到11分且雙方的分數(shù)差值大于1，則輸出雙方比分}beginwriteln(a,':',b);

第55頁，課件共227頁，創(chuàng)作于2023年2月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);{讀一個字符}

第56頁，課件共227頁，創(chuàng)作于2023年2月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){若有一方得分達到21分且雙方的分數(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)閉輸入文件和輸出文件}第57頁，課件共227頁，創(chuàng)作于2023年2月數(shù)字游戲（Game.pas）

丁丁最近沉迷于一個數(shù)字游戲之中。這個游戲看似簡單，但丁丁在研究了許多天之后卻發(fā)覺原來在簡單的規(guī)則下想要贏得這個游戲并不那么容易。游戲是這樣的，在你面前有一圈整數(shù)（一共n個），你要按順序?qū)⑵浞譃閙個部分，各部分內(nèi)的數(shù)字相加，相加所得的m個結(jié)果對10取模后再相乘，最終得到一個數(shù)k。游戲的要求是使你所得的k最大或者最小。例如，對于下面這圈數(shù)字（n=4，m=2）：第58頁，課件共227頁，創(chuàng)作于2023年2月當(dāng)要求最小值時，((2-1)mod10)×((4+3)mod10)=1×7=7，要求最大值時，為((2+4+3)mod10)×(-1mod10)=9×9=81。特別值得注意的是，無論是負數(shù)還是正數(shù)，對10取模的結(jié)果均為非負值。丁丁請你編寫程序幫他贏得這個游戲。

【輸入格式】輸入文件第一行有兩個整數(shù)，n（1≤n≤50）和m（1≤m≤9）。以下n行每行有個整數(shù)，其絕對值不大于104，按順序給出圈中的數(shù)字，首尾相接。

【輸出格式】輸出文件有兩行，各包含一個非負整數(shù)。第一行是你程序得到的最小值，第二行是最大值。第59頁，課件共227頁，創(chuàng)作于2023年2月算法分析

設(shè)圓周上的n個數(shù)字為a1、a2、…an。按照模運算的規(guī)則（a1+a2+…+ak）mod10=(a1mod10+a2mod10+akmod10)mod10；g[i，j]為ai、ai+1、…aj的數(shù)和對10的模，即

g[i，j]=（ai+ai+1+…+aj）mod10顯然

g[i，i]=（aimod10+10）mod10g[i，j]=(g[i,j-1]+g[j,j])mod10(1≤i≤n，i+1≤j≤n)當(dāng)m=1時，程序得到的最小值和最大值為g[1,n]；第60頁，課件共227頁，創(chuàng)作于2023年2月fmax1[p,I,j]為ai、ai+1、…aj分為p個部分，各部分內(nèi)的數(shù)字相加，相加所得的p個結(jié)果對10取模后再相乘，最終得到最大數(shù)。顯然，fmax1[1,i,j]=g[i，j]；fmin1[p,I,j]為ai、ai+1、…aj分為p個部分，各部分內(nèi)的數(shù)字相加，相加所得的p個結(jié)果對10取模后再相乘，最終得到最小數(shù)。顯然，fmin1[1,i,j]=g[i，j]；(1≤p≤m)問題是當(dāng)ai、ai+1、…aj劃分成的部分數(shù)p大于1時，怎么辦。我們采用動態(tài)程序設(shè)計的方法計算。第61頁，課件共227頁，創(chuàng)作于2023年2月設(shè)階段p：劃分成的部分數(shù),2≤p≤m-1；狀態(tài)（i，j）:將ai、ai+1、…aj劃分成p個部分，1≤i≤n，i≤j≤n；決策k:

將ai、ai+1、…ak劃分成p-1個部分，ak+1、…aj為第p部分，i≤k≤j-1；顯然，狀態(tài)轉(zhuǎn)移方程為

fmin1[p,i,j]={fmin1[p-1,i,k]*g[k+1,j]}fmax1[p,i,j]={fmax1[p-1,i,k]*g[k+1,j]}2≤p≤m-1第62頁，課件共227頁，創(chuàng)作于2023年2月max=min=

由于p-1階段僅和p階段發(fā)生聯(lián)系，因此我們將p-1階段的狀態(tài)轉(zhuǎn)移方程fmin1[p-1,i,j]設(shè)為fmin1[i,j]、fmax1[p-1,i,j]設(shè)為fmax1[i,j]，將p階段的狀態(tài)轉(zhuǎn)移方程fmin1[p,i,j]設(shè)為fmin[i,j]、fmax1[p,i,j]設(shè)為fmax[i,j]。第63頁，課件共227頁，創(chuàng)作于2023年2月read(n,m);{讀數(shù)字個數(shù)和劃分的部分數(shù)}fillchar(fmax1,sizeof(fmax1),0);fillchar(fmin1,sizeof(fmin1),$FF);{狀態(tài)轉(zhuǎn)移方程初始化}fillchar(g,sizeof(g),0);fori:=1tondo{依次讀入每個數(shù)，一個數(shù)組成一部分}beginread(g[i,i]);g[i,i]:=(g[i,i]modmask+mask)modmask;min1[i,i]:=g[i,i];fmax1[i,i]:=g[i,i];end;{for}fori:=1tondo{計算一部分內(nèi)的數(shù)和對10的模的所有可能情況}forj:=i+1tondo

beging[i,j]:=(g[i,j-1]+g[j,j])modmask;fmax1[i,j]:=g[i,j];fmin1[i,j]:=g[i,j];end;{for}forp:=2tom-1do{階段：遞推計算劃分2部分…m-1部分的結(jié)果值}beginfillchar(fmax,sizeof(fmax),0);{劃分p部分的狀態(tài)轉(zhuǎn)移方程初始化}fillchar(fmin,sizeof(fmin),$FF);

第64頁，課件共227頁，創(chuàng)作于2023年2月fori:=1tondo{狀態(tài)：枚舉被劃分為p部分的數(shù)字區(qū)間}forj:=itondofork:=itoj-1do{決策：ai…ak被劃分為p-1部分}beginiffmax1[i,k]*g[k+1,j]>fmax[i,j]{計算將ai、ai+1、…aj劃分成p個部分的狀態(tài)轉(zhuǎn)移方程}thenfmax[i,j]:=fmax1[i,k]*g[k+1,j];

if(fmin1[i,k]>=0)and((fmin1[i,k]*g[k+1,j]<fmin[i,j])or(fmin[i,j]<0))thenfmin[i,j]:=fmin1[i,k]*g[k+1,j];end;{for}fmin1:=fmin;fmax1:=fmax;end;{for}max:=0;min:=maxlongint;{將a1、a2、…an劃分成m個部分的最大值和最小值初始化}ifm=1{計算n個數(shù)劃分成一部分的最大值和最小值}thenbeginmax:=g[1,n];min:=g[1,n];end{then}

第65頁，課件共227頁，創(chuàng)作于2023年2月elsefori:=1tondo{將a1…ai-1、aj+1…an設(shè)為第m部分，計算最大值和最小值}forj:=itondoif(i<>1)or(j<>n)thenbeginif(g[1,i-1]+g[j+1,n])modmask*fmax1[i,j]>maxthenmax:=(g[1,i-1]+g[j+1,n])modmask*fmax1[i,j];if(fmin1[i,j]>=0)and((g[1,i-1]+g[j+1,n])modmask*fmin1[i,j]<min)thenmin:=(g[1,i-1]+g[j+1,n])modmask*fmin1[i,j];end;{then}writeln(min);writeln(max);{輸出最小值和最大值}第66頁，課件共227頁，創(chuàng)作于2023年2月棧（Stack.pas）

【問題背景】棧是計算機中經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，簡單的說，棧就是限制在一端進行插入刪除操作的線性表。棧有兩種最重要的操作，即pop（從棧頂彈出一個元素）和push（將一個元素進棧）。棧的重要性不言自明，任何一門數(shù)據(jù)結(jié)構(gòu)的課程都會介紹棧。寧寧同學(xué)在復(fù)習(xí)棧的基本概念時，想到了一個書上沒有講過的問題，而他自己無法給出答案，所以需要你的幫忙?！締栴}描述】第67頁，課件共227頁，創(chuàng)作于2023年2月寧寧考慮的是這樣一個問題：一個操作數(shù)序列，從1，2，一直到n（圖示為1到3的情況），棧A的深度大于n。現(xiàn)在可以進行兩種操作，1.將一個數(shù)，從操作數(shù)序列的頭端移到棧的頭端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的push操作）2.將一個數(shù)，從棧的頭端移到輸出序列的尾端（對應(yīng)數(shù)據(jù)結(jié)構(gòu)棧的pop操作）1113使用這兩種操作，由一個操作數(shù)序列就可以得到一系列的輸出序列，下圖所示為由123生成序列231的過程。（原始狀態(tài)如上圖所示）你的程序?qū)o定的n，計算并輸出由操作數(shù)序列1，2，…，n經(jīng)過操作可能得到的輸出序列的總數(shù)。第68頁，課件共227頁，創(chuàng)作于2023年2月【輸入格式】輸