python第二版第六章课后题答案嵩天 python第2版第五章课后答案 |
您所在的位置：网站首页 › python嵩天第二版答案 › python第二版第六章课后题答案嵩天 python第2版第五章课后答案 |
本人手写或借阅资料，仅供参考，有错误欢迎指正。 本章需调用第三章课后作业部分内容 import random from homework.homework3 import UnorderedList import timeit#5.1 进行随机实验，测试顺序搜索算法与二分搜索算法在处理整数列表时的差异 #顺序搜索 def sequentialsearch(ml, v): pos = 0 found = False while pos < len(ml) and not found: if ml[pos] == v: found = True else: pos += 1 return found #二分搜索 def binarysearch(ml, v): l, r = 0, len(ml) - 1 found = False while l v: r = mid - 1 else: l = mid + 1 return found #性能比较 mllen = 100000 ml = list(range(mllen)) def searchperformance(): t = timeit.Timer("sequentialsearch(ml, %d)" % random.randrange(mllen), "from homework.homework5 import random, sequentialsearch, ml") seqtime = t.timeit(number = 100) t = timeit.Timer("binarysearch(ml, %d)" % random.randrange(mllen), "from homework.homework5 import random, binarysearch, ml") bintime = t.timeit(number = 100) print("%10.3f, %10.3f" % (seqtime, bintime))#5.2 随机生成一个有序的整数列表。通过基准测试分析文中给出的二分搜索函数（递归版本 #与循环版本）。请解释你得到的结果。 #递归版本的二分搜索 def binarysearchrecursion(ml, v): if len(ml) == 0: return else: mid = len(ml) // 2 if ml[mid] == v: return True else: if ml[mid] > v: return binarysearchrecursion(ml[:mid], v) else: return binarysearchrecursion(ml[mid + 1:], v) #性能比较 def binsearchperform(): t = timeit.Timer("binarysearchrecursion(ml, %d)" % random.randrange(mllen), "from homework.homework5 import random, \ binarysearchrecursion, ml") bin1time = t.timeit(number = 100) t = timeit.Timer("binarysearch(ml, %d)" % random.randrange(mllen), "from homework.homework5 import random, binarysearch, ml") bin2time = t.timeit(number = 100) print("%10.3f, %10.3f" % (bin1time, bin2time))#5.3 不用切片运算符，实现递归版本的二分搜索算法。别忘了传入头元素和尾元素的下标。 #随机生成一个有序的整数列表，并进行基准测试。 def binarysearchrecursion2(ml, v, l, r): if l > r: return mid = (l + r) // 2 if ml[mid] == v: return True else: if ml[mid] > v: return binarysearchrecursion2(ml, v, l, mid - 1) else: return binarysearchrecursion2(ml, v, mid + 1, r) #性能比较 def binsearchrecurperform(): t = timeit.Timer("binarysearchrecursion(ml, %d)" % random.randrange(mllen), "from homework.homework5 import random, \ binarysearchrecursion, ml") bin1time = t.timeit(number = 100) t = timeit.Timer("binarysearchrecursion2(ml, %d, 0, mllen - 1)" % random.randrange(mllen), "from homework.homework5 import random,\ binarysearchrecursion2, ml, mllen") bin2time = t.timeit(number = 100) print("%10.3f, %10.3f" % (bin1time, bin2time))#5.4 为散列表实现len 方法（__len__） #5.5 为散列表实现in 方法（__contains__）。 #5.7 在本章中，散列表的大小为11。如果表满了，就需要增大。请重新实现put 方法，使 #得散列表可以在载荷因子达到一个预设值时自动调整大小（可以根据载荷对性能的影 #响，自己决定预设值）。 #5.8 实现平方探测这一再散列技巧 class HashTable: def __init__(self, hsize): self.size = hsize self.num = 0 self.rehashsquarenum = 0 self.loadrate = 0.5 self.slots = [None] * self.size self.data = [None] * self.size def hashfunction(self, key, size): return key % size def rehashlinear(self, oldhash, size): return (oldhash + 1) % size def rehashsquare(self, oldhash, size): self.rehashsquarenum += 1 return (oldhash + self.rehashsquarenum ** 2) % size def put(self, key, data): if self.num / self.size > self.loadrate: print(self.num, self.size, '扩容中') self.num = 0 oldslot = self.slots[:] olddata = self.data[:] self.slots = [None] * self.size * 2 self.data = [None] * self.size * 2 self.size *= 2 for (s, d) in zip(oldslot, olddata): if s != None: self.put(s, d) hashvalue = self.hashfunction(key, self.size) if self.slots[hashvalue] == None: self.num += 1 self.slots[hashvalue] = key self.data[hashvalue] = data else: if self.slots[hashvalue] == key: self.data[hashvalue] = data else: nextslot = self.rehashlinear(hashvalue, self.size) while self.slots[nextslot] != None and self.slots[nextslot] != key: nextslot = self.rehashlinear(nextslot, self.size) if self.slots[nextslot] == None: self.num += 1 self.slots[nextslot] = key self.data[nextslot] = data else: self.data[nextslot] = data def get(self, key): startslot = self.hashfunction(key, self.size) data = None stop = False found = False position = startslot while self.slots[position] != None and not found and not stop: if self.slots[position] == key: found = True data = self.data[position] else: position = self.rehash(position, self.size) if position == startslot: stop = True return data def __getitem__(self, key): return self.get(key) def __setitem__(self, key, value): return self.put(key, value) def __len__(self): return self.num def __contains__(self, key): return self.get(key) != None def hashdel(self, key): hashvalue = self.hashfunction(key, self.size) if self.slots[hashvalue] == None: return else: self.slots[hashvalue] = None self.data[hashvalue] = None def HashTabletest(): ht = HashTable(2) ht.put(1, 1) ht.put(2, 2) ht.put(3, 3) ht.put(5, 5) ht.put(7, 7) print(ht[7])#5.6 采用链接法处理冲突时，如何从散列表中删除元素？如果是采用开放定址法，又如何做 #呢？有什么必须处理的特殊情况？请为HashTable 类实现del 方法。 class LinkedHashTable(HashTable): def __init__(self, hsize): super().__init__(hsize) self.slots = [UnorderedList()] * self.size def put(self, key, data): hashvalue = self.hashfunction(key, self.size) self.num += 1 self.slots[hashvalue].add(data) def get(self, key): getslot = self.hashfunction(key, self.size) return str(self.slots[getslot]) def hashdel(self, key): hashvalue = self.hashfunction(key, self.size) self.slots[hashvalue] = UnorderedList() def LinkedHashTabletest(): lh = LinkedHashTable(11) lh.put(11, 100) lh.put(22, 200) print(lh.get(0)) lh.hashdel(0) print(lh.get(0))#5.9 使用随机数生成器创建一个含500 个整数的列表。通过基准测试分析本章中的排序算 #法。它们在执行速度上有什么差别？ #5.10 利用同时赋值特性实现冒泡排序。 #5.12 利用同时赋值特性实现选择排序。 def bubblesort(ml): for passnum in range(len(ml) - 1, 0, -1): exchange = False for i in range(passnum): if ml[i] > ml[i + 1]: ml[i], ml[i + 1] = ml[i + 1], ml[i] exchange = True if passnum and not exchange: break def selectionsort(ml): for fillslot in range(len(ml) - 1, 0, -1): positionofmax = ml.index(max(ml[0:fillslot + 1])) ml[positionofmax], ml[fillslot] = ml[fillslot], ml[positionofmax] def insertionsort(ml): for idx in range(1, len(ml)): cur = ml[idx] pos = idx while pos > 0 and ml[pos - 1] > cur : ml[pos] = ml[pos - 1] pos -= 1 ml[pos] = cur def shellsort(ml): sublistcount = len(ml) // 2 while sublistcount > 0: for sp in range(sublistcount): gapinsertionsort(ml, sp, sublistcount) sublistcount //= 2 def gapinsertionsort(ml, start, gap): for i in range(start + gap, len(ml), gap): cur = ml[i] pos = i while pos >= gap and ml[pos - gap] > cur: ml[pos] = ml[pos - gap] pos -= gap ml[pos] = cur def mergesort(ml): if len(ml) > 1: mid = len(ml) // 2 l = ml[:mid] r = ml[mid:] mergesort(l) mergesort(r) i, j ,k = 0, 0, 0 while i < len(l) and j < len(r): if l[i] < r[j]: ml[k] = l[i] i += 1 else: ml[k] = r[j] j += 1 k += 1 while i < len(l): ml[k] = l[i] i += 1 k += 1 while j < len(r): ml[k] = r[j] j += 1 k += 1 def quicksort(ml): quicksorthelper(ml, 0, len(ml) - 1) def quicksorthelper(ml, l, r): if l < r: pivotvalue = ml[l] leftmark = l + 1 rightmark = r done = False while not done: while leftmark |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |