发布时间 : 星期六 文章Noip常用算法大全更新完毕开始阅读
merge_sort(a,1,n); end.
G.基数排序
思想：对每个元素按从低位到高位对每一位进行一次排序 五、高精度计算 高精度数的定义： type
hp=array[1..maxlen] of integer; 1．高精度加法
procedure plus ( a,b:hp; var c:hp); var i,len:integer; begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0]; for i:=1 to len do begin inc(c,a+b);
if c>10 then begin dec(c,10); inc(c[i+1]); end; {进位} end;
if c[len+1]>0 then inc(len); c[0]:=len; end;{plus}
2．高精度减法
procedure substract(a,b:hp;var c:hp); var i,len:integer; begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then len:=a[0] else len:=b[0]; for i:=1 to len do begin inc(c,a-b);
if c<0 then begin inc(c,10);dec(c[i+1]); end; while (len>1) and (c[len]=0) do dec(len); c[0]:=len; end;
3．高精度乘以低精度
procedure multiply(a:hp;b:longint;var c:hp); var i,len:integer; begin
fillchar(c,sizeof(c),0); len:=a[0];
for i:=1 to len do begin inc(c,a*b);
inc(c[i+1],(a*b) div 10); c:=c mod 10; end; inc(len);
while (c[len]>=10) do begin {处理最高位的进位} c[len+1]:=c[len] div 10; c[len]:=c[len] mod 10; inc(len); end;
while (len>1) and (c[len]=0) do dec(len); {若不需进位则调整len} c[0]:=len; end;{multiply}
4．高精度乘以高精度
procedure high_multiply(a,b:hp; var c:hp} var i,j,len:integer; begin
fillchar(c,sizeof(c),0); for i:=1 to a[0] do
for j:=1 to b[0] do begin inc(c[i+j-1],a*b[j]); inc(c[i+j],c[i+j-1] div 10); c[i+j-1]:=c[i+j-1] mod 10; end;
len:=a[0]+b[0]+1;
while (len>1) and (c[len]=0) do dec(len); c[0]:=len; end;
5．高精度除以低精度
procedure devide(a:hp;b:longint; var c:hp; var d:longint); {c:=a div b; d:= a mod b} var i,len:integer; begin
fillchar(c,sizeof(c),0); len:=a[0]; d:=0;
for i:=len downto 1 do begin d:=d*10+a; c:=d div b; d:=d mod b; end;
while (len>1) and (c[len]=0) then dec(len); c[0]:=len; end;
6．高精度除以高精度
procedure high_devide(a,b:hp; var c,d:hp); var
i,len:integer; begin
fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); len:=a[0];d[0]:=1;
for i:=len downto 1 do begin multiply(d,10,d); d[1]:=a;
while(compare(d,b)>=0) do {即d>=b} begin
Subtract(d,b,d); inc(c); end; end;
while(len>1)and(c.s[len]=0) do dec(len); c.len:=len; end;
六、 树的遍历
1．已知前序中序求后序
procedure Solve(pre,mid:string); var i:integer; begin
if (pre='') or (mid='') then exit; i:=pos(pre[1],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+pre[1]; {加上根，递归结束后post即为后序遍历} end;
2．已知中序后序求前序
procedure Solve(mid,post:string); var i:integer; begin
if (mid='') or (post='') then exit; i:=pos(post[length(post)],mid);
pre:=pre+post[length(post)]; {加上根，递归结束后pre即为前序遍历} solve(copy(mid,1,I-1),copy(post,1,I-1));
solve(copy(mid,I+1,length(mid)-I),copy(post,I,length(post)-i));
end;
3．已知前序后序求中序的一种 function ok(s1,s2:string):boolean; var i,l:integer; p:boolean; begin
ok:=true; l:=length(s1);
for i:=1 to l do begin p:=false;
for j:=1 to l do
if s1=s2[j] then p:=true;
if not p then begin ok:=false;exit;end; end; end;
procedure solve(pre,post:string); var i:integer; begin
if (pre='') or (post='') then exit; i:=0; repeat inc(i);
until ok(copy(pre,2,i),copy(post,1,i)); solve(copy(pre,2,i),copy(post,1,i)); midstr:=midstr+pre[1];
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:integer); var