算法试题代码实现.doc

小学手算的程序实现C+#includeusing namespace std;#define N 10int main() int i,j,set=0; char kN; int aN,bN,c2*N; for(i=0;iN;i+) /cin.getline(c,N);/for(i=0;iN;i+) ai=ci-48; /cin.getline(c,N);/for(i=0;iN;i+) bi=ci-48; ai=rand()%N; bi=rand()%N; /公式rand()%(b-a)，是求范围随机数的计算公式，%是做求余运算，正整数对n求余的范围/肯定是在0n-1之间，/也就是rand()%(b-a)的范围是0b-a-1，然后加上a，也就是范围变成了ab-1。 /而rand()%90+10=rand()%（100-10）+10，自己算算看吧。 cout=0;i-) cinai; coutendl; cout=0;i-) cinbi; coutendl; for(i=0;i2*N;i+) ci=0; coutendl; /算法 for(i=0;iN;i+) for(j=0;jN;j+) cj+i=cj+i+bi*aj+set; set=cj+i/10; cj+i=cj+i%10; cj+i+=set; set=0; cout=0;i-) coutci; coutendl;分治法求解大整数乘积：#include#include#include using namespace std; int n,x,y,result;/全局变量 void input() coutn; coutendl请输入两个乘数的值:endl; coutx; couty; int calculate(int a,int b) /计算数值函数-循环体 int temp1,temp2; long s; int x1,x0,y1,y0; if(n1) /可以分治算法的条件 temp1=(int)pow(10,n/2); temp2=(int)pow(10,n); x1=a/temp1; /x值的前半部分 x0=a-x1*temp1; /x值的后半部分 y1=b/temp1;/y值的前半部分 y0=b-y1*temp1;/y值的后半部分 n=n/2; /经过一次分治后,数的位数减半 s=calculate(x1,y1)*temp2+(calculate(x1+x0,y1+y0)-calculate(x1,y1)-calculate(x0,y0)*temp1+calculate(x0,y0); else return a*b; return s; void print()/输出函数 cout乘数x=xty=yendl; cout结果result=resultendl; int main()/主函数 char c; do system(cls);/清屏函数 input(); result=calculate(x,y); print(); cout是否继续?(y/n)c; while(c=y|c=Y); 最大子段和蛮力法：include #include #define N 7int aN = -2,11,-4,13,-5,-2,8;/用蛮力法求最大子段和 int ManLiFa(int *a,int n) int besti=-1; int bestj=-1; int sum = 0; for(int i = 1;i=n;i+) int thissum = 0; for (int j = i;jsum) sum = thissum; besti = i; bestj = j; printf(起点 = +besti); printf(终点 = +bestj); return sum; int main() printf(蛮力法 最大子段和: %dn,ManLiFa(a, N);return 0;最大子段和分治法：#include #include #include #define N 7int MaxSubSum(int *a, int left, int right); /分治法求最大子段和 int aN = -2,11,-4,13,-5,-2,8;int MaxSum(int *a, int n) /a是数组,n是数组大小 return MaxSubSum(a, 0, n-1); /分治法int MaxSubSum(int a,int left,int right) int i,sum=0;if(left=right)sum=aleft0?aleft:0;else int center=(left+right)/2;int leftsum=MaxSubSum(a,left,center);int rightsum=MaxSubSum(a,center+1,right);int s1=0,lefts=0; for(i=center;i=left;i-) lefts+=ai;if(leftss1)s1=lefts; int s2=0;int rights=0; for(i=center+1;is2)s2=rights; sum=s1+s2;if(sumleftsum) sum=leftsum;if(sumrightsum) sum=rightsum; return sum; int main() printf(分治法 最大子段和: %dn, MaxSum(a, N); return 0; 最大子段和动态规划法：#include #include #include #define N 7int aN = -2,11,-4,13,-5,-2,8;int MaxSumDP(int *a, int n) int i,sum=0,b=0; for(i=1;i0)b+=ai; elseb=ai;if(bsum)sum=b; return sum; int main() printf(动态规划 最大子段和: %dn, MaxSumDP(a, N); return 0; 0-1背包问题动态规划：#includeint c10100;/*对应每种情况的最大价值*/int knapsack(int m,int n) int i,j,w10,p10; printf(请输入每个物品的重量,价值：n); for(i=1;i=n;i+) scanf(%d,%d,&wi,&pi); for(i=0;i10;i+) for(j=0;j100;j+) cij=0;/*初始化数组*/ for(i=1;i=n;i+) for(j=1;j=m;j+) if(wici-1j) /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/ /*大于上一次选择的最佳方案则更新cij*/ cij=pi+ci-1j-wi; else cij=ci-1j; else cij=ci-1j; return(cnm); int main() int m,n;int i,j;printf(请输入背包的承重量,物品的总个数：n); scanf(%d,%d,&m,&n); printf(旅行者背包能装的最大总价值为%d,knapsack(m,n); printf(n); return 0; 0-1背包问题回溯法：#include using namespace std; class Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm ; coutendl; ; private: int Bound(int i); void Backtrack(int i); int c;/背包容量 int n; /物品数 int *w;/物品重量数组 int *p;/物品价值数组 int cw;/当前重量 int cp;/当前价值 int bestp;/当前最优值 int *bestx;/当前最优解 int *x;/当前解 ; int Knap:Bound(int i) /计算上界 int cleft=c-cw;/剩余容量 int b=cp; /以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) cleft-=wi; b+=pi; i+; /装满背包 if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(int p,int w,int c,int n); public: int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) /为Knap:Backtrack初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i=n;i+) Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi; W+=wi; if(W=c) return P;/装入所有物品 /依物品单位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0;K.bestx0=0; for( i=1;i=n;i+) K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; K.cw=0; K.c=c;K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; delete K.p; return K.bestp; int main() int *p; int *w; int c=0; int n=0;int i=0; char k; cout0-1背包问题-回溯法 endl; while(k) cout请输入背包容量(c)：c; cout请输入物品的个数(n)：n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout请输入物品的价值(p)：endl; for(i=1;ipi; cout请输入物品的重量(w)：endl; for(i=1;iwi; cout最优解为(bestx)：endl; cout最优值为(bestp)：endl; coutKnapsack(p,w,c,n)endl; couts 重新开始endl; coutq 退出k; 0-1背包分支限界：#include #include using namespace std; #define N 100 class HeapNode public: double upper,price,weight; /upper为结点的价值上界，price是结点所对应的价值，weight为结点所相应的重量 int level,xN; /活节点在子集树中所处的层序号 ; double MaxBound(int i); double Knap(); void AddLiveNode(double up,double cp,double cw,bool ch,int level); stack High; /最大队High double wN,pN; double cw,cp,c=50; /cw为当前重量，cp为当前价值，定义背包容量为50 int n=10; /货物数量为10 int main() int i; for(i=1;iwi; /输入10个物品的重量 for(i=1;ipi; /输入10个物品的价值 coutKnap()endl; /调用knap函数 输出最大价值 return 0; double MaxBound(int j) /MaxBound函数求最大上界 double left=c-cw,b=cp; /剩余容量和价值上界 while(j=n&wj=left) /以物品单位重量价值递减装填剩余容量 left-=wj; b+=pj; j+; if(j=n) b+=pj/wj*left; /装填剩余容量装满背包 return b; void AddLiveNode(double up,double cp,double cw,bool ch,int lev) /将一个新的活结点插入到子集数和最大堆High中 HeapNode be; be.upper=up; be.price=cp; be.weight=cw; be.level=lev; if(lev=n) High.push(be); /调用stack头文件的push函数 double Knap() /优先队列分支限界法，返回最大价值，bestx返回最优解 int i=1; cw=cp=0; double bestp=0,up=MaxBound(1); /调用MaxBound求出价值上界，best为最优值 while(1) /非叶子结点 double wt=cw+wi; if(wtbestp) bestp=cp+pi; AddLiveNode(up,cp+pi,cw+wi,true,i+1); up=MaxBound(i+1); if(up=bestp) /右子数可能含最优解 AddLiveNode(up,cp,cw,false,i+1); if(High.empty() return bestp; HeapNode node=High.top(); /取下一扩展结点 High.pop(); cw=node.weight; cp=node.price; up=node.upper; i=node.level; 0-1背包贪心算法程序代码： #include structgoodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号 ; /物品信息结构体 voidInsertionsort(goodinfo goods,int n) intj,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(goodinfo goods,float M,int n) float cu; inti,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/该物品所要放的量 for(j=2;j=n;j+) /*按物品编号做降序排列*/ goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; void main() cout|-运用贪心法解背包问题-|endl; int j; int n; float M; goodinfo *goods;/定义一个指针 while(j) coutn; goods=new structgoodinfo n+1;/ coutM; coutendl; inti; for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请输入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj; 运动员最佳配对问题回溯法：#include#include /文件输入输出流#include /I/O流控制头文件#include /vector是一个能够存放任意类型的动态数组，/能够增加和压缩数据using namespace std;vector Re; /全局变量,Re用来记录配对情况vectorvector P;vectorvector Q;class PairUp friend int nPairUp(int);private:bool Place(int k);void Backtrack(int k);int n; /运动员个数int bestsum;vector x; /当前解public:PairUp(int m,int c,int b) x.resize(m+1); Re.resize(m+1);n = c; bestsum = b; PairUp() ;bool PairUp:Place(int k) for(int j=1;jn)int currentsum=0; /第次还原为进行下次的累加for(int i=1;i=n;i+) currentsum += (Pixi) * (Qxii); /累加，计算当前配对总和 if(bestsum=currentsum) /记录最大可行解bestsum=currentsum;copy(x.begin(),x.end(),Re.begin(); elsefor(int i=t;i=n;i+) swap(xt,xi);if(Place(t)Backtrack(t+1);swap(xt,xi); int nPairUp(int n) PairUp X(n,n,0); /初始化Xvector p;for(int i=0;i=n;i+)p.push_back(i); /当前的P数组尾部插入i的值copy(p.begin(),p.end(),X.x.begin();X.Backtrack(1);return X.bestsum;int main() ifstream fin(input.txt);ofstream fout(output.txt);int n,i,j,currentsum;vector r; vector t;finn;r.push_back(0); P.push_back(r);t.push_back(0); Q.push_back(t);cout回溯法求解运动员最佳配对endlendl;cout从文件input.txt中获得数据.endl;for(i=1;i=n;i+)for(j=1;jcurrentsum;r.push_back(currentsum); P.push_back(r);for(vector:iterator vr = r.begin()+1;vr != r.end();) vr = r.erase(vr); for(i=1;i=n;i+) for(j=1;jcurrentsum;t.push_back(currentsum); Q.push_back(t);for(vector:iterator vt = t.begin()+1;vt != t.end();)vt = t.erase(vt); cout结果为：nPairUp(n)，并已保存至output.txt.endlendl;cout男运动员 & 女运动员endl;for(i=1;i=n;i+) coutsetw(4)isetw(12)Reiendl; /保证输出宽度为n foutnPairUp(n)endl;return 0 ;运动员最佳配对问题分支限界法：#include #include #include #include #include using namespace std; int n; int *P; /女运动员和男运动员配对的竞赛优势 int *Q; /男运动员和女运动员配对的竞赛优势 int best; /最优解 int *w;/当前男运动员排列 class ArgNode public: int x;/arg1:x已排列 int csum;/此种排列的竞赛优势值 public: int *w;/当前男运动员排列 ArgNode(const ArgNode &one) w = new int n + 1; for (int i = 0; i w= new int n + 1; for (int i = 0; i wi = wi; this-x = x; this-csum = csum; ; /大顶堆 bool operator csum other.csum) return false; else return true; void compute();/计算当前节点值 ; void ArgNode:compute() csum = 0; for (int i = 1; i x; +i) csum += Piwi * Qwii; int Athletes() /初始化 priority_queue Heap; int *iniArr = new intn + 1; int i= 0; for (i = 0; i = n; +i) iniArri = i; ArgNode *initial = new ArgNode(iniArr,0,0); delete iniArr; Heap.push(*initial); while(!Heap.empty() ArgNode fatherNode = Heap.top(); Heap.pop(); if (fatherNode.x = n)/是一个全排列，则比较节点内值是否比当前最优值更佳 if (best fatherNode.csum) best = fatherNode.csum; else for (i = fatherNode.x + 1; i = n; +i)/广度优先所搜子树 ArgNode newNode(fatherNode);/把子节点内容先复制为父节点内容 +newNode.x;/深度+ newNode.wnewNode.x = fatherNode.wi;/选择第i个女选手 newNode.wi = fatherNode.wnewNode.x; newNpute();/子节点计算val Heap.push(newNode); return best; int main() ifstream infile(input3.txt); ofstream outfile(output3.txt); cout分支限界法求解运动员最佳配对 endl; coutinput.txt n; int i,j; P = new int *n + 1; Q = new int *n + 1; for (i = 0; i = n; +i) Pi = new intn + 1; Qi = new intn + 1; for (i = 1; i= n; +i) for (j = 1; j Pij; for (i = 1; i= n; +i) for (j = 1; j Qij; coutoutput.txt:endl; coutAthletes()endl; for (i = 0; i = n; +i) delete Pi; delete Qi; delete P; delete Q; 旅行售货员回溯法：# include using namespace std;const int NoEdge=-1;const int MAX=20;int GMAXMAX;int ansMAX,xMAX;int bestc,cc;void init(int n) int i,j,len; memset(G,NoEdge,sizeof(G); while( cinij ) if( i=0 & j=0 ) break; cinlen; Gij=len ; Gji=len; for(i=1;i=n;i+) xi=i; bestc=0x7fffffff; cc=0; void Swap( int& i,int& j) int t=I ; i=j; j=t; void BackTrack(int i,int n) int j; if(i=n+1) if(G xn-1 xn != NoEdge & G xn 1 != NoEdge & (cc + G xn 1 bestc ) ) for(j=1;j=n;j+) ansj = xj; bestc = cc + G xn 1 ; else for(j=i;j=n;j+) if( G xi-1 xj != NoEdge & (cc + G xi-1 xj bestc) ) Swap( xi,xj ); cc += G xi-1 xi ; BackTrack(i+1,n); cc -= G xi-1 xi ; Swap( xi,xj ); void print(int n) cout最小的旅行费用为：bestcendl; cout最佳路径是：; for(int i=1;i=n;i+) coutansi; coutans1n&n ) init(n); BackTrack(2,n); print(n) ; return 1; 旅行售货员分支限界法：#include #include using namespace std;#define MAX 9999#define N 40float aNN; int n;class HeapNodepublic: float lcost,cc,rcost; int s,xN; HeapNode( ) HeapNode(float lc,float ccc,float rc,int ss,int xx) lcost=lc,cc=ccc,s=ss; for(int i=0; in; i+) xi=xxi; bool operator=node.lcost; ;void init() int i,j; for(i=1; i=n; i+) for(j=1; jaij; if(aij0) aij=MAX; float BBTSP(int v) int flag=0; priority_queue heap; float minOutn+1,minSum=0; for(int i=1; i=n; i+) /计算最小出边费用和minSum和minOut float min=MAX; for(int j=1; j=n; j+) if(aijMAX & aijmin) mi