算法设计与分析复习资料1
一 1.循环赛日程表问题的相关叙述。 2.算法运行时所需要占用的存储空间有? 3.动态规划法的求解步骤 4.解空间树是排列树的问题有。 5.分治法的步骤 6.就会场安排问题,贪心法的最佳贪心策略 7.快速排序法基准元素的选取方法 8.满足满m叉树的问题有? 9.分支限界法的解题步骤 10.事前分析法相关的影响因素有 11.用分治法求解的问题一般需要具备一些特征,主要有? 二 1.给定一个有向带权图G=(V,E),其中每条边的权是一个非负实数,另外,给定V中的一个顶点,称为源点。现在要计算从源点到所有其它各个顶点的最短路径长度,这里的路径长度是指路径上经过的所有边上的权值之和,这个问题通常称为单源最短路径问题。 2.采用回溯法可以求解0-1背包问题,其解空间的形式为:(x1,x2,…,xn)或n 元组。 3.当所给的问题是从n个元素的排列中找出满足某种性质的一个排列时,相应的解空间树称为排列树。 4.一个正在生成孩子的结点称为扩展结点。 5.子集树是用回溯法解题时经常遇到的一种典型的解空间树。当所给的问题是从n个元素组成的集合S中找出满足某种性质的一个子集时,相应的解空间树称为子集树。 6.当所给问题的n个元素中每一个元素均有m种选择,要求确定其中的一种选择,使得对这n个元素的选择结果组成的向量满足某种性质,即寻找满足某种特性的n个元素取值的一种组合,这类问题的解空间树称为满m叉树。 7.一个自身已生成但其孩子还没有全部生成的结点称为活结点 8.回溯法中,对于问题的一个实例,解向量满足显约束的所有n元组构成了该实例的一个解空间 9.分支限界法有两种:队列式分支限界法和优先队列式分支限界法。 10.分支限界法采用的是宽度优先搜索。 11.时间复杂性的度量方法通常有两种:事后统计法和事前分析估算法 12.一个所有孩子已经生成的结点称做死结点 13.在最小生成树的生成方法中,Kruskal算法从边的角度出发,每一次将图中的权值最小的边取出来,在不构成环的情况下,将该边加入最小生成树。 三 1.分治法字面上的解释是分而治之,就是把一个复杂的问题分成两个或更多的相同子问题,子问题相互独立,如果子问题还是不容易解决,再把子问题分成更小的子问题…,直到最后各个子问题可以简单地直接求解,对各个子问题递归求解,将子问题的解进行合并即得原问题的解。 2.动态规划法要求将大问题分解成规模较小的子问题,经分解得到的各个子问题往往不是相互独立的。在求解过程中,将已解决的子问题的解进行保存,在需要时可以轻松找出。采
《算法设计与分析》实验一
学号1607070212 《算法设计与分析》 实验报告一 学生姓名张曾然 专业、班级16软件二班 指导教师唐国峰 成绩 计算机与信息工程学院软件工程系 2018 年9 月19 日
实验一:递归策略运用练习 一、实验目的 本次实验是针对递归算法的算法设计及应用练习,旨在加深学生对该算法原理的理解,提高学生运用该算法解决问题的能力。 二、实验步骤与要求 1.实验前复习课程所学知识以及阅读和理解指定的课外阅读材料; 2.学生独自完成实验指定内容; 3.实验结束后,用统一的实验报告模板编写实验报告。 4.提交说明: (1)电子版提交说明: a 需要提交Winrar压缩包,文件名为“《算法设计与分析》实验一_学号_姓名”, 如“《算法设计与分析》实验一_09290101_张三”。 b 压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹, 其下为两个文件夹,一个文件夹命名为“源程序”,另一个文件夹命名为“实验 报告电子版”。其下分别放置对应实验成果物。 (2)打印版提交说明: a 不可随意更改模板样式。 b 字体:中文为宋体,大小为10号字,英文为Time New Roman,大小为10号 字。 c 行间距:单倍行距。 (3)提交截止时间:2018年10月10日16:00。 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: 【必做题】 (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份?
《算法设计与分析》递归算法典型例题
算法递归典型例题 实验一:递归策略运用练习 三、实验项目 1.运用递归策略设计算法实现下述题目的求解过程。 题目列表如下: (1)运动会开了N天,一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚,第二天发金牌2枚加剩下的七分之一枚,第3天发金牌3枚加剩下的七分之一枚,以后每天都照此办理。到了第N天刚好还有金牌N枚,到此金牌全部发完。编程求N和M。 (2)国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份,然后给第一个儿子一份,再加上剩余财产的1/10;给第二个儿子两份,再加上剩余财产的1/10;……;给第i 个儿子i份,再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几个儿子?财产共分成了多少份? 源程序: (3)出售金鱼问题:第一次卖出全部金鱼的一半加二分之一条金鱼;第二次卖出乘余金鱼的三分之一加三分之一条金鱼;第三次卖出剩余金鱼的四分之一加四分之一条金鱼;第四次卖出剩余金鱼的五分之一加五分之一条金鱼;现在还剩下11条金鱼,在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼? (4)某路公共汽车,总共有八站,从一号站发轩时车上已有n位乘客,到了第二站先下一半乘客,再上来了六位乘客;到了第三站也先下一半乘客,再上来了五位乘客,以后每到一站都先下车上已有的一半乘客,再上来了乘客比前一站少一个……,到了终点站车上还有乘客六人,问发车时车上的乘客有多少? (5)猴子吃桃。有一群猴子摘来了一批桃子,猴王规定每天只准吃一半加一只(即第二天吃剩下的一半加一只,以此类推),第九天正好吃完,问猴子们摘来了多少桃子? (6)小华读书。第一天读了全书的一半加二页,第二天读了剩下的一半加二页,以后天天如此……,第六天读完了最后的三页,问全书有多少页? (7)日本著名数学游戏专家中村义作教授提出这样一个问题:父亲将2520个桔子分给六个儿子。分完后父亲说:“老大将分给你的桔子的1/8给老二;老二拿到后连同原先的桔子分1/7给老三;老三拿到后连同原先的桔子分1/6给老四;老四拿到后连同原先的桔子分1/5给老五;老五拿到后连同原先的桔子分1/4给老六;老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子? 四、实验过程 (一)题目一:…… 1.题目分析 由已知可得,运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数,且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天, If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
《算法设计与分析》实验报告
算法设计与分析课程实验项目目录 学生:学号: *实验项目类型:演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。
本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日~6月30日温度24℃ 1.实验目的和要求: 熟悉蛮力法的设计思想。 2.实验原理和主要容: 实验原理:蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容:以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序,实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的: S END +MORE MONEY . 这里有两个前提假设: 第一,字母和十进制数字之间一一对应,也就是每个字母只代表一个数字,而且不同的字母代表不同的数字;第二,数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意,解可能并不是唯一的,不同人的解可能并不相同。3.实验结果及分析: (将程序和实验结果粘贴,程序能够注释清楚更好。)
该算法程序代码如下: #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数:\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l算法设计与分析课后习题
第一章 1. 算法分析题 算法分析题1-1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是,n^2 < 2 ^n 所以,当n >= 1时,n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为:f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以:f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为:log(n) < √n; f(n) = 2log(n); g(n)= √n 所以:f(n) = O(g(n)) (3)因为:log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以;f(n) = Ω(g(n)) (4)因为:f(n) = nlogn +n; g(n) = logn 所以:f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10)
所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为:f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1-9 证明:如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答: 因此,Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章 算法分析题
算法设计与分析实验报告 统计数字问题
算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4.实现具体的编程与上机实验,验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排,每个页码都不含多余的前导数字0。例如,第6 页用数字6 表示,而不是06 或006 等。数字计数问题要求对给定书的总页码n,计算出书的全部页码中分别用到多少次数字0,1,2, (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0,1,2, (9) 三.程序算法 将页码数除以10,得到一个整数商和余数,商就代表页码数减余数外有多少个1—9作为个位数,余数代表有1—余数本身这么多个数作为剩余的个位数,此外,商还代表1—商本身这些数出现了10次,余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int s[10]; //记录0~9出现的次数 int a[10]; //a[i]记录n位数的规律 void sum(int n,int l,int m) { if(m==1) {
int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i南京邮电大学算法设计实验报告——动态规划法
实验报告 (2009/2010学年第一学期) 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程
实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的:加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的最长公共子序列问题。 任务:用动态规划法实现求两序列的最长公共子序列,其比较结果可用于基因比较、文章比较等多个领域。 要求:掌握动态规划法的思想,及动态规划法在实际中的应用;分析最长公共子序列的问题特征,选择算法策略并设计具体算法,编程实现两输入序列的比较,并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件:计算机 软件:Visual C++
三、实验原理及内容(包括操作过程、结果分析等) 1、最长公共子序列(LCS)问题是:给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n},要求找出X和Y的一个最长公共子序列。 例如:X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列,检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法,求解时间为指数级别的,因此不可取。 2、分析LCS问题特征可知,如果Z={z1,z2,……,z k}为它们的最长公共子序列,则它们一定具有以下性质: (1)若x m=y n,则z k=x m=y n,且Z k-1是X m-1和Y n-1的最长公共子序列; (2)若x m≠y n且x m≠z k,则Z是X m-1和Y的最长公共子序列; (3)若x m≠y n且z k≠y n,则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题,分解为求解较小规模的问题: 若x m=y m,则进一步分解为求解两个(前缀)子字符序列X m-1和Y n-1的最长公共子序列问题; 如果x m≠y n,则原问题转化为求解两个子问题,即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列,取两者中较长者作为X和Y的最长公共子序列。 由此可见,两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列,具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度,由上述分析可得如下递推式: 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见,最长公共子序列的求解具有重叠子问题性质,如果采用递归算法实现,会得到一个指数时间算法,因此需要采用动态规划法自底向上求解,并保存子问题的解,这样可以避免重复计算子问题,在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解(即最长公共子序列),还需要一个二维数组s[][],数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到,从而可以得到最优解的当前解分量(即最长公共子序列中的当前字符),最终构造出最长公共子序列自身。
最新算法设计与分析复习要点(1)
算法设计与分析的复习要点 第一章:算法问题求解基础 算法是对特定问题求解步骤的一种描述,它是指令的有限序列。 一.算法的五个特征: 1.输入:算法有零个或多个输入量; 2.输出:算法至少产生一个输出量; 3.确定性:算法的每一条指令都有确切的定义,没有二义性; 4.可行性:算法的每一条指令必须足够基本,它们可以通过已经实现的基本运算执行有限次来实现; 5.有穷性:算法必须总能在执行有限步之后终止。 二.什么是算法?程序与算法的区别 1.笼统地说,算法是求解一类问题的任意一种特殊的方法;较严格地说,算法是对特定问题求解步骤的一种描述,它是指令的有限序列。 2.程序是算法用某种程序设计语言的具体实现;算法必须可终止,程序却没有这一限制;即:程序可以不满足算法的第5个性质“有穷性”。 三.一个问题求解过程包括:理解问题、设计方案、实现方案、回顾复查。 四.系统生命周期或软件生命周期分为: 开发期:分析、设计、编码、测试;运行期:维护。 五.算法描述方法:自然语言、流程图、伪代码、程序设计语言等。 六.算法分析:是指对算法的执行时间和所需空间的估算。算法的效率通过算法分析来确定。 七.递归定义:是一种直接或间接引用自身的定义方法。一个合法的递归定义包括两部分:基础情况和递归部分; 基础情况:以直接形式明确列举新事物的若干简单对象; 递归部分:有简单或较简单对象定义新对象的条件和方法 八.常见的程序正确性证明方法: 1.归纳法:由基础情况和归纳步骤组成。归纳法是证明递归算法正确性和进行算法分析的强有力工具; 2.反证法。 第二章:算法分析基础 一.会计算程序步的执行次数(如书中例题程序2-1,2-2,2-3的总程序步数的计算)。二.会证明5个渐近记法。(如书中P22-25例2-1至例2-9) 三.会计算递推式的显式。(迭代法、代换法,主方法) 四.会用主定理求T(n)=aT(n/b)+f(n)。(主定理见P29,如例2-15至例2-18)五.一个好的算法应具备的4个重要特征: 1.正确性:算法的执行结果应当满足预先规定的功能和性能要求; 2.简明性:算法应思路清晰、层次分明、容易理解、利于编码和调试; 3.效率:算法应有效使用存储空间,并具有高的时间效率; 4.最优性:算法的执行时间已达到求解该类问题所需时间的下界。 六.影响程序运行时间的主要因素: 1.程序所依赖的算法; 2.问题规模和输入数据规模; 3.计算机系统性能。 七.1.算法的时间复杂度:是指算法运行所需的时间;
算法设计与分析实验报告
算法设计与分析实验报告 教师: 学号: 姓名:
实验一:串匹配问题 实验目的:(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求:( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include //BF算法 int BF(char s[],char t[]) { int i; int a; int b; int m,n; m=strlen(s); //主串长度 n=strlen(t); //子串长度 printf("\n*****BF*****算法\n"); for(i=0;i深圳大学算法设计与分析杨煊实验三
深圳大学实验报告 课程名称:算法设计与分析 实验项目名称:高斯消元 学院: 专业、班级: 指导教师:杨烜 报告人:学号: 实验报告提交时间: 2015.5.15 教务处制
一、实验目的 1.掌握变治法思想。 2.学会高斯列主元消去法及其应用。 二、实验内容 1. 高斯列主元消去法求解线性方程组。 2. 高斯列主元消去法判断矩阵是否可逆?需要说明理由,如果可逆,求出其逆矩阵。 三、实验原理 算法:GaussElimination(A[1...n,1...n],b[1...n]) //用部分选主元法实现高斯消去法 //输入:矩阵A[1...n,1...n]和列向量b[1...n] //输出:一个代替A的上三角形等价矩阵图,相应的右边的值位于第(n+1)列中for i<-1 to n do A[i,n+1]<-b[i] //把b作为最后一列添加到A中 for i<-1 to n-1 do pivotrow<-i for j<-i+1 to n do if |A[j,i]|>|A[pivotrow,i]| pivotrow<-j for k<-i to n+1 do
swap(A[i,k],A[pivotrow,k]) for j<-i+1 to n do temp<-A[j,i]/A[i,i] for k<-i to n+1 do A[j,k]<-A[j,k]-A[i,k]*temp 算法:GaussBackSub(A[1...n,1...n+1]) //实现高斯消去法的反向替换 //输入:一个代替A的上三角形等价矩阵图,相应的右边的值位于第(n+1)列中 //输出:方程组的n个解 for i<-n downto 1 do temp<-0.0 for j<-n downto i+1 temp<-temp+A[i,j]*x[j] x[i]<-(A[i,n+1]-temp)/A[i,i] return x 算法:IsInverseMatrix(A[1...n,1...n],b[1...n]) //用高斯消去法判断是否为逆矩阵 //输入:矩阵A[1...n,1...n] //输出:如果是逆矩阵输出1,否则输出0 for i<-1 to n do A[i,n+1]<-b[i] //把b作为最后一列添加到A中 for i<-1 to n-1 do pivotrow<-i for j<-i+1 to n do if |A[j,i]|>|A[pivotrow,i]| pivotrow<-j for k<-i to n+1 do swap(A[i,k],A[pivotrow,k]) for j<-i+1 to n do temp<-A[j,i]/A[i,i] for k<-i to n+1 do A[j,k]<-A[j,k]-A[i,k]*temp for i<-1 to n if(A[i,i]=0) return 0 return 1 算法:求矩阵的逆矩阵(伪代码篇幅较长,仅描述主要思想) 思想描述:设待求矩阵B的逆矩阵为X,根据逆矩阵的定义,满足BX=I(其中I为n阶单位矩阵)。显然,对于一个n*n的矩阵B,其逆矩阵X同样为n*n。将待求矩阵X的第i 列xi看做一组未知数,同样的将单位矩阵I的第i列ei看作方程组右边的值。(1<=i<=n) 求解 Bxi=ei;所得解即为所求可逆矩阵第i列的值。即利用高斯消元法进行n次的方程求解,最终得到的矩阵即为逆矩阵。
算法设计与分析第一章习题解1.1,1.10,1.15
1.15练习 1.1(a) 1)A[1…60] = A[(1+60)/2]=A[30]=40 由于33<40,舍弃A[30…60]; 2)A[1…29] = A[(1+29)/2]=A[15]=25 由于33>25,舍弃A[1…15]; 3) A[16…29]= A[(16+29)/2]=A[22]=32 由于33>32,舍弃A[16…22]; 4) A[23…29] = A[(23+29)/2]=A[26]=36 由于33<36,舍弃A[26…29]; 5) A[23…25] = A[(23+25)/2]=A[24]=34; 由于33<34,舍弃A[24, 25]; 6) A[23] = 11 12 13 … 68 69 70 11 12 13 … 37 38 39 26 27 28 … 37 38 39 33 34 35 36 37 38 39 33 34 35 33
由于33=33,搜索完毕。 综上,搜索33共执行了6次比较。 同理可得(b )搜索7共执行了5次比较。 (c )搜索70共执行了6次比较。 (d )搜索77共执行了6次比较。 1.10 对11 12 1 5 15 3 4 10 7 2 16 9 8 14 13 6用bottomupsort 算法,按非降序排列。 解:用图示,如下进行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 3 4 5 10 11 12 15 1 5 11 1 2 1.15用Θ表示函数。 (b) 2 6 7 8 9 1 3 1 4 16 3 4 10 1 5 2 7 9 1 6 6 8 13 14 11 12 1 5 15 3 4 10 2 7 9 16 8 14 6 13
算法设计与分析习题与实验题(12.18)
《算法设计与分析》习题 第一章引论 习题1-1 写一个通用方法用于判定给定数组是否已排好序。 解答: Algorithm compare(a,n) Begin J=1; While (j=a[j+1]) do j=j+1; If j=n then return true else return false end if End if end 习题1-2 写一个算法交换两个变量的值不使用第三个变量。 解答:x=x+y; y=x-y; x=x-y; 习题1-3 已知m,n为自然数,其上限为k(由键盘输入,1<=k<=109),找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。 解答: m:=k; flag:=0; repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (m=0); 第二章基础知识
习题2-1 求下列函数的渐进表达式: 3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。 解答: 3n 2+10n=O (n 2), n 2/10+2n =O (2n ), 21+1/n=O (1), log n 3=O (log n ),10 log3n =O (n )。 习题2-2 说明O (1)和 O (2)的区别。 习题2-3 照渐进阶从低到高的顺序排列以下表达式:!n , 3 /22 ,2,20,3,log ,4n n n n n 。 解答:照渐进阶从低到高的顺序为:!n 、 3n 、 2 4n 、2 3n 、20n 、log n 、2 习题2-4 (1) 假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机 上实现并完成该算法的时间为t 秒。现有另外一台计算机,其运行速度为第一台计算机的64倍,那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题? (2) 若上述算法的计算时间改进为2)(n n T =,其余条件不变,则在新机器上用 t 秒时间能解输入规模多大的问题? (3) 若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变,那么在新机 器上用t 秒时间能解输入规模多大的问题? 解答: (1) 设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有 64 /2 3231 n n t ?=?=,解得61+=n n 。 (2) n n n n 8641221==>=。 (3) 由于=)(n T 常数,因此算法可解任意规模的问题。 习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ,2n ,3n 和!n 的各算法,若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题,那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题?
算法设计与分析C++语言描述(陈慧南版)课后答案
第一章 15P 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数,程序1-2的while 循环体做了10次,程序1-3的while 循环体做了14141次(14142-2循环) 若考虑其他语句,则没有这么多,可能就601倍。 第二章 32P 2-8.(1)画线语句的执行次数为log n ??? ?。(log )n O 。划线语句的执行次数应该理解为一格整体。 (2)画线语句的执行次数为 111 (1)(2)16 j n i i j k n n n ===++= ∑∑∑。3 ()n O 。 (3)画线语句的执行次数为 。O 。 (4)当n 为奇数时画线语句的执行次数为 (1)(3) 4 n n ++, 当n 为偶数时画线语句的执行次数为 2(2)4 n +。2 ()n O 。 2-10.(1) 当 1n ≥ 时,225825n n n -+≤,所以,可选 5c =,01n =。对于0n n ≥, 22()5825f n n n n =-+≤,所以,22582()n n n -+=O 。 (2) 当 8n ≥ 时,2222582524n n n n n -+≥-+≥,所以,可选 4c =,08n =。对于0n n ≥, 22()5824f n n n n =-+≥,所以,22582()n n n -+=Ω。 (3) 由(1)、(2)可知,取14c =,25c =,08n =,当0n n ≥时,有22212582c n n n c n ≤-+≤,所以2 2 582()n n n -+=Θ。 2-11. (1) 当3n ≥时,3 log log n n n <<,所以()20log 21f n n n n =+<,3 ()log 2g n n n n =+>。可 选 21 2 c = ,03n =。对于0n n ≥,()()f n cg n ≤,即()(())f n g n =O 。注意:是f (n )和g (n )的关系。