《太原理工大学2018级算法实验报告》由会员分享，可在线阅读，更多相关《太原理工大学2018级算法实验报告（34页珍藏版）》请在金锄头文库上搜索。
1、HUYUANr UNIVERSITY OP TECHNOLOGY实验报告实践报告口课程名称： 算法设计与分析R实验、实践名称：实验、实践地点：专业班级：软件 班学号：学生姓名：指导教师：2020 年 月 日一、实验目的和要求1. 进一步熟悉C/C+语言的集成开发环境；2. 通过本实验加深对递归与分治策略的理解和运用二、实验内容和原理实验内容：Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元 素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆 可）。对于给定的正整数n,格雷码为满足如下条件的一个编码序列。（1）序列由2n个编码组成
2、，每个编码都是长度为n的二进制位串。（2）序列中无相同的编码。（3）序列中位置相邻的两个编码恰有一位不同。实验原理：动态规划（Dynamic Programming）算法思想：把待求解问题分解成若干个子问 题，先求解子问题，然后由这些子问题的解得到原问题的解，但动态规划求解过的子问题的 结果会被保留下来，丌像递归那样每个子问题的求解都要从头开始反复求解。动态规划求解问题 的关键在于获得各个阶段子问题的递推关系式：（1）分析原问题的最优解性质，刻画其结构特征；（2）递归定义最优值；（3）自底向上（由后向前）的方式计算最优值；（4）根据计算最优值时得到的信息，构造一个最优解。三、实验环境WinlO
3、Codeblocds gcc四、算法描述和程序代码1.2.3.4.5.6.7.&9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.#inelude #inelude #inelude #inelude using namespace std;class Solutionpublic:veetor grayCode(int n)veetor gray;if (n 1) gray.push_baek(0);return gray;int num =
4、 pow(2,n);int grayeoden;for (int i = 0; i = 0) eodei- = n%2; n/=2;void BitToGray(int *eode, int bit) int tempbit;temp0 = 0Aeode0;for (int i = 0; i bit-1; i+) tempi+1 = eodeiAeodei+1; for (int i = 0; i bit; i+) eodei = tempi;43.44.45.46.47.48.49.50.51.52.53.56.57.58.59.60.61.62.63.64.int GrayBitToInt
5、(int *code, int bit) int number = 0;for (int i = 0; i bit; i+) if (codei = 1) number += pow(2, bit-i-1);return number;54.;int main(int argc, const char * argv) vector test;Solution sl;test = slgrayCode(3);vector:iterator iter;for (iter = test.begin(); iter != test.end(); iter+) printf(%dn,*iter);65.
6、66.return 0;五、实验结果截图iJ F:cpp-fil胡耳法Ml块谊归与分治gra/binDebuggray.exenput n：3100101111no10110100rocess returned 0 (0x0) eecutian time : 2.025 s ress any key to continue六、算法时间分析和总结分治算法是很有用的算法，分治法的设计一般是递归的。通过编写代码，我很好的掌握了 分治法的步骤：划分；求解子问题；合并。对“分治策略”有了更深的体会，它将原问题 划分为彼此独立的、规模较小而结构相同的子问题。七、思考题(1) 递归的关键问题在哪里？先弄清楚
7、递归的顺序。在递归的实现中，往往需要假设后续的调用已经完成，在此基础之 上，才实现递归的逻辑。分析清楚递归体的逻辑，然后写出来考虑递归退出的边界条件。return语句该放在哪儿。(2) 递归与非递归之间如何实现程序的转换？递归问题非递归实现的基本思想：将原问题分解成若干结构与原问题相同，但规模较小的 子问题，并建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录递推关系 的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更 大子问题的解的过程；当得到原问题解时，递推过程便可结束了。(3) 分析二分査找和快速排序中使用的分治思想。二分搜索每次都要舍弃一半，从留下
8、的一半中寻找目标；而分治法把一个大问题分成两个 或多个小问题，递归地求这些小问题的解，最后再把它们小心谨慎的合并起来，并且要仔 细考虑合并时产生的新的情况。这当然没有错，但你也马上会从这里意识到两者的巨大联 系。就拿选取数组中第k个最小的数的算法来说，有一个版本便是从快速排序中修改而来: 划分后，舍弃掉不存在的区间，对剩余部分迭代，而快速排序是分治法的典型代表。快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot)，然后对数组进行分区 操作，使基准左边元素的值都不大于基准值，基准右边的元素值都不小于基准值，如此作为 基准的元素调整到排序后的正确位置。递归快速排序，将其他n-1个元
9、素也调整到排序后的 正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心 算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。HUYUANr UNIVERSITY OP TECHNOLOGY实验报告实践报告口课程名称： 算法设计与分析R实验、实践名称：实验、实践地点：专业班级：软件 班学号：学生姓名：指导教师：2020 年 月 日一、实验目的和要求1. 理解贪心算法的基本思想；2. 运用贪心算法解决实际问题，加深对贪心算法的理解和运用二、实验内容和原理实验内容：给定等待服务的客户集合A=1,2,n，预计对客户i的服务时长为ti0, T=(t1,
10、t2,tn), 客户i希望的服务完成时刻为di0, D=(d1,d2,dn)； 个调度f:A-N, f(i)为客户i的开始 时亥0。如果对客户i的服务在di之前结束，那么对客户i的服务没有延迟，即如果在di之后 结束，那么这个服务就被延迟了，延迟的时间等于该服务的实际完成时刻f(i)+ti减去预期结 束时刻di。一个调度f的最大延迟是所有客户延迟时长的最大值maxiWAf(i)+ti-di。附图2 所示是不同调度下的最大延迟。使用贪心策略找出一个调度使得最大延迟达到最小。实验原理：贪心算法的思想：(1) 贪心算法(GreedyApproach)能得到问题的最优解，要证明我们所做的第 一步选择一
11、定包含着一个最优解，即存在一个最优解的第一步是从我们的贪心选 择开始。(2) 在做出第一步贪心选择后，剩下的子问题应该是和原问题类似的规模较小 的子问题，为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。三、实验环境WinlOCodeblocds gcc八、算法描述和程序代码1./*2.最小延迟调度问题3.越前浩波4.*/5.6.#include7.using namespace std;#define N 1009.10./也可以用sort()11.struct Mission12.13.intnum;14.intlas t;15.intend;16.;17.18./19.void
12、QuickSort(Mission *mi,int f,int t)20.21.if(ft)22.23.int i=f-1,j=f;24.Mission m=mit;25.while(jt)26.27.if(mij.end=m.end)28.29.i+;30.Mission tmp=mii;31.mii=mij;32.mij=tmp;33.34.j+;35.36.Mission tmp1=mit;37.mit=mii+1;38.mii+1=tmp1;39.QuickSort(mi,f,i);40.QuickSort(mi,i+2,t);41.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.int main()int n;cou t请输入任务总数:n;Mission miN;/Mission0卜Missionn-1int start N+1;/排好序的任务的开始时间，s
