pascal-基本算法模塊_第1頁
pascal-基本算法模塊_第2頁
pascal-基本算法模塊_第3頁
pascal-基本算法模塊_第4頁
pascal-基本算法模塊_第5頁
已閱讀5頁,還剩16頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

1、基本算法模塊For NOIP2007Billy.Linux對于NOIP,基礎是相當重要的,在3個小時之內(nèi)做完4道題,那么就要求我們有相當快的速度。特別是對于一些簡單的、常用的算法模塊,一定要要熟練掌握并靈活運用。由于NOIP是一個比較基礎的比賽,因此基本算法的掌握尤為重要,所以要求能夠把這些基本的模塊快速、準確的移植到不同的程序中,才能在穩(wěn)中取勝。基本算法模塊中最重要的是基本程序框架,也就是說,要養(yǎng)成適合于自己的程序風格,這樣對于程序編寫的速度與程序的準確度都有較大的提高。模塊目錄一、 排序1 選擇排序2 插入排序3 冒泡排序4 快速排序5 堆排序6 歸并排序7 線性時間排序二、 高精度1 高

2、精度比較2 高精度加法3 高精度減法4 單精度乘法5 高精度乘法6 單精度除法7 高精度除法8 進制轉換三、 數(shù)論1 歐幾里德算法2 擴展歐幾里德3 求最小公倍數(shù)4 求解線形同余方程5 素數(shù)的判斷6 素數(shù)的生成四、 排列組合1 排列生成算法2 組合生成算法3 排列按序生成法4 排列字典序生成法五、 圖論1 圖的讀入2 深度優(yōu)先搜索3 廣度優(yōu)先搜索4 強連同分量5 拓撲排序6 最小生成樹7 最短路徑六、 背包問題1 裝滿背包2 一維價值最大背包3 二位價值最大背包一、 排序算法var a:array1.maxnof longint;排序對象1 選擇排序Select_sortprocedure s

3、elect_sort;beginfor i:=1 to n-1 do for j:=i+1 to n doif ai>aj then begin temp:=ai;ai:=aj;aj:=temp;end;end;2 插入排序Insert_sortprocedure insert_sort; beginfor i:=2 to n do beginkey:=ai;j:=i-1;while (key<aj)and(j>0) do begin aj+1:=aj;dec(j);end;aj+1:=key; end;end;3 冒泡排序Bubble_sortprocedure bubbl

4、e_sort; beginfor i:=1 to n-1 do for j:=n downto i+1 do if aj<aj-1 then begin temp:=aj;aj:=aj-1;aj-1:=temp;end; end;4 快速排序Quick_sortprocedure qsort(s,t:longint); var i,j,x:longint; begini:=s;j:=t;x:=a(i+j)div 2;repeat while ai<x do inc(i); 找左邊比他大的 while aj>x do dec(j);找右邊比他小的 if i<=j then

5、交換 begin temp:=ai;ai:=aj;aj:=temp; inc(i);dec(j); end;until i>j;if s<j then qsort(s,j);if i<t then qsort(i,t); end;5 堆排序Heap_sortprocedure heap(i,n:longint);將第i個元素向下篩 var j,x:longint; beginj:=i*2;x:=ai;while j<=n do beginif (j<n)and(aj<aj+1) then inc(j);if x<ajthen begin ai:=aj;

6、i:=j;j:=i*2; endelse j:=n+1;end;ai:=x;end;procedure heap_sort; beginfor i:=n div 2 downto 1 do heap(i,n);for i:=n downto 2 do begin temp:=ai;ai:=a1;a1:=temp; heap(1,i-1); end; end;6 歸并排序Merge_sortprocedure mergesort(s,t:longint); varm,i,j,k:longint;beginif t-s=0 then exit;m:=(s+t)div 2; mergesort(s,

7、m); mergesort(m+1,t); for i:=1 to m-s+1 do bi:=as+i-1; for j:=m+1 to t do cj-m:=aj; i:=1;j:=1;bm-s+2:=max;ct-m+1:=max; for k:=s to t do if bi<cj then begin ak:=bi;inc(i);end else begin ak:=cj;inc(j);end; end;7 線性時間排序基數(shù)排序、計數(shù)排序、桶排序二、 高精度算法High_precisionconst maxcount=進制位 maxlen=記錄高精度數(shù)組大小type bignum

