算法总结材料由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“推荐系统算法总结”。
源程序代码：
}
一、自然数拆分（递归）
} #include
二、快速排序（递归）int a[100];void spilt(int t)#include { int k,j,l,i;main()for(k=1;k
spilt(j+1);} } int partitions(int a[],int from,int to)void main(){ { int n,i;
int value=a[from];printf(“please enter the number:”);
while(from
a[from]=a[to];
while(from
++from;
a[to]=a[from];
}
a[from]=value;
return from;
}
void qsort(int a[],int from,int to){ int pivottag;if(from
{pivottag=partitions(a,from,to);qsort(a,from,pivottag-1);qsort(a,pivottag+1,to);
} scanf(“%d”,&n);
for(i=1;i
三、删数字（贪心）
#include #include void main(){
int a[11]={3,0,0,0,9,8,1,4,7,5,1};
int k=0,i=0,j;
int m;
while(i
{
printf(“%d ”,a[i]);
i++;}
printf(“n please input delete number:”);
四、全排列（递归）#include A(char a[],int k,int n){
int i;char temp;if(k==n)
for(i=0;i
{printf(“%c ”,a[i]);} else {
for(i=k;i
{ temp=a[i];
a[i]=a[k];
a[k]=temp;
A(a,k+1,n);
} } } main(){
int n;
char a[4]={'a','b','c','d'},temp;
A(a,0,3);
getch();
return 0;}
五、多段图（动态规划）#include “stdio.h”
#define n 12 //图的顶点数
{ while(from=value)--to;
scanf(“%d”,&m);for(k=0;k
{
for(i=0;i
{
if(a[i]>a[i+1])
{
for(j=i;j
{a[j]=a[j+1];}
break;//满足条件就跳转
}
} }
int quicksort(int a[],int n){
qsort(a,0,n);}
}
printf(“the change numbers:”);
for(i=0;i
{
if(a[i]!=0)
{ printf(“%d ”,a[i]);}
}
}
#define k 4 //图的段数 #define MAX 23767 int cost[n][n];//成本值数组
int path[k];//存储最短路径的数组
void creatgraph()//创建图的(成本)邻接矩阵 { int i,j;
for(i=0;i
for(j=0;j
scanf(“%d”,&cost[i][j]);//获取成本矩阵数据 }
void printgraph()//输出图的成本矩阵 { int i,j;
printf(“成本矩阵:n”);
for(i=0;i
{ for(j=0;j
printf(“%d ”,cost[i][j]);
printf(“n”);
} }
//使用向前递推算法求多段图的最短路径 void FrontPath(){ int i,j,length,temp,v[n],d[n];
for(i=0;i
v[i]=0;for(i=n-2;i>=0;i--){ for(length=MAX,j=i+1;j
if(cost[i][j]>0 &&(cost[i][j])+v[j]
{length=cost[i][j]+v[j];temp=j;}
v[i]=length;
d[i]=temp;
}
path[0]=0;//起点
path[k-1]=n-1;//最后的目标
for(i=1;i
//使用向后递推算法求多段图的最短路径
void BackPath(){ int i,j,length,temp,v[n],d[n];
for(i=0;i
for(i=1;i
{ for(length=MAX,j=i-1;j>=0;j--)
if(cost[j][i]>0 &&(cost[j][i])+v[j]
{length=cost[j][i]+v[j];temp=j;}
v[i]=length;
d[i]=temp;
}
path[0]=0;
path[k-1]=n-1;
for(i=k-2;i>=1;i--)(path[i])=d[path[i+1]];}
//输出最短路径序列 void printpath(){ int i;
for(i=0;i
printf(“%d ”,path[i]);}
main(){ freopen(“E:1input.txt”,“r”,stdin);
creatgraph();
printgraph();
FrontPath();
printf(“输出使用向前递推算法所得的最短路径:n”);
printpath();
printf(“n输出使用向后递推算法所得的最短路径:n”);
BackPath();
printpath();printf(“n”);}
六、背包问题（递归）int knap(int m, int n){
int x;
x=m-mn;
if x>0
sign=1;
else if x==0
sign=0;
else
sign=-1;
switch(sign){
case 0: knap=1;break;
case 1: if(n>1)
if knap(m-mn,n-1)
knap=1;
else
knap= knap(m,n-1);
else
knap=0;
case-1: if(n>1)
knap= knap(m,n-1);
else
knap=0;
} }
七、8皇后（回溯）#include #include #define N 4 int place(int k, int X[N+1]){
int i;
i=1;
while(i
if((X[i]==X[k])||(abs(X[i]-X[k])==abs(i-k)))
return 0;
i++;
}
return 1;}
void Nqueens(int X[N+1]){
int k, i;
X[1]=0;k=1;
while(k>0){
X[k]=X[k]+1;
while((X[k]
X[k]=X[k]+1;
if(X[k]
if(k==N){ for(i=1;i
printf(“%3d”,X[i]);printf(“n”);
}
else{ k=k+1;
X[k]=0;
}
else k=k-1;
} }
void main(){
int n, i;
int X[N+1]={0};
clrscr();
Nqueens(X);
printf(“The end!”);}
八、图着色（回溯）#include #define N 5 int X[N]={0,0,0,0,0};int GRAPH[N][N]={ {0,1,1,1,0}, {1,0,1,1,1}, {1,1,0,1,0}, {1,1,1,0,1}, {0,1,0,1,0} };int M=4;int count=0;int mcoloring(int k){
int j,t;
while(1){
nextValue(k);
if(X[k]==0)
return 0;
if(k==(N-1)){
for(t=0;t
printf(“%3d”,X[t]);
printf(“n”);
count++;
}
else
mcoloring(k+1);
} } int nextValue(int k){
int j;
while(1){
X[k]=(X[k]+1)%(M+1);
if(X[k]==0)
return 0;
for(j=0;j
if((GRAPH[k][j]==1)&&(X[k]==X[j]))
break;
}
if(j==N){
return 0;
}
} } void main(){
int k;
clrscr();
k=0;
mcoloring(k);
printf(“ncount=%dn”,count);}
矩阵链乘法（动态规划） 符号S[i, j]的意义：
符号S(i, j)表示，使得下列公式右边取最小值的那个k值
public static void matrixChain(int [ ] p, int [ ][ ] m, int [ ][ ] s)
{
int n=p.length-1;
for(int i = 1;i
for(int r = 2;r
for(int i = 1;i
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
for(int k = i+1;k
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(t
m[i][j] = t;
s[i][j] = k;}
}
}
}
O的定义：
如果存在两个正常数c和n0，对于所有的n≥n0时，有：
|f(n)|≤c|g(n)|，称函数f(n)当n充分大时的阶比g(n)低，记为
f(n)=O(g(n))。计算时间f(n)的一个上界函数 Ω的定义：
如果存在正常数c和n0，对于所有n≥n0时，有：
|f(n)|≥c|g(n)|，则称函数f(n)当n充分大时下有界，且g(n)是它的一个下界，即f(n)的阶不低于g(n)的阶。记为：
f(n)=Ω(g(n))。Θ的定义：
如果存在正常数c1，c2和n0，对于所有的n>n0，有：
c1|g(n)|≤f(n)≤c2|g(n)|，则记f(n)=Θ(g(n))意味着该算法在最好和最坏的情况下计算时间就一个常因子范围内而言是相同的。(1)多项式时间算法：
O(1)
(2)指数时间算法：
O(2n)
Move(n,n+1)(2n+1,2n+2)move(2n-1,2n)(n,n+1)call che(n-1)
贪心方法基本思想：
贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择
所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
多段图：
COST[j]=c(j,r)+COST[r];
回溯法：
(假定集合Si的大小是mi)不断地用修改过的规范函数Pi(x1,…,xi)去测试正在构造中的n-元组的部分向量(x1,…,xi)，看其是否可能导致最优解。如果判定(x1,…,xi)不可能导致最优解，那么就将可能要测试的mi+1…mn个向量略去。约束条件：
(1)显式约束：限定每一个xi只能从给定的集合Si上取值。
(2)解
空
间：对于问题的一个实例，解向量满足显式
约束条件的所有多元组，构成了该实例
的一个解空间。
(3)隐式约束：规定解空间中实际上满足规范函数的元
组，描述了xi必须彼此相关的情况。基本做法：
在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解：如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
8皇后问题
约束条件
限界函数：
子集和数问题：
约束条件
限界函数：
回溯法－－术语：
活结点：已生成一个结点而它的所有儿子结点还没有
全部生成的结点称为活结点。
E-结点：当前正在生成其儿子结点的活结点叫E-结点。
死结点：不再进一步扩展或其儿子结点已全部生成的结点称为死结点。
使用限界函数的深度优先节点生成的方法成为回溯法；E-结点一直保持到死为止的状态生成的方法 称之为分支限界方法
且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。区别：
分支限界法本质上就是含有剪枝的回溯法，根据递归的条件不同，是有不同的时间复杂度的。
回溯法深度优先搜索堆栈或节点的所有子节点被遍历后才被从栈中弹出找出满足约束条件的所有解
分支限界法广度优先或最小消耗优先搜索队列，优先队列每个结点只有一次成为活结点的机会找出满足约束条件下的一个解或特定意义下的最优解
一般如果只考虑时间复杂度二者都是指数级别的可是因为分支限界法存在着各种剪枝，用起来时间还是很快的int M, W[10],X[10];void sumofsub(int s, int k, int r){
int j;
X[k]=1;
if(s+W[k]==M){
for(j=1;j
printf(“%d ”,X[j]);
printf(“n”);
}
else
if((s+W[k]+W[k+1])
sumofsub(s+W[k],k+1,r-W[k]);
}
if((s+r-W[k]>=M)&&(s+W[k+1]
X[k]=0;
sumofsub(s,k+1,r-W[k]);
} } void main(){
M=30;
W[1]=15;
W[2]=9;
W[3]=8;
W[4]=7;
W[5]=6;
W[6]=5;
W[7]=4;
W[8]=3;
W[9]=2;
W[10]=1;
sumofsub(0,1,60);}
P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合 如果可满足星月化为一个问题L，则此问题L是NP-难度的。如果L是NP难度的且L NP，则此问题是NP-完全的
算法分块总结为备战2005年11月4日成都一战，特将已经做过的题目按算法分块做一个全面详细的总结，主要突出算法思路，尽量选取有代表性的题目，尽量做到算法的全面性，不漏任何ACM可......
算法分析与设计总结报告71110415 钱玉明在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过......
算法总结1.穷举法穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法......
abs(x):y 取x的绝对值，x与 y可为整型或实型。* frac(x):y 取x的小数部分，x 与 y均为实型。* int(x):y 取x的整数部分，x 与 y均为实型，常写成 trunc(int(x)). * random(x):y......
Levent Ertoz等人提出了一种基于共享型邻居聚类算法SNN。该算法的基本思想为：先构造相似度矩阵，再进行最近k邻居的稀疏处理，并以此构造出最近邻居图，使得具有较强联系的样本间......
