算法总结（材料）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“推荐系统算法总结”。
abs(x):y
取x的绝对值，x与 y可为整型或实型。
* frac(x):y
取x的小数部分，x 与 y均为实型。
* int(x):y
取x的整数部分，x 与 y均为实型，常写成 trunc(int(x)).* random(x):y
在 0-x 之间的整数中随机找一个整数，x与 y均为整型。
* sin(x):y;cos(x):y;arctan(x):y;exp(x):y;ln(x):y
均与数学运算一致,三角函数返回的均为弧度,转换成角度即乘以 Pi 除以 180.* copy(str,n1,n2):substr
从字符串str中取从第n1个字符开始长度为n2个字符的子串substr.n1和n2是整型表达式，如果 n1 大于 s 的长度，则返回空字符串。如果指定的 n2 大于第 n1 个字符后剩下的字符数，则返回剩下的字符串。
* pos(substr,str):num
查找 substr 是否为 str 的子串，若是则返回 substr 在 str 中的起始位置，若否则返0.* val(str,int,code)
将字串str转为数值型数据存入int, 如果字符串无效，其中非法字符的下标放在Code中；否则，code 为零。
* str(num,str)
将 num表达式转成字符串 str。
* delete(str,n1,n2)
从原字符串 str中删去一个从 n1 开始长度为 n2 的子串，如果 Index比 s 长，不删除任何字符。如果指定的 Count 大于从第 1ndex 大到结尾的字符数，删除剩余部分。
* Insert(Source：String；Var S：String；Index：Integer)
Source是字符串表达式。S是任意长度的字符串变量。Index是整型表达式。过程Insert把字符串 Source 插入字符串 S 中第 1ndex 个字符开始的位置上。如果字符串比 255 个字符长，则将第 255 后面的字符截去。
二、小技巧
1.ord('0')=48;ord('A'):=65;ord('a')=97;chr(32)=’ ‘;chr(33)=’!’;2.求x^y: int(exp(y*ln(x)))
3.求x 的n 次方根：exp(1/n*ln(x))
一、常见递推关系
1.Fibonacci 数列
A(1)=1;A(2)=1;
A(n)=A(n-1)+ A(n-2);2.Catalan 数：
考虑具有n 个结点不同形态的二叉树的个数 H(n)
H(0)= 1;
H(n)= H(0)H(n-1)+ H(1)H(n-2)+ H(2)H(n-3)… + H(n-2)H(1)+ H(n-1)H(0);
——>
H(n)=(1/(n+1))* C(n, 2n)
求关键路径 type arr=record
x1,y1:longint;
end;var
n,m,i,j,k,x,y,c,t,l:longint;
ok:boolean;
a,b:array[1..100,1..100] of integer;
h,ee,le:array[1..200] of longint;
d:array[1..100] of arr;begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y,c);
a[x,y]:=c;
b[x,y]:=1;
end;
for i:=1 to n do 寻找拓扑序起点
begin
ok:=true;
for j:=1 to n do
if b[j,i]=1 then begin ok:=false;break;end;
if ok then
begin
h[1]:=i;
break;
end;
end;
t:=1;
l:=0;
while tl do 求拓扑序
begin
inc(l);
x:=h[l];
for i:=1 to n do
if ix then
if b[x,i]=1 then
begin
b[x,i]:=0;
ok:=true;
for j:=1 to n do
if ij then
if b[j,i]=1 then begin ok:=false;break;end;
if ok then
begin
inc(t);
h[t]:=i;
end;
end;
end;
fillchar(ee,sizeof(ee),0);
ee[h[1]]:=0;
for i:=1 to n do
for j:=1 to n do
if ij then
if a[h[i],j]0 then
if ee[j]
ee[j]:=ee[h[i]]+a[h[i],j];
for i:=1 to n do
le[i]:=10000;
le[n]:=ee[n];最后一个点的最早时间就是它的最晚时间
for i:=n downto 1 do
for j:=1 to n do
if ij then
if a[j,h[i]]0 then
if le[j]>le[h[i]]-a[j,h[i]] then 求j的最晚时间
le[j]:=le[h[i]]-a[j,h[i]];
x:=1;
i:=h[1];
j:=h[1];
while jh[n] do 求关键路径
for j:=1 to n do
if ij then
if a[i,j]0 then（如果j的最晚时间减i的最早时间等于i到j的时间说明i-j是关键路径）
if le[j]-ee[i]=a[i,j] then
begin
d[x].x1:=i;
d[x].y1:=j;
i:=j;
inc(x);
break;
end;
for i:=1 to n do
writeln(ee[i]);输出每个点的最晚时间
for i:=1 to n do
writeln(le[i]);输出每个点的最早时间
for i:=1 to x-1 do
writeln(d[i].x1,' ',d[i].y1);输出每条关键路径 end.树状数组 var
a,c:array[1..100] of longint;
x,y,i,n,p,k,j:longint;function lowbit(x:longint):longint;begin
lowbit:=x and(-x);end;procedure add(k,delt:longint);修改点值 点k增加delt begin
while k
begin
c[k]:=c[k]+delt;
k:=k+lowbit(k);
end;end;function sum(k:Longint):longint;求和：1至k的和 var
t:longint;begin
t:=0;
while k>0 do
begin
t:=t+c[k];
k:=k-lowbit(k);
end;
sum:=t;end;begin
readln(n,k,p);
for i:=1 to n do read(a[i]);
fillchar(c,sizeof(c),0);
for i:=1 to n do
for j:=i-lowbit(i)+1 to i do
c[i]:=c[i]+a[j];
for i:=1 to k do
begin
readln(x,y);
add(x,y);
end;
for i:=1 to p do
begin
readln(x,y);
writeln(sum(y)-sum(x-1));
end;end.二维树状数组
Function getsum(x,y):integer;(求出矩阵(1,1)~(x,y)点值和)Var z,t:longint;Begin
t:=0;
while x>0 do
begin
z:=y;
while z>0 do
begin
t:=t+c[x,z];
z:=z-lowbit(z);
end;
x:=x-lowbit(x);
end;
getsum:=t;End;
最短路SPFA procedure spfa;begin fillchar(q,sizeof(q),0);h:=0;t:=0;//队列
fillchar(v,sizeof(v),false);//v[i]判断i是否在队列中 for i:=1 to n do dist[i]:=maxint;//初始化最小值
t:=1;q[t]:=1;v[1]:=true;dist[1]:=0;//这里把1作为源点 while not(h=t)do begin
h:=h+1;
x:=q[h];v[x]:=false;
for i:=1 to n do
if(cost[x,i]>0)and(dist[x]+cost[x,i]
begin
dist[i]:=dist[x]+cost[x,i];
if not(v[i])then
begin
t:=t+1;q[t]:=i;v[i]:=true;
end;
end;end;
end;floyd求最短环
g存储图 f存储最短路 for i:=1 to n do
for j:=1 to n do
f[i,j]:=g[i,j];for k:=1 to n do begin(找最短环res)for a:=1 to k-1 do
for b:=1 to k-1 do
if f[a,b]+g[a,k]+g[k,b]
for i:=1 to n do
for j:=1 to n do
if f[i,k]+f[k,j]
f[i,j]:=f[i,k]+f[k,i];end;最小生成树
function top(i:longint):longint;Begin
If if[i] then f[i]:=top(f[i]);
Top:=f[i];End;Procedure union(i,j,c:longint);Var
x,y:longint;Begin
x:=top(i);
y:=top(j);
if xy then begin
inc(ans,c);f[y]:=x;
end;end;begin
for i:=1 to m do read(e[i].x,e[i].y,e[i].c);sort;for i:=1 to n do f[i]:=i;ans:=0;for i:=1 to m do
union(e[i].x,e[i].y,e[i].c);writeln(ans);end;
求最大公约数
Function gcd(a,b:longint):longint;Begin
If b=0 then gcd:=a else
gcd=gcd(b,a mod b);End;
图的传递背包 For k:=1 to n do for i:=1 to n do
for j:=1 to n do a[i,j]:=a[i,j] or(a[i,k] and a[k,j]);无向图的连通分量 深度优先
procedure dfs(now,color:longint);
begin
for i:=1 to n do
if a[now,i] and c[i]=0 then
begin
c[i]:=color;
dfs(i,color);
end;
end;超快排
program superquicksort;const n=2000000;var a:array[0..n]of longint;i:longint;procedure sort(l,r,k:longint);var i,j:longint;begin i:=l;j:=r;repeat
while a[i] shr k and 1=0 do inc(i);
while a[j] shr k and 1=1 do dec(j);
if i
a[0]:=a[i];a[i]:=a[j];a[j]:=a[0];
inc(i);dec(j);
end;until i>j;if k=0 then exit;if l
begin randomize;for i:=1 to n do a[i]:=random($7fffffff);sort(1,n,30);end.快排(加上第二关键字)procedure sort(l,r:longint);var i,j:longint;
x,y:re;
begin
i:=l;
j:=r;
x:=c[(i+j)div 2];
repeat
while(c[i].a
while(c[j].a>x.a)or((c[j].a=x.a)and(c[j].b>x.b))do dec(j);
if i
begin
y:=c[i];
c[i]:=c[j];
c[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if i
if j>l then sort(l,j);
end;归并排序
procedure merge(var a:数组;p,q,r:longint);(将已排序好的子序列a[p..q]与a[q+1..r]合并为有序的tmp[p..r])var i,j,t:longint;tmp:数组； begin
t:=p;i:=p;j:=q+1;(t为tmp指针);
while(t
if ir)or(a[i]
begin
tmp[t]:=a[i];inc(i);
end else
begin
tmp[t]:=a[j];inc(j);
end;
inc(t);
end;
for i:=p to r do a[i]:=tmp[i];
end;
procedure merge_sort(var a:数组;p,r:longint);(合并a[p..r])
var q:longint;
begin if pr then begin
q:=(p+r-l)div 2;
merge_sort(a,p,q);
merge_sort(a,q+1,r);
merge(a,p,q,r);end;
end;begin merge_sort(a,1,n);{拆掉a数组然后合并} end.排列的生成（1..n）
Procedure solve(dep:integer);var
i:integer;begin
if dep=n=1 then begin writeln(s);exit;end;
for i:=1 to n do
if not used[i] then
begin
s:=s+chsr(i+ord(‘0’));used[i]:=true;
solve(dep+1);
s:=copy(s,1,length(s)-1);used[i]:=false;
end;end;组合的生成（1..n中选k个数的所有方案）procedure solve(dep,pre:longint);var
i:longint;begin
if dep=k+1 then begin writeln(s);exit;end;
for i:=1 to n do
if(not used[i])and(i>pre)then
begin
s:=s+chr(i+ord(‘0’));used[i]:=true;
solve(dep+1,i);
s:=copy(s,1,length(s)-1);used[i]:=false;
end;end;
快速幂
求a的p次幂 t:=a;ans:=1;while p0 do begin
if(p and 1)=1 then ans:=ans*t;
t:=t*t;
p:=p shr 1;
end;高精度加法
procedure highplus(a,b:arr;var c:arr);var i:longint;begin
fillchar(c,sizeof(c),0);
if a[0]>b[0] then c[0]:=a[0]
else c[0]:=b[0];
for i:=1 to c[0] do
inc(c[i],a[i]+b[i]);
for i:=1 to c[0] do
if c[i]>=10000 then
begin
dec(c[i],10000);
inc(c[i+1]);
end;
while c[c[0]+1]>0 do inc(c[0]);end;
高精度乘法
function cheng(a,b:arr):arr;var
i,j:longint;begin
fillchar(cheng,sizeof(cheng),0);
for i:=1 to a[0] do
for j:=1 to b[0] do
begin
cheng[i+j-1]:=cheng[i+j-1]+a[i]*b[j];
cheng[i+j]:=cheng[i+j]+cheng[i+j-1] div 10000;
cheng[i+j-1]:=cheng[i+j-1] mod 10000;
end;
cheng[0]:=a[0]+b[0]-1;
if cheng[cheng[0]+1]>0 then inc(cheng[0]);end;
高精度除
function chu(a:arr,b:longint):arr;var
i,j,x:longint;begin
x:=0;y:=0;
for i:=a[0] downto 1 do
begin
x:=(a[i]+y*10000)div b;
y:=(a[i]+y*10000)mod b;
a[i]:=x;
end;
while(a[a[0]]=0)and(a[0]>1)do dec(a[0]);
chu:=a;end;进制转换
负数进制一样。每次取的余数保证在0~-m-1之间。（例如m=-16,则余数应该在0~15）就可以直接输出。所以用系统的“mod”运算符的时候必须注意检查是不是在该范围（可能在m+1~0），否则就调整。调整的方法是： if 余数
const ch:string[20]='0123456789ABCDEFGHIJ';readln(n,k);
i:=0;s:=n;
while(s=-k)do
begin
b[i]:=s mod k;
s:=s div k;
if b[i]
begin
b[i]:=b[i]-k;
s:=s+1;
end;
inc(i);
end;
b[i]:=s;
for j:=i downto 0 do
write(ch[b[j]+1]);K进制转换十进制
function ktodec(st:string;k:longint):longint;
const alph='012456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';var i,j,ans:longint;begin
ans:=0;
j:=1;
for i:=length(st)downto 1 do
begin
inc(ans,j*(pos(st[i],alph)-1));
j:=j*k;end;
exit(ans);end;
筛素数
procedure makeprimelist;var i,j:longint;begin fillchar(p,sizeof(p),true);for i:=2 to 10000 do if p[i] then begin inc(np);pp[np]:=i;j:=i*i;while j
算法分块总结为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可......
算法分析与设计总结报告71110415 钱玉明在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过......
算法总结1.穷举法穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法......
Levent Ertoz等人提出了一种基于共享型邻居聚类算法SNN。该算法的基本思想为：先构造相似度矩阵，再进行最近k邻居的稀疏处理，并以此构造出最近邻居图，使得具有较强联系的样本间......
算法！ High low methodp62 Inventory control level p123 Formal of EOQp125 Formal of EBQp127 Efficiency，capacity and production volume ratios p140 Remuneration......
