编程基本算法普及组.DOC

1、第 1页 共 13 页 1 编程 基本算法 (普及组 ) For NOIP 2009 By Climber Pascal 目录 计算程序运行时间 . 3 高精度运算 . 3 初始化 . 3 比较大小 (Max) . 3 高精度 (a)+整型 (b)=高精度 (c) . 3 高精度 (a)-整型 (b)=高精度 (c) . 3 高精度 (a)整型 (b)=高精度 (c) . 3 高精度 (a)整型 (b)=高精度 (c) . 4 高精度 (a)+高精度 (b)=高精度 (c). 4 高精度 (a)-高精度 (b)=高精度 (c). 4 高精度 (a)高精度 (b)=高精度 (c). 4 高精度

2、(a)高精度 (b)=高精度 (c). 4 高精度进制转换 . 5 压位高精度 . 5 高精度阶乘 . 7 高精 度阶乘求和 (秦九韶算法 ) . 7 快速幂算法 (分治 ). 8 排序算法 . 9 冒泡排序 . 9 插入排序 . 9 合并排序 . 9 快速排序 . 10 数论算法 . 10 辗转相除法 (最大公约数 ,最小公倍数 ). 10 素数 (筛法 ) . 10 素数测试 . 10 欧拉函数 .11 组合算法 .11 组合数计算 .11 排列数计算 .11 组合生成算法 .11 排列生成算法 .11 卡特兰数 .11 树和图的算法 .11 前序 +中序 =后序 .11 前序 +中序 =

3、后序 . 12 前序 +后序 =中序 . 12 二叉树遍历 . 12 查找算法 . 12 第 2页 共 13 页 2 顺序查找 . 12 二分查找 . 12 动态规划 . 12 0/1背包 . 12 贪心算法 . 12 部分背包 . 12 搜索算法 . 12 0/1背包 . 12 第 3页 共 13 页 3 计算程序运行时间 uses dos; var h,m,s,ss:word; t1,t2:real; begin gettime(h,m,s,ss); t1:=h*3600+m*60+s+ss/100; * /主程序 gettime(h,m,s,ss); t2:=h*3600+m*60+s+

4、ss/100; writeln(t2-t1):0:2); end. 高精度运算 初始化 【加减法初值】 tmp0:=1; 【乘法初值】 tmp0:=1;tmp1:=1; 【高精度类型】 type hp = array 0.250 of integer; /hp0表示该数的长度 比较大小 (Max) if (a0 b0) then max:=true else max:=false; /比较 for i:=a0 downto 1 do if ai bi then max:=true else max:=false; if max=false then begin tmp:=a;a:=b;b=tm

