应用数学学院信息安全专业班学号姓名
实验题目递归与分治法
综合实验评分表
实验报告
一、实验目的与要求
1.掌握递归算法的设计思想
2.掌握分治法设计算法的一般过程
3.理解并掌握算法渐近时间复杂度的分析方法
二、实验内容
1、折半查找的递归算法
(1)源程序代码
#include
#include
using namespace std;
int bin_search(int key[],int low, int high,int k)
{
int mid;
if(low>high)
return -1;
else{
mid = (low+high) / 2;
if(key[mid]==k)
return mid;
if(k>key[mid])
return bin_search(key,mid+1,high,k);
else
return bin_search(key,low,mid-1,k);
}
}
int main()
{
int n , i , addr;
int A[10] = {2,3,5,7,8,10,12,15,19,21};
cout << "在下面的10个整数中进行查找" << endl;
for(i=0;i<10;i++){
cout << A[i] << " " ;
}
cout << endl << endl << "请输入一个要查找的整数" << endl;
cin >> n;
addr = bin_search(A,0,9,n);
if(-1 != addr)
cout << endl << n << "是上述整数中的第" << addr << "个数" << endl;
else
cout << endl << n << "不在上述的整数中" << endl << endl;
getchar();
return 0;
}
(2)运行界面
①查找成功
②查找失败
2、用分治法求x的n次方,要求时间复杂度为O(lgn)
(1)源程序代码
#include
#include
using namespace std;
int Pow(int x, int n)
{
if (n == 1)
return x;
else if (n > 1)
{
int s;
int m = n / 2;
s = Pow (x, m);
if (n % 2 == 0)
return (s * s);
else
return (s * s * x);
}
}
int main()
{
int x, n;
cout << "你将进行x的n次方计算" << endl << endl;
cout << "请输入x:" << endl;
cin >> x;
cout << "请输入n:" << endl;
cin >> n;
cout << endl << "计算结果:" << Pow(x, n) << endl << endl;
return 0;
}
(2)运行界面
3、自然合并排序算法
(1)源程序代码
#include "StdAfx.h"
#include
using namespace std;
const int SIZE = 100;
int arr[SIZE];
int rec[SIZE];
void merge(int fir,int end,int mid);
int pass(int n);
void mergeSort(int n);
void mergeSort(int n){
int num=pass(n);
while(num!=2){
for(int i=0;i merge(rec[i],rec[i+2]-1,rec[i+1]-1); num=pass(n); } } void merge(int fir,int end,int mid){ int tempArr[SIZE]; int fir1=fir,fir2=mid+1; for(int i=fir;i<=end;i++){ if(fir1>mid) tempArr[i]=arr[fir2++]; else if(fir2>end) tempArr[i]=arr[fir1++]; else if(arr[fir1]>arr[fir2]) tempArr[i]=arr[fir2++]; else tempArr[i]=arr[fir1++]; } for(int i=fir;i<=end;i++) arr[i]=tempArr[i]; } int pass(int n){ int num=0; int biger=arr[0]; rec[num++]=0; for(int i=1;i if(arr[i]>=biger)biger=arr[i]; else { rec[num++]=i; biger=arr[i]; } } rec[num++]=n; return num; } int main(){ int n; cout<<"请输入需要排序的整数个数:"< while(cin>>n){ for(int i=0;i cout<<"请输入整数:"< cin>>arr[i]; } mergeSort(n); cout<<"排序结果为:"< for(int i=0;i cout< } cout< cout<<"请输入需要排序的整数个数:"< } return 0; } (2)运行界面 三、问题与讨论 问题:分治法能解决的问题一般具有什么特征? 解答:任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小越容易直接求解,解题所需的计算时间也越少。分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。 分治法所能解决的问题一般具有以下几个特征: (1)该问题的规模缩小到一定的程度就可以容易地解决; (2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质; (3)利用该问题分解出的子问题的解可以合并为该问题的解; (4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。 四、总结 这次实验的内容都很有代表性,通过上机操作实践与对问题的思考,让我更深层地领悟到了分治法的效率。 分治法的基本思路并不难理解,就是将一个难以直接解决的大问题,分割成一些规模较小的相同问题,在计算机的处理当中,问题的规模越小就越容易直接求解,解题所需的计算时间也越少,所以分治法在合适的问题中是能大大提高效率的。 我非常喜欢上机课,因为课上听的理论内容也许觉得懂了,但课后没有一些实践,于是对一些难点实际上掌握得并不好。刚看到课题的实验内容,其实基本思路和条理还是会有的,因为会有一定的知识基础,能够想到一些相关的解决思路,但有思路不一定就能够解决问题,真正动手去做的时候才发现会出现更多的实际问题。解决遇到的问题就是我们学习的过程,同时也能让我注意到一些以前不曾在意的问题。像我是使用C++来写代码的,其中我这次实验时我就发现,“#include “StdAfx.h””一定要放在首行,不然就会出错;调试程序时如果出现“Cannot find or open the PDB file”的提示而导致程序不能正常运行时,按Ctrl+F5来直接执行就能正常运行了,因为这跟系统环境有关系;等等。 每次的实践都能有一些发现,不管是大是小,积累多了就成了自己丰富的经验。所以我还是挺喜欢实验课的,能进行一些实用性很强的实践,更深层地领悟到书本的理论知识,同时还能享受把bug逐个解决的快感。 《计算机算法设计与分析》习题及答案 一.选择题 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、熟悉C/C++语言的集成开发环境; 2、通过本实验加深对递归过程的理解 二、实验内容: 掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。 三、实验题 任意输入一个整数,输出结果能够用递归方法实现整数的划分。 四、算法思想 对于数据n,递归计算最大加数等于x 的划分个数+最大加数不大于x-1的划分个数。最大加数x 从n 开始,逐步变小为n-1, (1) 考虑增加一个自变量:对于数据n,最大加数n1不大于m 的划分个数记作),(m n q 。则有: ???????>>=<==-+--+=1 1,1),()1,()1,(1),(1),(m n m n m n m n m m n q m n q n n q n n q m n q 五、代码实现 #include "stdafx.h" #include return 0; } int q(intn,int m){ if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 (1)源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } (2)运行界面 ①查找成功 ②查找失败 算法实现题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 本科实验报告 课程名称:算法设计与分析 实验项目:递归与分治算法 实验地点:计算机系实验楼110 专业班级:物联网1601 学号:2016002105 学生姓名:俞梦真 指导教师:郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1.进一步熟悉C/C++语言的集成开发环境; 2.通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治(Divide-and-Conquer)的思想:一个规模为n的复杂问题的求解,可以划分成若干个规模小于n的子问题,再将子问题的解合并成原问题的解。 需要注意的是,分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同,可用相同的求解方法。最后,当子问题规模足够小时,可以直接求解,然后逆求原问题的解。 1.4 实验题目 1.上机题目:格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素,每个元素都是长度为n的串,相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码(分治、减治、变治皆可)。 对于给定的正整数n,格雷码为满足如下条件的一个编码序列。 (1)序列由2n个编码组成,每个编码都是长度为n的二进制位串。 (2)序列中无相同的编码。 (3)序列中位置相邻的两个编码恰有一位不同。 2.设计思想: 根据格雷码的性质,找到他的规律,可发现,1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0,N-2为倒转再前面再加1。 3.代码设计: 算法分析与设计习题集整理 第一章算法引论 一、填空题: 1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征:输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣:时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为: O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法:自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求:正确性 和 可读性。 8、计算下面算法的时间复杂度记为: O(n 2) 。 for (i =1;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 n = 3 Backtrack(1) t=1 for i = 1 to 3 i=1 Swap(x[1], x[1]) t=1时,x[1]取了x[1]=1 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时,x[2]取了x[2]=2 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时,x[3]取了x[3]=3 Backtrack(4) ---> t = 4 > 3 输出(1,2,3) swap(x[3],x[3]) swap(x[2],x[2]) i=3 swap(x[2],x[3]) x[2]=3, x[3]=2 t=2时,x[2]取了3 Backtrack(3) -------> t=3 for i = 3 to 3 swap(x[3],x[3]) t=2时,x[3]取了x[3]=2 Backtrack(4) ---> t = 4 > 3 输出(1,3,2) swap(x[3],x[3]) swap(x[2],x[3]) x[2]=2, x[3]=3 Swap(x[1], x[1]) i=2 Swap(x[1], x[2]) x[1]=2, x[2]=1 t=1时,x[1]取了2 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时,x[2]取了x[2]=1 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时,x[3]取了x[3]=3 Backtrack(4) ---> 精品文档习题胡明-版)-王红梅-算法设计与分析(第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、算法的特征 答:1)算法有零个或多个输入;2)算法有一个或多个输出; 3)确定性;4)有穷性 3、算法的描述方法有几种 答:自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答:(1) 算法实现所耗费的时间(时间复杂度); (2) 算法实现所所耗费的存储空间(空间复杂度); (3) 算法应易于理解,易于编码,易于调试等等。 5、时间复杂度、空间复杂度定义 答:指的是算法在运行过程中所需要的资源(时间、空间)多少。 6、时间复杂度计算: {i=1; while(i<=n) i=i*2; } 答:语句①执行次数1次, 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间: T(n)= 2log2n +1 时间复杂度:记为O(log2n) ; 7.递归算法的特点 答:①每个递归函数都必须有非递归定义的初值;否则,递归函数无法计算;(递归终止条件) ②递归中用较小自变量函数值来表达较大自变量函数值;(递归方程式) 8、算法设计中常用的算法设计策略 答:①蛮力法;②倒推法;③循环与递归;④分治法; ⑤动态规划法;⑥贪心法;⑦回溯法;⑧分治限界法 9、设计算法: 递归法:汉诺塔问题兔子序列(上楼梯问题) 整数划分问题 蛮力法:百鸡百钱问题 倒推法:穿越沙漠问题 答:算法如下: (1) 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列(fibonaci 数列 ) 递归实现: Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述:将正整数n 表示成一系列正整数之和,n=n1+n1+n3+… 将最大加数不大于m 的划分个数,记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系: 递归算法: Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 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算法的思想。 《算法设计与分析》实验报告 分治策略 姓名:XXX 专业班级:XXX 学号:XXX 指导教师:XXX 完成日期:XXX 一、试验名称:分治策略 (1)写出源程序,并编译运行 (2)详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序,实现归并排序。 (2)编写一段程序,实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序,实现归并排序。 将待排序元素分成大小大致相同的2个子集合,分别对2个子集合进行 排序,最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序,实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有 数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数 据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略,将所有的选手分为两组,n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割, 直到只剩下2个选手时,比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序,实现归并排序。 #include 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型: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)《计算机算法设计与分析》习题及答案
实验报告 分治与递归
算法设计与分析:递归与分治法-实验报告
算法设计与分析课后部分习题答案
算法设计与分析实验报告
算法分析与设计习题集整理
算法设计与分析课程期末试卷-A卷(自测 )
算法设计与分析排列树递归推算
算法设计与分析第2版 王红梅 胡明 习题答案
算法设计与分析习题
算法设计与分析考试题及答案
算法分析实验报告--分治策略
算法设计与分析试卷及答案
算法设计与分析习题解答