算法分析基础

作业一学号：_____ 姓名：_____说明：1、正文用宋体小四号，1.5倍行距。

2、报告中的图片、表格中的文字均用宋体五号，单倍行距。

3、图片、表格均需要有图片编号和标题，均用宋体五号加粗。

4、参考文献用宋体、五号、单倍行距，请参照参考文献格式国家标准（GB/T 7714-2005）。

5、公式请使用公式编辑器。

P144.用伪代码写一个算法来求方程ax2+bx+c=0的实根，a，b，c 是任意实系数。

（可以假设sqrt(x)是求平方根的函数。

）算法：Equate(a,b,c)//实现二元一次方程求解实数根//输入：任意系数a，b，c//输出：方程的实数根x1，x2或无解If a≠0p←b2−4acIf p>0x1←−b+sqrt(p)2ax2←−b−sqrt(p)2areturn x1，x2else if p=0return −b2aelsereturn “no real roots”elseif b≠0return −cbelseif c≠0return “no real numbers”elsereturn “no real roots”5.写出将十进制正整数转换为二进制整数的标准算法。

a.用文字描述。

b.用伪代码描述。

a.解：输入：一个正整数n输出：正整数n相应的二进制数第一步：用n 除以2，余数赋给K[i](i=0,1,2...)，商赋给n第二步：如果n=0 ，则到第三步，否则重复第一步第三步：将K[i]按照i从高到低的顺序输出b.解：算法：DecToBin(n)//实现正整数十进制转二进制//输入：一个正整数n//输出：正整数n对应的二进制数组K[0..i]i ←1while n≠0 doK[i]←n%2n←(int)n/2i ++while i≠0doprint K[i]i - -p462.请用O，Ω 和θ的非正式定义来判断下列断言是真还是假。

a. n(n+1)/2∈O(n3)b. n(n+1)/2∈O(n2)c. n(n+1)/2∈θ(n3)d. n(n+1)/2∈Ω(n)解：断言为真：a，b，d断言为假：cP535.考虑下面的算法。

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<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次..对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.(农夫过河)P—农夫 W—狼 G—山羊 C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设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=1while 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])n-1]a.应用该算法对列表”60,35,81,98,14,47”排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表”60,35,81,98,14,47”排序的过程如下所示:b.该算法不稳定.比如对列表”2,2*”排序c.该算法不在位.额外空间for S and Count[]4.(古老的七桥问题)习题1.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度.a.删除数组的第i个元素(1<=i<=n)b.删除有序数组的第i个元素(依然有序)hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array’s element., 0 for an array of positive numbers ) to mark the i th position is empty. (“lazy deletion”)第2章习题7.对下列断言进行证明:(如果是错误的,请举例)a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n))b.α>0时,Θ(αg(n))= Θ(g(n))解:a. 这个断言是正确的。

算法设计与分析基础习题参考答案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并且这种交换处理只发⽣⼀次.7.a.对于所有1≤m,n≤10的输⼊, Euclid算法最少要做⼏次除法?(1次)b. 对于所有1≤m,n≤10的输⼊, Euclid算法最多要做⼏次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—⼭⽺C—⽩菜2.(过桥问题)1,2,5,10---分别代表4个⼈, f—⼿电筒4. 对于任意实系数a,b,c, 某个算法能求⽅程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平⽅根的函数)算法Quadratic(a,b,c)//求⽅程ax^2+bx+c=0的实根的算法//输⼊:实系数a,b,c//输出:实根或者⽆解信息D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将⼗进制整数表达为⼆进制整数的标准算法a.⽤⽂字描述b.⽤伪代码描述解答：a.将⼗进制整数转换为⼆进制整数的算法输⼊：⼀个正整数n输出：正整数n相应的⼆进制数第⼀步：⽤n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第⼆步：如果n=0，则到第三步，否则重复第⼀步第三步：将Ki按照i从⾼到低的顺序输出b.伪代码算法DectoBin(n)//将⼗进制整数n转换为⼆进制整数的算法//输⼊：正整数n//输出：该正整数相应的⼆进制数，该数存放于数组Bin[1...n]中i=1while 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])//输⼊:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样⼀个排序算法,该算法对于待排序的数组中的每⼀个元素,计算⽐它⼩的元素个数,然后利⽤这个信息,将各个元素放到有序数组的相应位置上去.a.应⽤该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所⽰:b.该算法不稳定.⽐如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[]4.(古⽼的七桥问题)习题1.41.请分别描述⼀下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty . (―lazy deletion ‖)第2章习题2.17.对下列断⾔进⾏证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断⾔是正确的。

