版權說明:本文檔由用戶提供并上傳,收益歸屬內(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. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 防溺水安全活動總結
- 社會實踐部的述職報告
- 櫥柜銷售經(jīng)理工作總結
- 家鄉(xiāng)環(huán)境建議書
- 微教育閱讀心得7篇
- 蔬菜年終總結6篇
- 市政道路監(jiān)理會議紀要范文(3篇)
- 銷售主管工作匯報模板4篇
- 種草莓教案5篇
- 2024年危險化學品經(jīng)營單位主要負責人理論試題及答案
- 高考英語復習讀后續(xù)寫人與自然(4)講義
- 2023版道德與法治教案教學設計專題5第1講 全體人民共同的價值追求
- 南京市鼓樓區(qū)2023-2024學年八年級上學期期末英語試卷(含答案解析)
- 數(shù)字經(jīng)濟概論 習題參考答案 李三希
- “教學評一致性”意義與含義
- 人工智能人才培養(yǎng)的智能醫(yī)學與健康大數(shù)據(jù)分析技術
- 涉密內(nèi)網(wǎng)分級保護設計方案
- 《學術不端行為》課件
- 當代世界文化發(fā)展的趨勢
- 花茶大學生創(chuàng)新創(chuàng)業(yè)計劃書
- 燃燒器調(diào)試報告
評論
0/150
提交評論