当前我正在为CS的离散结构类中,我们在Python中为我们提供了编程分配以研究递归。他给了我们三个模块,他希望我们实施代码以使功能提供一个真实或错误的变量。这是他的代码:
class WrongTypeArgumentException( Exception ): pass
def car(lst):
"""
The first of the 3 primitive functions: return the first element of a
sequence.
.. note:: The Law of Car: The `car` function is only defined for non-empty lists.
:param lst: a non-empty sequence; passing an empty sequence will raise an exception.
:type lst: tuple
:returns: an object
:rtype: object
"""
if type(lst) is not tuple:
raise WrongTypeArgumentException("Argument is not a list.")
if len(lst)==0:
raise WrongTypeArgumentException("List has no element")
if len(lst)>=1:
return lst[0]
def cdr( lst ):
""" The second of the 3 primitive functions: return a sequence, minus the first element.
.. note:: The Law of Cdr: The `cdr` function is only defined for non-empty lists; the `cdr` of any non-empty list is always another list.
:param lst: a non-empty sequence; passing an empty sequence will raise an exception.
:type lst: tuple
:returns: a tuple; if the sequence has only one element, return an empty sequence.
:rtype: tuple
"""
if type(lst) is not tuple:
raise WrongTypeArgumentException("Argument is not a list.")
if len(lst)==0:
raise WrongTypeArgumentException("Cannot cdr on an empty list.")
if len(lst)==1:
return ()
return lst[1:]
def cons( a, lst):
""" The third of the 3 primitive functions: return the sequence created by
adding element `a` to the sequence `lst`.
.. note:: The Law of Cons: the primitive `cons` takes two arguments; the
second argument to `cons` must be a list; the result is a list.
:param a: an object
:param lst: a tuple
:type a: object
:type lst: tuple
:returns: the tuple resulting from adding parameter `a` in front of sequence
`lst`.
:rtype: tuple
"""
if type(lst) is not tuple:
raise WrongTypeArgumentException("Argument is not a list.")
return (a,) + lst
def copy_sequence( seq ):
""" Return the copy of a sequence, recursively.
:param seq: the sequence to be copied
:type seq: tuple
:returns: a tuple, identical to the sequence that has been passed in
:rtype: tuple
"""
if seq == ():
return ()
print('seq={} CONSing {} to copy_sequence( {} )'.format(seq, car(seq),
cdr(seq)))
return cons( car(seq), copy_sequence( cdr( seq) ))
def reverse_sequence( seq ):
""" Return a sequence, in the reverse order, recursively.
:param seq: the sequence to be reversed.
:type seq: tuple
:returns: a tuple, with the same elements, in the reverse order.
:rtype: tuple
"""
## A function in a function (= inner function), that recursively accumulates
## elements in the bag
def reverse_sequence_recursive( seq, bag):
if seq == ():
return bag
return reverse_sequence_recursive( cdr(seq), cons(car(seq), bag))
# Calling the inner function, with an empty bag to start with
return reverse_sequence_recursive( seq, () )
这是我们应该实现的代码:
def count_sequence( seq ):
""" Count the elements in a sequence, recursively. PROVIDE AN IMPLEMENTATION (TASK #1). This function should use **car** and **cdr**.
:param seq: the sequence whose elements are to be counted
:type seq: tuple
:returns: the numbers of elements in the sequence
:rtype: int
"""
def search_sequence( seq, item ):
""" Search a sequence for the given item. PROVIDE AN IMPLEMENTATION (TASK
#2). This function should use **car** and **cdr**.
:param seq: the sequence to be searched.
:param item: the item to be searched
:type seq: tuple
:type item: str
:returns: True if the item is contained in the sequence, False otherwise.
:rtype: bool
"""
## YOUR CODE HERE #1. Base Case 2. Recursive Call 3. RC steps toward the
base case.
pass
最后,这是他提供的测试功能,以便实际测试我们的代码是否正确。
class PyLisp_unittest( unittest.TestCase ):
sandwich = ("jelly","butter", "mustard", "bread", "pickles", "jam",
"cheese")
def test_copy_sequence_0(self):
""" Read empty tuple """
sandwich = ()
self.assertEqual( copy_sequence( sandwich ), ())
def test_copy_sequence_1(self):
""" Read single-element tuple"""
sandwich = ('mustard',)
self.assertEqual( copy_sequence( sandwich ), ('mustard',))
def test_copy_sequence_2(self):
""" Read 7-element tuple"""
sandwich = ("jelly","butter", "mustard", "bread", "pickles", "jam", "cheese")
self.assertEqual( copy_sequence( sandwich ), sandwich)
def test_reverse_sequence_0(self):
""" Reverse empty tuple """
sandwich = ()
self.assertEqual( reverse_sequence( sandwich ), ())
def test_reverse_sequence_1(self):
""" Reverse single-element tuple"""
sandwich = ('mustard',)
self.assertEqual( reverse_sequence( sandwich ), ('mustard',))
def test_reverse_sequence_2(self):
""" Reverse 7-element tuple"""
sandwich = ("jelly","butter", "mustard", "bread", "pickles", "jam", "cheese")
self.assertEqual( reverse_sequence( sandwich ), sandwich[::-1])
def test_count_sequence_0(self):
""" Count empty tuple """
sandwich = ()
self.assertEqual( count_sequence( sandwich ), 0)
def test_count_sequence_1(self):
""" Count single-element tuple"""
sandwich = ('mustard',)
self.assertEqual( count_sequence( sandwich ), 1)
def test_count_sequence_2(self):
""" Count 7-element tuple"""
sandwich = ("jelly","butter", "mustard", "bread", "pickles", "jam", "cheese")
self.assertEqual( count_sequence( sandwich ), 7)
def test_search_sequence_0(self):
""" Search empty tuple """
sandwich = ()
self.assertEqual( search_sequence( sandwich, 'ham' ), False)
def test_search_sequence_size_1_1(self):
""" Search single-element tuple: successful search"""
sandwich = ('mustard',)
self.assertEqual( search_sequence( sandwich, 'mustard' ), True)
def test_search_sequence_size_1_2(self):
""" Search single-element tuple: unsuccessful search"""
sandwich = ('mustard',)
self.assertEqual( search_sequence( sandwich, 'ham' ), False)
def test_search_sequence_size_7_1(self):
""" Search 7-element tuple: successful search"""
sandwich = ("jelly","butter", "mustard", "bread", "pickles", "jam",
"cheese")
self.assertEqual( search_sequence( sandwich, 'pickles'), True)
def test_search_sequence_size_7_2(self):
""" Search 7-element tuple: unsuccessful search"""
sandwich = ("jelly","butter", "mustard", "bread", "pickles", "jam",
"cheese")
self.assertEqual( search_sequence( sandwich, 'pear'), False)
他没有对此材料进行任何演讲,没有人100%确定该怎么做。我已经尝试与同行导师会面,但他并没有提供太多帮助,只重新重新调整了序列的教科书定义,而不是如何实现代码。所以我想我问代码的外观。我需要添加到count_sequence(seq)
和search_sequence(seq, item)
:函数中。谢谢!
您被要求实施的内容是微不足道的,所以不要惊慌。
count_sequence(seq)
这是两者中更容易的。如果seq
为空,请返回零。您会在讲师的其他功能中找到空的示例测试,例如copy_sequence()
。
如果seq
没有空,则返回1加上seq
尾巴(cdr()
(上递归调用count_sequence()
的结果。就是这样。
这可以通过一个if
语句实现,该语句包含return
语句,该语句涵盖了两种情况之一。if
语句之后将是涵盖其他情况的return
语句。
search_sequence(seq, item)
这只是代码略多。如果seq
是空的,请返回False
,因为它是布尔(谓词(函数。如果不是空的,请将item
与seq
的第一项(car()
(进行比较。如果它们相同,请返回True
。
否则,返回在同一item
上递归调用search_sequence()
的结果,但剩余的seq
(cdr()
(。这个递归电话的真相或虚假是答案,您不需要检查它,只需返回即可。
这里有三种情况,因此可以使用两个if
语句来实施,每个语句返回一个值,以及最终的return
语句,涵盖第三种情况。