算法分析与设计实验报告三——动态规划算法
一、实验目的
掌握动态规划方法贪心算法思想掌握最优子结构原理了解动态规划一般问题二、实验内容
编写一个简单的程序，解决0-1背包问题。设N=5，C=10，w={2，2，6，5，4},v={6,3,5,4,6}合唱队形安排问题【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，则他们的身高满足T1…>TK(1s[1][i]=0;}for(inti=boundary;i//防止溢出情况出现intbound=min(weight[i],C);//当0value[i];}knapSack(situation,weight,value,C,n);for(inti=1;iif(j==C)coutif(i!=1){if(situation[i][tempC]>situation[i-1][tempC]){res[i]=1;tempC-=weight[i];}}else{if(situation[i][tempC]>0){res[i]=1;}}}coutcoutintmax=0;intindex=-1;for(intj=0;jmax=up[j];index=j;}}if(index==-1)up[i]=1;else{up[i]=up[index]+1;}}}//从右向左递归LISvoidmaxDown(inta[],intdown[],intn){for(inti=n-1;i>=0;i--){intmax=0;intindex=-1;for(intj=n-1;j>i;j--){if(a[i]>a[j]&&down[j]>max){max=down[j];index=j;}}if(index==-1)down[i]=1;else{down[i]=down[index]+1;}}}//向左向右求得结果voidchorus(intheight[],intup[],intdown[],intn){maxUp(height,up,n);maxDown(height,down,n);}intmain(){intn;coutn;intheight[n];intup[n]={0};intdown[n]={0};coutintlen=up[i]+down[i]-1;if(max算法分析与设计实验报告——二分搜索算法的实现
算法分析与设计实验报告——二分搜索算法的实现目录：算法分析与设计实验报告——二分搜索算法的实现一、实验目的二、实验要求三、实验原理四、实验过程(步骤)五、运行结果六、实验分析与讨论七、实验特色与心得附件一实验过程(步骤)附件二运行结果一、实验目的掌握分治法的基本思想，建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。
二、实验要求用c++语言实现二分搜索算法，分析时间复杂性。实现二分搜索的递归与非递归程序，并进行跟踪分析其执行过程，体会两者的执行效率。
三、实验原理折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(logn)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。
四、实验过程(步骤)见附件一实验步骤、特点重要源代码（流操作的部分要醒目的提示并注释）
五、运行结果见附件二
六、实验分析与讨论编写程序时由于传参错误，导致结果不能输出，一直输出没有找到，然后更改了参数之后，程序输出就正确了。还有数组的大小计算不能用strlen函数，要用sizeof（a）/sizeof（a[0]）。遇到的问题，及解决方案
七、实验特色与心得这是我第一次实质上应用分治法编写程序。二分搜索算法能够实现O（logn）的时间复杂度，比一般的顺序搜索快了不少。这次实验也加深了我对分治法的理解。
附件一实验过程(步骤)二分搜索的递归程序：
#includeusingnamespacestd;templateintBinarySearch2(Typea[],constType&x,intleft,intright)//递归算法{intmiddle=(left+right)/2;if(x==a[middle])//查找成功，返回下标{returnmiddle;}if(left>=right){return-1;}elseif(x>a[middle])//如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x{returnBinarySearch2(a,x,middle+1,right);}elseif(xintx,len,b1,b2;inta[]={1,2,3,4,5,6,7,8,9,10};//初始化a数组len=sizeof(a)/sizeof(a[0]);//计算a数组的长度coutx;b2=BinarySearch2(a,x,0,len);if(b2==-1)coutintmiddle=(left+right)/2;if(x==a[middle])//查找成功，返回下标returnmiddle;if(x>a[middle])//如果x>a[n/2]，则我们只要在数组a的右半部继续搜索xleft=middle+1;else//如果x1,2,3,4,5,6,7,8,9,10};//初始化a数组len=sizeof(a)/sizeof(a[0]);//计算a数组的长度coutx;b1=BinarySearch1(a,x,len);if(b1==-1)cout