编程常用基本算法.doc

编程基本算法(普及组)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压位高精度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顺序查找17二分查找17动态规划170/1背包17贪心算法17部分背包17搜索算法170/1背包17计算程序运行时间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.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);end;dec(a0);c:=a;高精度(a)-整型(b)=高精度(c)While x0 do begin /相减dec(cc0,x mod 10); x := x div 10;inc(c0);end;for i:=1 to c0 do if ci 1) do dec(c0); 高精度(a)整型(b)=高精度(c)for i:=1 to a0 do ci:=ai*x;c0:=a0+10;for i:=1 to c0 do if ci 9 then begin inc(ci+1,ci);ci:=ci mod 10;end;while (cc0=0) and (c01) do dec(c0);高精度(a)整型(b)=高精度(c)void div_int(hp a, int x, hp &res, int &rest) memset(res, 0, sizeof(res); 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 & l 1) l-; 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 ci1) 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 then begin 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 &a, hp &b, hp &rest) hp tmp; 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 & l 1) l-; tmp0 = l; memcpy(res, tmp, sizeof(tmp); return rest; 高精度进制转换的主函数，n为当前进制，k为目标进制，b 为结果：void N_to_K(hp &a, int n, int k, hp &b) memset(b, 0, sizeof(b); while (a0 != 1 | a1 != 0) b0+; bb0 = change_div_int(a, k, a, n); return ; 压位高精度void Init(hp &a) string s; 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 k; i+) t = l - 8 * i; tmp = 0; for (int j = 0; j = 7; j+) tmp = tmp * 10 + (st + j - 0); ai = tmp; l = l - (a0 - 1) * 8, tmp = 0; for (int t = 0; t l; t+) tmp = tmp * 10 + st - 0; aa0 = tmp; return ; void add(hp a, hp b, hp &c) int l = max(a0, b0); hp tmp; memset(tmp, 0, sizeof(tmp); for (int i = 1; i = l; i+) tmpi = ai + bi; for (int i = 1; i = 100000000) tmpi + 1 +, tmpi -= 100000000; l+; while (tmpl = 0 & l 1) l-; tmp0 = l; memcpy(c, tmp, sizeof(c); return ; void Zero(int x) /补零 if (x 10) cout 0000000; return ; if (x 100) cout 000000; return ; if (x 1000) cout 00000; return ; if (x 10000) cout 0000; return ; if (x 100000) cout 000; return ; if (x 1000000) cout 00; return ; if (x 10000000) cout 0; return ; return ; void prin(hp a) cout = 1; i-) Zero(ai); cout ai; cout 1 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 10;end;while slast=10 dobegininc(last);slast:=slast-1 div 10;slast-1:=slast-1 mod 10;end;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);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 & 1) res *= tmp; tmp *= tmp; k = k 1; return res; 先将底数转化为高精度数，然后只要将上面的整型全部替换为高精度数即可。代码如下：幂为整型： void QM_int(hp a, int k, hp &b) hp tmp, res; memcpy(tmp, a, sizeof(tmp); /复制底数 memset(res, 0, sizeof(res); /清零 res0 = res1 = 1; while (k != 0) if (k & 1) mul_hp(res, tmp, res); mul_hp(tmp, tmp, tmp); k = k 1; memcpy(b, res, sizeof(b); return ; 幂为高精度 （十进制）：void QM_int(hp a, hp &k, hp &b) hp tmp, res; 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(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 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;q,n1,n2,k:longint;if p c then q:=(p+c) shr 1 else exit;sort(p,q);sort(q+1,c);n1:=q-p+1;n2:=c-q;fillchar(l,sizeof(l),0);fillchar(r,sizeof(r),0);for i:=1 to n1 do li:=ap+i-1;for j:=1 to n2 do rj:=aq+j;ln1+1:=655360;rn2+1:=655360;i:=1;j:=1;for k:=p to c doif li=rj thenbegin ak:=li;inc(i);endelsebegin ak:=rj;inc(j);end;快速排序var i,j,x,temp:longint;i:=s;j:=t;x:=a(i+j)div 2;repeatwhile aix do dec(j);找右边比他小的if