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 1001
int 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]=j) break;
swap(a[i],a[j])
}
if(j=left+1==k) return piovt;
a[left]=a[j];
a[j]=piovt;
if(j-left+1
3、整数因子分解
#include
using namespace std;
int total;
void solve(int n){
if(n==1)
total++;
else for(int i=2;i<=n;i++)
if(n%i==0) solve(n/i);
}
int main(){
int n;
while(cin>>n){
total=0;
solve(n);
cout<
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
#include
using namespace std;
int a[1001];
int comp(int n){
int ans=1;
if(a[n]>0) return a[n];
for(int i=1;i<=n/2;i++)
ans+=comp(i);
a[n]=ans;
return ans;
}
int main(){
int n;
while(cin>>n){
memset(a,0,sizeof(a));
a[1]=1;
cout<
5、输油管道问题
采用分治算法计算中位数
#include
#include
#include
using namespace std;
int main(){
int n;
int x;
int a[1000];
cin>>n;
for(int i=0;i>x>>a[i];
int y=select(0,n-1,n/2);
int min=0;
for(int i=0;i
采用排序算法计算中位数
#include
#include
#include
using namespace std;
int main(){
int n;
int x;
int a[1000];
cin>>n;
for(int i=0;i>x>>a[i];
sort(a,a+n);
int min=0;
for(int i=0;i
6、取余运算
#include
#include
#include
using namespace std;
int mod(int a,int p,int k){
if(p==1) return a%k;
if(p%2) return mod(a%k,p-1,k)*a%k;
else return mod((a*a)%k,p/2,k);
}
int main(){
unsigned a,p,k;
while(cin>>a>>p>>k)
cout<
7、集合全排列
#include
using namespace std;
void Perm(int list[],int k,int m){
if(k==m){
for(int i=0;i<=m;i++)
cout<
int main()
{
int list[5]={1,2,3,4,5};
Perm(list,0,3);
return 0;
}
8、矩阵连乘问题
#define NUM 51
int 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 100
int 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 101
int 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 101
int 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 1500
int 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 100
int 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 100
int 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 Speed
struct 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;imice[j].weight&&
mice[i].speed
// 查找最大的序列长度
int max=0;
int pos;
for(int i=1;imax){
max=count[i];
pos=i;
}
cout<
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 5001
struct 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;imax){
max=fish[j];
id=j;
}
if(id!=-1){
++p[id];
fish[id]-=d[id];
t+=max;
}
else ++p[0];
}
if(t>best){
best=t;
memset(plan,0,sizeof(plan));
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 100
int 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;jbestw)
bestw=wt;
if(ibestw&&i
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;
}
