logo资料库

算法分析与设计实验报告（贪心法，动态规划法）.docx

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.09M 资料格式：docx 举报 版权申诉
第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
资料共23页，剩余部分请下载后查看
    算法设计与分析
    实验报告
    实验一：递归与分治
    实验二：贪心算法
    实验三：动态规划
    算法设计与分析 实验报告
    实验一：递归与分治 一．实验目的 1.理解递归算法的思想和递归程序的执行过程，并能熟练编写递归程序。 2.掌握分治算法的思想，对给定的问题能设计出分治算法予以解决。 二．实验内容 编程实现讲过的例题：二分搜索、合并排序、快速排序。 对本实验中的问题，设计出算法并编程实现。 1.二分查找 在对线性表的操作中，经常需要查找某一个元素在线性表中的位置。 此问题的输入是待查元素 x 和线性表 L，输出为 x 在 L 中的位置或者 x 不 在 L 中的信息。表 L 中的元素必须是有序的。 2.合并排序 合并排序法是将两个或两个以上有序表合并成一个新的有序表，即把 待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序 列合并为整体有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。合并排序是分治法的一个典型例子。 3.快速排序 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的 所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分 数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 三．实验源代码和实验结果 1. 二分查找 #include using namespace std; //创建一个顺序表 int sql[100]; //顺序表中的数据按照升序排列。 int sx_sql(int n);
    int sx_sql(int n) { cout<<"请按照升序输入数据："<>sql[i]; cout<<"输入的数据为："<sql[middle]) left=middle+1;//去右边的区间查找 else right=middle-1;//取左边的区间查找 } cout<<"元素不在表中"<>n; sx_sql(n); cout<>x; s=Binarysearch(x,n); if(s!=-1) cout<<"查找成功，在表中的位置为:"<
    2. 合并排序 #include using namespace std; //两路归并排序 int array[100];//待排序的序列 int temparray[100];//临时数组 void merge(int a[],int b[],int left,int right,int middle); void sort(int a[],int b[],int left,int right) { if(left
    int index2=middle+1;//右边区间起始位置 int i=left; while(index1<=middle&&index2<=right){//将两边区间中较小者 优先放入表中 if(b[index1]>array[i]; sort(array,temparray,0,10); for(int i=0;i<=10;i++) cout<<" "<
    3.快速排序 #include using namespace std; int quicksort_partition(int a[],int low,int high) { int k,i=low; int x=a[low]; for(k=low+1;k<=high;k++) { if(a[k]<=x){ i=i+1; if(i!=k) swap(a[i],a[k]); } } swap(a[low],a[i]); return i; } void quicksort(int a[],int left,int right)
    { int k; if(left>sql[i]; quicksort(sql,0,9); for(int j=0;j<=9;j++) cout<<" "<
    四．实验总结 递归和分治是算法设计中极其重要的两种方法。递归是一种自身调用自 身的算法。在解决许多复杂问题时，使用递归算法，往往能使问题变得简单 易懂，有规律性，从而得到解决。分治则是在处理一个情况较多的复杂问题 时，根据问题具有的某些特性，并从这些特性出发，将问题划分为多个子问 题来求解，缩小了问题的规模，逐个解决，从而解决整个问题。 其中，合并排序是运用分治方法的一个典型例子。先将 n 元素待排序序 列化为 n/2 对，用 merge 算法，将相邻两对序列合并成有序序列，结合为 n/4 对，这 n/4 对在以上述方法合并，直至将所有序列合并为一个有序序列， 完成排序。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料