算法分析与设计实验报告.docx

安 徽 工 业 大 学专 业：班 级：姓 名：学 号： 实验一：回溯法完成0-1背包问题代码如下：#include stdafx.h#include#include#include#includeusing namespace std;templateclass Knappublic:friend void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator(Knap a)constif(fla.fl) return true;else return false;private:ty w; /重量ty v; /价值float fl; /单位重量的价值v/wint kk; /记录第几个物品int flag; /记录是否放入包中;templatevoid Sort(Knap *li,int n)int i,j,k; Knap minl;for(i=1;in;i+)minl=li0; k=0;for(j=1;j=n-i;j+)if(minllij)minl=lij; swap(lij,lik); k=j;namespace jie /命名空间int c=0,n=0;int *x=NULL;Knap *bag=NULL;int cp=0,cw=0;int bestp=0;using namespace jie;void Init()int i=0;coutendl;coutn; coutendl;coutc; coutendl;bag=new Knap n;x=new intn;cout请依次输入n个物品的重量W:endl;for(i=0;ibagi.w;coutendl;cout请依次输入n个物品的价值P:endl;for(i=0;ibagi.v;for(i=0;i=n) /到达叶节点bestp=cp; /更新最优价值return;if(cw+bagi.wbestp)/进入右子树bagi.flag=0; Backtrack(i+1);/计算当前节点处的上界float Bound(int i)int cleft = c-cw; /剩余容量float b = cp;while (in&bagi.w=cleft)/以物品单位重量价值递减序装入cleft-=bagi.w ;b+=bagi.v;i+;/装满背包if (in) b+=1.0*bagi.v/bagi.w * cleft;return b;void Knapsack() /计算最优解和变量值int L(0); /用L累计价值，初始价值设置为0for(int k=0;kn;k+)xbagk.kk=bagk.flag; /x=0表示未放入背包，x=1表示放入背包L+=bagk.flag*bagk.v; /价值累加coutendl;cout当前最优价值为:Lendl;cout变量值 x = ;for(int i=1;i=n;i+)coutxi-1;delete bag; bag=NULL;delete x; x=NULL;coutendl; getch();int main()coutendl;cout|*回溯法解0-1背包问题*|endl;Init();Backtrack(0);Knapsack();return 0;运行结果:实验二：分治法实现快速排序代码如下：#include #include #include void MergeSort(int *data,int x,int y,int *temp) int p,q,m,i=x; if (y-x1) m = x+(y-x)/2; p = x; q = m; MergeSort(data,x,m,temp); MergeSort(data,m,y,temp); while(pm|q=y|(pm&datapdataq) tempi+ = datap+; else tempi+ = dataq+; for(i=x;iy;i+) datai = tempi; void HoareSort(int *data,int x,int y) int p=x,q=y-1,temp; while(pp&dataq=datap) q-; if (qp) temp = datap,datap = dataq,dataq =temp; p+; while(qp&datap=dataq) p+; if (pq) temp = datap,datap = dataq,dataq =temp; q-; if (p=q) HoareSort(data,x,p); HoareSort(data,p+1,y); int main() int data100,i; int temp100; srand(time(NULL); for (i=0;i=100;i+) datai = rand()%100; for (i=0;i=100;i+) printf(%d ,datai); printf(n); HoareSort(data,0,10); for (i=0;i=100;i+) printf(%d ,datai); printf(n); 运行结果：实验三：递归法实现杨辉三角的输出代码如下：#includestdio.h#include stdlib.h#includeconio.hint Try(int n, int k)/递归函数 if (k = 0 | k = n)/在左右两侧返回1return 1; /递归出口return Try(n-1,k-1) + Try(n-1,k);/返回递归公式void print_spack(int t,int mode=0)/显示空格函数，这个是杨辉三角格式控制的关键if (mode!=0)/当mode不等于0时，代表要输出每行前面的空格，直接循环输出t次空格，并退出函数for (int i = 0; i t; i+)printf( );return ;/直接返回Aif(t9&t99&t999&t10000)printf( );/如，我在此设计的每行开头部分减少3个空格，那么t9&t9999&t10)/当行数大于10行时，应该将窗口尺寸该大到150,以保证杨辉三角正常显示，这是一条dos命令，使用system函数推送执行的system(mode con cols=150 lines=150);for (int n=0; nrow; n+)print_spack(3*(row-n),1);/后面第二个参数传了一个非零参数，是因为告诉函数要直接输出3*(row-n)个空格for (int m=0; m=n; m+)/输出中间元素printf(%d,t = Try(n,m);/递归调用获得当前第n行，第m个元素的值，输出同时赋值给tprint_spack(t);/这儿没有传第二个参数是告诉函数，需要判断t参数的位数来决定输出的空格printf(n);/每行结束后打印