以下是Python作业描述，需要答案请联系本人微信scratch8。
CSE 30 Fall 2021 – Homework 3
Instructions
Please disregard the YOUR NAME and COLLABORATORS above. They are put there atomatically by the grading tool. You can find instructions on how to work on a homework on Canvas. Here is a short summary:
Submitting your work To submit your work:
First, click on “Runtime > Restart and run all”, and check that you get no errors. This enables you to catch any error you might have introduced, and not noticed, due to your running cells out of order.
Second, download the notebook in .ipynb format (File > Download .ipynb) and upload the
.ipynb file to this form.
You can submit multiple times; the last submission before the deadline is the one that counts.
Homework format
For each question in this notebook, there is:
A text description of the problem.
One or more places where you have to insert your solution. You need to complete every place marked:
# YOUR CODE HERE 在下面填写你的代码
and you should not modify any other place.
One or more test cells. Each cell is worth some number of points, marked at the top. You should not modify these tests cells. The tests pass if no error is printed out: when there is a statement that says, for instance:
assert x == 2
then the test passes if x has value 2, and fails otherwise. You can insert a print(x) (for this case!) somewhere if you want to debug your work; it is up to you.
Notes:
Your code will be tested both according to the tests you can see (the assert statements you can see), and additional tests. This prevents you from hard-coding the answer to the particular questions posed. Your code should solve the general intended case, not hard-code the particular answer for the values used in the tests.
Please do not delete or add cells! The test is autograded, and if you modify the test by adding or deleting cells, even if you re-add cells you delete, you may not receive credit.
Please do not import modules that are not part of the standard library. You do not need any, and they will likely not available in the grading environment, leading your code to fail.
If you are inactive too long, your notebook might get disconnected from the back-end. Your work is never lost, but you have to re-run all the cells before you continue.
You can write out print statements in your code, to help you test/debug it. But remember: the code is graded on the basis of what it outputs or returns, not on the basis of what it prints.
TAs and tutors have access to this notebook, so if you let them know you need their help, they can look at your work and give you advice.
Grading
Each cell where there are tests is worth a certain number of points. You get the points allocated to a cell only if you pass all the tests in the cell.
The tests in a cell include both the tests you can see, and other, similar, tests that are used for grading only. Therefore, you cannot hard-code the solutions: you really have to solve the essence of the problem, to receive the points in a cell.
Code of Conduct
Work on the test yourself, alone.
You can search documentation on the web, on sites such as the Python documentation sites, Stackoverflow, and similar, and you can use the results.
You cannot share your work with others or solicit their help.
Problem: Dicothomic Search
You are given a sorted list l , and you need to look into it for an element x . Of course, you could start looking at the beginning for x , and continue until you are done:
for el in l:
if el == x:
…
or you can do the same with l.index(x) , but these approaches do not take advantage of the fact that l is sorted, and take an amount of time that is proportional to the length of the list l : on average, you will find x about halfway through.
When you search in a dictionary, you don’t take this approach. If you look for “hedgehog”, you open the dictionary in the middle, and based on that you decide whether to search in the first half or the second half. This continues until you narrow the range of search to a single page.
We want to follow the same idea to search in our list. We ask you to write a recursive function
search(l, x, i, k) which searches for the earliest occurrence of x in the list l from position i to position k – 1 , inclusive, and returns the smallest index at which x has been found, or None if it has not been found.
To find if x is in the list, you would call search(l, x, 0, len(l)) . The function search should work as follows:
If k <= i , there is nowhere you can search, and you return None . If k = i + 1 , then you know what to check!
If k > i + 1 , then there is more than one position to consider. You split the range you have to search in the middle, say, at j = i + (k – i) // 2 , and then look at l[j] . Based on that, you decide whether to search (calling search recursively) from i to j , or from j to k .
Note: in this exercise, the whole point is to use recursion, and to avoid accessing the list too many times. If you have code that reads (for example):
if l[k] == …
…
if l[k] < …
…
then that code would be accessing l[k] twice. You may want to cache the value of l[k] in an intermediate place to avoid such accesses:
lk = l[k]
if lk == …
…
if lk < …
…
|
This is only an example; the actual piece of code is not like the one above, but the idea is what
def binary_search(l, x): “””Helper function.”””
return search(l, x, 0, len(l))
## Here is a place for you to play with your code.
# YOUR CODE HERE
First, let’s do a small sanity check, checking that at least you find the correct element.
# 5 points.
assert binary_search([1, 2, 3, 4, 5, 6], 2) == 1
assert binary_search([1, 2, 3, 5, 6, 7], 4) is None
# We did say, the earliest occurrence.
assert binary_search([1, 2, 3, 3, 3, 4, 5], 3) == 2
assert binary_search([1, 2, 2, 2, 2, 3, 4, 5], 2) == 1
assert binary_search([1, 1, 1, 1, 1, 2, 3], 1) == 0
To keep you honest, we implement two tricks. First, we will not let you work on a list, but rather, on a WeakList, which counts how many times it has been accessed, and if you access it too many times, it raises an exception. This will force you to implement dicothomic search rather than just scanning the list.
To help in debugging, we make a WeakList also print out where it is accessed.
import math
class TooManyAccesses(Exception): pass
class WeakList(object):
def init (self, *args, verbose=True):
“””You create a tired list passing it the elements as arguments.”””
self.l = list(args) # Do not rely on this being called l… it will be renamed in gra self.num_accesses = 0
self.max_accesses = int(math.log2(len(self.l))) + 2 self.verbose = verbose
def len (self):
“””This implements the len() method.””” return len(self.l)
def getitem (self, i):
“””This implements the lookup via [i] syntax.””” if self.verbose:
print(“Accessed position”, i) self.num_accesses += 1
if self.num_accesses > self.max_accesses:
raise TooManyAccesses(“You have exceeded the maximum of {} accesses”.format(self. return self.l[i]
## Here is a place for you to play with your code.
# YOUR CODE HERE
We can now test that you can find the earliest occurrence of an element in a list without accessing too many elements.
# 5 points. Some simple tests. l = WeakList(3, 4, 5, 6, 7, 8)
assert binary_search(l, 8) == 5
l = WeakList(3, 4, 4, 5, 7, 8)
assert binary_search(l, 4) == 1
l = WeakList(3, 4, 4, 5, 7, 8)
assert binary_search(l, 5) == 3
l = WeakList(3, 5, 6, 7)
assert binary_search(l, 8) is None
# 15 points. Now, some randomized tests. import random
for _ in range(1000):
n = random.randint(10, 100)
l = list(random.choices(list(range(100)), k=n)) l.sort()
k = random.randint(0, 99)
wl = WeakList(*l, verbose=False)
# print(“Searching”, l, “for”, k) if k in l:
# print(“It should be there.”) bs = binary_search(wl, k)
ix = l.index(k)
assert bs == ix, “Error: l: {}, k: {}, index: {}, binary: {}”.format(l, k, ix, bs) else:
# print(“It should not be there.”)
assert binary_search(wl, k) is None, “Error: {} found in {}”.format(k, l)
Next, we know that students typically loathe recursion, and would rather write unfathomable goops of code rather than use a simple recursive solution. We are not talking about you obviously. But just to keep the other students honest, we define here a decorator that checks that the function is indeed called recursively.
from bdb import Bdb import sys
import traceback
class NonRecursive(Exception): pass
class RecursionDetector(Bdb): def do_clear(self, arg):
pass
def init (self, depth=1): Bdb. init (self) self.depth = depth self.stack = [] self.passed = False
def user_call(self, frame, argument_list): code = frame.f_code
depth = sum([code == c for c in self.stack]) if depth >= self.depth:
self.passed = True self.stack.append(code)
def user_return(self, frame, return_value): assert self.stack[-1] == frame.f code
self.stack.pop()
def test_recursion(func, depth=1):
detector = RecursionDetector(depth=depth) detector.set_trace()
try:
r = func() except:
traceback.print_exc() r = None
finally:
sys.settrace(None) return r
def test_enough_recursion(wl, el):
“””Tests that you do enough recursion when calling binary_search(wl, el)””” n = int(math.log2(len(wl))) – 1
return test_recursion(lambda: binary_search(wl, el), depth=n)
assert test_recursion(lambda: binary_search([2, 3, 4, 5, 5, 6, 7, 8, 10, 11, 12], 5)) == 3
# 15 points: Let’s check that you solved the problem through recursion. for _ in range(1000):
n = random.randint(10, 100)
l = list(random.choices(list(range(100)), k=n)) l.sort()
k = random.randint(0, 99)
wl = WeakList(*l, verbose=False) idx = test_enough_recursion(wl, k) if k in l:
assert l.index(k) == idx else:
assert idx is None
