《算法设计与程序分析习题精选含答案(第四章).docx》由会员分享，可在线阅读，更多相关《算法设计与程序分析习题精选含答案(第四章).docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法设计与程序分析习题精选含答案(第四章) 作业四 4.1.2 Alternating glasses a. There are 2n glasses standing next to each other in a row, the first n of them filled with a soda drink and the remaining n glasses empty. Make the glasses alternate in a filled-empty-filled-empty pattern in the minimum number of glass moves. Ga
2、r78 b. Solve the same problem if 2n glassesn with a drink and n emptyare initially in a random order 答： 图1 杯子分组 a.两个为一组，在前n个杯子中判断偶数的杯子是否为空，不为空与同组的进行交换，共需 要交换n/2次，考虑n为奇数对n/2进行向下取整即可。 b.由于最终偶数位置为空杯，奇数位置为满杯，从第一项开始遍历，如果在奇数位置出现空 杯与后面偶数位置出现的第一个满杯进行交换，如果偶数位置出现满杯则与后面奇数出现的第一个空杯进行交换，每次交换使得两个位置满足条件，最坏情况是2n位置均为
3、乱序，则需要交换n次，最好的情况为2n位置均满足条件，则交换次数为0,n 4.1.7 Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order. 4.2.1 Apply the DFS-based algorithm to solve the topological sorting problem for the following digraphs: 答： (a) f e g b c a d 从堆栈中弹出：efgbcad,反转输出为:dacbgfe (b) 由于存在回环b图不是无向回环图。
4、4.2.5 Apply the source-removal algorithm to the digraphs of Problem 1 above. 答：（a）得到的解为：dacbgfe 图2 源删除算法 图2 b的源删除算法 （b）无解 4.3.7 Write pseudocode for a recursive algorithm for generating all 2n bit strings of length n. 4.4.10 (a) Write pseudocode for the divide-into-three algorithm for the fake-coin
5、problem. Make sure that your algorithm handles properly all values of n, not only those that are multiples of 3. (b) Set up a recurrence relation for the number of weighings in the divide-intothree algorithm for the fake-coin problem and solve it for n = 3k. (c) For large values of n, about how many
6、 times faster is this algorithm than the one based on dividing coins into two piles? Your answer should not depend on n. 答： (a)如果硬币为3K，则将硬币分为三堆K枚硬币；如果硬币为3K+1，则将硬币分为两堆K+1，一堆K-1；如果硬币为3K+2则将硬币分为两堆K+1，一堆K。称重两堆个数一样的，如果重量相同，则假币在第三堆中，对第三堆进行操作再进行操作，不断重复直至找出假币。如果有一堆轻（假设假币为轻的）则假币在这堆里，对该堆进行操作再进行操作。 (b)第n次分每堆为3
7、k?n，最坏的情况为n为k时。 =log23 (c)log2n log3n 4.5.2 Apply quickselect to find the median of the list of numbers 9, 12, 5, 17, 20, 30, 8. 答： import random # 快速选择排序 def quicksort(l): if len(l) base return quicksort(left)+base+quicksort(right) lists =list(eval(input(请输入列表，使用逗号隔开: ) lists =quicksort(lists) L =len(lists) if L %2=0: print(listsint(L /2)+ listsint(L /2)+1)/2) else: print(listsint(L -1)/2)