下载文档原格式
算法设计与分析习题答案算法设计与分析是计算机科学中一个重要的领域，它涉及到算法的创建、优化以及评估。
以下是一些典型的算法设计与分析习题及其答案。
习题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]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。
算法设计技巧与分析习题答案【篇一：算法设计与分析考试题及答案】一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
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算法的思想。
3.若n=4，在机器m1和m2上加工作业i所需的时间分别为ai和bi，且(a1,a2,a3,a4)=(4,5,12,10)，(b1,b2,b3,b4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。
4.使用回溯法解0/1背包问题：n=3，c=9，v={6,10,3}，w={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。
算法设计与分析第二版课后习题及解答算法设计与分析基础课后练习答案习题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这个断言是正确的。
第六章动态规划法• P137 2 ,3, 4•2.解答:cost[i]表示从顶点i 到终点n-1 的最短路径，path[i]表示从顶点i 到终点n-1 的路径上顶点i 的下一个顶点。
cost[i]=min{cij+cost[j]}3 有5 个物品，其重量分别是{3, 2, 1, 4,5}，价值分别为{25, 20, 15, 40, 50}，背包的容量为6。
V[i][j]表示把前i 个物品装入容量为j 的背包中获得的最大价值。
最优解为（0，0，1，0，1）最优值为65. 4.序列A =(x, z , y , z , z , y,x )，B =(z , x , y , y , z , x , z )，建立两个(m+1)×(n+1)的二 维表L 和表S ，分别存放搜索过程中得到的子序列的长度和状态。
z , x , y , y , z,x , z )path[i]= 使 cij+cost[j] 最小的 j i 012345678 9 10 11 12 13 14 15 Cost[i] 18 13 16 13 10 9 12 7 6875943Path[i]145778911 11 11 13 14 14 15 15 0得到最短路径 0->1->4->7->11->14->15 , 长度为 18(a)长度矩阵L(b)状态矩阵S 。
第七章贪心算法2.背包问题:有7 个物品，背包容量W=15。
将给定物品按单位重量价值从大到小排序，结果如下：个物品，物品重量存放在数组w[n]中，价值存放在数组放在数组x[n]中。
按算法7.6——背包问题1．改变数组w 和v 的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；2．将数组x[n]初始化为0；//初始化解向量3．i=1;4．循环直到( w[i]>C )4.1 x[i]=1; //将第i个物品放入背包4.2 C=C-w[i];4.3 i++;5. x[i]=C/w[i];得出,该背包问题的求解过程为:: x[1]=1;c=15-1=14 v=6 x[2]=1; c=14-2=12V=6+10=10 x[3]=1; c=12-4=8V=16+18=34 x[4]=1; c=8-5=3V=34+15=49 x[5]=1; c=3-1=2 V=49+3=52x[6]=2/3 ; c=0; V=52+5*2/3=156/3 最优值为156/3 最优解为(1,1,1,1,1,2/3,0)) (x[i]按排序后物品的顺序构造)5.可以将该问题抽象为图的着色问题,活动抽象为顶点,不相容的活动用边相连(也可以将该问题理解为最大相容子集问题,重复查找剩余活动的最大相容子集,子集个数为所求).具体参见算法7.3 算法7.3——图着色问题1．color[1]=1; //顶点1着颜色12．for (i=2; i<=n; i++) //其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++; //取下一个颜色4.2for (i=2; i<=n; i++) //用颜色k 为尽量多的顶点着色4.2.1 若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2 若图中与顶点i邻接的顶点着色与顶点i着颜色k 不冲突，则color[i]=k;5．输出k;第八章回溯法4.搜索空间(a) 一个无向图(b) 回溯法搜索空间最优解为（1，2，1，2，3）5.0-1 背包问题n∑w i x i≤c 1• 可行性约束函数：i =1• 上界函数：nr =∑Vi5 = 3A B *CD8 ** * 131 =12 =23 = 14 = 2 34215课后答案网（）i=k+1 1第九章分支限界法5，解：应用贪心法求得近似解：(1,4,2,3)，其路径代价为：3+5+7+6=21，这可以作为该问题的上界。
计算机算法设计与分析第4版(王晓东著)课后答
案下载
计算机算法设计与分析第4版内容简介
第1章算法概述
1.1 算法与程序
1.2 算法复杂性分析
1.3 NP完全性理论
算法分析题1
算法实现题1
第2章递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.4 大整数的乘法
2.5 Strassen矩阵乘法
2.6 棋盘覆盖
2.7 合并排序
2.8 快速排序
2.9 线性时间选择
2.10 最接近点对问题
第3章动态规划
第4章贪心算法
第5章回溯法
第6章分支限界法
第7章随机化算法
第8章线性规划与网络流
附录A C++概要
参考文献
计算机算法设计与分析第4版目录
本书是普通高等教育“十一五”__规划教材和国家精品课程教材。
全书以算法设计策略为知识单元，系统介绍计算机算法的设计方法与分析技巧。
主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回溯法、分支限界法、__化算法、线性规划与网络流等。
书中既涉及经典与实用算法及实例分析，又包括算法热点领域追踪。
为突出教材的`可读性和可用性，章首增加了学习要点提示，章末配有难易适度的算法分析题和算法实现题;配套出版了《计算机算法设计与分析习题解答(第2版)》;并免费提供电子课件和教学服务。
算法分析与设计习题答案《算法分析与设计》期末复习题及答案⼀、简要回答下列问题：1.算法重要特性是什么？2.算法分析的⽬的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述⼆分检索（折半查找）算法的基本过程。
7.背包问题的⽬标函数和贪⼼算法最优化量度相同吗？8.采⽤回溯法求解的问题，其解如何表⽰？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么⽤分治法设计的算法⼀般有递归调⽤？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。
14.⼆分检索算法最多的⽐较次数？15.快速排序算法最坏情况下需要多少次⽐较运算？16.贪⼼算法的基本思想？17.回溯法的解（x1,x2,……x n）的隐约束⼀般指什么？18.阐述归并排序的分治思路。
19.快速排序的基本思想是什么。
20.什么是直接递归和间接递归？消除递归⼀般要⽤到什么数据结构？21.什么是哈密顿环问题？22.⽤回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。
参考答案：1. 确定性、可实现性、输⼊、输出、有穷性2. 分析算法占⽤计算机资源的情况，对算法做出⽐较和评价，设计出额更好的算法。
3. 算法的时间复杂性与问题的规模相关，是问题⼤⼩n的函数。
4．当问题的规模n趋向⽆穷⼤时，影响算法效率的重要因素是T(n)的数量级，⽽其他因素仅是使时间复杂度相差常数倍，因此可以⽤T(n)的数量级(阶)评价算法。
时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
5. 最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输⼊实例下的算法所耗时间。
最坏情况下的时间复杂性取的输⼊实例中最⼤的时间复杂度：W(n) = max{ T(n，I) } , I∈Dn平均时间复杂性是所有输⼊实例的处理时间与各⾃概率的乘积和：A(n) =∑P(I)T(n，I) I∈Dn6. 设输⼊是⼀个按⾮降次序排列的元素表A[i：j] 和x，选取A[(i+j)/2]与x⽐较，如果A[(i+j)/2]=x，则返回(i+j)/2，如果A[(i+j)/2]回溯法的搜索特点是什么7. 不相同。
算法分析与设计作业及参考答案作业题目1、请分析冒泡排序算法的时间复杂度和空间复杂度，并举例说明其在实际中的应用场景。
2、设计一个算法，用于在一个未排序的整数数组中找到第二大的元素，并分析其时间复杂度。
3、比较贪心算法和动态规划算法的异同，并分别举例说明它们在解决问题中的应用。
参考答案1、冒泡排序算法时间复杂度：冒泡排序的基本思想是通过相邻元素的比较和交换，将最大的元素逐步“浮”到数组的末尾。
在最坏情况下，数组完全逆序，需要进行 n 1 轮比较和交换，每一轮比较 n i 次（i 表示当前轮数），所以总的比较次数为 n(n 1) ／ 2，时间复杂度为 O(n^2)。
在最好情况下，数组已经有序，只需要进行一轮比较，时间复杂度为 O(n)。
平均情况下，时间复杂度也为 O(n^2)。
空间复杂度：冒泡排序只在原数组上进行操作，不需要额外的存储空间，空间复杂度为 O(1)。
应用场景：冒泡排序算法简单易懂，对于规模较小的数组，或者对算法的简单性要求较高而对性能要求不是特别苛刻的场景，如对少量数据进行简单排序时，可以使用冒泡排序。
例如，在一个小型的学生成绩管理系统中，需要对一个班级的少量学生成绩进行排序展示，冒泡排序就可以满足需求。
2、找到第二大元素的算法以下是一种使用遍历的方法来找到未排序整数数组中第二大元素的算法：｀｀｀pythondef find_second_largest(arr)：largest ＝ arr0second_largest ＝ float(＇inf'）for num in arr:if num ＞ largest:second_largest ＝ largestlargest ＝ numelif num ＞ second_largest and num!＝ largest:second_largest ＝ numreturn second_largest｀｀｀时间复杂度分析：这个算法需要遍历数组一次，所以时间复杂度为O(n)。
算法设计技巧与分析参考答案第1章算法分析基本概念1.1(a)6 (b)5 (c)6 (d)61.4算法执行了7+6+5+4+3+2+1=28次比较1.5(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。
(b) 算法MODSELECTIONSORT执行的元素赋值的最多次数是3(1)2n n ,元素已按非升序排列的时候达到最小值。
1.7由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。
1.11由上图可以得出比较次数为5+6+6+9=26次。
1.13FTF,TTT,FTF,TFF,FTF 1.16(a) 执行该算法，元素比较的最少次数是n-1。
元素已按非降序排列时候达到最小值。
(b) 执行该算法，元素比较的最多次数是(1)2n n -。
元素已按非升序排列时候达到最大值。
(c) 执行该算法，元素赋值的最少次数是0。
元素已按非降序排列时候达到最小值。
(d) 执行该算法，元素赋值的最多次数是3(1)2n n -。
元素已按非升序排列时候达到最大值。
(e)n 用O 符号和Ω符号表示算法BUBBLESORT 的运行时间：2()t O n =，()t n =Ω(f)不可以用Θ符号来表示算法的运行时间：Θ是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。
1.27不能用关系来比较2n 和2100n 增长的阶。
∵221lim0100100n n n →∞=≠ 2n ∴不是2(100)o n 的，即不能用关系来比较2n 和2100n 增长的阶。
1.32(a)当n 为2的幂时，第六步执行的最大次数是：12,2k k n j -==时，11[log ]log n ni i k n n n ====∑∑(b)由(a)可以得到：当每一次循环j 都为2的幂时，第六步执行的次数最大，则当33,22k kmn j ===（其中32k 取整）时，11[log(31)]log(1)n nkii i m n n ===-=-∑∑(c)用O 符号表示的算法的时间复杂性是(log )O n n 已证明n=2k 的情况，下面证明n=2k +1的情况：因为有⎥⎦⎥⎢⎣⎢+=⎥⎦⎥⎢⎣⎢21222k k所以n=2k +1时，第六步执行的最大次数仍是n log n 。
习题4.13(b)元素最大交换次数：A9~A5 各1次；A4~A3 各2次；A2最多3次；A1最多4次 最多共需16次元素交换4.13另解：考虑第i个节点，其子节点为2i，则最多可交换1次；若子节点有子节点22i, 则最多可交换2次；若…..有子节点i×2k, 则最多可交换k次；因此有i×2k≤ 19求出满足上述不等式的最大的k值即可。
i=1时, k=4;i=2时, k=3;i=3或4时, k=2;i=5~9时, k=1;因此最多交换4+3+2×2+1×5=16次6.5 用分治法求数组A[1…n]元素和，算法的工作空间是多少？输入：数组A[1…n]输出：数组的所有元素之和∑A[i] {i=1…n}SUM(low, high)1.if high = low then2.return A[low]3.else4.mid←⎣(low+high)/2⎦5.s1←SUM(low,mid)6.s2←SUM(mid+1, high)7.return s1+s28.end if工作空间：mid~Θ(logn), s1&s2~Θ(1)（后序遍历树，不断释放空间，故为常数Θ(1)），总的工作空间为Θ(logn).6.6 用分治法求元素x在数组A中出现的频次。
freq(A[low, high], x)1.if high=low then2.if A[low]=x then3.return 14.else5.return 06.end if7.else8.mid ←⎣(low+high)/2⎦9.f1 ←freq(A[low, mid])10.f2 ← freq(A[mid+1, high])11.return f1+f212.end if复杂度:T(n)=T(⎣n/2⎦)+ T(⎡n/2⎤)≈2T(n/2) (设2k≤n<2k+1) =…=2k T(n/2k) =2k T(1) = n6.16修改后的MERGESORT算法最大比较次数(1)/2()2(/2)1n n if n m T nT n n if n m-≤⎧=⎨+->⎩最小比较次数1()2(/2)/2n if n m C nC n n if n m-≤⎧=⎨+>⎩令n/2k=m≥2，展开可知：T(n)= 2k T(n/2k) + kn - (2k-1)= n/m×m(m-1)/2 + nlog(n/m)- n/m+1= n(m-1)/2 + nlog(n/m) -n/m+1若T(n)=Θ(nlogn), 其中表达式有nm, nlogn, nlogm, n/m等. 有n/m < nlogm < nm且须有nm=O(nlogn), i.e., nm ≤ c·nlogn, 则须有m≤c·logn. 可令c=1,则m≤logn. 另一方面，C(n) = 2k C(n/2k)+kn/2 = n/m×(m-1) + (n/2)log(n/m)= Θ(nlogn)6.35split(A[low,...high])1. x←A[low] //备份为x2. while (low<high){3. while (low<high && A[high]>0) --high;4. A[low] ←A[high]5. while (low<high && A[low]≤0) ++low;6.A[high] ←A[low]7.}8.A[low] ← x//这时, low=high7.3 动态规划法计算二项式系数knC ，并分析其时间复杂度。
1. for i←1 to n2. C[i,0] ← 1; C[i, i ] ←13. end for4. for i←2 to n5. for j ←1 to i-1 / min(k, i-1) //例如计算C[6,2]6. C[i,j] ←C[i-1,j-1] + C[i-1,j]7. end8. end for9. return C[n.k]复杂度分析：212(1)(1)2n n i j i i cn n c i c c i ====-=-===∑∑∑∑i-1n-121Θ(n ) 或212(1)n ni j i c kc ck n =====-=∑∑∑k O(nk)8.5硬币的面值为1, 2, 4, 8, ..., 2k, 要兑换的值n<2k+1，用贪心算法解这个问题，要求算法复杂度为O(log n)输入：k+1个不同硬币的面值，其中包括单位币（面值为1）输出：若要兑换的值n，给出各个面值硬币的数目num[0…k]1.将k+1个不同的面值按递增顺序排列，记为Value[0...k]2.num[0…k]←03.fo r j← k downto 04.num[j] ←⎣n/Value[j]⎦5.n←n - num[j]×Value[j]6.end for7.return num[0…k]8.16 修改Dijkstra算法，使它找出最短路径和它的长度。
1. X={1}; Y←V-{1}; λ[1]←0; pre[1]←0;2. for y←2 to n3. if y 相邻于1 then λ[y]←length[1,y]4. else λ[y]← ∞5. end if6. end for7. for j←1 to n-18. 令y∈Y, 使得λ[y]为最小的9. X←X∪{y}10. Y←Y - {y}11. for 每条边(y,w)12. if w∈Y and λ[y]+length[y,w]< λ[w] then13. λ[w] ←λ[y]+length[y,w]14. pre[w] ← y14. end if15. end for16.end for输出最短路径void PrintPath(int node) //输出格式为1→…→node{ if (node==1) print(“1”);else {PrintPath( pre[node] ); //先递归再输出print(“→”, node);}}色向量c[1…n]是否是合法的。
输入：图G=(V,E)，向量c[1…n]输出：flag=true 若合法着色；否则flag=false2. for i←1 to n3. if c[i]≠04. for (i,j)∈E5. if c[j]≠0 and c[j]=c[i]6. return false;7. end if8. end for9. end if10. end for11. return true色向量c[1…k]是否是部分的。
输入：图G=(V,E)，向量c[1…k]输出：true 若着色是部分的；否则输出false2. for i←1 to k3. if c[i]≠04. for (i,j)∈E5. if j≤k and c[j]≠0 and c[j]=c[i]6. return false;7. end if8. end for9. end if10. end for11. return true13.10 设计一个回溯算法来生成数字1,2,…,n的所有排列。
输入：数字1,2,…,n输出：数字1,2,…,n的所有排列c[1,…,n]向量1. for k ←1 to n2. c[k] ←03. end for5. k ←16.while k≥17. while c[k]≤n-18. c[k] ←c[k]+19. if c为合法的then output c (and goto 12)10. else if c为部分解then k ←k+111. end while12. c[k] ←013. k ←k-114. end while14.7 对二分查找算法进行随机化，即每次迭代时，随机选择剩下的位置代替搜索空间减半，假设在low与high之间每个位置被选中的概率都是相同的。
比较这种随机化算法与二分查找的表现。
输入：n个元素的升序数组A[1…n]和元素x输出：若x=A[j], 1≤j≤n, 则输出j, 否则输出01. low←1; high ←n; j←02.while(low ≤high) and (j=0)3.mid ← ⎣( low+high)/2⎦ / mid←random(low,high)4.if x=A[mid] then j ←mid5.else if x<A[mid] then high ←mid-16.else low ←mid+17.end while8.return j时间复杂度分析将每次迭代时随机选择的位置记为k ，且在low 与high 之间每个位置被选中的概率都是1/n ，期望比较次数C(n)满足[][]111111()1(1)()11(1)()11()()21()nk nk j j j C n C k C n k n C k C n k n C j C j n C j n ======+-+-=+-+-⎛⎫=++ ⎪⎝⎭=+∑∑∑∑∑n-1n-1n-1nC(n) = n + 2{C(1)+C(2)+…+C(n-2) +C(n-1)} (1) (n-1)C(n-1)= n-1 + 2{C(1)+C(2)+…+C(n-2)}(2) (2)-(1) ⇒ nC(n) - (n-1)C(n) = 1 + 2C(n-1) ⇒nC(n) = 1 + (n+1)C(n-1)nC(n) = 1 + (n+1)C(n-1) ⇒11()(1)11111(2)(*)(1)1111(1)11111(3)(*)(1)(1)(2)2...n C n C n n n n n n n n C n n n n n n n n n n n n n n C n n n n n n n +=+-+⎧⎫=+⎨⎬⎩⎭++=++---++⎧⎫=++⎨⎬--⎩⎭+++=+++-----=1n+C(n -2)n -1n -11n -1+C(n -3)n -2n -211()(2)111(2)111(2)121(2)11211121(1)(1)1(1)(2)(1)(2)n C n C n n n n C n n n n C n n n n C n n n n n n n n n C n n n n n +=++--⎧⎫+=++-⎨⎬-⎩⎭+⎧⎫=++-⎨⎬-⎩⎭+=+---+⎧⎫=+⎨⎬--⎩⎭++++-=++------n +1n(n -1)n 1n(n -1)n(n -1)111n -1n -1n (*)1n -1+C(n -3)n -2n -2(3)21(3)1221(3)1231(3)22n n C n n n n C n n n n C n n n -⎧⎫+=++-⎨⎬--⎩⎭+⎧⎫=++-⎨⎬--⎩⎭+=+---n -12+(n -1)(n -2)(n -1)(n -2)122+-n -2n -2n -1(*)11()(1)21(2)1131(3)22...11()2211//{()1}22n C n C n n nn C n n n n C n n n n n C n n C +=+-+=+---+=+---==-+=+-+=+==4n +1+C(n -4)n -3n -311nQ (可将C(n)=n 代入推导过程，以验证其正确性) 因此，随机化拟二分查找的时间复杂度为O(n)，二分查找的时间复杂度为O(log n )。
