编程常用基本算法.doc
文本预览下载声明
编程基本算法(普及组)
For NOIP 2009
By Climber目录
计算程序运行时间 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
动态规划 17
0/1背包 17
贪心算法 17
部分背包 17
搜索算法 17
0/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. 高精度运算
初始化
【加减法初值】tmp[0]:=1;
【乘法初值】tmp[0]:=1;tmp[1]:=1;
【高精度类型】type hp = array [0..250] of integer; //hp[0]表示该数的长度if (a[0] b[0]) then max:=true else max:=false; //比较
for i:=a[0] downto 1 do
if a[i] b[i] then max:=true else max:=false;
if max=false then begin tmp:=a;a:=b;b=tmp;end; //交换 高精度(a)+整型(b)=高精度(c)
In(a[1],b);//相加
while ([a[0]]9) do begin//进位
in(a[a[0]+1],a[a[0]] div 10);
a[a[0]]:=a[a[0]] mod 10;inc(a[0]);end;
dec(a[0]);c:=a; 高精度(a)-整型(b)=高精度(c)
While x0 do begin //相减
dec(c[c[0]],x mod 10);
x := x div 10;inc(c[0]);end;
for i:=1 to c[0] do if c[i] 0 then //退位
begin inc(c[i],10);dec(c[i + 1]);end;
while (c[c[0]]=0) and (c[0]1) do dec(c[0]); 高精度(a)×整型(b)=高精度(c)
for i:=1 to a[0] do c[i]:=a[i]*x;c[0]:=a[0]+10;
for i:=1 to c[0] do if c[i] 9 then
begin inc(c[i+1],c[i]);c[i]:=c[i] mod 10;end;
while (c[c[0]]=0) and (c[0]1) do dec(c[0]); 高精度(a)÷整型(b)=高精度(c)
void div_int(hp a, int x, hp res, int rest)
{
memset(res, 0, sizeof(res));
rest = 0;
for (int i = a[0]; i = 1; i--)
{
rest = rest * 10 + a[i];
if (rest = x) res[i] = rest / x, rest %= x;
}
int l = a[0];
while (res[l] == 0 l 1) l--;
res[0] = l;
return ;
} 高精度(a)+高精度(b)=高精度(c)
for
显示全部