5、p;end; /交换 高精度 (a)+整型 (b)=高精度 (c) Inc(a1,b);/相加 while (aa09) do begin/进位 inc(aa0+1,aa0 div 10); aa0:=aa0 mod 10;inc(a0);end; dec(a0);c:=a; 高精度 (a)-整型 (b)=高精度 (c) While x 9 then begin inc(ci+1,ci);ci:=ci mod 10;end; while (cc0=0) and (c01) do dec(c0); 第 4页 共 13 页 4 高精度 (a)整型 (b)=高精度 (c) void div_int(

6、hp a, int x, hp rest = 0; for (int i = a0; i = 1; i-) rest = rest * 10 + ai; if (rest = x) resi = rest / x, rest %= x; int l = a0; while (resl = 0 res0 = l; return ; 高精度 (a)+高精度 (b)=高精度 (c) for i:= 1 to a0 do tmpi:=ai+bi; /相加 for i:= 1 to a0+1 do if ci9 then /进位 begin inc(ci+1);dec(ci,10);end; inc(c

7、0);while (cc0=0) and (c01) do dec(c0);/长度计算 高精度 (a)-高精度 (b)=高精度 (c) Max(a,b); for i:= 1 to a0 do ci:=ai-bi;/相减 for i:= 1 to a0 do if ci1) do dec(c0);/长度计算 高精度 (a)高精度 (b)=高精度 (c) for i:=1 to a0 do for j:=1 to a0 do inc(ci+j-1,ai*bj); c0:=a0+b0; for i:=1 to c0 do if ci9 then begin inc(ci+1,tmpi div 10

8、);tmpi:=tmpi mod 10;end; while (cc0=0) and (c01) do dec(c0); 高精度 (a)高精度 (b)=高精度 (c) int div_hp(hp int l = MIN_RES, r = MAX_RES, mid; while (l = 1; i-) rest = rest * k + ai; if (rest = x) tmpi = rest / x, rest %= x; int l = a0; while (tmpl = 0 tmp0 = l; memcpy(res, tmp, sizeof(tmp); return rest; 高精度进

9、制转换的主函数， n为当 前进制， k为目标进制， b 为结果： void N_to_K(hp while (a0 != 1 | a1 != 0) b0+; bb0 = change_div_int(a, k, a, n); return ; 压位高精度 void Init(hp 第 6页 共 13 页 6 int tmp = 0, t = 0, l, k; cin s; memset(a, 0, sizeof(a); l = s.size(); k = l / 8; if (l % 8 != 0) k+; a0 = k; for (int i = 1; i = 100000000) tmpi

10、 + 1 +, tmpi -= 100000000; l+; while (tmpl = 0 tmp0 = l; memcpy(c, tmp, sizeof(c); return ; void Zero(int x) /补零 if (x = 1; i-) Zero(ai); cout 1 do begin s:=s*n+1; dec(n); end; fac:=s; end; begin read(n); s:=1; writeln(fac(n):0:0); end. 说明 :本程序基于秦九韶算法，大大减少了乘法的计算次数，优于利用递归求阶乘然后求和的方法。 type ary=array 0.

11、100 of integer; var n,i,last:integer; s:ary; procedure mult(n:integer;var s:ary); begin s1:=s1*n; for i:=2 to last do begin si:=si*n; si:=si + si-1 div 10; si-1:=si-1 mod 10; end; while slast=10 do begin inc(last); slast:=slast-1 div 10; slast-1:=slast-1 mod 10; 第 8页 共 13 页 8 end; end; procedure add

12、(var s:ary); begin s1:=s1+1; i:=1; while si10 do begin si+1:=si+1+si div 10; si:=si mod 10; end; if ilast then inc(last); end; procedure fac(n:integer); begin while n1 do begin mult(n,s); add(s); dec(n); end; end; begin read(n); last:=2;s1:=1; fac(n); for i:=last downto 1 do write(si); end. 说明 :本程序基

13、于秦九韶算法，大大减少了乘法的计算次数，优于利用递归求阶乘然后求和的方法。 快速幂算法 (分治 ) 整型快速幂代码 （ n为底数， k为指数）： int QM(int n, int k) int tmp = n, res = 1; while (k != 0) if (k tmp *= tmp; k = k 1; return res; 先将底数转化为高精度数，然后只要将上面的整型全部 替换为高精度数即可。代码如下： 幂为整型： void QM_int(hp a, int k, hp memcpy(tmp, a, sizeof(tmp); /复制底数 memset(res, 0, sizeof

14、(res); /清零 res0 = res1 = 1; while (k != 0) if (k mul_hp(tmp, tmp, tmp); k = k 1; memcpy(b, res, sizeof(b); return ; 幂为高精度 （十进制）： void QM_int(hp a, hp memcpy(tmp, a, sizeof(tmp); /复制底数 memset(res, 0, sizeof(res); /清零 res0 = res1 = 1; while (k0 != 1 | k1 != 0) if (change_div_int(k, 2, k, 10) mul_hp(re

15、s, tmp, res); mul_hp(tmp, tmp, tmp); memcpy(b, res, sizeof(b); return ; 排序算法 冒泡排序 var i,j,k:longint; for i:=1 to n-1 do for j:=i+1 to n do if aiaj then begin k:=ai;ai:=aj;aj:=k;end; 插入排序 var key,i,j:longint; for j:=2 to n do begin key:=aj;i:=j-1; while (i0) and (aikey) do begin ai+1:=ai;dec(i);end; ai+1:=key;end; 合并排序 var l,r:array1.6238 of longint; 第 10 页 共 13 页 10 q,n1,n2,k:longint; if p x do dec(j);找右边比他小的 if ij; if sj then sort(s,j); if it then sort(i,t); 数论算法 辗转相除法 (最大公约数 ,最小公倍数 ) function gcd(x,y:longint):longint; begin if y=0 then gcd:=x else gcd:=gcd(y,x mod y); end; 素数 (筛法 ) 素数测试