8、=array0.maxlenof longint;0為位數(shù)1 高精度比較function compare(a,b:bignum):longint; begin while aa0=0 do dec(a0);檢查位數(shù)是否正確 while bb0=0 do dec(b0); while aa0+1>0 do inc(a0); while bb0+1>0 do inc(b0); if a0>b0 then exit(1); if a0<b0 then exit(-1); for i:=a0 downto 1 do begin if ai>bi then exit(1);

9、 if ai<bi then exit(-1); end; exit(0); end;2 高精度加法procedure add(a,b:bignum;var c:bignum); var i:longint; beginfillchar(c,sizeof(c),0);c0:=1;if a0>b0 then c0:=a0else c0:=b0; for i:=1 to a0 do inc(ci,ai); for i:=1 to b0 do inc(ci,bi); for i:=1 to c0 do begin inc(ci+1,ci div maxcount); ci:=ci mod

10、 10; end; while cc0+1>0 do begin inc(c0); inc(cc0+1,cc0 div maxcount); cc0:=cc0 mod maxcount; end;end;3 高精度減法procedure minus(a,b:bignum;var c:bignum); var i:longint; beginfillchar(c,sizeof(c),0);c0:=a0;for i:=1 to c0 do ci:=ai-bi;for i:=1 to c0 do if ci<0 then begin dec(ci+1); inc(ci,maxcount)

11、; end;while (c0>1)and(cc0=0) do dec(c0);end;4 單精度乘法procedure mulnum(a:bignum;x:longint,var c:bignum); vari:longint; begin fillchar(c,sizeof(c),0);c0:=a0; for i:=1 to c0 do ci:=ai*x; for i:=1 to c0 do begin inc(ci+1,ci div maxcount); ci:=ci mod 10; end; while cc0+1>0 do begin inc(c0); inc(cc0+1

12、,cc0 div maxcount); cc0:=cc0 mod maxcount;end;end;5 高精度乘法procedure mul(a,b:bignum;var c:bignum); vari,j:longint; begin fillchar(c,sizeof(c),0);c0:=a0+b0-1; for i:=1 to a0 do for j:=1 to b0 do inc(ci+j-1,ai*bj); for i:=1 to c0 do begin inc(ci+1,ci div maxcount); ci:=ci mod 10; end; while cc0+1>0 d

13、o begin inc(c0); inc(cc0+1,cc0 div maxcount); cc0:=cc0 mod maxcount; end;end;6 單精度除法function divnum(a:bignum;x:longint;var c:bignum):longint; var i,temp:longint; begin fillchar(c,sizeof(c),0);c0:=a0;temp:=0;for i:=a0 downto 1 do begin temp:=temp*maxcount+ai; ci:=temp div x; temp:=temp mod x; end;whi

14、le (co>1)and(cc0=0) do dec(c0);exit(temp);end;7 高精度除法procedure div(a,b:bignum;var c,d:bignum); var i:longint; beginfillchar(c,sizeof(c),0);c0:=a0-b0+1;fillchar(d,sizeof(d),0);d0:=1;for i:=c0 downto 1 do begin ci:=maxcount; repeat dec(ci);mul(c,b,temp); until compare(a,temp)>=0; end;while (co&g

15、t;1)and(cc0=0) do dec(c0);minus(a,temp,d);end;8 進制轉換10進制數(shù)用bignum記,maxcount=10k進制數(shù)用string記const repchar:array0.35of string=(0,1,2,a,b,z);數(shù)碼對應的字符 repnum:array48.122of longint=(0,1,2,34,35);字符的ASCCI碼對應的數(shù)碼k進制轉十進制:procedure change_to_ten(s:string;k:longint):bignum; var i,l:longint; temp:bignum; begin l:=

