《算法试题代码实现》由会员分享，可在线阅读，更多相关《算法试题代码实现（15页珍藏版）》请在金锄头文库上搜索。
1、 小学手算的程序实现小学手算的程序实现 C+ #include using namespace std; #define N 10 int main() int i,j,set=0;char kN;int aN,bN,c2*N;for(i=0;i=0;i-)cinai;cout=0;i-)cinbi;cout=0;i-)cout #include #include using namespace std; int n,x,y,result;/全局变量void input() coutn; coutx;couty; int calculate(int a,int b) /计算数值函数-循环体in
2、t 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+
3、calculate(x0,y0); elsereturn a*b; return s; void print()/输出函数coutc;while(c=y|c=Y); 最大子段和蛮力法：最大子段和蛮力法： include #include #define N 7 int 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;isum) sum = thissum;besti = i;bestj = j; printf(“起点
4、 = “+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 MaxSu
5、bSum(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 s
6、2=0; int rights=0; for(i=center+1;is2) s2=rights;sum=s1+s2; if(sum#include #include #define N 7 int 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;else b=ai; if(bsum) sum=b; return sum; int main() printf(“动态规划 最大子段和: %dn“, MaxSumDP(a, N);return 0; 0-1 背包问题动态规
7、划：背包问题动态规划： #include int c10100;/*对应每种情况的最大价值*/ int knapsack(int m,int n) int i,j,w10,p10;printf(“请输入每个物品的重量,价值：n“);for(i=1;ici-1j)/*如果本物品的价值加上背包剩下的空间能放的物 品的价值*/*大于上一次选择的最佳方案则更新 cij*/cij=pi+ci-1j-wi;elsecij=ci-1j; else cij=ci-1j; return(cnm); int main() int m,n;int i,j; printf(“请输入背包的承重量,物品的总个数：n“);
8、scanf(“%d,%d“,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;mn) if(bestpbestp)/搜索右子树 xi=0; Backtrack(i+1); class Object friend int Knapsack(i
9、nt 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;ic; coutn; p=new intn+1; w=new intn+1; p0=0; w0=0; coutpi; coutwi; coutk; 0-1 背包分支限界：背包分支限界： #include
10、#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; /最大队 H
11、igh 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 个物品的价值 coutbestp) 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(H
12、igh.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) i
13、ntj,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;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(in; goods=new structgoodinfo n+1;/ coutM; coutgoodsi.w; coutgoodsi.p; goodsi.p=goods
14、i.p/goodsi.w;/得出物品的效益，重 量比 cout to run agian“ to exit“j; 运动员最佳配对问题回溯法运动员最佳配对问题回溯法： #include#include /文件输入输出流 #include /I/O 流控制头文件 #include /vector 是一个能够存放任意类 型的动态数组， /能够增加和压缩数据 using namespace std;vector Re; /全局变量,Re 用来记录配对情况 vector P; vector 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()
