基本算法网络版

《基本算法网络版》由会员分享，可在线阅读，更多相关《基本算法网络版（15页珍藏版）》请在装配图网上搜索。

1、生成序列01序列Procedure poducer1(n:integer); Var I,j:integer; B:array0.100 of integer; BeginB0:=0;While b0=0 do Begin I:=n; While bi=1 do dec(i); Bi:=1; For j:=I+1 to n do Bj:=0; End; End;全排列Procedure producer2(n:integer); Var x,I,j,p,min:integer; B:array0.100 of integer; BeginFor i:=1 to n do Bi:=I;B0:=0

2、;While b0=0 do Begin I:=n; While bibj) and (bjbi-1) then Begin P:=j;min:=bj; End; X:=bp;bp:=bi-1;bi-1:=x; For j:=I to (n+i) div 2 do Begin X:=bj;bj:=bn+i-j;bn+i-j:=x; End; End; End;组合Procedure producer3(n,m:integer); Var I,j:integer; B:array0.100 of integer; BeginFor i:=1 to m do Bi:=I;B0:=0;While b

3、0=0 do Begin I:=m; While bi=n+i-m do dec(i); If i=0 then break; Inc(bi); For j:=I+1 to m do Bj:=bj-1+1; End; End;数论素数的判断朴素算法Function isprime(n:longint):boolean; Var i:longint; BeginIsprime:=true;For i:=2 to trunc(sqrt(n) do If n mod i=0 then Begin Isprime:=false; Exit; End;If i=1 then isprime:=false

4、; End;Miller_RabbinFunction miller_rabbin(p:longint):boolean; Var I,x:longint; Begin Miller_rabbin:=true; Randomize;For i:=1 to 30 do Begin X:=trunc(random*100+1); If modular(x,p-1,p)1 then/*a(p-1) mod p Begin Miller_Rabbin:=false; Exit; End; End;If p=1 then miller_rabbin:=false; End;分治求ab mod cFunc

5、tion modular(a,b,c:longint):longint; Var I,j,len:longint; Bin:array1.50 of integer; BeginIf b=1 then Begin If b=1 then modular:=a mod c; If b=0 then modular:=1; Exit; End;Len:=0;J:=b;While j0 do Begin Inc(i); Bini:=j and 1; Bini:=j shr 1; End;J:=a;For i:=len-1 downto 1 do Begin J:=j mod c*j mod c; I

6、f bini=1 then j:=a mod c*j mod c; End;Modular:=j; End;欧几里德辗转相除法Function gcd(va,vb:longint):longint; Var r:longint; BeginWhile va mod vb0 do Begin R:=va mod vb; Va:=vb;vb:=r; End;Gcd:=vb; End;进制转换Function change(a:string;dx,dy:longint):string; Var temp:string; Len,I,j,x,t:longint; BeginT:=0;temp:=;Le

7、n:=length(a);j:=1;For i:=len downto 1 do Begin If (ai=A) and (ai=F) then x:=ord(ai)-55 else x:=ord(ai)-48; T:=t+x*j; T:=t*dx; End;While t0 do Begin X:=t mod dy; If (x=10) and (xlb then lc:=la else lc:=lb;For i:=1 to lc do Begin Ci:=ai+bi; Ci+1:=ci+1+ci div 1000; Ci:=ci mod 1000; End; End;Procedure m

8、inus_part; BeginIf lalb then lc:=la else lc:=lb;For i:=1 to lc do Begin Ci:=ai-bi; If ci0 thenBeginCi+1:=ci+1-1;Ci:=ci+1000; End; End; End;Procedure mult_part; BeginFor i:=1 to la do For j:=1 to lb do Begin Cla+lb-1:=cla+lb-1+ai*bj; Cla+lb:=cla+lb+cla+lb-1 div 1000; Cla+lb-1:=cla+lb-1 mod 1000; End;

9、 End;二分法Binary SearchProcedure binary_search; begin left:=1;right:=n+1;c:=0; while left=right do begin mid:=(left+right) div 2; if fmid=1 then begin right:=mid-1; c:=mid; end else begin left:=mid+1; c:=mid+1 ; end; end; end;排序直接选择排序insertion sortProcedure insertion_sort; BeginFor i:=1 to n do Begin

10、J:=1; While (jaj) do inc(j); X:=ai; For k:=j to I-1 do Ak+1:=ak; Aj:=x; End; End;快速排序QuicksortProcedure qsort(be,en:longint); Var I,j,x,mid,temp:longint; BeginI:=be;j:=en;mid:=(i+j) div 2;X:=amid;Repeat While xai do inc(i); While xaj do dec(j); If ij;If ien then qsort(I,en);If bej then qsort(be,j);

11、End;Procedure quicksort BeginFor i:=1 to n do Read(ai);Qsort(1,n); End;堆排序HeapsortProcedure heapsort; Begin Heapn:=0;For i:=1 to n do Begin read(x);Insert(x);/*Heap End;For i:=1 to n do Delete(1);/*Heap End;矩阵matrixProcedure matrix; BeginFor i:=1 to n do For j:=1 to m do For k:=1 to t do CI,j:=cI,j+

12、aI,k*bk,j; End;并查集Find_Union SetFunction find(x:longint):longint; Var vi,vj,sum:longint; Temp:array1.10000 of longint; BeginSum:=0;Inc(sum);Tempsum:=x;Vi:=x;While xssetx do Begin Inc(sum); Tempsum:=ssetx; X:=ssetx; End;For vj:=1 to sum do Ssettempvj:=x;Find:=x; End;Procedure find_union set; BeginIf

13、find(x)=find(y) then writeln(YES)ElseBegin X:=find(x);y:=find(y); Ssetx:=ssety; Writeln(NO); End; End;树结构排序二叉树BSTProcedure insert(x:longint); Var p,q,s:point; BeginNew(p);p:=root;new(q);q:=nil;New(s);s.data:=x;s.left:=nil;s.right:=nil;Flag:=true;While flag and (pnil) do Begin Q:=p; If p.datas.data t

14、hen p:=p.left Else If p.dataq.data then q.right:=s else q.left:=s;Dispose(p);dispose(q); End;Procedure bst; BeginNew(root);Root.left:=nil;root.right:=nil;Read(x);Root.data:=x;For i:=2 to n-1 do Begin Read(x); Insert(x); End; End;二叉堆HeapProcedure insert(x:longint); Var I,j:longint; BeginInc(heapn);He

15、apheapn:=x;I:=heapn;j:=I div 2;While (j0) and (heapiheapj) do Begin Temp:=heapi;heapi:=heapj;heapj:=temp; I:=j;j:=j div 2; End; End;Procedure delete(k:longint); Var I,j:longint; BeginHeapk:=heapheapn;Dec(heapn);I:=k;j:=k*2;If (j+1=heapn) and (heapjheapj+1) then inc(j);While (j=heapn) and (heapiheapj

16、) do Begin Temp:=heapi;heapi:=heapj;heapj:=temp; I:=j;j:=j*2; If (j+1=heapn) and (heapjheapj+1) then inc(j); End; End;Procedure heap; BeginHeapn:=0;for i:=1 to n do beginreadln(x);insert(x); end;for i:=n downto 1 do delete(i);end;图论最短路径FloyedProcedure floyed; Begin For k:=1 to n do For i:=1 to n do

17、For j:=1 to n do If (ij) and (ik) and (kj) and (gi,k+gk,jgI,j) then GI,j:=gI,k+gk,j; End;最短路径DijkstraProcedure dijkstra; BeginFor k:=1 to n-1 do Begin I:=0;min:=maxlongint; For j:=1 to n do If (hashj=0) and (disjmin) then Begin Min:=disj; I:=j; End; If i=0 then exit; Hashi:=1; For j:=1 to n do If (h

18、ashj=0) and (disi+gI,jdisj) then Disj:=disi+gI,j; End; End;最短路径Bellman_FordProcedure bellmanford; BeginRepeat Flag:=true; For i:=1 to m do Begin X:=linei.x;y:=linei.y;w:=linei.w; If disx+wdisy then Begin Disy:=disx+w; Flag:=false; End; End;Until flag; End;最短路径SPFAProcedure spfa; BeginFront:=0;rear:=

19、1;Q1:=s;hashs:=1;While frontrear do Begin X:=q(front+1) mod maxn; If startvx0 then For i:=startvx to endvx do Begin Y:=linei.y;w:=linei.w; If disxdisy+w then Begin Disx:=disy+w; If hashy=0 then Begin Hashy:=1; Rear:=(rear+1) mod maxn; Qrear:=y; End; End; End; Front:=(front+1) mod maxn; Hashx:=0; End

20、; End; MST问题PrimProcedure prim; Beginfor i:=1 to n-1 do begin linei.x:=1;linei.y:=i+1;linei.w:=g1,i+1; end;for k:=1 to n-1 do begin min:=maxlongint;i:=0; for j:=k to n do if linej.wmin then begin min:=linej.w;i:=j; end; if i=0 then exit; temp:=linei;linei:=linek;linek:=temp; x:=linek.y; for j:=k+1 t

21、o n-1 do begin y:=linej.y;w:=gx,y; if wlinei.w then begin linei.w:=w; linei.x:=x; end; end; end; End;MST问题KruscalProcedure kruscal; BeginQsort(1,m);/*QuicksortSum:=0;count:=0;For j:=1 to m do Begin X:=find(linei.x);y:=find(linei.y); If xy then Begin Ssetx:=ssety;/*Find_Union Set Inc(count,linei.w);

22、Inc(sum); If sum=n-1 then break; End; End; End;Euler图Procedure find(x:longint); Var I:longint; BeginIf outdegreex=0 then Begin Inc(sum); Cntsum:=x; EndElse Begin For i:=1 to n do If gx,i0 then Begin Gx,i:=0; Dec(outdegreex); Find(i); End; Inc(sum); Cntsum:=x; End; End;Procedure euler; Begin Sum:=0;F

23、or i:=1 to n do If odd(outdegreei) then begin find(i);exit;end;Find(1); End;AOV网(topo_sort)Procedure topo_sort; BeginFront:=1;rear:=0; for i:=1 to n do If indegreei=0 then Begin Inc(rear); Qrear:=I; End;While front=rear do Begin X:=qfront; For i:=1 to n do If gx,i0 then Begin Dec(indegreei); If inde

24、greei=0 then Begin Inc(rear); Qrear:=I; End; End Inc(front); End; End;AOE网Procedure AOE;Beginline1:=line;front:=1;rear:=0;for i:=1 to n do if indegreei=0 then begin inc(rear); qrear:=i; earlyi:=0; end; while front=rear do begin x:=qfront; if startvx0 then for i:=startvx to endvx do begin y:=linei.y;

25、 w:=linei.w; dec(indegy); if indegy=0 then begin inc(rear); qrear:=y; end; if earlyyearlyx+w then earlyy:=earlyx+w; end; inc(front); end; line:=line1;for i:=1 to n do lasti:=maxint; lastqrear:=earlyqrear; for i:=rear-1 downto 1 do begin x:=qi; if startvx0 then for j:=startvx to endvx do if lastxlast

26、linej.y-linej.w then lastx:=lastlinej.y-linej.w; end;end;网络流Ford_FulksonFunction findpath:boolean; var i,x:longint; begin can:=0; hashs:=maxint; q1:=s;front:=1;rear:=1; while front0) and (min(hashx,cx,i-fx,i)hashi) then begin inc(rear); qrear:=i; prei:=x; hashi:=min(hashx,cx,i-fx,i); end; inc(front); end; can:=hasht; if can0 then findpath:=true else findpath:=false; end;Procedure relax; begin i:=t; while is do begin j:=prei; inc(fj,i,can); dec(fi,j,can); i:=j; end; end;Procedure Ford_Fulkson begin while findpath do relax; end;