算法程序

排序问题P11#include<iostream>using namespace std;inline void swap(int &a,int&b){int temp=a;a=b;b=temp;}void perm(int list[],int k,int m){if(k==m){for(int i=0;i<=m;i++) cout<<list[i];cout<<endl;}elsefor(int i=k;i<=m;i++){swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}void main(){int a[10],n;cout<<"请输入要排列的数的个数:";cin>>n;for(int i=0;i<n;i++)cin>>a[i];perm(a,0,n-1);}二分搜索P16#include<iostream.h>int n,i,j; int a[1000];void xuanzhe(){int i, j, min, t;for (i=0; i<n-1; i++){min = i;for (j=i+1; j<n; j++){if (a[j] < a[min]){min = j;}}if (min != i){t = a[i];a[i] = a[min];a[min] = t;}}}int BinarySearch(int x){int left=0;int right=n-1;while(left<=right){int middle=(left+right)/2;if (x==a[middle]) return middle;if (x>a[middle]) left=middle+1;else right=middle-1;}return -1;}void main(){cout<<"输入数字的个数："<<endl;cin>>n;for(i=0;i<n;i++)cin>>a[i];xuanzhe();cout<<"请输入要查找的数:";cin>>j;int m=BinarySearch(j);if(m==-1)cout<<"没有你要找的数"<<endl;elsecout<<"你要找的数在数组中的第"<<m+1<<"个"<<endl; }棋盘覆盖P13（应用，运行的的结果的图会画，标数字）#include<iostream.h>int tile=1;int board[100][100];void chessBoard(int tr,int tc,int dr,int dc,int size){if(size==1)return;int t=tile++;int s=size/2;if(dr<tr+s && dc<tc+s)chessBoard(tr, tc, dr, dc, s);else{board[tr+s-1][tc+s-1]=t;chessBoard(tr, tc, tr+s-1, tc+s-1, s);}if(dr<tr+s && dc>=tc+s)chessBoard(tr, tc+s, dr, dc, s);else{board[tr+s-1][tc+s]=t;chessBoard(tr, tc+s, tr+s-1, tc+s, s);}if(dr>=tr+s && dc<tc+s)chessBoard(tr+s, tc, dr, dc, s);else{board[tr+s][tc+s-1]=t;chessBoard(tr+s, tc, tr+s, tc+s-1, s);}if(dr>=tr+s && dc>=tc+s)chessBoard(tr+s, tc+s, dr, dc, s);else{board[tr+s][tc+s]=t;chessBoard(tr+s, tc+s, tr+s, tc+s, s);}}void main(){int size;cout<<"输入棋盘的size(大小必须是2的n次幂): "; cin>>size;int index_x,index_y;cout<<"输入特殊方格位置的坐标: ";cin>>index_x>>index_y;chessBoard(0,0,index_x,index_y,size);for(int i=0;i<size;i++){for(int j=0;j<size;j++)cout<<board[i][j]<<"\t";cout<<endl;}}石子合并问题P90#include <iostream>using namespace std;int Fx[200][200],Fn[200][200],Arr[200];int i,j,k,Temp,Maxm,Minm,N;int main(){while(cin>> N){for(i=1;i<=N;i++){cin>> Temp;Arr[i]=Arr[i-1]+Temp;Arr[i+N]=Temp;}for(i=N+1;i<=2*N;i++)Arr[i]=Arr[i-1]+Arr[i];for(k=1;k<=N-1;k++)for(i=1;i<=2*N-k;i++){Maxm=0;Minm=765432100;for(j=i+1;j<=i+k;j++){Temp=Arr[i+k]-Arr[i-1]+Fx[i][j-1]+Fx[j][i+k]; if (Temp > Maxm)Maxm=Temp;Temp=Arr[i+k]-Arr[i-1]+Fn[i][j-1]+Fn[j][i+k]; if(Temp<Minm)Minm=Temp;}Fx[i][i+k]=Maxm;Fn[i][i+k]=Minm;}Maxm=0;Minm=765432100;for(i=1;i<=N;i++){if (Fx[i][i+N-1] > Maxm) Maxm=Fx[i][i+N-1];if (Fn[i][i+N-1] < Minm) Minm=Fn[i][i+N-1];}cout<< Minm <<endl;cout<< Maxm <<endl;}return 0;}数字三角形P90#include<iostream>using namespace std;int main (){int n,i,j,k;int a[102][102]={0};int c[102]={0};int d[102]={0};int max;cin>>n;for (i=1;i<=n;i++)for (j=1;j<=i;j++)cin>>a[i][j];for (i=1;i<=n;i++) {for (k=1;k<=i;k++){d[k]=c[k-1]>c[k]?c[k-1]:c[k]; d[k]+=a[i][k];}for(j=1;j<k;j++){c[j]=d[j];}}max=0;for(i=1;i<=n;i++){if(c[i]>max) max=c[i];}cout<<max;return 0;}租用游艇P91#include<iostream>using namespace std;#define N 201int f[N][N];int n;void init(){int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++) f[i][j]=0;cout<<"请输入每两站之间的租金："<<endl;for(i=0;i<n-1;i++)for(j=i+1;j<n;j++) cin>>f[i][j];}void dyna(){for(int k=2;k<n;k++)for(int i=0;i<n-k;i++){int j=i+k;for(int p=i+1;p<j;p++){int temp=f[i][p]+f[p][j];if(f[i][j]>temp) f[i][j]=temp;}}}int main(){cout<<"请输入游艇站的个数：";cin>>n;init();dyna();cout<<f[0][n-1]<<endl;return 0;}数量极差P133#include<iostream>using namespace std;long int a[5000]={0},b[5000]={0};void quicksort(int low,int high){int mid=a[(low+high)/2],i=low,j=high,t;while(i<=j){while(a[i]<mid)i++;while(a[j]>mid)j--;if(i<=j){t=a[i];a[i]=a[j];a[j]=t;i++;j--;}}if(low<j)quicksort(low,j);if(high>i)quicksort(i,high);}int main(){long int i,j,n,maxx=0,minn=0;cout<<"请输入正整数个数:";cin>>n;for(i=1;i<=n;i++) cin>>a[i];quicksort(1,n);for(i=1;i<=n;i++)b[i]=a[i];i=2;while(i<=n){maxx=a[i-1]*a[i]+1;if(i==n)break;j=i;while(a[j+1]<maxx&&j+1<=n){a[j]=a[j+1];j++;}a[j]=maxx;i++;}i=n-1;while(i>=1){minn=b[i+1]*b[i]+1;if(i==1)break;j=i;while(b[j-1]>minn&&j-1>=1)j--;b[j]=minn;i--;}cout<<"数列极差是:"<<maxx-minn<<endl;return 0;}N后问题#include<iostream>using namespace std;#include<iostream>using namespace std;class Queen{friend int nQueen(int);private:bool Place(int k);void Backtract(int t);int n,*x;long sum;};bool Queen::Place(int k){for(int j=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))return false;return true;}void Queen::Backtract(int t){if (t>n){sum++;cout<<"第"<<sum<<"种方法：";for(int i=1;i<=n;i++)cout<<x[i]<<" ";cout<<endl;}else{for(int i=1;i<=n;i++){x[t]=i;if(Place(t)) Backtract(t+1);}}}int nQueen(int n){Queen X;X.n=n;X.sum=0;int *p=new int[n+1];for(int i=0;i<=n;i++)p[i]=0;X.x=p;X.Backtract(1);delete []p;return X.sum;}void main(){int n,m;cout<<"请输入皇后个数:";cin>>n;m=nQueen(n);cout<<endl;cout<<"有"<<m<<"种可行方法"<<endl; }图的m着色问题P163#include<iostream>using namespace std;const int N=10;int a[N][N];class Color{friend int mColoring(int ,int );private:bool OK(int k);void Backtrack(int k);int n,m,*x;long sum;};bool Color::OK(int k){for(int j=1;j<=n;j++)if((a[k][j]==1) && x[j]==x[k])return false;return true;}void Color::Backtrack(int t){if(t>n){sum++;for(int i=1;i<=n;i++)cout<<x[i]<<'\t';cout<<endl;}elsefor(int j=1;j<=m;j++){x[t]=j;if(OK(t)) Backtrack(t+1);x[t]=0;}}int mColoring(int n,int m){Color X;X.n=n;X.m=m;X.sum=0;int *p=new int [n+1];for(int i=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1);delete [] p;return X.sum;}int main(){int n,m,t;int i,j;cout<<"输入图中顶点的个数"<<endl;cin>>n;cout<<"输入颜色的种数："<<endl;cin>>m;cout<<"输入图的邻接矩阵"<<endl;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j];cout<<endl;t=mColoring(n,m);if(t)cout<<"可行方案个数："<<t<<endl;elsecout<<"这个图不是m="<<m<<"可着色的"<<endl; return 0;}。