1、正整数n的划分算法
int split(int n,int m){ if(n==1||m==1) return 1; else if(n
2、对于给定的包含n个元素的数组a[0:n-1]，要求从中找出第k小的元素
#define NUM 1001int a[NUM];int select(int left,int right,int k){ int (left>=right)return a[left]; int i=left; int j=right+1; int pivot=a[left]; while(true){ do{ i=i+1; }while(a[i]
3、整数因子分解
#include
4、半数集问题
半数集递归算法
int comp(int n){ int ans=1; if(n>1) for(int i=1;i<=n/2;i++) ans+=comp(i); return ans;}
记忆式搜索
#include
int main(){ int n; while(cin>>n){ memset(a,0,sizeof(a)); a[1]=1; cout<
5、输油管道问题
采用分治算法计算中位数
#include
采用排序算法计算中位数
#include
6、取余运算
#include
7、集合全排列
#include int main(){ int list[5]={1,2,3,4,5}; Perm(list,0,3); return 0;} 8、矩阵连乘问题 #define NUM 51int p[NUM];int m[NUM][NUM];int s[NUM][NUM];void MatrixChain(int n){ for(int i=1;i<=n;i++) m[i][i]=0; for(int r=2;r<=n;r++) for(int i=1;i<=n;i++){ int j=i+r-1; m[i][j]=m[i+1][j]+p[i-1]*[p[i]*p[i]; s[i][j]=i; for(int k=i+1;k 9、最长公共子序列 #define NUM 100int c[NUM][NUM];int b[NUM][NUM];void LCSLength(int m,int n,const char x[],char y[]){ int i,j; for(i=1;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++) for(j=1;j<=n;j++){ if(x[i]==y[j]){ c[i][j]=c[i-1][[j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[[i][j-1]){ c[i][j]=c[i-1][j]; b[i][j]=2; } else { c[i][j]=c[i][j-1]; b[i][j]=3; } }} 10、最大子段和 #define NUM 101int a[NUM];int MaxSum(int n){ int sum=0; int b=0; for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else b=a[i]; if(b>sum) sum=b; } return sum;} 11、最大子段和的最优解 #define NUM 101int a[NUM];int MaxSum(int n,int &besti,int &bestj){ int sum=0; int b=0; int begin=0; for(int i=1;i<=n;i++){ if(b>0) b+=a[i]; else{ b=a[i]; begin=i; } if(b>sum){ sum=b; besti=begin; bestj=i; } } return sum;} 12、0—1背包问题 #define NUM 50#define CAP 1500int w[NUM];int v[NUM];int p[NUM][CAP];void knapsack(int c,int n){ int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) p[n][j]=0; for(int j=w[n];j<=c;j++) p[n][j]=v[n]; for(int i=n-1;i>1;i--){ jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) p[i][j]=p[i+1][j]; for(int j=w[n];j<=c;j++) p[i][j]=max(p[i+1][j],p[i+1][j-w[n]]+v[i]); } p[1][c]=p[2][c]; if(c>=w[1]) p[1][c]=max(p[1][c],p[2][c-w[n]]+v[1]);} 0—1背包最优解 void traceback(int c,int n,int x[]){ for(int i=1;i 13、最长单调递增子序列 #define NUM 100int a[NUM];int Lls_n2(int n){ int b[NUM]={0}; int i,j; b[1]=1; int max=0; for(i=2;i<=n;i++){ int k=0; for(j=1;j 14、数字三角形问题 #define NUM 100int tri[NUM][NUM];int triangle(int n){ int i,j; for(i=n-2;i>=0;i--) for(j=0;j<=i;j++){ if(tri[i+1][j]>tri[i+1][j+1]) tri[i][j]+=tri[i+1][j]; else tri[i][j]+=tri[i+1][j+1]; } return tri[0][0];} 15、Human Gene Functions cin>>first>>secend;gene[0][0]=0;for(i=1;i<=secend;i++) gene[0][i]=gene[0][i-1]+score[4][map[str2[i-1]]];for(i=1;i<-first;i++) gene[i][0]=gene[i-1][0]+score[map[str1[i-1]]][4];int m1,m2,m3;for(i=1;i<=first;i++) for(j=1;j<=secend;j++){ m1=gene[i-1][j]+score[map[str1[i-1]]][4]; m2=gene[i][j-1]+score[4][map[str2[i-1]]]; m3=gene[i-1][j-1]+score[map[str1[i-1]][map[str2[i-1]]];} FatMouses Speedstruct mouse{ int weight,speed,id;}mice[1001]; //排序因子 int cmp(const void *a,const void *b){ mouse*ta=(mouse*)a; mouse*tb=(mouse*)b; if(ta->weight==tb->weight) return tb->speed-ta->speed; return ta->weight-tb->weight;} //最长单调递增子序列算法 int count[1001]={0};int path[1001]={0};count[1]=1;for(int i=2;i // 查找最大的序列长度 int max=0;int pos;for(int i=1;i 16、活动安排问题 struct action{ int s; int f; int index;}bool cmp(coust action &a,const action &b){ if(a.f<=b.f) return true; return false;}void GreedySelector(int n,action a[],bool b[]){ b[1]=true; int preEnd=1; for(int i=2;i<=n;i++) if(a[i].s>=a[preEnd].f){ b[i]=true; preEnd=i; }} 17、背包问题 struct bag{ int w; int v; double c;}a[1001];bool cmp(bag a,bag b){ return a.c>=b.c;}double knapsack(int n, bag a[],double c){ double cleft=c; int i=0; double b=0; while(i 18、Wooden Sticks #define maxN 5001struct stick{ int l; int w;};stick data[maxN];int cmp(stick a,stick b){ if(a.l==b.l) return a.w 19、Gone Fishing void greedy(int pos,int time){ if(time<=0) return; int i,j; int fish[MAXN]; int p[MAXN]; int t=0; for(i=0;i 20、回溯法-装载问题 void Backtrack(int t){ if(t>n){ f(cw>bestw){ for(int i=1;i<=n;i++) bestx[i]=x[i]; bestw=cw; } return; } r-=w[t]; if(cw+w[t]<=c){ x[t]=1; cw+=w[t]; Backtrack(t+1); cw-=w[t]; } if(cw+r>bestw){ x[t]=0; Backtrack(t+1); } r+=w[t];} 21、回溯法-0-1背包问题 struct Object{ int w; int v; double d;}Q[NUM];bool cmp(Object a,Object b){ if(a.d=b.d) return true; else return false;}void backtrack(int t){ if(i+1>n){ bestv=cv; return; } if(cw+Q[i].w<=c){ cw+=Q[i].w; cv+=Q[i].v; backtrack(i+1); cw-=Q[i].w; cv-=Q[i].v; } if(Bound(i+1)>bestv) backtrack(i+1);}int Bound(int i){ int cleft=c-cw; int b=cv; while(i 22、回溯法-n皇后问题 void Backtrack(int t){ int i; if(t>n){ sum++; for(i=1;i<=n;i++) cout< 23、回溯法-旅行商问题 void Backtrack(int t){ if(t==n){ if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n]][1]!=NoEdge&& (cc+a[x[n-1]][x[n]]+a[x[n]][1] 24、装载问题 #define NUM 100int n;int c;int w[NUM];int MaxLoading(){ queue (int)Q; Q.push(-1); int i=0; int Ew=0; int bestw=0; int r=0; for(int j=1;j 25、Fire Net char cMap[5][5];int iBest;int n;void solve(int k,int current){ int x,y; if(k==n*n){ if(current>iBest){ iBest=current; return ; } } else { x=k/n; y=k%n; if(cMap[x][y]=='.'&&CanPut(x,y)){ cMap[x][y]='0'; solve(k+1,current+1); cMap[x][y]='.'; } solve(k+1,current); }}bool CanPut(int row,int col){ int i; for(i=row-1;i>=0;i--){ if(cMap[i][col]=='0') return false; if(cMap[i][col]=='X') break; } for(i=col-1;i>=0;i--){ if(cMap[row][i]=='0') return false; if(cMap[row][i]=='X') break; } return true;}