算法设计与分析实验报告
实验名称分治法实现归并排序算法评分
实验日期年月日指导教师
姓名专业班级学号
一.实验要求
1.了解用分治法求解的问题:当要求解一个输入规模为n,且n的取值相当大的问题时,如果问题可以分成k个不同子集合,得到k个不同的可独立求解的子问题,其中1 2.掌握分治法的一般控制流程。 DanC(p,q) global n,A[1:n]; integer m,p,q; // 1≤p≤q≤n if Small(p,q) then return G(p,q); else m=Divide(p,q); // p≤m return Combine(DanC(p,m),DanC(m+1,q)); endif end DanC 3.实现典型的分治算法的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 1.编程实现归并排序算法,程序中加入比较次数的计数功能,输出排序结果和比较次数。 2.输入10组相同的数据,验证排序结果和完成排序的比较次数。 3.与复杂性函数所计算的比较次数比较。 4.用表格列出比较结果。 5.给出文字分析。 三.程序算法 1. 归并排序算法 procedure MERGESORT(low,high) //A(low;high)是一个全程数组,它含 有high-low+1≥0个待排序的元素// integer low,high; if low then mid←, //求这个集合的分割点// call MERGESORT(low,mid) //将一个子集合排序// call MERGESORT(mid+1,high) //将另一个子集合排序 call MERGE(low,mid,high) //归并两个已排序的子集合// endif end MERGESORT 归并两个已排序的集合 procedure MERGE(low,mid,high) //A(low:high)是一个全程数组// //辅助数组B(low;high)// integer h,i,j,k; h←low;i←low;j←mid+1; while h≤mid and j≤high do //当两个集合都没取尽时// if A(h)≤A(j) then B(i) ←A(h);h←h+1 else B(i) ←A(j);j←j+1 endif i←i+1 repeat if h>mid then for k←j to high do //处理剩余的元素// B(i) ←A(k);i←i+1 repeat else for k←h to mid do B(i) ←A(k);i←i+1 repeat endif 将已归并的集合复制到A end MERGE 2. 快速排序算法 QuickSort(p,q) //将数组A[1:n]中的元素 A[p], A[p+1], , A[q]按不降次序排列, 并假定A[n+1]是一个确定的、且大于 A[1:n]中所有的数。// int p,q; global n, A[1:n]; if p j=Partition(p, q+1); // 划分后j成为划分元素的位置 QuickSort(p,j-1); QuickSort(j+1,q); endif end QuickSort procedure PARTITION(m,p) //退出过程时,p带着划分元素所在的下标位置。// integer m,p,i;global A(m:p-1) v←A(m);i←m //A(m)是划分元素// loop loop i←i+1 until A(i)≥v repeat //i由左向右移// loop p←p-1 until A(p)≤v repeat //p由右向左移// if i then call INTERCHANGE(A(i),A(p)) //A(i)和A(p)换位// else exit endif repeat A(m) ←A(p);A(p) ←v //划分元素在位置p// End PARTITION 四.程序代码 1.归并排序 #include #include #include #include #define M 11 typedef int KeyType; typedef int ElemType; struct rec{ KeyType key; ElemType data; }; typedef rec sqlist[M]; class guibing{ public: guibing(sqlist b) { for(int i=0;i r[i]=b[i]; } void output(sqlist r,int n) { for(int i=0;i cout< cout< } void xuanze(sqlist b,int m,int n) { int i,j,k; for(i=m;i { k=i; for(j=i;j if(b[k].key>b[j].key) k=j; if(k!=i) { rec temp=b[k]; b[k]=b[i]; b[i]=temp; } } } void merge(int l,int m,int h,sqlist r2) { xuanze(r,l,m); xuanze(r,m,h); output(r,M); int i,j,k; k=i=l; for(j=m;i { if(r[i].key<=r[j].key) { r2[k]=r[i]; i++; } else { r2[k]=r[j]; j++; } output(r2,M); } while(j { r2[k]=r[j]; j++; k++; } while(i<=m) { r2[k]=r[i]; i++; k++; } output(r2,M); } private: sqlist r; }; void main() { cout<<"guibingfa1运行结果:\n"; sqlist a,b; int i,j=0,k=M/2,n=M; srand(time(0)); for(i=0;i { a[i].key=rand()%80;b[i].key=0; } guibing gx(a); cout<<"排序前数组:\n"; gx.output(a,M); cout<<"数组排序过程演示:\n"; gx.merge(j,k,n,b); cout<<"排序后数组:\n"; gx.output(b,M); cin.get(); } 2.快速排序 #include #include #include #include #define MAXI 10 typedef int KeyType; typedef int ElemType; struct rec{ KeyType key; ElemType data; }; typedef rec sqlist[MAXI]; class kuaisu { public: kuaisu(sqlist a,int m):n(m) { for(int i=0;i } void quicksort(int s,int t) { int i; if(s i=part(s,t); quicksort(s,i-1); quicksort(i+1,t); } else return; } int part(int s,int t) { int i,j; rec p; i=s;j=t;p=b[s]; while(i { while(i b[i]=b[j]; while(i b[j]=b[i]; } b[i]=p; output(); return i; } void output() { for(int i=0;i cout< cout< } private: sqlist b; int n; }; void main() { cout<<"kuaisu1.cpp运行结果:\n"; sqlist a1; int i,n=MAXI,low=0,high=9; srand(time(0)); for(i=0;i a1[i].key=rand()%80; kuaisu px(a1,n); cout<<"数组排序过程演示:\n"; px.quicksort(low,high); cout<<"排序后数组:\n"; px.output(); cin.get(); } 五.程序调试中的问题 相同数字在比较的过程中会使用很多的时间,不能提高排序的速度 六.实验结果 1.归并排序 2.快速排序 《计算机算法设计与分析》习题及答案 一.选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是(A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是( A )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5.下列算法中通常以自底向上的方式求解最优解的是(B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是( C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是( D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是(A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9.下面不是分支界限法搜索方式的是(D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10.下列算法中通常以深度优先方式系统搜索问题解的是(D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。( B ) A、分治法 B、动态规划法 C、贪心法 D、回溯法 12.哈夫曼编码的贪心算法所需的计算时间为(B )。 A、O(n2n) B、O(nlogn) C、O(2n) D、O(n) 13.分支限界法解最大团问题时,活结点表的组织形式是(B )。 A、最小堆 B、最大堆 C、栈 D、数组 14.最长公共子序列算法利用的算法是(B)。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15.实现棋盘覆盖算法利用的算法是(A )。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是(C )。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素( D ) A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略(B ) A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. (D)是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由( B )设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时,活结点表的组织形式是( A )。 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 (1)源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } (2)运行界面 ①查找成功 ②查找失败 #include count++; }//满足条件,前移 if(count==0) break;//位置恰当,退出 } } }//insort插入排序函数 selsort(int a[30001]) { int i,j,temp; for(i=1;i<30000;i++) for(j=i+1;j<30001;j++) if(a[i]>a[j]) { temp=a[j]; a[j]=a[i]; a[i]=temp; } }//选择排序 bubsort(int a[30001]) { int i,j,temp; for(i=1;i<30001;i++) for(j=30000;j>i;j--) { if(a[j-1]>a[j]) { temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } }//冒泡排序 int partition(int a[30001],int low,int high) 算法实现题3-7 数字三角形问题 问题描述: 给定一个由n行数字组成的数字三角形,如图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。编程任务: 对于给定的由n行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入: 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n,1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出: 程序运行结束时,将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序: #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in,out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i 信息学部算法分析 上机报告 学号0901******** 姓名陈龙 指导老师秦明 时间2011.11.1~11.23 一.上机实验题目 实验1 比较归并排序和快速排序的区别。 实验2 利用贪心算法对背包问题进行求解。 二.算法设计思路 归并排序: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列,设定两个指针,最初位置分别为两个已经排序序列的起始位置,比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置,重复步骤直到某一指针达到序列尾,将另一序列剩下的所 有元素直接复制到合并序列尾。 快速排序: 设置两个变量I、J,排序开始的时候:I=0,J=N-1;以第一个数组元素作为关键数据,赋值给key,即key=A[0];从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key的值A[J],并与key交换;从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key的A[I],与key交换;重复第3、4、5步,直到I=J;(3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i,j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。) 背包问题: 用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 。可以压缩空间,f[v]=max{f[v],f[v-c[i]]+w[i]} 三. 源程序 归并排序 #include import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import java.util.Random; public class GuiBing { public static void main(String[] args) throws Exception { int datalength=1000000; GuiBing gui=new GuiBing(); int[] array1=gui.createArray(datalength); int[] array2=gui.createArray(datalength); Thread.sleep(20000); long startTime = System.nanoTime();//纳秒精度 long begin_freeMemory=Runtime.getRuntime().freeMemory(); int[] final_array=gui.guibing(array1,array2); boolean result=gui.testResult(final_array); long end_freeMemory=Runtime.getRuntime().freeMemory(); System.out.println("result===="+result); long estimatedTime = System.nanoTime() - startTime; System.out.println("elapsed time(纳秒精 度):"+estimatedTime/100000000.0); System.out.println("allocated memory:"+(begin_freeMemory-end_freeMemory)/1000.0+" KB"); Thread.sleep(20000); } /** * 显示数组的内容 * @param array */ private static void dispalyData(int[] array) { for(int i=0;i 华南农业大学期末考试试卷(A卷) 2008学年第一学期考试科目:算法分析与设计 考试类型:(闭卷)考试时间:120分钟 学号姓名年级专业 一、选择题(20分,每题2分) 1.下述表达不正确的是。 A.n2/2 + 2n的渐进表达式上界函数是O(2n) B.n2/2 + 2n的渐进表达式下界函数是Ω(2n) C.logn3的渐进表达式上界函数是O(logn) D.logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时,算法增长率最大的是。 A.5n B.20log2n C.2n2D.3nlog3n 3.T(n)表示当输入规模为n时的算法效率,以下算法效率最优的是。A.T(n)= T(n – 1)+1,T(1)=1 B.T(n)= 2n2 C.T(n)= T(n/2)+1,T(1)=1 D.T(n)= 3nlog2n 4.在棋盘覆盖问题中,对于2k×2k的特殊棋盘(有一个特殊方块),所需的L型骨 牌的个数是。 A.(4k– 1)/3 B.2k /3 C.4k D.2k 5.在寻找n个元素中第k小元素问题中,若使用快速排序算法思想,运用分治算法 对n个元素进行划分,应如何选择划分基准?下面答案解释最合理。A.随机选择一个元素作为划分基准 B.取子序列的第一个元素作为划分基准 C.用中位数的中位数方法寻找划分基准 D.以上皆可行。但不同方法,算法复杂度上界可能不同 6. 现在要盖一所邮局为这9个村庄服务,请问邮局应该盖在 才能使到邮局到这9个村庄的总距离和最短。 A .(4.5,0) B .(4.5,4.5) C .(5,5) D .(5,0) 7. n 个人拎着水桶在一个水龙头前面排队打水,水桶有大有小,水桶必须打满水, 水流恒定。如下 说法不正确? A .让水桶大的人先打水,可以使得每个人排队时间之和最小 B .让水桶小的人先打水,可以使得每个人排队时间之和最小 C .让水桶小的人先打水,在某个确定的时间t 内,可以让尽可能多的人打上水 D .若要在尽可能短的时间内,n 个人都打完水,按照什么顺序其实都一样 8. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题,分 别解决子问题,最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题 。 A .问题规模相同,问题性质相同 B .问题规模相同,问题性质不同 C .问题规模不同,问题性质相同 D .问题规模不同,问题性质不同 9. 对布线问题,以下 是不正确描述。 A .布线问题的解空间是一个图 B .可以对方格阵列四周设置围墙,即增设标记的附加方格的预处理,使得算法简化对边界的判定 C .采用广度优先的标号法找到从起点到终点的布线方案(这个方案如果存在的话)不一定是最短的 D .采用先入先出的队列作为活结点表,以终点b 为扩展结点或活结点队列为空作为算法结束条件 10. 对于含有n 个元素的子集树问题,最坏情况下其解空间的叶结点数目为 。 A .n! B .2n C .2n+1-1 D . ∑=n i i n 1 !/! 答案:DACAD CACCB 归并排序算法实现(迭代和递归)\递归实现归并排序的原理如下: 递归分割: 递归到达底部后排序返回: 最终实现排序: #include } while(i 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题)—1783Leonhard Euler,17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉(提 出并解决了该问题。七桥问题是这样描述的:北区一个人是否能在一次步行中穿越哥尼斯堡(现东区在叫加里宁格勒,在波罗的海南岸)城中全部岛区的七座桥后回到起点,且每座桥只经过一次,南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来,并判断此问题是否有解。 七桥问题属于一笔画问题。 输入:一个起点 输出:相同的点一次步行1,经过七座桥,且每次只经历过一次2,回到起点3,该问题无解:能一笔画的图形只有两类:一类是所有的点都是偶点。另一类是只有二个奇点的图形。)用的不是除法而是减最初的欧几里德算法2.在欧几里德提出的欧几里德算法中(即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 .设计算法求数组中相差最小的两个元素(称为最接近数)的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档. 精品文档 #include 1.一个算法就是一个有穷规则的集合,其中之规则规定了解决某一特殊类型问题的一系列运算,此外,算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分,衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时,应明确定义问题的解空间,问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________,先求解___________,然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题(50分) 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型:C 卷 考试时量:120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?,则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中,可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限,这个下限的阶越___________,结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 第一章作业 1.证明下列Ο、Ω和Θ的性质 1)f=Ο(g)当且仅当g=Ω(f) 证明:充分性。若f=Ο(g),则必然存在常数c1>0和n0,使得?n≥n0,有f≤c1*g(n)。由于c1≠0,故g(n) ≥ 1/ c1 *f(n),故g=Ω(f)。 必要性。同理,若g=Ω(f),则必然存在c2>0和n0,使得?n≥n0,有g(n) ≥ c2 *f(n).由于c2≠0,故f(n) ≤ 1/ c2*f(n),故f=Ο(g)。 2)若f=Θ(g)则g=Θ(f) 证明:若f=Θ(g),则必然存在常数c1>0,c2>0和n0,使得?n≥n0,有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0,c2≠0,f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n),同时,f(n) ≤c2*g(n),有g(n) ≥ 1/c2*f(n),即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n),故g=Θ(f)。 3)Ο(f+g)= Ο(max(f,g)),对于Ω和Θ同样成立。 证明:设F(n)= Ο(f+g),则存在c1>0,和n1,使得?n≥n1,有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以,F(n)=Ο(max(f,g)),即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4)log(n!)= Θ(nlogn)《计算机算法设计与分析》习题及答案
算法设计与分析:递归与分治法-实验报告
C (++)内部排序汇总(快速排序&冒泡排序&堆排序&选择排序&插入排序&归并排序)
算法设计与分析课后部分习题答案
排序算法比较实验报告
简单的归并排序算法例子
算法设计与分析课程期末试卷-A卷(自测 )
归并排序算法实现 (迭代和递归)
算法设计与分析第2版 王红梅 胡明 习题答案
算法设计与分析考试题及答案
算法设计与分析试卷及答案
算法设计与分析习题解答