实验一分治与递归算法的应用一、实验目的1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。

2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。

3．学会利用分治算法解决实际问题。

二 . 实验内容金块问题老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。

假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。

并对自己的程序进行复杂性分析。

三.问题分析:一般思路：假设袋中有n 个金块。

可以用函数M a x（程序1 - 3 1）通过n-1次比较找到最重的金块。

找到最重的金块后，可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。

这样，比较的总次数为2n-3。

分治法：当n很小时，比如说，n≤2，识别出最重和最轻的金块，一次比较就足够了。

当n 较大时（n＞2），第一步，把这袋金块平分成两个小袋A和B。

第二步，分别找出在A和B中最重和最轻的金块。

设A中最重和最轻的金块分别为HA 与LA，以此类推，B中最重和最轻的金块分别为HB 和LB。

第三步，通过比较HA 和HB，可以找到所有金块中最重的；通过比较LA 和LB，可以找到所有金块中最轻的。

在第二步中，若n＞2，则递归地应用分而治之方法程序设计据上述步骤，可以得出程序1 4 - 1的非递归代码。

该程序用于寻找到数组w [ 0 : n - 1 ]中的最小数和最大数，若n < 1，则程序返回f a l s e，否则返回t r u e。

当n≥1时，程序1 4 - 1给M i n和M a x置初值以使w [ M i n ]是最小的重量，w [ M a x ]为最大的重量。

首先处理n≤1的情况。

若n>1且为奇数，第一个重量w [ 0 ]将成为最小值和最大值的候选值，因此将有偶,数个重量值w [ 1 : n - 1 ]参与f o r循环。

当n 是偶数时，首先将两个重量值放在for 循环外进行比较，较小和较大的重量值分别置为Min和Max，因此也有偶数个重量值w[2:n-1]参与for循环。

在for 循环中，外层if 通过比较确定( w [ i ] , w [ i + 1 ] )中的较大和较小者。

此工作与前面提到的分而治之算法步骤中的2) 相对应，而内层的i f负责找出较小重量值和较大重量值中的最小值和最大值，这个工作对应于3 )。

for 循环将每一对重量值中较小值和较大值分别与当前的最小值w [ M i n ]和最大值w [ M a x ]进行比较，根据比较结果来修改M i n和M a x（如果必要）。

源程序#include<iostream>#include<string.h>#include<algorithm>using namespace std; 0float max(float g1,float g2)//比较找大值{return(g1>g2?g1:g2);}float min(float g1,float g2)//比较找小值{return(g1<g2?g1:g2);}float Search_Max(float g[],int left,int right)//用二分法递归找最大值{if(left==right) //当只有一个数时，直接返回该值{float max;max=g[right];return max;}if(right-left==1){float LM,RM;LM=g[left];RM=g[right];return(max(LM,RM));}if(right-left>1){float LM,RM;int mid=(left+right)/2;//取中点LM=Search_Max(g,left,mid);RM=Search_Max(g,mid,right);//左半部分，右半部分的最大值比较找最大return(max(LM,RM));}}float Search_Min(float g[],int left,int right)//用二分法递归找最小值{if(left==right){float min;min=g[right];return min;}if(right-left==1){float LM,RM;LM=g[left];RM=g[right];return(min(LM,RM));}if(right-left>1){float LM,RM;int mid=(left+right)/2;LM=Search_Min(g,left,mid);RM=Search_Min(g,mid,right);//左半部分，右半部分的最小值比较找最小return(min(LM,RM));}}int main(){float gold[100];int n;cout<<"请输入金块的数目: ";cin>>n;cout<<"请输入各金块的重量: ";for(int i=0;i<n;i++){cin>>gold[i];}cout<<"最重的金块: "<<Search_Max(gold,0,n-1)<<endl;cout<<"最轻的金块: "<<Search_Min(gold,0,n-1)<<endl;return 0;}实验结果输入金块数量：5得到最轻和最重的金块实验总结通过这次实验，我深刻了解到分治法的实用性，有效性。

当遇到规模较大的问题，用我们以前学过的方法就太不明智了。

将原问题划分成若干个较小规模的子问题，再继续求解，划分，能够简化问题。

递归法，是一个很重要的方法，具有结构自相似的特性，刚开始学习编写的时候遇到了很多问题，不知道要找边界，不知道如何划分问题。

