c算法大全常用c语言算法,包括数论算法,图论算法、排序算法、高精度计算、树的遍历算法等等

1、一、数论算法1 .求两数的最大公约数fun cti ongcd(a,b:i nteger):i nteger;begi nif b=0 then gcd:=aelse gcd:=gcd (b,a mod b);end ;2 求两数的最小公倍数fun cti onlcm(a,b:i nteger):i nteger;begi nif a0 do inc(lcm,a);end;3.素数的求法A.小范围内判断一个数是否为质数：function prime (n: integer): Boolean;var I: integer;begi nfor I:=2 to trunc(sqrt(n)doif

2、n mod 1=0 then beginprime:二false;exit;end;prime:二true;end;B.判断Iongint范围内的数是否为素数（包含求50000以内的素数表）：procedure getprime;vari, j:l ongint;p:array1.50000 of boolean;begi nfillchar(p,sizeof(p),true);p1:=false;i:=2;while i50000 do beginif pi the n beg inj:=i*2;while j=x then breakelse if x mod pri=0 then exi

3、t;prime:二true;en d;prime、图论算法最小生成树A. Prim 算法:procedure prim(v0:i nteger);varlowcost,closest:array1.maxn of integer;i,j,k,m in:i nteger;begi nfor i:=1 to n do beginlowcosti:二costvO,i;closesti:二vO;end;for i:=1 to n-1 do beg in寻找离生成树最近的未加入顶点 kmi n:二maxi on gi nt;for j:=1 to n dobeg inif (lowcostj0)then

4、min :=lowcostj;k:=j;end;lowcostk:=0; 将顶点k加入生成树生成树中增加一条新的边k到closestk修正各点的lowcost和closest值for j:=1 to n doif costk,jvlwocostj then beginlowcostj:=costk,j;closestj:=k;end;end;en d;primB. Kruskal算法：（贪心）按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。function find(v:integer):integer;返回顶点 v 所在的集合var i:integer;begi ni:=1;

5、while (i0 do beg ini:=fi nd(eq.v1);j:=fi nd(eq.v2);if ij then beginin c(tot,eqe n);vseti:=vseti+vsetj;vsetj:=;dec(p);end;in c(q);end;writel n(tot);end;2. 最短路径A.标号法求解单源点最短路径:vara:array1.maxn,1.maxnof integer;b:array1.maxn of integer; bi指顶点i到源点的最短路径mark:array1.maxnof boolean;procedure bhf;varbest,best

6、_j:i nteger;beg infillchar(mark,sizeof(mark),false);mark1:=true; b1:=0;1 为源点repeatbest:=0;for i:=1 to n doIf marki then 对每一个已计算出最短路径的点for j:=1 to n doif (not markj) and (ai,j0) thenif (best=0) or (bi+ai,j0 the n beg inbbest_j:二best ； markbest_j:=true;end;until best=0;en d;bhfB. FIoyed算法求解所有顶点对之间的最短路

7、径：procedure floyed;begi nfor I:=1 to n dofor j:=1 to n doj的前驱结点if al,j0 then pl,j:=l else pl,j:=O;pl,j表示 I 到 j 的最短路径上for k:=1 to n do 枚举中间结点for i:=1 to n dofor j:=1 to n doif ai,k+aj,kvai,j then beginai,j：=ai,k+ak,j;Pl,j：=Pk,j；end;end;C. Dijkstra 算法：varb, pre:array1.maxn of integer; prei指最短路径上 I 的前驱

8、结点 mark:array1.maxn of boolean;procedure dijkstra(vO:integer);begi nfillchar(mark,sizeof(mark),false);for i:=1 to n do begindi:=av0,i;if di0 then prei:=v0 else prei:=0;end;markv0:=true;repeat每循环一次加入一个离1集合最近的结点并调整其他结点的参数mi n:二maxi nt;u:=0; u记录离1集合最近的结点for i:=1 to n doif (not marki) and (dimi n)the n

9、beg inu:=i; mi n:=di;end;if u0then beginmarku:=true;for i:=1 to n doif (not marki) and (au,i+duvdi) then begindi:=au,i+du;prei:=u;end;end;until u=0;end;3. 计算图的传递闭包Procedure Longlink;VarT:array1.maxn,1.maxn of boolean;BeginFillchar(t,sizeof(t),false);For k:=1 to n doFor I:=1to n doFor j:=1 to n do Tl

10、,j:=tl,j or (tl,k and tk,j);End;4 无向图的连通分量A. 深度优先procedure dfs ( now,color: integer);beginfor i:=1 to n doif anow,i and ci=0 then begin 对结点 I 染色ci:二color;dfs(I,color);end;end;B宽度优先（种子染色法）5. 关键路径几个定义：顶点1为源点，n为汇点。a. 顶点事件最早发生时间Vej, Ve j = max Ve j + wl,j ,其中Ve =0;b. 顶点事件最晚发生时间Vlj, VI j = min Vlj - wl,j

11、 ,其中 Vl（n） = Ve（n）;c. 边活动最早开始时间EeI,若边I由勺k表示，则EeI = Vej;d. 边活动最晚开始时间ElI,若边I由j,k表示，则ElI = Vlk - wj,k;若Eej = Elj，则活动j为关键活动，由关键活动组成的路径为关键路径。求解方法：a. 从源点起topsort,判断是否有回路并计算Ve;b. 从汇点起topsort,求Vl;c. 算 Ee 和 El;6. 拓扑排序找入度为0的点，删去与其相连的所有边，不断重复这一过程。例寻找一数列，其中任意连续 p项之和为正，任意q项之和为负，若不存在则输出NO.7. 回路问题Euler 回路（DFS）定义：经

12、过图的每条边仅一次的回路。（充要条件：图连同且无奇点）Hamilton 回路定义：经过图的每个顶点仅一次的回路。一笔画充要条件：图连通且奇点个数为0个或2个。9 判断图中是否有负权回路Bellma n-ford 算法xl,yl,tl分别表示第I条边的起点，终点和权。共n个结点和m条边。procedure bellma n-fordbegi nfor I:=0 to n-1 do dl:=+infinitive;d0:=0;for I:=1 to n-1 dofor j:=1 to m do 枚举每一条边if dxj+tjdyj then dyj:=dxj+tj;for I:=1 to m do

13、if dxj+tjdyj then return false else return true;end;10 第n最短路径问题*第二最短路径：每举最短路径上的每条边，每次删除一条，然后求新图的最短路径，取这些路径中最短的一条即为第二最短路径。*同理，第n最短路径可在求解第n-1最短路径的基础上求解。color二#0000FF 三、背包问题/color*部分背包问题可有贪心法求解：计算Pi/Wi数据结构：wi:第i个背包的重量；pi：第i个背包的价值；1. 0-1背包：每个背包只能使用一次或有限次(可转化为一次)：A. 求最多可放入的重量。NOIP2001 装箱问题有一个箱子容量为 v(正整数，

14、ow v 20000)同时有n个物品(o n=bestthen exit; sn为前 n 个物品的重量和if kv=n then beginif vwk then search(k+1,v-wk);search(k+1,v);end;end;l DPFl,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现:将最优化问题转化为判定性问题边界：fO,O:=true.f I, j = f i-1, j-wi (wl=j0thenif j+nowv=nthen inc(cj+now,aj);a:=c;end;2.可重复背包A求最多可放入的重量。Fl,j为前i个物品中选择若干个放入使其

15、体积正好为j的标志，为布尔型。状态转移方程为fl,j = f I-1, j - wl*k (k=1. j div wl)B. 求可以放入的最大价值。USACO 1.2 Score In flation进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti (解答此题所需的时间)和一个si (解答此题所得的分数)，现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。*易想到：fi,j = max f i- k*wj,j-1 + k*pj (0=k=0 ThenBegint:=problemj.po in t+fi-probl

16、emj.time;If tfi Then fi:=t;End;Writel n(fM);En d.C. 求恰好装满的情况数。Ahoi2001 Problem2求自然数n本质不同的质数和的表达式的数目。思路一，生成每个质数的系数的排列，在一一测试，这是通法。procedure try(dep:integer);var i,j:integer;begi ncal; 此过程计算当前系数的计算结果，now为结果if nown then exit; 剪枝if dep=l+1then begin 生成所有系数cal;if now=n then inc(tot);exit;end;for i:=0 to n

17、 div prdep do beg inxsdep:=i;try(dep+1);xsdep:=0;end;end;思路二，递归搜索效率较高procedure try(dep,rest:integer);var i,j,x:integer;begi nif (rest0thenfor k:=1 to n div now doif j+now*kv=nthen inc(cj+now*k,aj);a:=c;end;mainbegi nread( no w);读入第一个物品的重量i：=0;ai为背包容量为i时的放法总数while iv=n do beginai:=1;inc(i,now);end; 定

18、义第一个物品重的整数倍的重量a值为1,作为初值for i:=2 to v dobegi nread( no w);update; 动态更新end;writel n(a n);四、排序算法1.快速排序：procedure qsort(l,r:integer);var i,j,mid:integer;begini:=l;j:=r; mid:=a(l+r) div 2; 将当前序列在中间位置的数定义为中间数repeatwhile aimid do dec(j);在右半部分寻找比中间数小的数if ij;if lj then qsort(lj);若未到两个数的边界，则递归搜索左右区间if ir then

19、 qsort(i,r);en d;sortB.插入排序：思路：当前a1.ai-1已排好序了，现要插入ai使a1.ai有序。procedure in sert_sort;var i,j:integer;beginfor i:=2 to n do begina0:=ai;j:=i-1;while a0ajthen swap(ai,aj);end;D. 冒泡排序procedure bubble_sort;var i,j,k:integer;beginfor i:=1 to n-1 dofor j:=n downto i+1 doif ajaj-1 then swap( aj,aj-1);每次比较相邻

20、元素的关系 end;E. 堆排序：procedure sift(i,m:integer); 调整以i为根的子树成为堆，m为结点总数var k:integer;begi na0:=ai;k:=2*i;在完全二叉树中结点i的左孩子为2*i,右孩子为2*i+1while k=m do beg inif (km) and (akak+1) then inc(k);找出 ak与 ak+1中较大值endif a0vakthen begin ai:=ak;i:=k;k:=2*i;else k:=m+1;end;ai:=a0;将根放在合适的位置end;procedure heapsort;varj:i nte

21、ger;begi nfor j:=n div 2 downto 1 do sift(j,n);for j:=n downto 2 do beginswap(a1,aj);sift(1,j-1);end;end;F. 归并排序a为序列表，tmp为辅助数组procedure merge(var a:listtype;p,q,r:i nteger);将已排序好的子序列ap.q与aq+1.r合并为有序的tmpp.rvar I,j,t:integer;tmp:listtype;begi nt:=p;i:=p;j:=q+1;t 为tmp指针，l,j分别为左右子序列的指针 while (t=r) do be

22、ginif (ir) or (ai=aj)满足取左边序列当前元素的要求then begintmpt:=ai; in c(i);endelse begintmpt:=aj;i nc(j);end;in c(t);end;for i:=p to r do ai:=tmpi;en d;mergeprocedure merge_sort(var a:listtype; p,r: integer); 合并排序 ap.rvar q:integer;beg inif pr then beginq:=(p+r-1) div 2;merge_sort (a,p,q);merge_sort (a,q+1,r);m

23、erge (a,p,q,r);end;end;mainbeg inmerge_sort(a,1, n);end.G. 基数排序思想：对每个元素按从低位到高位对每一位进行一次排序五、高精度计算高精度数的定义：typehp二array1.maxlenof integer;高精度加法procedure plus ( a,b:hp; var c:hp);var i,len:integer;begi nfillchar(c,sizeof(c),0);if a0b0then len:=a0else len:=b0;for i:=1 to len do beginin c(ci,ai+bi);if ci10

24、 then begin dec(ci,10); inc(ci+1); end; 进位 end;if clen+10then inc(len);c0:=le n;en d;plus2 高精度减法procedure substract(a,b:hp;var c:hp);var i,len:integer;beg infillchar(c,sizeof(c),0);if aObO then len:二a0else len:=b0;for i:=1 to len do beginin c(ci,ai-bi);if ci1) and (clen=0)do dec(len);c0:=le n;end;3

25、高精度乘以低精度procedure multiply(a:hp;b:l ongin t;varc:hp);var i,len:integer;beg infillchar(c,sizeof(c),0);le n:=a0;for i:=1 to len do beginin c(ci,ai*b);in c(ci+1,(ai*b) div 10);ci:=ci mod 10;end;in c(le n);while (clen=10)do begin 处理最高位的进位cle n+1:=cle ndiv 10;cle n:=cle nmod 10;in c(le n);end;while (len1

26、) and (clen=0)do dec(len); 若不需进位则调整lenc0:=le n;en d;multiply4 高精度乘以高精度procedure high_multiply(a,b:hp; var c:hpvar i,j,len:integer;beg infillchar(c,sizeof(c),0);for i:=1 to a0 dofor j:=1 to b0 do beginin c(ci+j-1,ai*bj);in c(ci+j,ci+j-1 div 10);ci+j-1:=ci+j-1 mod 10;end;len :=a0+b0+1;while (len1) and

27、 (clen=0)do dec(len);c0:=le n;end;5 高精度除以低精度procedure devide(a:hp;b:longint;var c:hp; var d:longint);c:=a div b; d:= a mod bvar i,len:integer;beg infillchar(c,sizeof(c),0);le n:=a0;d:=0;for i:=len downto 1 do begind:=d*10+ai;ci:=d div b;d:=d mod b;end;while (len1) and (clen=0)then dec(len);c0:=le n;

28、end;6 高精度除以高精度procedure high_devide(a,b:hp; var c,d:hp);vari,le n:i nteger;beg infillchar(c,sizeof(c),0);fillchar(d,sizeof(d),0);len :=a0;d0:=1;for i:=len downto 1 do beginmultiply(d,10,d);d1：=ai;while(compare(d,b)=0) do 即 d=bbeg inSubtract(d,b,d);end;end;while(len1)and(c.slen=0)do dec(len);c.le n:=

29、le n;end;六、树的遍历已知前序中序求后序procedure Solve(pre,mid:stri ng);var i:integer;beg inif (pre=H)or (mid=H)then exit;i:=pos(pre1,mid);solve(copy(pre,2,i),copy(mid,1,i-1);solve(copy(pre,i+1,length(pre)-i),copy(mid,i+1,length(mid)-i);post:二post+pre1;加上根，递归结束后post即为后序遍历end;2 已知中序后序求前序procedure Solve(mid,post:str

30、i ng);var i:integer;beg inif (mid=”“)or (post=H)then exit;i:=pos(postle ngth(post),mid);pre:=pre+postlength(post); 加上根，递归结束后 pre即为前序遍历solve(copy(mid,1,l-1),copy(post,1,l-1);solve(copy(mid,l+1,length(mid)-l),copy(post,l,length(post)-i);end;3.已知前序后序求中序的一种 fun cti on ok(s1,s2:stri ng):boolea n;var i,l:

31、integer; p:boolean;beg inok:=true;l:=le ngth(s1);for i:=1 to l do beg inp:=false;for j:=1 to l doif s1i=s2j then p:=true;if not p then begin ok:=false;exit;end;end;end;procedure solve(pre,post:string);var i:integer;begi nif (pre二”)or (post=”“)then exit;i:=0;repeatinc(i);until ok(copy(pre,2,i),copy(p

32、ost,1,i);solve(copy(pre,2,i),copy(post,1,i);midstr:=midstr+pre1;solve(copy(pre,i+2,length(pre)_i_1),copy(post,i+1,length(post)_i_1);end;七进制转换1. 任意正整数进制间的互化除n取余2. 实数任意正整数进制间的互化乘n取整3. 负数进制：设计一个程序，读入一个十进制数的基数和一个负进制数的基数，并将此十进制数转换为此负进制下的数：-R _2 , _3, _4,._20八全排列与组合的生成1.排列的生成：（1.n ）procedure solve(dep:int

33、eger);vari:i nteger;begi nif dep二n+1then begin writeln(s);exit;end;for i:=1 to n doif not usedi then begin s:=s+chr(i+ord(0);usedi:=true; solve(dep+1);s:=copy(s,1,le ngth(s)-1);usedi:二false;end;end;2.组合的生成(1.n中选取k个数的所有方案)procedure solve(dep,pre:integer);vari:i nteger;begi nif dep=k+1then begin write

34、ln(s);exit;end;for i:=1 to n doif (not usedi) and (ipre)the n beg ins:=s+chr(i+ord(0);usedi:=true; solve(dep+1,i);s:=copy(s,1,le ngth(s)-1);usedi:二false;end;end;九查找算法1. 折半查找fun cti on bin search(k:keytype):i nteger;var low,hig,mid:integer;begi nlow:=1;hig:=n;mid:=(low+hig) div 2;while (amid.keyvk) a

35、nd (lowkthen hig:=mid-1else low:=mid+1;mid:=(low+hig) div 2;end;if lowhig then mid:=0;bin search:二mid;end;2. 树形查找二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。查找function treesrh(k:keytype):pointer;var q:pointer;beg inq:二root;while (qvnil) and (qdkeyok)doif kvqkeythen q:二qeftelse q:=qA.right;treesrh:=q;end;

36、十、贪心*会议问题(1) n个活动每个活动有一个开始时间和一个结束时间，任一时刻仅一项活动进行，求满足活动数最多的情况。解：按每项活动的结束时间进行排序，排在前面的优先满足。(2) 会议室空闲时间最少。(3) 每个客户有一个愿付的租金，求最大利润。(4) 共R间会议室，第i个客户需使用i间会议室，费用相同，求最大利润。十一、回溯法框架1. n皇后问题procedure try(i:byte);var j:byte;begi nif i=n+1then begin print;exit;end;for j:=1 to n doif ai and bj+i and cj-i then begin刈

37、:=j;aj:二false;bj+i:二false; cj-i:二false;try(i+1);aj:=true; bi+j:=true; cj-i:=true;end;end;2. Hanoi Tower 汉诺塔h(n )=2*h( n-1)+1h(1)=1初始所有铜片都在a柱上procedure hanoi(n,a,b,c:byte);将第n块铜片从 a柱通过b柱移到c柱上begi nif n=0 then exit;hanoi(n-1,a,c,b);将上面的n-1块从a柱通过c柱移到b柱上write(n, moviedm ,a, ; to ,hanoi(n-1,b,a,c); 将b上的n

38、-1块从b柱通过a柱移到c柱上end;初始铜片分布在3个柱上，给定目标柱 goalh1.3,0.n存放三个柱的状态，now与nowp存最大的不到位的铜片的柱号和编号，hl,0存第I个柱上的个数。Procedure move(k,goal:integer);将最大不到位的 k移到目标柱 goal上Begi nIf k=0 then exit;For I:=1 to 3 doFor j:=1 to han 1,0doIf hl,j=kthen begin now:=l;nowp:二j;end; 找到 k 的位置If nowgoalthen begin若未移到目标Move(k-1,6-now-goal);剩下的先移到没用的柱上 Writeln(k moved from now to goal);Hgoal,hgoal,0+1:=h now,no wp;hnow,no wp:=0;In c(hgoal,0);dec(h no w,0);Move(k-1,goal);剩下的移到目标上End;十二、DFS框架NOIP2001 数的划分procedure work(dep,pre,s:longint);入口为 work(1