编程基本算法普及组.DOC

1、第 1 页 共 13 页 1编程基本算法(普及组)For NOIP 2009By ClimberPascal目录计算程序运行时间 .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).5高精度(a) 高精度 (b)=高精度 (c).6高精度进制转换 .7压位高精度

2、 .8高精度阶乘 .11高精度阶乘求和(秦九韶算法) .11快速幂算法(分治 ).12排序算法 .14冒泡排序 .14插入排序 .15合并排序 .15快速排序 .15数论算法 .16辗转相除法(最大公约数 ,最小公倍数 ).16素数(筛法 ).16素数测试 .16欧拉函数 .16组合算法 .16组合数计算 .16排列数计算 .16组合生成算法 .16排列生成算法 .16卡特兰数 .16树和图的算法 .16前序+中序 =后序 .16前序+中序 =后序 .17前序+后序 =中序 .17二叉树遍历 .17查找算法 .17第 2 页 共 13 页 2顺序查找 .17二分查找 .17动态规划 .170/

3、1背包 .17贪心算法 .17部分背包 .17搜索算法 .170/1背包 .17第 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+ss/100; writeln(t2-t1):0:2); end.高精度运算初始化【加减法初值】tmp0:=1;【乘法初值】tmp0:=1;tmp1:=1;【高精度类型】type hp = array 0

4、.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=tmp;end; /交换高精度(a)+ 整型 (b)=高精度 (c)Inc(a1,b);/相加while (aa09) do begin/进位inc(aa0+1,aa0 div 10);aa0:=aa0 mod 10;inc(a0)

5、;end;dec(a0);c:=a;高精度(a)- 整型 (b)=高精度 (c)While x 9 thenbegin 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(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 =

6、 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(c0);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 c

7、i1) do dec(c0);/长度计算高精度(a) 高精度 (b)=高精度 (c)for i:=1 to a0 do for j:=1 to a0 doinc(ci+j-1,ai*bj);c0:=a0+b0; for i:=1 to c0 do if ci9 thenbegin inc(ci+1,tmpi div 10);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

8、 = 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; 高精度进制转换的主函数，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 第 7

9、页 共 13 页 7int 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 + 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

10、dobegins:=s*n+1;dec(n);end;fac:=s;end;beginread(n);s:=1;writeln(fac(n):0:0);end.说明:本程序基于秦九韶算法，大大减少了乘法的计算次数，优于利用递归求阶乘然后求和的方法。type ary=array 0.100 of integer;varn,i,last:integer;s:ary;procedure mult(n:integer;var s:ary);begins1:=s1*n;for i:=2 to last dobeginsi:=si*n;si:=si + si-1 div 10;si-1:=si-1 mod

11、 10;end;while slast=10 dobegininc(last);slast:=slast-1 div 10;slast-1:=slast-1 mod 10;第 9 页 共 13 页 9end;end;procedure add(var s:ary);begins1:=s1+1;i:=1;while si10 dobeginsi+1:=si+1+si div 10;si:=si mod 10;end;if ilast then inc(last);end;procedure fac(n:integer);beginwhile n1 dobeginmult(n,s);add(s);

12、dec(n);end;end;beginread(n);last:=2;s1:=1;fac(n);for i:=last downto 1 do write(si);end.说明:本程序基于秦九韶算法，大大减少了乘法的计算次数，优于利用递归求阶乘然后求和的方法。快速幂算法(分治 )整型快速幂代码 （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; 先将底数转化为高精度数，然后只要将上面的整型全部替换为高精度数即可。代码如下：

13、幂为整型：void QM_int(hp a, int k, hp memcpy(tmp, a, sizeof(tmp); /复制底数 memset(res, 0, sizeof(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); /

14、清零 res0 = res1 = 1; while (k0 != 1 | k1 != 0) if (change_div_int(k, 2, k, 10) mul_hp(res, tmp, res); mul_hp(tmp, tmp, tmp); memcpy(b, res, sizeof(b); return ; 排序算法冒泡排序var i,j,k:longint;for i:=1 to n-1 dofor j:=i+1 to n doif aiaj then begink:=ai;ai:=aj;aj:=k;end;插入排序var key,i,j:longint;for j:=2 to n

15、do beginkey:=aj;i:=j-1;while (i0) and (aikey) dobegin ai+1:=ai;dec(i);end;ai+1:=key;end;合并排序varl,r:array1.6238 of longint;第 11 页 共 13 页 11q,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;beginif y=0 then gcd:=x else gcd:=gcd(y,x mod y);end;素数(筛法 )素数测试