《算法导论参考答案》由会员分享，可在线阅读，更多相关《算法导论参考答案（47页珍藏版）》请在金锄头文库上搜索。
1、第二章 算法入门由于时间问题有些问题没有写的很仔细,并且估计这里会存在不少不恰当之处。另，思考题 23 有关霍纳规则，有些部分没有完毕,故没把解答写上去，我对其 问题有疑问，请有解答措施者提供个意见。给出的代码目前也仅仅为解决问题,没有做优化，请见谅，等有时间了我再好好修改。插入排序算法伪代码INSETION-SORT(）or j 2 t lngth2do eyAnser A int tsortesequnc .j14i j-15ie i 0 nd A 𝑘𝑒𝑦6dAi+1i 1A+keyC对揑入排序算法的实现:pubicsttic id nser
2、tionSrT( Input) ereT：CompaabeTke；int i;for (int j = ； j= 0 & nputi.CompareTo(key)0;i- ） Inputi 1 = Inpti;nputi+1=key;揑入算法的设计使用的是增量(ncremental)措施:在排好子数组A1.-1后,将元素Aj揑入，形成排好序的子数组A.j这里需要注意的是由于大部分编程语言的数组都是从0开始算起,这个不伪代码觉得的数组的数是第1个有所丌同,一般要注意有几种核心值要比伪代码的小1.如果按照大部分计算机编程语言的思路，修改为：NERTION-SORT(A)1for 1 to engt
3、h2o key Aj3i j-4whie 0 and i𝑘𝑒𝑦5do i+1i6 i 1iey循环丌变式(Loop Inrian)是证明算法对的性的一种重要工具。对于循环丌变式,必须证明它的三个性质:初始化（nitialzaion)：它在循环的第一轮迭代开始之前,应当是对的的。保持(Mainteanc):如果在循环的某一次迭代开始之前它是对的的,那么,在下一次迭代开始之前,它也是对的的。终结(Termition)：当循环结束时,丌变式给了我们一种有用的性质,它有助于表明算法是对的的。运用循环丌变式对插入排序算法的对的性进行证明：初始化:j=,子数
4、组.j1只涉及一种元素,显然它是已排序的。保持:若 A.j-1是已排序的，则按照大小拟定了插入元素 A j位置之后的数组 .j显然也是已排序的。终结:当 =n1 时，退出循环，此时已排序的数组是由A1,A2,A3An构成的1n,此即原始数组A。练习3141592641582.1-1:以图 - 为模型,阐明 INSRTIO-SORT 在数组 A=上的执行过程。1415641531452641582614159126314115958263141492.1-2:重写过程ISERTIO-SORT,使之按非升序（而丌是按非降序）排序。INSERION-SORT（A）1 j 2 t length2do
5、key Aj3sertAto terd eune 1j-14i j-1wlei 0 and Ai 𝑘𝑒𝑦6doA+1Ai 17Ai1ey2.：考虑下面的查找问题:输入:一列数 A和一种值 v输出：下标 i，使得 v=Ai，戒者当v丌在 A 中浮现时为NIL。写出针对这个问题的现行查找的伪代码，它顺序地扫描整个序列以查找 。运用循环丌变式证明算法的对的性。保证所给出的循环丌变式满足三个必要的性质。LIA-SERCH（，)1 for i1 t lenghA2 if vAi3reurnireturn NI现行查找算法对的性的证明。初始化:i=1，子数组
6、为A.，只有一种元素1,如果 v=A1就返回 1,否则返回 NL， 算法显然是对的的。保持：若算法对数组1.i对的,则在数组增长一种元素 Ai1时,只需要多作一次比较, 因此显然对 A1.i+1也对的。终结：算法如果在非最坏状况下定能返回一种值此时查找成功，如果n次查找（遍历了所有的数)都没有成功，则返回 NL。算法在有限次查找后肯定可以给出一种返回值，要么阐明 查找成功并给出下标，要么阐明无此值。因此算法对的。该算法用 #实现的代码:l stati in LinearSerch(T Inpt, T v) where T：Compaaleor (ini= 0; i 1 flg17f flag=
7、8Cn11.RM(Rnom-Aes acine)模型分析一般可以较好地预测实际计算机上的性能，RA计算模型中，指令一条接一条地执行，没有并发操作。AM 模型中涉及了真实计算机中常用的指令:算术指令（加法、剑法、乘法、出发、取余、向下取整、向上取整指令）、 数据移动指令（装入、存储、复制指令)和控制指令（条件和非条件转移、子程序调用和返 回指令)。其中每天指令所需时间都为常量。RAM 模型中的数据类型有整数类型和浮点实数类型。2.算法的运营时间是指在特定输入时，所执行的基本操作数（戒步数)。插入算法的分析比较简朴,但是丌是很有用，因此略过。（在解思考题 2-1时有具体的实例 分析，请参看)3.一
8、般考察算法的最坏状况运营时间。这样做的理由有三点： .一种算法的最坏状况运营时间是在仸何输入下运营时间的一种上界。 B对于某些算法,最坏状况浮现的是相称频繁的。 .大体上来看,“平均状况“一般不最坏状况同样差。4.如果一种算法的最坏状况运营时间要比另一种算法的低，我们常常就觉得它的效率更高。练习𝚯(𝐧 ）2.2-:考虑对数组 中的 个数迚行排序的问题:一方面找出 A 中的最小元素，并将其不 1中的元素迚行互换。接着,找出 A 中的次最小元素,并将其不2中的元素迚行互换。对A 中头n-1 个元素继续这一过程。写出这个算法的伪代码,该算法称为选择排序(selecti
9、o ort）。对这个算法来说,循环丌变式是什么?为什么它仅需要在头 -1 个元素上运营,而丌是在所有n 个元素上运营？以𝚯形式写出选择排序的最佳和最坏状况下的运营时间。假设函数 N(,i，）从子数组 Ai.n中找出最小值并返回最小值的下标。SELECTION-SOR(A） fo i1 o n-12 jMIN(A，n)3 exchane A j选择排序算法对的性的证明初始化:i=1，从子数组 A1.n里找到最小值 A j，并不 Ai互换,此时子数组 A1.i只有 一种元素 A1,显然是已排序的。保持:若 A1.是已排序子数组。这里显然A1A23Ai，而1.n里最小值也必不小于 ，
10、找出此最小值不 +1互换并将 Ai+1插入 A1.i得到子数组 A1.i。1.i+1显然也是已排序的。终结:当= 时终结，此时已得到已排序数组 .-1，而是通过 - 次比较后剩余 的元素,因此 An不小于 A1.-1中仸意元素,故数组A.n也即是原数组此时已是已排序的。因此，算法对的。由于IN（)函数和SW()函数对于仸意状况运营时间都相等,故这里最佳和最坏状况下运行时间是同样的。选择算法的的 C#实现：prvate stc in Mi（ Inut,intt,inten) wher T:Comparabeintflgsart;for (in = strt;i 0）fag = i;eur lag
11、;privte sttic void wap(e T a,re T b) where T : ComparbleTtmp; t=a;a = ；b tmp;pbi statiTelctno（Iut)whee T:Iomprabler (n i = ; iInut.Lngt- 1;i+)Swap(efInptMin(It,i,Iut.Le）,e Iuti);returnIpu；22-：再次考虑线性查找问题(见练习 2.1-3)。在平均状况下,需要检查输入序列中的多少个元素？假定查找的元素是数组中任何一种元素的也许性都是相等的。在最坏状况下又怎么样呢？用相似表达的话，线性查找的平均状况和最坏状况运营时间怎么样？对你的答案加以阐明。平均：n2次。由于仸意一种元素不小于、不不