16、length(s); temp0:=1;temp1:=repnumord(sl); for i:=1 to l-1 do begin inc(temp1,repnumord(sl-i); mulnum(temp,k); end; exit(temp);end;十進制轉k進制:procedure change_to_k(num:bignum;k:longint):string; var i,temp:longint; s:string; begin if (num0=1)and(num1=0) then exit(0); while not(num0=1)and(num1=0) do begin

17、 temp:=divnum(num,k,num); s:=repchartemp+s; end; exit(s); end;三、 數(shù)論算法1 求最大公約數(shù)gcd(歐幾里德算法)遞歸(recursion): function gcd(a,b:longint):longint; begin if b=0 then exit(a); exit(gcd(b,a mod b); end;非遞歸(iterative): function gcd(a,b:longint):longint; var t:longint; begin while b<>0 do begin t:=a;a:=b;b:

18、=t mod b; end; exit(a); end;2 擴展歐幾里德算法 function extended_euclid(a,b:longint;var x,y:longint):longint; var p,q:longint; begin if b=0 then begin x:=1;y:=0; exit(a); end; p:=extended_euclid(b, a mod b,x,y); q:=x;x:=y;y:=q-a div b *y; exit(p); end;3 求最小公倍數(shù)k:=a*b div gcd(a,b);4 求解線性同余方程typeansnode=record

19、 ansnum:longint;解的個數(shù) num:array1.maxnnumof longint;解 end;procedure modular_linear_equation(a,b,n:longint;var ans:ansnode); var d,i,x,y,temp:longint; begin d:=extended_euclid(a,n,x,y); if b mod d <>0 then ans.ansnum:=0 else begin ans.ansnum:=d;temp:=(x*(b div d)mod n; for i:=1 to d do ans.numi:=

20、(temp+i*(n div d)mod n; end; end;5 素數(shù)的判斷function prime_bool(x:longint):boolean; var i:longint; begin for i:=2 to trunc(sqrt(x) do if x mod i=0 then exit(false); exit(true); end;6 素數(shù)的生成maxnum=生成質數(shù)的范圍maxprime=對應范圍中的質數(shù)個數(shù)var prime:array0.maxprimeof longint;存儲質數(shù) bool:array1.maxnnumof boolean;存儲每個數(shù)是不是質數(shù)pr

21、ocedure prime_make; var i,j:longint; begin fillchar(bool,sizeof(bool),0); i:=2; while i<=maxnnum do begin if not pi then begin j:=2*i; while i<=maxnnum do begin pj:=true; inc(j,i); end; inc(prime0);primeprime0:=i; end; inc(i); end;end;四、 排列組合算法1 排列生成算法m的n排列var a:array0.maxnof longint;排列方案 b:ar

22、ray0.maxmof boolean;每個數(shù)是否被用過遞歸(recursion):procedure make_permutation_recursion(t:longint) var i:longint; begin if t=n+1 then begin write(a1);for i:=2 to n do write( ,ai);writeln; exit; end; for i:=1 to m do if not bi then begin bi:=true;at:=i; make(t+1); bi:=false; end;end;非遞歸(iterative):procedure m

23、ake_permutation_iterative(m,n:longint); var i,j:longint; begin i:=1;a1:=0; repeat j:=ai+1; while (j<=m)and(bj) do inc(j); if j<=m then begin ai:=j;bj:=true; if i=n then begin write(a1);for j:=2 to n do write( ,aj);writeln; ban:=false; end else begin inc(i);ai:=0; end; end else begin dec(i);bai

24、:=false; end; until i=0;end;2 組合生成算法m的n組合procedure make_combination(t:longint) var i:longint; begin if t=n+1 then begin write(a1);for i:=2 to n do write( ,ai);writeln; exit; end; for i:=at-1 to m do if not bi then begin bi:=true;at:=i; make(t+1); bi:=false; end; end;3 排列按序生成法const power:array1.maxno

25、f longint=();poweri為i的階乘type permutationnode=array1.maxnof longint;排列方案求n的全排的字典序:function get_number(n:longint;a:permutationnode):longint; var b:array1.maxnof longint; i,j,s:longint; begin for i:=1 to n do bi:=i-1; s:=0; for i:=1 to n-1 do begin inc(s,bai*powern-i); for j:=ai+1 to n do dec(bj); end;

26、 exit(s+1); end;求字典序為m的n的全排:function get_permutation(m,n:longint;):permutationnode; var use:array1.maxnof boolean; a:array0.maxnof longint; temp:permutationnode; begin dec(m); for i:=1 to n-1 do begin ai:=m mod (i+1); m:=m div (i+1); end;a0:=0; for i:=1 to n do begin j:=0; for k:=1 to an-i+1 do begi

27、n inc(j); while usej do inc(j); end; tempi:=j;usej:=true; end; exit(temp); end;4 排列字典序生成法求n的某個全排的下m個字典序排列procedure make_next(n,m:longint;a:permutationnode):permutationnode; var i,j,k,t,temp:longint; begin for t:=1 to m do begin i:=n; while (i>1)and(ai<ai-1) do dec(i); j:=n; while aj<ai-1 do

28、 dec(j); temp:=ai-1;ai-1:=aj;aj:=temp; for k:=i to (i+n)div 2 do begin temp:=ak;ak:=an+i-k;an+i-k:=temp; end; end; exit(a); end;五、 圖論算法1 圖的讀入以點為基礎讀入(沒有特殊說明,一般以此方法讀入):var vetex:array1.maxn,0.maxnof longint;鄰接表,記錄與那些點相連 map:array1.maxn,1.maxnof longint;鄰接矩陣,記錄點點之間的距離procedure initgraph; var i,u,v,c:lo

29、ngint; begin readln(n,e); for i:=1 to e do begin readln(u,v,c); inc(vetexu,0);vetexu,vetexu,0:=v; mapu,v:=c; end; end;以邊為基礎讀入:type node=record u,v,w:longint;u為起點,v為終點,w為權 end;var vetex:array1.maxeof node;記錄邊procedure initgraph; var i:longint; begin readln(n,e); for i:=1 to e do with vetexi do readln

30、(u,v,w); end;2 深度優(yōu)先搜索DFSvar time:longint;時間 flag:array1.maxnof boolean;是否標記procedure DFS(t:longint); var i:longint; begin inc(time);gettimet:=time;flagt:=true; for i:=1 to vetext,0 do if not flagvetext,i then begin fromvetext,i:=t;depvetext,i:=dept+1; DFS(vetext,i); end; inc(time);finishtimet:=time;

31、 end;3 廣度優(yōu)先搜索BFSprocedure BFS(t:longint); var time,open,closed,i,v:longint; flag:array1.maxnof boolean; x0:array1.maxnof longint; begin fillchar(flag,sizeof(flag),0); open:=0;closed:=1;x01:=t;dept:=0; time:=1;flagt:=true;flagtimet:=1; repeat inc(open);v:=x0open; inc(time);finishtimev:=time; for i:=1

32、 to vetexv,0 do if not flagvetexv,i then begin inc(closed);x0closed:=vetexv,i; flagvetexv,i:=true;depvetexv,i:=depv+1; inc(time);gettimevetexv,i:=time; end; until open>=closed; end;4 強連通分量var connected:array1.maxn,0.maxnof longint;connecti,0為此分量包含的節(jié)點數(shù) total:longint;強連同分量的個數(shù)procedure strongly_conn

33、ected; var i,time:longint; flag:array1.maxnof boolean; sign:array1.maxnof longint; procedure sort1(t:longint); var i:longint; begin flagt:=true; for i:=1 to n do if (mapt,i<>0)and(not flagi) then sort1(i); inc(time);signtime:=t; end; procedure sort2(t:longint); var i:longint; begin flagt:=true

34、; for i:=1 to n do if (not flagi)and(mapi,t<>0) then sort2(i); inc(connectedtotal,0);connectedtotal,connetedtotal,0:=t; end; begin fillchar(flag,sizeof(flag),0); for i:=1 to n do if not flagi then sort1(i); for i:=n downto 1 do if not flagsigni then begin inc(total); sort(signi); end; end;5 拓撲

35、排序procedure topological_sort; var i,open,closed:longint; flag:array1.maxnof boolean; begin open:=0;closed:=0; for i:=1 to n do if invi=0 then begin inc(closed); flagi:=true;AOVclosed:=i; end; if closed=0 then exiterror; repeat inc(open);v:=AOVopen; for i:=1 to vetexv,0 do if not flagvetexv,i then be

36、gin dec(invvetexv,i); if invvetexv,i=0 then begin inc(closed); AOVclosed:=vetexv,i;flagvetexv,i:=true; end; end; until open=closed; if closed<n then exiterror; end;6 最小生成樹Prime:procedure prime_normal; var i,j,min,mj:longint; flag:array1.maxnof boolean; lowcost:array1.maxnof longint; begin fillcha

37、r(lowcost,sizeof(lowcost),$5F); lowcost1:=0;flag1:=true; for i:=1 to v1,0 do lowcostv1,i:=map1,v1,i; for i:=2 to n do begin min:=maxlongint; for j:=1 to n do if (not flagj)and(lowcostj<min) then begin min:=lowcostj;mj:=j; end; flagmj:=true;inc(totallen,min); for j:=1 to vmj,0 do if (not flagvmj,j

38、) and(lowcostvmj,j>mapmj,vmj,j) then lowcostvmj,j:=mapmj,vmj,j; end; end;Kruskal以邊為基礎讀入:procedure kruskal; var set1,set2,vetex_pointer,last_set_num:longint; function find(x:longint):longint; begin if fatherx=x then find:=fatherx else begin fatherx:=find(fatherx);find:=fatherx;end; end; begin qsor

39、t(1,e);對vetex以w為關鍵字從小到大排序 for i:=1 to n do fatheri:=i; vetex_pointer:=1;last_set_num:=n; while (last_set_num>1)and(vetex_pointer<=e) do begin set1:=find(vetexvetex_pointer.u); set2:=find(vetexvetex_pointer.v); if set1<>set2 then begin inc(totallen,vetexvetex_pointer.w); dec(last_set_num)

40、; fatherset1:=set2; end; inc(vetex_pointer); end; writeln(totallen); end;7 最短路徑Dijktra:procedure Dijkstra(s:longint); var i,j,min,mi:longint; begin fillchar(shortest,sizeof(shortest),$5F); shortests:=0; for i:=1 to n do begin min:=max; for j:=1 to n do if (not flagj)and(shortestj<min) then begin

41、min:=shortestj;mi:=j;end; flagmi:=true; for j:=1 to vetexmi,0 do if (not flagvetexmi,j) and(shortestvetexmi,j>min+mapmi,vetexmi,j) then shortestvetexmi,j:=min+mapmi,vetexmi,j; end; end;Floyd:procedure Floyd; var i,j,k:longint; begin fillchar(len,sizeof(len),$5F); for i:=1 to n do begin leni,i:=0;

42、 for j:=1 to vetexi,0 do leni,vetexi,j:=mapi,vetexi,j; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do if leni,k+lenk,j<leni,j then leni,j:=leni,k+lenk,j; end;Bellman-ford以邊為基礎讀入:procedure Bellman-ford(s:longint); var i,j:longint; bool:boolean; begin fillchar(shortest,sizeof(shortest),$5F

43、);shortests:=0; bool:=true; for i:=1 to n-1 do if bool then begin bool:=false; for j:=1 to e do if shortestvetexj.v>shortestvetexj.u+vetexj.w then begin shortestvetexj.v:=shortestvetexj.u+vetexj.w; bool:=true; end; end; for j:=1 to e do if shortestvetexj.v>shortestvetexj.u+vetexj.w then exit(flase); exit(true); end;SPFA:procedure SPFA(s:longint); var u,i:longint; x0:array1.maxno

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論