算法分析基础——主定理
对于形为T(n) = aT(n / b) + f(n)的递推⽅程，我们有如下结论：
主定理（MasterTheorem）设a≥1，b>1 为常数，f(n)为函数，n为⾮负整数，且 T(n) = aT(n / b) + f(n)，则有以下结果：
1. 若存在ε>0，使得f(n) = O(n log b a-ε)，则T(n) = Θ(n log b a)
2. 若f(n) = Θ(n log b a)，则T(n) = Θ(n log b a logn)
3. 若存在ε>0，使得f(n) = Ω(n log b a+ε)，并且对于某个常数c<1和所有充分⼤的n，有af(n / b)≤cf(n)，则T(n) = Θ(f(n))
证明：详见教材（推导过程略复杂，不想写了qwq）。

由主定理可以直接得到下述推论：
推论1 依主定理条件，递推⽅程为T(n)= aT(n / b) + c，则
1. 当a≠1时，T(n) = Θ(n log b a)
2. 当a=1时，T(n) = Θ(logn)
推论2 依主定理条件，递推⽅程为T(n) = aT(n / b) + cn，则
1. 当a>b时，T(n) = Θ(n log b a)
2. 当a=b时，T(n) = Θ(nlogn)
3. 当a<b时，T(n) = Θ(n)
例根据主定理及其推论，我们可以直接得到⼆分检索算法的平均时间复杂度为Θ(logn)，⽽⼆分归并排序的平均时间复杂度为Θ(nlogn)。

算法分析教学设计引言算法作为计算机科学的基础，几乎贯穿了计算机科学的方方面面。

它的重要性在于如何去解决一个问题，并且算法的运行时间直接影响到计算机的运行效率。

因此，在计算机科学专业的课程中，算法分析是一个必不可少的环节。

本文将从课程目标、课程设计、教学方法和教学评价这四个方面来讨论如何进行算法分析的教学设计。

课程目标在本课程中，我们将学习如何分析算法的好坏、效率和优化，为我们后面的编程实践提供基础和指导。

具体的学习目标如下：1.了解算法分析的基本概念和方法；2.理解常见的算法复杂度表示方法，包括大O、大Ω和大Θ；3.掌握常见的算法分析技巧，例如递归公式、迭代法、主定理等；4.学会如何进行算法的优化和改进。

课程设计教学内容1.算法分析基础–介绍算法分析的基本概念和方法–讲解渐进符号和算法复杂度的概念–常见时间复杂度分析方法，包括大O、大Ω和大Θ2.常见的算法分析技巧–递归公式的求解方法–迭代法的应用–主定理的使用方法说明3.掌握算法的优化策略–分治法的基本思想–贪心算法的特点与应用–动态规划算法的原理和使用方法–回溯算法的优化策略教学方法1.理论讲解在教学过程中，应该注重将抽象的概念和理论融入实例中，以便学生理解。

例如，讲解渐进符号时，可以通过分析代码的时间复杂度来帮助学生理解。

2.案例分析通过实际的案例来让学生掌握算法复杂度分析的方法和技巧。

例如，在讲解大O符号时，可以通过对一个具体案例的分析来让学生了解O的定义。

3.编程实践学生可以通过实现和测试不同的算法来加深对算法分析的理解。

例如，可以通过比较不同排序算法的效率，让学生更好地理解复杂度的概念。

教学评价1.分组讨论学生可以分小组进行讨论，每组讨论一个算法的优化策略，并最终演示出来。

这可以让学生深入掌握算法优化的方法。

2.考试通过考试来测试学生对算法分析的理解程度，考核内容包括算法复杂度的概念、渐进符号的使用、算法分析技巧和算法优化策略等。

考试形式可以包括选择、填空和简答等。

