算法导论答案（第一章）
发布时间
阅读量：
阅读量
练习
1.1-1 需要排序的例子：火车购票中查询当天最早的车次；计算凸壳的例子：求包含平面上所有点的连线的最小面积。
1.1-2 有关效率的度量：每小时工资额就是对劳动效率的度量。
1.1-3 链表，优点是插入删除方便，缺点是查找元素需要遍历很多元素，不能随机存取数据。
1.1-4 最短路径和旅行商问题的相似之处在于都是寻找从A点到B点之间的最短距离，区别是，旅行商问题的路径中边的权值可能有不同。路径的长短不是算法追求的度量
1.1-5 只有最佳解才行的问题：没找到。近似最佳的解：比如地图上从A到B的最佳乘坐方式（公交系统内如何换乘）
1.2-1 应用层需要算法内容的一个例子是之前做过的vDesigner GUI 中net点和连线联动、自动layout位置等。涉及算法的功能包括链接两个net之间的线段如何调整位置，如何自动规整等。
1.2-2 对于只有一个元素的序列，插入排序执行步骤8，并归排序执行步骤0，这不符合实际的情况，只有一个元素的序列，不需要排序。对有多余一个元素的序列，当n最大43时，插入排序优于并归排序。
import math
def insert_sort_step_num(n):
return 8 * n * n
def merge_sort_step_num(n):
return 64 * n * math.log(n, 2)
if __name__ == '__main__':
i = 1
while True:
i += 1
print i, insert_sort_step_num(i), merge_sort_step_num(i), insert_sort_step_num(i) < merge_sort_step_num(i)
if insert_sort_step_num(i) >= merge_sort_step_num(i):
print 'hit i:', i
break
1.2-3 这个与上一题类似，n=15时，满足题目假设
def algorithm_a_step_num(n):
return 100 * n * n
def algorithm_b_step_num(n):
return pow(2, n)
if __name__ == '__main__':
i = 1
while True:
i += 1
print i, algorithm_a_step_num(i), algorithm_b_step_num(i), algorithm_a_step_num(i) < algorithm_b_step_num(i)
if algorithm_a_step_num(i) < algorithm_b_step_num(i):
print 'hit i:', i
break
思考题
1-1
全部评论 (0)
还没有任何评论哟~