太原理工大学算法设计实验报告

《太原理工大学算法设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验1分治法实验目的：1.掌握合并排序的基本思想2.掌握合并排序的实现方法3.学会分析算法的时间复杂度4.学会用分治法解决实际问题实验内容：分治法求几个大小不同整数的最大最小元。主要仪器设备：华硕笔记本、visualstdio2013上机调试修改源程序：#include#include#defineN5usingnamespacestd;voidgetData(inta[],intn){time_tt;srand((unsigned)time(&t));inti;fo

2、r(i=0;i

3、xminl)min=minl;}}voidmain(){intl[N],max,min;getData(l,N);for(inti=0;i

4、为元素比较，最坏情况下的时间为W(n)=O(nlogn)，在排序过程中需要使用与原序列相同长度的辅助数组temp，因此它所需的额外空间为O(n)。通过编写代码，我很好的掌握了分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题划分为彼此独立的、规模较小而结构相同的子问题。实验2贪心法实验目的：1.掌握贪心算法的基本思想2.掌握贪心算法的典型问题求解3.进一步多级调度的基本思想和算法设计方法4.学会用贪心法分析和解决实际问题实验内容：利用贪心法来解决背包问题，使得具有有限空间的背

5、包具有最大的价值。主要仪器设备：华硕笔记本、visualstdio2013上机调试修改源程序：#includeusingnamespacestd;voidDP(intc[50][50],intw[50],intv[50],intn,intC){for(inti=0;i<=C;i++){c[0][i]=0;}for(intt=1;t<=n;t++){c[t][0]=0;for(intj=1;j<=C;j++){if(w[t]<=j){if(v[t]+c[t-1][j-w[t]]>c[t

6、-1][j])c[t][j]=v[t]+c[t-1][j-w[t]];elsec[t][j]=c[t-1][j];}elsec[t][j]=c[t-1][j];}}}voidOutput(intc[50][50],intx[50],intw[50],intn,intC){for(intk=n;k>=2;k--){if(c[k][C]==c[k-1][C])x[k]=0;else{x[k]=1;C=C-w[k];}}x[1]=c[1][C]?1:0;}intmain(){intc[50][50];intw

7、[50],v[50],x[50],C,n;cout<<"输入物品总个数:";cin>>n;cout<<"输入背包的总容量：";cin>>C;cout<<"依次输入物品的重量："<>w[i];}cout<<"依次输入物品的价值："<>v[t];}DP(c,w,v,n,C);Output(c,x,w,n,C);cout<<"最优解为："<

8、+){cout<