算法设计与分析的基本方法1.递推法递推算法是一种用若干步可重复的简运算（规律）来描述复杂问题的方法.递推是序列计算机中的一种常用算法。

它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定象的值。

其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

2.递归法程序调用自身的编程技巧称为递归（recursion）。

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。

一般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：(1) 递归就是在过程或函数里调用自身;(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

3.穷举法穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。

例如一个已知是四位并且全部由数字组成的密码，其可能共有10000种组合，因此最多尝试10000次就能找到正确的密码。

理论上利用这种方法可以破解任何一种密码，问题只在于如何缩短试误时间。

因此有些人运用计算机来增加效率，有些人辅以字典来缩小密码组合的范围。

4.贪心算法贪婪算法是一种对某些求最优解问题的更简单、更迅速的设计技术。

用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

算法设计与分析基础第二版课后答案【篇一：算法设计与分析基础课后习题答案(中文版)】class=txt>习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立. hint:根据除法的定义不难证明:?如果 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=mgcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.2 1.(农夫过河)p—农夫w—狼 g—山羊 c—白菜 2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数) 算法quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法 //输入:实系数a,b,c//输出:实根或者无解信息if a≠0d←b*b-4*a*c if d0temp←2*ax1←(-b+sqrt(d))/temp x2←(-b-sqrt(d))/temp return x1,x2else if d=0 return –b/(2*a) else return “no real roots” else //a=0 if b≠0 return –c/b else //a=b=0if c=0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法 a.用文字描述 b.用伪代码描述解答： a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给ki(i=0,1,2...)，商赋给n 第二步：如果n=0，则到第三步，否则重复第一步第三步：将ki按照i从高到低的顺序输出b.伪代码算法 dectobin(n)//将十进制整数n转换为二进制整数的算法 //输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组bin[1...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]) //输入:数组a[0..n-1]//输出:the smallest distance d between two of its elements习题1.31. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗? 解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for s and count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i个元素(1=i=n)b.删除有序数组的第i个元素(依然有序) hints:a. replace the ith element with the last element and decreasethe array size of 1b. replace the ith element with a special symbol that cannot be a value of the arr ay’s element(e.g., 0 for an array of positive numbers ) to mark the ith position is empty. (―lazy deletion‖)第2章习题2.1a. 这个断言是正确的。

算法分析与设计基础（清华版）Taken from "Introduction to The Design and Analysis of Algorithms" by Anany Levitin节选自《算法设计与分析基础》潘彦译蛮力法就像宝剑不是撬棍一样，科学也很少使用蛮力。

——Edward Lytton (1830 - 1873)，leila，第二卷，第一章认真做事常常是浪费时间。

——Robert Byrne，撞球大师，台球选手和作家人们是这样描述它的：蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。

这里的“力”是指计算机的能“力”，而不是人的智“力”。

我们也可以用“直接做吧！”来描述蛮力法的策略。

而且一般来说，蛮力策略也常常是最容易应用的方法。

虽然巧妙和高效的算法很少来自于蛮力法，但我们不应该忽略它作为一种重要的算法设计策略的地位。

第一，和其他某些策略不同，我们可以应用蛮力法来解决广阔领域的各种问题（实际上，它可能是惟一一种几乎什么问题都能解决的一般性方法）。

具体来说，蛮力法常常用于一些非常基本、但又十分重要的算法，比如计算n个数字的和，求一个列表的最大元素，等等。

第二，对于一些重要的问题来说（比如：排序、查找、矩阵乘法和字符串匹配），蛮力法可以产生一些合理的算法，它们多少具备一些实用价值，而且并不限制实例的规模。

第三，如果要解决的问题实例不多，而且蛮力法可以用一直能够接受的速度对实例求解，那么，设计一个更高效算法所花费的代价很可能是不值得的。

第四，即使效率通常很低，仍然可以用蛮力算法解决一些小规模的问题实例。

最后，一个蛮力算法可以为研究或教学目的服务，例如，它可以作为准绳，来衡量同样问题的更高效算法。

下列这些著名的算法可以看作是蛮力法的例子：基于定义的矩阵乘法算法；选择排序；顺序查找；简单的字符串匹配算法。

穷举查找是解组合问题的一种蛮力方法。