关于这次算法，我觉得，类的部分还是一个难点，也就是说，不会将问题分解成抽象的概念，这也是我以后需要重点学习的地方。

实验二动态规划算法的应用一、实验目的1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。

2．熟练掌握分阶段的和递推的最优子结构分析方法。

3．学会利用动态规划算法解决实际问题。

二、实验内容最长单调递增子序列问题设计一个O（n2）复杂度的算法，找出由n个数组成的序列的最长单调递增子序列。

思路分析1、把a1,a2,...,an排序，假设得到a'1,a'2,...,a'n，然后求a的a'的最长公共子串，这样总的时间复杂度为o(nlg(n))+o(n^2)=o(n^2)；2、动态规划的思路：另设一辅助数组b,定义b[n]表示以a[n]结尾的最长递增子序列的长度，则状态转移方程如下：b[k]=max(max(b[j]|a[j]<a[k],j<k)+1,1);（见状态转移方程）状态转移方程设辅助数组b[]，定义b[n]表示以a[n]结尾的最长递增子序列的长度，状态转移方程表示为：b[k] = max ( max（b[j]|a[j]<a[k], j<k）+1, 1 )其中0<=k<=n-1，在a[k]前面找到满足a[j]<a[k]的最大b[j]，a[k]作为后继，得到a[k]的最长递增子序列的长度，如果a[k]前面没有更小的a[j]，此时a[k]形成序列，长度为1，继续计算，最后整个序列的最长递增子序列：max(b[k] |0<=k<=n-1)，此时时间复杂度仍为O(n^2)。

另外定义一数组c，c中元素满足c[b[k]]=a[k]，即当递增子序列的长度为b[k]时子序列的末尾元素为c[b[k]]=a[k]。

实现代码第一种思路：#include<stdio.h> //时间复杂度O(n^2)int main(){int i,j,k,n,a[100],b[100],c[100],max;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)scanf("%d",&a[i]);b[0]=1; //初始化，以a[0]结尾的最长递增子序列长度为1c[0]=a[0]; k=1;for(i=1;i<n;i++){b[i]=1; //b[i]最小值为1for(j=0;j<i;j++)if(a[i]>a[j] && b[j]+1>b[i]){b[i]=b[i]+1;}}for(max=i=0;i<n;i++) //求出整个序列的最长递增子序列的长度if(b[i]>max)max=b[i];printf("%d\n",max);}return 0;}运行结果实验总结通过实现动态规划的这个题目，对动态规划算法有了进一步的了解。

先分析问题，判断是否具有最优子结果和重叠字问题的性质实验三贪心算法的应用一、实验目的1．掌握贪心算法的基本概念和两个基本要素2．熟练掌握贪心算法解决问题的基本步骤。

3．学会利用贪心算法解决实际问题。

二、实验内容题目三：程序存储问题设有n个程序{1,2,3,…,n}要存放在长度为L的磁带上。

程序i 存放在磁带上的长度是l i,1≤i≤n。

要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。

输入数据中，第一行是2个正整数，分别表示程序文件个数和磁带长度L。

接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。

输出为最多可以存储的程序个数。

输入数据示例6 502 3 13 8 80 20输出数据5三. 题目分析：题目要求计算给定长度的磁带最多可存储的程序个数，先对程序的长度从小到大排序，再采用贪心算法求解。

3、算法设计：a. 定义数组a[n]存储n个程序的长度，s为磁带的长度；b. 调用库函数sort（a，a+n）对程序的长度从小到大排序；c. 函数most（）计算磁带最多可存储的程序数，采用while 循环依次对排序后的程序长度进行累加，用i计算程序个数，用sum计算程序累加长度（初始i=0，sum=0）：① sum=sum+a[i]；②若sum<=s，i加1，否则i为所求；③ i=n时循环结束；d. 若while循环结束时仍有sum<=s，则n为所求。

源程序：#include<iostream>using namespace std；#include<algorithm>int a[1000000]；int most（int *a，int n，int s）{int i=0，sum=0；while（i<n）{sum=a[i]+sum；if（sum<=s）i++；else return i；}return n；}main（）{int i，n，s；scanf（"%d %d\n"，&n，&s）；for（i=0；i<n；i++）scanf（"%d"，&a[i]）；sort（a，a+n）；printf（"%d"，most（a，n，s））；return 0；}实验总结此次实验让我对贪心算法的思想有了初步的了解，并且学会了用贪心算法解决一些实际问题。