算法设计与分析复习资料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.动态规划法要求将大问题分解成规模较小的子问题,经分解得到的各个子问题往往不是相互独立的。在求解过程中,将已解决的子问题的解进行保存,在需要时可以轻松找出。采
OpenJudge算法设计与分析习题解答
1、硬币面值组合 描述 使用1角、2角、5角硬币组成n 角钱。 设1角、2角、5角的硬币各用了a、b、c个,列出所有可能的a, b, c组合。 输出顺序为:先按c的值从小到大,若c相同则按b的值从小到大。 输入 一个整数n(1 <= n <= 100),代表需要组成的钱的角数。 输出 输出有若干行,每行的形式为: i a b c 第1列i代表当前行数(行数从001开始,固定3个字符宽度,宽度不足3的用0填充),后面3列a, b, c分别代表1角、2角、5角硬币的个数(每个数字固定12个字符宽度,宽度不足的在左边填充空格)。
源代码: #include #include int main(){ int t=1; int i,j,k; int n; scanf("%d",&n); int A=n,B=n/2,C=n/5; for(i=0;i<=C;i++){ for(j=0;j<=B;j++){ for(k=0;k<=A;k++){ if(i*5+j*2+k*1==n){ printf("%03d%12d%12d%12d\n",t,k,j,i); t++; } } } } getchar(); return 0; } 2、比赛排名 描述 5名运动员参加100米赛跑,各自对比赛结果进行了预测:A说:E是第1名。 B说:我是第2名。 C说:A肯定垫底。 D说:C肯定拿不了第1名。
E说:D应该是第1名。 比赛结束后发现,只有获第1名和第2名的选手猜对了,E不是第2名和第3名,没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求:按ABCDE的顺序输出5行,其中第1行是A的名次,第2行是B的名次,第3行是C的名次,第4行是D的名次,第5行是E的名次。 样例输入 样例输出 源代码: #include int main() { printf("5\n"); printf("2\n"); printf("1\n"); printf("3\n"); printf("4\n"); return 0; } 3、鸡兔同笼 描述 一个笼子里面关了鸡和兔子(鸡有2只脚,兔子有4只脚,没有例外)。已经知道了笼子里面脚的总数a,问笼子里面至少有多少只动物,至多有多少只动物。
算法设计与分析考试重点归纳
算法设计考试重点整理 题型: 一选择题(10*2=20 分) 二简答题(4*5=20 分) 三应用题(3*10=30 分) 四算法题(3*10=30 分) 第一、二章 算法的定义:解某一特定问题的一组有穷规则的集合(对特定问题求解步骤的一种描述,是指令的有限序列) 算法的特征:1)有限性 2)确定性 3)输入 4)输出 5)能行性 算法分析的目的: 基本数据结构: 线性结构(元素之间是一对一的关系) 用顺序存储结构存储的线性表称为顺序表 用链式存储结构存储的线性表称为链表。 树形结构(元素之间是一对多的关系) 图(网)状结构(元素之间是多对多的关系) 栈:是一种只允许在表的一端进行插入或删除操作的线性表。允许进行插入、删除操作的一端称为栈顶,另一端称为栈底。当栈中没有数据元素时,称之为空栈。栈的插入操作称为进压栈,删除操作称为出栈。 队列:只允许在一端进行插入操作,在另一端进行删除操作的线性表。允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。当队列中没有数据元素时,称之为空队列。队列的插入操作称为进队或入队。队列的删除操作称为退队或出队。 树:树型结构是一种非线性结构,它用于描述数据元素之间的层次关系图 图:G=(V,E)是一个二元组
其中:V是图G中数据元素(顶点)的非空有限集集合 E是图G中关系的有限集合 由表达式求渐进表达式:例:(n2+n)/4 n2/4(增长速率最快的那一项) 时间复杂度的计算:(P23) 性能的比较:O(1) < O(log2n) < O(n) < O(nlog2n) =O(nlogn)< O(n2) < O(n3) < O(n k) < O(2n) 第三章 算法思想、稳定性、时间复杂度、应用、排序的移动次数: 希尔排序(数据结构P265):先将待排序列分割为若干个子序列分别进行直接插入排序;待整个序列基本有序时,再对全体记录进行一次直接插入排序。也称缩小增量的直接插入排序。 希尔排序的时间复杂度在O(nlog2n)和 O(n2)之间,大致为O 合并排序(P59):设初始序列含有n个记录,则可看成n个表长为1的有序表将这n个有序表两两合并,则可得n/2个表长为2的有序表再将这n/2个有序表两两合并,则可得n/4个长为4的有序表依次重复,直到对2个表长为n/2的有序表两两合并得1个表长为n的有序表为止。 堆排序、堆调整(P62): 初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。 基数排序(P71):不进行记录关键字的比较,借助多关键字排序的思想对单逻辑关键字进行排序。 算法时间复杂度稳定性 希尔排序 O不稳定 快速排序 O(nlogn)不稳定
算法设计与分析第2版 王红梅 胡明 习题答案
精品文档习题胡明-版)-王红梅-算法设计与分析(第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 using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low=prvotkey)
算法设计与分析复习题目及答案
一。选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( B )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是( B )。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是( B )。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6.下列算法中通常以自底向上的方式求解最优解的是( B )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是(C )。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是(D )。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是( A )。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是(C ) A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11.下面不是分支界限法搜索方式的是( D )。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12.下列算法中通常以深度优先方式系统搜索问题解的是( D )。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。( B )
算法设计与分析考试题及答案
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语言描述课后答案
P 15 1-3. 最大公约数为1。快1414倍。 主要考虑循环次数,程序1-2的while循环体做了10次,程序1-3的while循环体做了14141次(14142-2循环) 若考虑其他语句,则没有这么多,可能就601倍。 第二章 2-8.(1)画线语句的执行次数为。。划线语句的执行次数应该理解为一格整体。 (2)画线语句的执行次数为。。 (3)画线语句的执行次数为。。 (4)当n为奇数时画线语句的执行次数为, 当n为偶数时画线语句的执行次数为。。 2-10.(1)当时,,所以,可选,。对于,,所以,。 (2)当时,,所以,可选,。对于,,所以,。 (3)由(1)、(2)可知,取,,,当时,有,所以。 2-11. (1) 当时,,所以,。可选,。对于,,即。注意:是f(n)和g(n)的关系。 (2)当时,,所以,。可选,。对于,,即。 (3)因为,。当时,,。所以,可选,,对于,,即。 第二章 2-17. 证明:设,则。 当时,。所以,。
第五章 5-4. SolutionType DandC1(int left,int right) { while(!Small(left,right)&&leftP[m]) left=m+1; else return S(P) } } 5-7. template int SortableList::BSearch(const T&x,int left,int right) const { if (left<=right) { int m=(right+left)/3; if (xl[m]) return BSearch(x,m+1,right); else return m; } return -1; } 第五章 9. 4 26 35 17 01234567 -10 证明:因为该算法在成功搜索的情况下,关键字之间的比较次数至少为,至多为。在不成功搜索的情况下,关键字之间的比较次数至少为,至多为。所以,算法的最好、最坏情况的时间复杂度为。 假定查找表中任何一个元素的概率是相等的,为,那么, 不成功搜索的平均时间复杂度为, 成功搜索的平均时间复杂度为。
算法设计与分析试卷及答案
湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型:开卷 试卷类型: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-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.应用Johnson法则的流水作业调度采用的算法是(D) A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上,并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为:(B) " ; | A. void hanoi(int n, int A, int C, int B) 《 { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); ] move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } }
3. 动态规划算法的基本要素为(C ) A. 最优子结构性质与贪心选择性质 B .重叠子问题性质与贪心选择性质 C .最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中,记号O 表示(B ), 记号Ω表示(A ), 记号Θ表示(D )。 … A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有:(A ) A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ?=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f (n)O(g(n))g(n)O(f (n))=?= D. void hanoi(int n, int C, int A, int B) { if (n > 0) { | hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); }
最新算法设计与分析复习要点(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-1 加减得1的数学游戏 西西很喜欢数字游戏,今天他看到两个数,就想能否通过简单的加减,使最终答案等于1。而他又比较厌烦计算,所以他还想知道最少经过多少次才能得到1。 例如,给出16,9:16-9+16-9+16-9-9-9+16-9-9=1,需要做10次加减法计算。 设计算法,输入两个不同的正整数,输出得到1的最少计算次数。(如果无法得到1,则输出-1)。 (1)若输入两个不同的正整数a,b均为偶数,显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值,令n从1开始递增,x在1——n中取值,y=n+1-x: 检测d=x*a+y*b,若d=1或-1,则n=x+y-1为所求的最少次数。 (2)算法描述 // 两数若干次加减结果为1的数学游戏 #include void main() {long a,b,d,n,x,y; printf(" 请输入整数a,b: "); scanf("%ld,%ld",&a,&b); if(a%2==0 && b%2==0) { printf(" -1\n");return;} n=0; while(1) { n++; for(x=1;x<=n;x++) { y=n+1-x;d=x*a-y*b; if(d==1 || d==-1) // 满足加减结果为1 { printf(" n=%ld\n",n);return;} } } } 请输入整数a,b: 2012,19 961 请输入整数a,b: 101,2013 606
算法设计与分析第一章习题解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
算法设计与分析基础课后习题答案
Program算法设计与分析基础中文版答案 习题 5..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. Hint: 根据除法的定义不难证明: 如果d整除u和v, 那么d一定能整除u±v; 如果d整除u,那么d也能够整除u的任何整数倍ku. 对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn;显然,若d能整除n和r,也一定能整除m=r+qn和n。 数对(m,n)和(n,r)具有相同的公约数的有限非空集,其中也包括了最大公约数。故gcd(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint: 对于任何形如0<=m设sqrt(x)是求平方根的函数) 算法Quadratic(a,b,c) 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述 解答: a.将十进制整数转换为二进制整数的算法 输入:一个正整数n 输出:正整数n相应的二进制数 第一步:用n除以2,余数赋给Ki(i=0,1,2...),商赋给n 第二步:如果n=0,则到第三步,否则重复第一步 第三步:将Ki按照i从高到低的顺序输出 b.伪代码 算法 DectoBin(n) .n]中 i=1 while n!=0 do { Bin[i]=n%2; n=(int)n/2; i++; } while i!=0 do{ print Bin[i]; i--; } 9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略)对这个算法做尽可能多的改进. 算法 MinDistance(A[0..n-1])