下载文档原格式
算法设计与分析第二版课后习题解答算法设计与分析基础课后练习答案习题 4.设计一个计算的算法，n是任意正整数。
除了赋值和比较运算，该算法只能用到基本的四则运算操作。
算法求//输入：一个正整数n2//输出：。
step1:a=1；step2:若a*a 5. a．用欧几里德算法求gcd。
b. 用欧几里德算法求gcd,比检查min｛m，n｝和gcd间连续整数的算法快多少倍？请估算一下。
a. gcd(31415, 14142) = gcd(14142, 3131) = gcd(3131, 1618) =gcd(1618, 1513) = gcd(1513,105) = gcd(1513, 105) = gcd(105, 43) =gcd(43, 19) = gcd(19, 5) = gcd(5, 4) = gcd(4, 1) = gcd(1, 0) = 1.b.有a可知计算gcd欧几里德算法做了11次除法。
连续整数检测算法在14142每次迭代过程中或者做了一次除法，或者两次除法，因此这个算法做除法的次数鉴于1·14142 和 2·14142之间，所以欧几里德算法比此算法快1·14142/11 ≈ 1300 与 2·14142/11 ≈ 2600 倍之间。
6.证明等式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)7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次? Hint:对于任何形如0 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)//求方程ax^2+bx+c=0的实根的算法 //输入:实系数a,b,c//输出:实根或者无解信息 If a≠0D←b*b-4*a*c If D>0temp←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=0if 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=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. 考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.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.(古老的七桥问题) 第2章习题7.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n)∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。
以下是一些典型的算法设计与分析习题及其答案。
习题1：二分查找算法问题描述：给定一个已排序的整数数组，编写一个函数来查找一个目标值是否存在于数组中。
答案：二分查找算法的基本思想是将数组分成两半，比较中间元素与目标值的大小，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。
这个过程会不断重复，直到找到目标值或搜索范围为空。
```pythondef binary_search(arr, target):low, high = 0, len(arr) - 1while low <= high:mid = (low + high) // 2if arr[mid] == target:return Trueelif arr[mid] < target:low = mid + 1else:high = mid - 1return False```习题2：归并排序算法问题描述：给定一个无序数组，使用归并排序算法对其进行排序。
答案：归并排序是一种分治算法，它将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。
```pythondef merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1arr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print("Sorted array is:", arr)```习题3：动态规划求解最长公共子序列问题问题描述：给定两个序列，找到它们的最长公共子序列。
习题13．设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求分别给出伪代码和C++描述。
//采用分治法//对数组先进行快速排序//在依次比较相邻的差#include <iostream>using namespace std;int partions(int b[],int low,int high){int prvotkey=b[low];b[0]=b[low];while (low<high){while (low<high&&b[high]>=prvotkey)--high;b[low]=b[high];while (low<high&&b[low]<=prvotkey)++low;b[high]=b[low];}b[low]=b[0];return low;}void qsort(int l[],int low,int high){int prvotloc;if(low<high){prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high}}void quicksort(int l[],int n){qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个}int main(){int a[11]={0,2,32,43,23,45,36,57,14,27,39};int value=0;//将最小差的值赋值给valuefor (int b=1;b<11;b++)cout<<a[b]<<' ';cout<<endl;quicksort(a,11);for(int i=0;i!=9;++i){if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) )value=a[i+1]-a[i];elsevalue=a[i+2]-a[i+1];}cout<<value<<endl;return 0;}4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。
算法设计与分析第三版第四章课后习题答案4.1 线性时间选择问题习题4.1问题描述：给定一个长度为n的无序数组A和一个整数k，设计一个算法，找出数组A中第k小的元素。
算法思路：本题可以使用快速选择算法来解决。
快速选择算法是基于快速排序算法的思想，通过递归地划分数组来找到第k小的元素。
具体步骤如下： 1. 选择数组A的一个随机元素x作为枢纽元。
2. 使用x将数组划分为两个子数组A1和A2，其中A1中的元素小于等于x，A2中的元素大于x。
3. 如果k等于A1的长度，那么x就是第k小的元素，返回x。
4. 如果k小于A1的长度，那么第k小的元素在A1中，递归地在A1中寻找第k小的元素。
5. 如果k大于A1的长度，那么第k小的元素在A2中，递归地在A2中寻找第k-A1的长度小的元素。
6. 递归地重复上述步骤，直到找到第k小的元素。
算法实现：public class LinearTimeSelection {public static int select(int[] A, int k) { return selectHelper(A, 0, A.length - 1, k);}private static int selectHelper(int[] A, int left, int right, int k) {if (left == right) {return A[left];}int pivotIndex = partition(A, left, righ t);int length = pivotIndex - left + 1;if (k == length) {return A[pivotIndex];} else if (k < length) {return selectHelper(A, left, pivotInd ex - 1, k);} else {return selectHelper(A, pivotIndex + 1, right, k - length);}}private static int partition(int[] A, int lef t, int right) {int pivotIndex = left + (right - left) / 2;int pivotValue = A[pivotIndex];int i = left;int j = right;while (i <= j) {while (A[i] < pivotValue) {i++;}while (A[j] > pivotValue) {j--;}if (i <= j) {swap(A, i, j);i++;j--;}}return i - 1;}private static void swap(int[] A, int i, int j) {int temp = A[i];A[i] = A[j];A[j] = temp;}}算法分析：快速选择算法的平均复杂度为O(n)，最坏情况下的复杂度为O(n^2)。
算法设计与分析常见习题及详解⽆论在以后找⼯作还是⾯试中，都离不开算法设计与分析。
本博⽂总结了相关算法设计的题⽬，旨在帮助加深对贪⼼算法、动态规划、回溯等算法的理解。
1、计算下述算法执⾏的加法次数：输⼊：n =2^t //t 为整数输出：加法次数 k K =0while n >=1 do for j =1 to n do k := k +1 n = n /2return k解析：第⼀次循环执⾏n次加法，第⼆次循环执⾏1/2次加法，第三次循环执⾏1/次加法…因此，上述算法执⾏加法的次数为==2n-12、考虑下⾯每对函数 f(n) 和 g(n) ，如果它们的阶相等则使⽤Θ记号，否则使⽤ O 记号表⽰它们的关系解析：前导知识：，因为解析：，因为解析:，因为解析：解析:3、在表1.1中填⼊ true 或 false解析：利⽤上题的前导知识就可以得出。
2=21/4n +n +21n +41...+1n +n −n +21n −21n +41....−1f (n )=(n −2n )/2，g (n )=6n1<logn <n <nlogn <n <2n <32<n n !<n ng (n )=O (f (n ))f (n )=Θ(n ),g (n )=2Θ(n )f (n )=n +2,g (n )=n n 2f (n )=O (g (n ))f (n )=Θ(n ),g (n )=Θ(n )2f (n )=n +nlogn ,g (n )=n nf (n )=O (g (n ))f (n )=Θ(nlogn ),g (n )=Θ(n )23f (n )=2(log ),g (n )=n 2logn +1g (n )=O (f (n ))f (n )=log (n !),g (n )=n 1.05f (n )=O (g (n ))4、对于下⾯每个函数 f(n),⽤f(n) =Θ(g(n))的形式，其中g(n)要尽可能简洁，然后按阶递增序排列它们（最后⼀列）解析：最后⼀个⽤到了调和公式：按阶递增的顺序排列：、、、、、、、、、(n −2)!=Θ((n −2)!)5log (n +100)=10Θ(logn )2=2n Θ(4)n 0.001n +43n +31=Θ(n )4(lnn )=2Θ(ln n )2+3n logn =Θ()3n 3=n Θ(3)n log (n !)=Θ(nlogn )log (n )=n +1Θ(nlogn )1++21....+=n1Θ(logn )=∑k =1nk 1logn +O (1)1++21....+n 15log (n +100)10(lnn )2+3n logn log (n !)log (n )n +10.001n +43n +313n 22n (n −2)!5、求解递推⽅程前导知识：主定理前导知识：递归树：例⼦：递归树是⼀棵节点带权的⼆叉树，初始递归树只有⼀个结点，标记为权重W(n)，然后不断进⾏迭代，最后直到树种不再含有权为函数的结点为⽌，然后将树根结点到树叶节点的全部权值加起来，即为算法的复杂度。
算法设计与分析第二版课后习题及解答算法设计与分析基础课后练习答案习题1.14.设计一个计算的算法,n是任意正整数。
除了赋值和比较运算,该算法只能用到基本的四则运算操作。
算法求 //输入:一个正整数n2//输出:。
step1:a1; step2:若a*an 转step 3,否则输出a; step3:aa+1转step 2;5. a.用欧几里德算法求gcd(31415,14142)。
b. 用欧几里德算法求gcd(31415,14142),比检查min{m,n}和gcd(m,n)间连续整数的算法快多少倍?请估算一下。
a. gcd31415, 14142 gcd14142, 3131 gcd3131, 1618 gcd1618, 1513 gcd1513, 105 gcd1513, 105 gcd105, 43 gcd43, 19 gcd19, 5 gcd5, 4 gcd4, 1 gcd1, 0 1.b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。
连续整数检测算法在14142每次迭代过程中或者做了一次除法,或者两次除法,因此这个算法做除法的次数鉴于1?14142 和 2?14142之间,所以欧几里德算法比此算法快1?14142/11 ≈1300 与2?14142/11 ≈ 2600 倍之间。
6.证明等式gcdm,ngcdn,m mod n对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:如果d整除u和v, 那么d一定能整除u±v;如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和rm mod nm-qn;显然,若d能整除n和r,也一定能整除mr+qn和n。
数对m,n和n,r具有相同的公约数的有限非空集,其中也包括了最大公约数。
故gcdm,ngcdn,r7.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0mn的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcdm,ngcdn,m并且这种交换处理只发生一次.8.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?1次b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?5次gcd5,8习题1.21.农夫过河P?农夫W?狼 G?山羊 C?白菜2.过桥问题1,2,5,10---分别代表4个人, f?手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c0的实根,写出上述算法的伪代码可以假设sqrtx是求平方根的函数算法Quadratica,b,c//求方程ax^2+bx+c0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D0temp←2*ax1←-b+sqrtD/tempx2←-b-sqrtD/tempreturn x1,x2else if D0 return ?b/2*ael se return “no real roots”else //a0if b≠0 return ?c/belse //ab0if c0 return “no real numbers”else return “no real roots”5. 描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答:a.将十进制整数转换为二进制整数的算法输入:一个正整数n输出:正整数n相应的二进制数第一步:用n除以2,余数赋给Kii0,1,2,商赋给n第二步:如果n0,则到第三步,否则重复第一步第三步:将Ki按照i从高到低的顺序输出b.伪代码算法 DectoBinn//将十进制整数n转换为二进制整数的算法//输入:正整数n//输出:该正整数相应的二进制数,该数存放于数组Bin[1n]中i1while n!0 doBin[i]n%2;nintn/2;i++;while i!0 doprint Bin[i];i--;9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.算法略对这个算法做尽可能多的改进.算法 MinDistanceA[0..n-1]//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements 习题1.3考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.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.古老的七桥问题第2章习题2.17.对下列断言进行证明:如果是错误的,请举例a. 如果tn∈Ogn,则gn∈Ωtnb.α0时,Θαgn Θgn解:a这个断言是正确的。
黄宇《算法设计与分析》课后习题解析（⼆）第2章：从算法的视⾓重新审视数学的概念2.1：(向下取整)题⽬：请计算满⾜下⾯两个条件的实数的区间解析：根据向下取整的含义，令，讨论a的取值范围即可解答：令，则可得：即：故的取值区间为：2.2: (取整函数)题⽬：证明：对于任意整数,（提⽰：将n划分为）。
解析：根据提⽰将n进⾏划分，根据取整函数的定义⽤k表⽰取整函数，即可证明；证明如下：因为对于任意整数,可划分为，则:① ；② ；综上：对于任意整数,, 得证；2.3: (斐波拉契数列)对于斐波拉契数列，请证明：1）题⽬：是偶数当且仅当n能被3整除解析：由斐波拉契数列的递归定义式，容易联想到数学归纳法；证明如下：（采⽤数学归纳法）i)当n = 1,2,3时，依次为1，1，2，符合命题；ii)假设当（k>=1）时命题均成⽴，则：① 当n = 3k+1时，是奇数，成⽴；② 当n = 3k+2时，是奇数，成⽴；③ 当 n = 3(k+1)时，是偶数，成⽴；综上：归纳可得为偶数当且仅当，得证;2）题⽬：x x =1+a (0<a <1)x =1+a (0<a <1)⌊x ⌋=1⇒⌊x ⌋=21⌊x ⌋=2⌊1+a +22a ⌋=1a +22a <1⇒0<a <−21⇒1<a +1<⇒21<x <2x (1，)2n ≥1⌈log (n +1)⌉=⌊logn ⌋+12≤k n ≤2−k +11n ≥12≤k n ≤2−k +11k +1=⌈log (2+k 1)⌉≤⌈log (n +1)⌉≤⌈log (2)⌉=k +1k +1=>⌈log (n +1)⌉=k +1k =⌊log (2)⌋≤k ⌊logn ⌋≤⌊log (2−k +11)⌋=k =>⌊logn ⌋=k n ≥1⌈log (n +1)⌉=k +1=⌊logn ⌋+1F n F n n ≤3k F =n F +n −1F =n −2F +3k F =3k −1>F 3k +1F =n F +3k +1F =3k >F 3k +2F =n F +3k +2F =3k +1>F 3k +3F n 3∣n F −n 2F F =n +1n −1(−1)n +1解析：同1）理，容易联想到数学归纳法证明如下：（采⽤数学归纳法）i)当n = 2时，, 易知成⽴；ii)假设当 n = k 时命题成⽴，① 若k = 2m, 则,当n = k+1 = 2m+1时，要证命题成⽴，即证： => ,代⼊递推式, 得：, 易知是恒等式，故命题成⽴；②当 k=2m+1时，同①理可证命题成⽴；综上：归纳可得，得证；2.4：(完美⼆叉树)给定⼀棵完美⼆叉树，记其节点数为，⾼度为，叶节点数为，内部节点数为1）题⽬：给定上述4个量中的任意⼀个，请推导出其他3个量解析：根据完美⼆叉树的结构特点易得解答：（仅以已知⾼度h推导其他三个量为例，其余同理）已知⾼度为h，可得：节点数：叶节点数：内部节点数：2）题⽬：请计算完美⼆叉树任意⼀层的节点个数：① 如果任意指定深度为的⼀层节点，请计算该层节点个数；② 如果任意指定⾼度为的⼀层节点，请计算该层节点个数；解析：根据完美⼆叉树的结构特点易得（注意节点深度和节点⾼度是互补的，相加为树⾼）解答：① ; ② ;2.5: (⼆叉树的性质)对于⼀棵⾮空的⼆叉树T，记其中叶节点的个数为，有1个⼦节点的节点个数为，有两个⼦节点的节点个数为1）题⽬：如果T是⼀棵2-tree，请证明。
