电子科技大学计算机学院实验中心实验报告实验一一、实验名称：分治和动态规划算法实现二、实验学时：4三、实验内容和目的：希望通过本次试验，加深对分治算法原理及实现过程的理解(1)二分法求方程近似解：求方程f(x)=x^3+x^2-1=0在[0,1]上的近似解，精确度为0.01。(2)给定一个顺序表，编写一个求出其最大值和最小值的分治算法。分析：由于顺序表的结构没有给出，作为演示分治法这里从简顺序表取一整形数组数组大小由用户定义，数据随机生成。我们知道如果数组大小为1则可以直接给出结果，如果大小为2则一次比较即可得出结果，于是我们找到求解该问题的子问题即:数组大小<=2。到此我们就可以进行分治运算了，只要求解的问题数组长度比2大就继续分治，否则求解子问题的解并更新全局解以下是代码。四、实验原理：分治算法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并到原问题的解。在递归算法中，原问题和子问题的区别关键在于尺寸的不同，实际上解决的是同样的问题，对于分解了的子问题分别求解，也可以在此分割，如此递归下去。最后，自底向上逐步求出原问题的解。五、实验器材（设备、元器件）硬件环境：i5-2450M双核处理器，2.5GHz，NVIDIAGT630M独立显卡芯片，1GB独立显存，2GBDDR3内存，500GB硬盘空间软件环境：Windows7操作系统及以上，MicrosoftVisualStudio2010六、实验步骤：（一）给定一个顺序表，编写一个求出其最大值和最小值的分治算法。编写实验源代码如下：/*给定一个顺序表编写一个求出其最大值和最小值的分治算法*/#include"stdafx.h"#include#include#include#include#defineLen1000000#defineMIN(a,b)((a)>(b)?(b):(a))#defineMAX(a,b)((a)>(b)?(a):(b))inta[Len],n;intGetMin(intl,intr){if(l==r)returna[l];intmid=(l+r)>>1;returnMIN(GetMin(l,mid),GetMin(mid+1,r));}intGetMax(intl,intr){if(l==r)returna[l];intmid=(l+r)>>1;returnMAX(GetMax(l,mid),GetMax(mid+1,r));}intmain(){inti;printf("请输入您顺序表中元素的个数：");scanf("%d",&n);printf("请依次输入您顺序表中的元素：");for(i=0;i#include#include#includedoublefunction(doublex){returnx*x*x+x*x-1;}intmain(){doublel=0,r=1.0,mid;while(r-l>0.01){mid=(r+l)/2;if(function(mid)>=0)r=mid;elsel=mid;}doubleans=r;printf("%.2f\n",ans);system("pause");}运行结果如下：七、实验数据及结果分析：程序的代码、数据、截图都放在实验步骤中具体体现，我们不妨来验证一下方程的解是否正确，将0.76带入函数中计算x^3+x^2-1中，得到结果为0.016576，这个结果在精度范围要求内是可以接受的，所以，我们可以说买这个程序得到的结果是可以接受的。八、实验结论、心得体会和改进建议：在本实验中，利用递归算法，很好地解决了求解序列表中最大、最小值以及求解方程的解的功能，当然递归算法虽然实现起来较为简单，但是效率上可能会造成一些资源的浪费，可能选用其他更高效的算法来解决这些问题。电子科技大学计算机学院实验中心实验报告实验二一、实验名称：动态规划算法实现二、实验学时：4三、实验内容和目的：加深对动态规划算法原理及实现过程的理解理解动态规划算法的原理，用动态规划算法实现最长公共子序列问题。四、实验原理：在动态规划算法中，对分治算法的效率进行了改善，同时能够解决更多种类的问题，一般适用于解最优化的问题。动态规划算法一般分为四...
