1、學習之前的建議：熟練三種結構 熟練三種循環熟練自定義函數、過程熟練一維數組操作熟練字符串包括相關函數與過程 了解字符串與一維數組之間的轉換關系了解文本文件操作其他： 1、程序閱讀能力打草稿 2、簡單的推算 3、簡單數學建模Pascal常用算法By阿默2021.8如何研究算法算法是指解決問題的方法和步驟代碼！如何讓根本算法成竹于胸？不要背代碼如何學習別人寫的程序？讀程序打草稿多嘗試思維訓練而非寫代碼草稿演算利用Fp調試功能來觀察數據變化F7+watch第一局部 數論算法素數判定最大公約數最小公倍數素數判定素數定義：除了1和本身之外，沒有其它的約數。思路：給出任意數N分別用(2,sqrt(N)之間

2、的整除去除N，如果N被任意一個整除就說明N不是素數，否那么就是素數大致算法flag:=true; 先假設N是素數，設立布爾型標志flag為true for i:=2 to trunc(sqrt(N) do if N mod i=0 then 如果N被i整除 beginflag:=false; N的標志量置為false，說明N不是素數break; 可以立即跳出循環，不需要再循環了 end;writeln(flag); 輸出標志量flag試除法判斷素數算法將其設計成一個函數模塊function isprime(x:longint):boolean; var i:longint; flag:bool

3、ean; begin flag:=true; for i:=2 to trunc(sqrt(x) do if x mod i=0 then begin flag:=false; break; end; isprime:=flag; end; var n:longint;主程序開始 begin readln(n); writeln(n,-,isprime(n) ; end./最簡化寫法，此算法不兼容tpfunction isprime(x:longint):boolean;var i:longint;begin isprime:=true; for i:=2 to trunc(sqrt(x) d

4、o if x mod i=0 then exit(false); /fp下exit過程可以帶參數返回end;isprime.pas引在紙上寫一行數字，從2到24將2的倍數劃去，將3的倍數劃去。都不劃本身。你發現了什么？恭喜你！你已經找出了24以內的所有素數。問：如果要找出100以內所有的素數，劃幾次？篩法策略求某個區間的所有素數var a:array2.1000000 of boolean; n,i,j:longint;begin readln(n); fillchar(a,sizeof(a),true); for i:=2 to trunc(sqrt(n) do if ai then for

5、 j:=2 to n div i do ai*j:=false;for i:=2 to n do if ai then write(i, );end.此句fillchar用法就相當于把整個數組元素的值都改為TRUE。如果數組過大，仍需要花費較多時間。怎么辦？我們去除這個fillchar，稍微改寫一下程序，利用原來的默認值就好了！/如果當前下標是素數才去篩/從2倍開始到n div i倍為止，否那么就要越界了/數值i的j倍這個數當然不是素數，就打上標記shai.pas篩法是一個策略篩法不是一個具體的算法，而是一個策略，篩法最大的優點就是時間！在1s內求出2N之間的素數時，用試除法的話N10萬之后根

6、本就超時了，而用篩法N最大可以大到一千萬左右。當然，沒有絕對的優勢，篩法的劣勢就在于需要用到大量的空間，本來篩法就是一個用空間換取時間的策略。請估算N=50000000的時候采用篩法求素數是否會超過市賽中程序規定的內存空間？布爾型按1字節計算。篩法策略其它典型問題約數研究common.pas 小聯最近在研究和約數有關的問題，每個正整數N2N5000000至少有兩個約數，最小的一個是1，但小聯并不關心它，因為所有正整數最小約數都是1。小聯關心是正整數的第二小約數，并f(N)來表示，下表給出了一些f(N)的取值： N 2 3 4 5 f(N) 2 3 2 5現在小聯需要統計f(2) 到f(N)的累

7、加和M。樣例輸入：5樣例輸出：12 common.pas最大公約數算法文字描述：1m除以n得到的余數為r；2假設 r=0 那么 算法結束，n為最大公約數3m=n，n=r，轉 1數字演算過程：MNR188118811891890function gcd(a,b:integer):integer; var t:integer;begin while a mod b 0 do begin t:=a mod b; a:=b; b:=t; end; gcd:=b;end;common.pas換種思路，精簡一下function gcd(x,y:longint):longint;begin if x mod

8、 y=0 then gcd:=y else gcd:=gcd(y,x mod y);end;gcd2.pas換種思路，換種算法？有a，b兩數，設c=mina,b ，然后利用從c至1逐個去試除 a ，b兩數，一旦通過試除立即退出即得解。var a,b,c,i:longint;begin readln(a,b); if aaj then m:=j; t:=am;am:=ai;ai:=t; end; for i:=1 to 10 do write(ai, ); writeln;end.n個數的排序中，比較了多少次？交換了多少次？優化？xz.pas多路排序多路排序是信息學奧賽初學者必須掌握的內容之一，

9、其大意是按照某一關鍵字進行排序，當這個關鍵字相同，那么按照第二關鍵字進行排序，當第二關鍵字再相同，就按照第三關鍵字排序，依此類推。解決這個問題最普遍的方法是利用條件結構進行邏輯判斷，然后進行多路選擇。練習輸入一組學生成績，按照成績從高到底進行排序，如果成績相同，那么按照學號從小到大排。輸入：6100 60 80 81 60 100輸出：1 1006 1004 813 802 605 60設數組a保存成績，數組h保存學號，那么此題的比較條件為：(amhj)duolu.pas深入理解選擇排序多路排序： 在對數據進行排序時，需要先后參照幾個條件進行排序。經過這兩個排序，你是否理解了選擇排序？?獎學金

10、? - 排五個！?精挑細選?- 排一個！scholar.pasbest.pas冒泡排序冒泡排序的根本概念是：依次比較相鄰的兩個數，將小大數放在前面，小大數放在后面。數據演示：利用重的下沉思路初始 49 38 65 97 76 13 27 49第一趟結束 38 49 65 76 13 27 49 97第二趟結束 38 49 65 13 27 49 76 97第三趟結束 38 49 13 27 49 65 76 97第四趟結束 38 13 27 49 49 65 76 97第五趟結束 13 27 38 49 49 65 76 97第六趟結束 13 27 38 49 49 65 76 97第七趟結束

11、 13 27 38 49 49 65 76 97var a:Array1.1000 of longint; n,i,j,t:longint;begin randomize; readln(n); for i:=1 to n do begin ai:=random(100); write(ai, ); end; writeln; for i:=1 to n-1 do /冒泡開始，一共經歷n-1趟循環 for j:=1 to n-i do if ajaj+1 then begin t:=aj;aj:=aj+1;aj+1:=t; end; for i:=1 to n do write(ai, );e

12、nd.當n=10時，一共比較了多少次？最差的情況下需要交換多少次？數據演示：利用重的下沉思路初始 49 38 65 97 76 13 27 49第一趟結束 38 49 65 76 13 27 49 97第二趟結束 38 49 65 13 27 49 76 97第三趟結束 38 49 13 27 49 65 76 97第四趟結束 38 13 27 49 49 65 76 97第五趟結束 13 27 38 49 49 65 76 97第六趟結束 13 27 38 49 49 65 76 97第七趟結束 13 27 38 49 49 65 76 97觀察第六趟結束后，排序其實已經完成了，那我們如何判

13、斷此時排序已經結束？在一趟中沒有發生數據交換！var a:Array1.1000 of longint; n,i,j,t:longint; flag:boolean;begin randomize; readln(n); for i:=1 to n do begin ai:=random(100);write(ai, ); end; writeln; for i:=1 to n-1 do begin flag:=false; /一趟開始，還沒有進行交換 for j:=1 to n-i do if ajaj+1 then begin t:=aj;aj:=aj+1;aj+1:=t; flag:=t

14、rue;/執行到此處，說明發生了交換。 end; if not flag then break;/沒有交換，那么說明已經排序完成，直接跳出 end; for i:=1 to n do write(ai, );end.經過優化之后的冒泡排序，效率提高在什么地方？優化前后哪個量沒有變？maopao.pas深入理解冒泡在一個舊式的火車站旁邊有一座橋，其橋面可以繞河中心的橋墩水平旋轉。一個車站的職工發現橋的長度最多能容納兩節車廂，如果將橋旋轉180度，那么可以把相鄰兩節車廂的位置交換，用這種方法可以重新排列車廂的順序。于是他就負責用這座橋將進站的車廂按車廂號從小到大排列。他退休后，火車站決定將這一工作

15、自動化，其中一項重要的工作是編一個程序，輸入初始的車廂順序，計算最少用多少步就能將車廂排序。【輸入格式】輸入文件有兩行數據，第一行是車廂總數N不大于10000，第二行是N個不同的數表示初始的車廂順序。 【輸出格式】一個數據，是最少的旋轉次數。 【輸入樣例】4 4 3 2 1 【輸出樣例】 6train.pas插入排序插入排序的工作機理與很多人打牌時，整理手中牌時的做法差不多。在開始摸牌時，左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的牌從右到左地進行比較。無論什么時候，左手中的牌都是排好序的。插入排序

16、數據演示：待排數據8，1，2，11，12，3依次出現先把8直接放入數組第1個位置：8第二次：1 1 8 比較1次后，移動1次，放入第三次：2 1 2 8 比較2次，移動1次，放入第四次：11 1 2 8 11 比較1次，不需移動，放入第五次：12 1 2 8 11 12 比較1次，不需移動，放入第六次：3 1 2 3 8 11 12 比較4次，移動3次，放入const maxN=10;var a:Array1.maxN of integer; x,i,j:integer;begin readln(a1); /第一個數直接放入數組最前位置 for i:=2 to maxN do begin re

17、adln(x); /讀入的數暫存在x中 j:=i-1; while (j0) and (x0) and (x0 do begin write(i, ); /輸出的是下標，一共輸出ai次 ai:=ai-1; end;end.如果要針對字符進行排序，我們需要把數組的下標更改為字符，定義方式如：A:arraya.z of longint;最后輸出局部也需要更改:For c:=ato zdo 當然，所有輸入數據的范圍不能超出數組定義的下標的范圍。count.pas相關練習第三局部 高精度我們知道在計算機里面每一種數據類型都有自己的存儲量。由于存儲量的限制所以都有著各自的精度，下面是一些常用數據類型的精

18、度：以Pascal為例 整型的精度就是在該類型范圍內所有的數。整型范圍Shortint -128 127Integer-32768 32767Longint-2147483648 2147483647Int64-9223372036854775808 9223372036854775807Byte0 255Word0 65535Cardinal 0 4294967295 但是在某些計算中，參與運算的數的范圍大大超出了標準數據類型整型，實型能表示的范圍的運算，例如求兩個100位數的和的精確值。如果用一個整型變量，無論如何也是存儲不了的，用實型那么會造成數據的不精確。 于是，我們想到了方法，將這個

19、數字拆開，拆成一位一位的或者是四位四位的存儲到一個數組中，用一個數組去表示一個數字，這樣表示的數字就被稱為高精度數。 對于高精度數，也要像平常數一樣做加減乘除以及乘方的運算，于是就有了高精度算法。數組下標12345678910111213存儲數據21098765432100 比方將這個數存到數組中，我們需要反向存儲到數組中，即原來的個位存于a1，十位存于a2依次類推，為什么要用反存？因為兩數和差積等都是要右對齊，即個位與個位對齊，而數組間最容易處理的是第一個元素對齊，所以一般情況下我們都將數字反向存入到數組中。反存var a:array1.255 of integer; i,j,la:inte

20、ger; s:string; /如果輸入的數字串長度超過255 就要用ansistringbegin readln(s); la:=length(s); /數字串s的長度 for i:=1 to la do /把對應位置的數字字符轉成數字 ai:=ord(sla-i+1)-ord(0); for i:=la downto 1 do write(ai);/反向輸出end.hprev.pas高精度加法5 5 9 8 7 5 6 + 1 2 3 4 5 6 7 8 9數組a數組b數組c151 5 141 4 151 5 151 5 151 5 101 0 921下標 9 8 7 6 5 4 3 2

21、1 逐位相加，結果可先存入數組c中，立即進位。演示計算過程中結果相加需要將c中原有的值也參加進去。用語句表示為 ci:=ci+ai+bi而進位可以用以下語句來表示。ci+1:=ci div 10;ci:=ci mod 10;另外，對應相加的次數就是數組a，b中較長的長度。var a,b,c:array1.256 of integer; /a,b至多用255，c有可能需256位 i,j,la,lb,lc:integer; s:string;begin readln(s); la:=length(s); for i:=1 to la do ai:=ord(sla-i+1)-ord(0); /反存a

22、 readln(s); lb:=length(s); for i:=1 to lb do bi:=ord(slb-i+1)-ord(0); /反存b if lalb then lc:=la else lc:=lb; /lc為相加運算的次數 for i:=1 to lc do begin ci:=ci+ai+bi; /加1位 ci+1:=ci div 10; /進位 ci:=ci mod 10; /去十 end; if clc+10 then lc:=lc+1; /判斷最高位是否發生進位 for i:=lc downto 1 do write(ci); /反向輸出 writeln;end.hip

23、lus.pas高精度減法思路與加法類似，逐位相減。要點：保證大數放在被減數的位置，如果小數在前，做標記，并交換兩數。如果當前為需要退位，那么c的高位需要變成-1，那么逐位相減的語句就是：ci:=ai-bi+ci相減的結果會產生前導0，需要去除，也有可能結果為0，那就需要保存一個0。var a,b,c:array1.1000 of integer; i,la,lb,lc,t:integer; sa,sb,st:string; flag:boolean;begin readln(sa);la:=length(sa); readln(sb);lb:=length(sb); if (lalb) or

24、(la=lb) and (sasb) then begin /直接比較數字串a，b的大小 flag:=true; /設置結果為負數的標記 st:=sa;sa:=sb;sb:=st; la:=length(sa);lb:=length(sb); end; lc:=la;/暫設結果長度為la for i:=1 to la do ai:=ord(sala-i+1)-ord(0); for i:=1 to lb do bi:=ord(sblb-i+1)-ord(0); for i:=1 to lc do begin ci:=ci+ai-bi; if ci1) do dec(lc);/去除前導0，但總長

25、要1 if flag then clc:=-clc; /write(-);輸出負號 for i:=lc downto 1 do write(ci); writeln;end.hisub.pas高精度乘法從兩個數相乘的筆算式中，個位數乘上十位數的積的最末一位是在十位，所十位數乘上十位數那么是在百位。由此推出對于ai * bj這個結果應該儲存在 ci + j - 1位上。 擺豎式ppt演示太難做了，略板書演示vara,b:array1.1000 of integer;c:array1.2000 of integer; /c的長度可以計算出來嗎？la,lb,lc,x,i,j:integer;s:an

26、sistring;beginreadln(s);la:=length(s);for i:=1 to la do ai:=ord(sla-i+1) -ord(0);readln(s);lb:=length(s);for i:=1 to lb do bi:=ord(slb-i+1) -ord(0);for i:=1 to la do /一共要乘的次數 begin x:=0; for j:=1 to lb do /逐位相乘 begin ci+j-1:=ci+j-1+ai*bj+x; /a的第i位和b的第j位相乘要放在c的i+j-1位，為什么？ x:=ci+j-1 div 10; /要進位的數暫存在x

27、中 ci+j-1:=ci+j-1 mod 10; end; ci+j:=x; end;lc:=la+lb;while (clc=0) and (lc1) do dec(lc); /去除前導0，用while不用if的原因是什么？for i:=lc downto 1 do write(ci);writeln;end.HImul.pas高精度加減乘小小結一下我們用大寫A，B，C來表示高精度數，用小寫a，b，c來表示低精度數。上面的加減乘我們用字母來表示就可以標記為：加法：C=AB減法：C=AB乘法：C=AB除此之外經常會碰到一些變式如：A=A+B 高精度數據的某個低精度范圍的連加等A=A+b 斐波那

28、契數列第N項等A=A*b 求N！等 njc.pas這些都可以看作是高精度運算的變式。局部注意點：1.A+B的結果長度：maxla，lb或maxla，lb+1；2.A*B的結果長度：la+lb或la+lb-1A，B皆不等于0；3.A*b計算中要考慮低精度數b與A中某位相乘得出結果的范圍。4.高精度運算中可以考慮利用10000進制即4位數字為一數組單元來提高運算效率，但注意輸出時要注意每位可能有前導0出現。高精度求余(高精度mod低精度)1234 mod 11=？計算方法1 mod 11=11*10+2 mod 11=11*10 +3 mod 11=22*10+4 mod 11=2vars:ans

29、istring;m,i,x:integer;beginreadln(s);/s為高精度數readln(m); /m為低精度整數for i:=1 to length(s) do x:=(x*10+ord(si)-ord(0) mod m;writeln(x)end.mod.pas第四局部 策略窮舉貪心遞推歸納窮舉法窮舉法也稱為枚舉法是把討論的對象分成假設干種情況分類，然后對各種情況逐一討論，最終解決整個問題。運用枚舉法有時要進行恰當的分類，分類的原那么是不重不漏。正確的分類有助于暴露問題的本質，降低問題的難度。摘自網絡簡單窮舉求11000中所有能被88或173整除的數。百錢買百雞的問題。求所有三

30、位數的水仙花數字。有些問題無法簡單窮舉01背包問題裝載問題有nn20個集裝箱要裝上一艘載重量為c的輪船，其中集裝箱i的重量為wi。找出一種最優裝載方案，將輪船盡可能裝滿，即在裝載體積不受限制的情況下，將盡可能重的集裝箱裝上輪船。輸入5 10 /5代表一共有5個貨物n，10代表輪船的最大載重c7 2 6 5 4輸出10 /針對這5個貨物輪船最多可能裝載1001背包解析因為貨物的數量不固定，所以我們不能簡單的用多層循環嵌套來解決了，所以必須尋找其他思路。但方法的關鍵仍然是不能遺漏任何一種可能性。因為選和不選只有兩種狀態，所以在這里我們用數字0代表不選取該貨物，用1表示選取該貨物。7 2 6 5 4

31、0 0 0 0 0 表示一個也不選0 0 0 0 1 表示選擇重量為4的一個貨0 0 0 1 0 表示選擇重量為5的一個貨0 0 0 1 1 表示選擇重量為4和5的兩個貨1 1 1 1 1 表示選取所有貨物二進制的累加器varb:array0.20 of integer; /一般最多可用到20位的01序列i,j,n,k:integer;begin readln(n); while b0=0 do /終止條件為b0=1，也就意味著溢出了。 begin for i:=1 to n do write(bi);writeln;/這里替換你的算法 i:=n; /找到最后位 while bi=1 do i

32、:=i-1;/找到第一個0的位置 bi:=1; /這個0變成1 for i:=i+1 to n do bi:=0; /從當前位的后一位起都清0 end;end.bin.pas7 2 6 5 4 數組a0 0 0 0 0 0 0 0 0 10 0 0 1 0 數組b的某一個狀態0 0 0 1 11 1 1 1 1如何求出當前取法下，一共選擇的貨物的重量呢？偽代碼如下：n=5for i1 to n do s=s+ai*bi現在的關鍵如何依次變化產生b數組中的值，其實b數組變化過程就是一個二進制的累加器，從00000開始一直到11111，不會遺漏任何一種可能性。01背包問題關鍵在于一個物品的取或不取

33、，只有兩種狀態，某些情況下，某些問題可能有三種或者更多狀態，因此，有時我們要把二進制累加器擴展到k進制累加器。varb:array0.20 of integer;i,j,n,k:integer;begin readln(n,k);/n位，k進制 while b0=0 do/b0為標志位 begin for i:=1 to n do write(bi);writeln; /累加器樣例輸出，使用時在此處替換算法 i:=n; /定位 while bi=k-1 do i:=i-1;/逆向尋找最后一個不是K-1的數 bi:=bi+1; /在當前位加1，本質就是進位 for i:=i+1 to n do

34、bi:=0;/從i+1往后都清0 end;end.k.pas二進制累加器終究是一種窮舉法，效率并不高，在二進制累加器下一般物品個數即累加器長度不應超過20，否那么根本都要超時。應用：01背包問題 運用二進制累加器22屆市賽?等式問題? 考慮到可填加號，減號或不填，一共三種狀態，所以應該使用三進制的窮舉累加器。貪心策略 貪心算法又稱貪婪算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。 貪心算法不是對所有問題都能得到整體最優解，但對范圍相當廣泛的許多問題他能產生整體最優解或者是整體最優解的近似解。摘自網絡先來看個例

35、子數塔問題有形如下圖的數塔，從頂部出發，在每一結點可以選擇向左走或是向右走，要求走到底層,找出一條路徑，使路徑上的值最大。 按照貪心原那么，每次都去找下方的數種較大的一個，那么得到結果為51，很明顯我們就發現51不是最大值，59才是最大值。所以此問題解決不能用貪心策略。 同樣，在解決一般問題中，如果你已經有了算法，嘗試推舉反例，看看是否能夠否認你的想法。so，在打草稿構思算法的時候，就應該開始尋找反例，等你寫完代碼才發現，那就杯具了典型貪心問題解析攔截導彈 某國為了防御敵國的導彈襲擊，開展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以后每一發炮

36、彈都不能高于前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。 輸入導彈依次飛來的高度雷達給出的高度數據是不大于30000的正整數，計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。輸入樣例：389 207 155 300 299 170 158 65輸出樣例：2daodan.pas389 207 155 300 299 170 158 65現在我們來構思一下算法：我們來嘗試找一個反例。68389 207 155 300 299 170 158 65這才是正確的方法，試驗下剛剛舉的反例吧，通過了嗎？此題的局部最優解是：用一套攔截系統攔截掉所有可以攔截的導彈。排隊接水有n個人在一個水龍頭前排隊接水，假設每個人接水的時間為