Homework 3
Q1: Num Eights
用递归函数求一个数中有几位8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def num_eights(n):
"""Returns the number of times 8 appears as a digit of n.
>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3
>>> from construct_check import check
>>> # ban all assignment statements
>>> check(HW_SOURCE_FILE, 'num_eights',
... ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True
"""
if n==0:
return 0
else:
if n%10 ==8: return num_eights(n//10)+1
else: return num_eights(n//10)递归出口：每一位都减完后n==0时
每次返回时递归调用自身，传入未判断的部分
若发现该位是8，则返回值加一，否则不变
Q2: Digit Distance
用递归函数求每两位的差的绝对值之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def digit_distance(n):
"""Determines the digit distance of n.
>>> digit_distance(3)
0
>>> digit_distance(777)
0
>>> digit_distance(314)
5
>>> digit_distance(31415926535)
32
>>> digit_distance(3464660003)
16
>>> from construct_check import check
>>> # ban all loops
>>> check(HW_SOURCE_FILE, 'digit_distance',
... ['For', 'While'])
True
"""
if n<10:
return 0
else:
res,last = n//10,n%10
sec_last = res%10
return digit_distance(res)+abs(sec_last-last)递归出口：当查到最后一位时绝对值为0，返回0
否则将最后一位与倒数第二位取出，将取完最后一位的剩余部分传入递归函数继续判断，返回值加上两位数绝对值之差
Q3: Interleaved Sum
写一个函数，要求对1-n中的所有奇数传入odd_func，所有偶数传入even_func，返回所有数计算后和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def interleaved_sum(n, odd_func, even_func):
"""Compute the sum odd_func(1) + even_func(2) + odd_func(3) + ..., up
to n.
>>> identity = lambda x: x
>>> square = lambda x: x * x
>>> triple = lambda x: x * 3
>>> interleaved_sum(5, identity, square) # 1 + 2*2 + 3 + 4*4 + 5
29
>>> interleaved_sum(5, square, identity) # 1*1 + 2 + 3*3 + 4 + 5*5
41
>>> interleaved_sum(4, triple, square) # 1*3 + 2*2 + 3*3 + 4*4
32
>>> interleaved_sum(4, square, triple) # 1*1 + 2*3 + 3*3 + 4*3
28
>>> from construct_check import check
>>> check(HW_SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
"""
def check_num(k):
if k>n:
return 0
elif k==n:
return odd_func(k)
else:
return check_num(k+2)+odd_func(k)+even_func(k+1)
return check_num(1)由于题目不让使用循环与取模运算判断奇偶，我们只能使用递归函数
由于奇数与偶数是分开的，我们可以发现，奇数+2=奇数，奇数+1=偶数
因此我们可以写一个内嵌函数，让一个计数变量k从1开始，将k传入odd_func，k+1传入even_func
然后递归调用该函数从k+2开始
递归出口即k>n或k=n（此时k一定为奇数，直接传入odd_func并返回）
Q4: Count Coins
给予n刀乐，把他分为面值分别为1刀乐，5刀乐，10刀乐，25刀乐的四种货币，输出分法数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def count_coins(total):
"""Return the number of ways to make change using coins of value of 1, 5, 10, 25.
>>> count_coins(15)
6
>>> count_coins(10)
4
>>> count_coins(20)
9
>>> count_coins(100) # How many ways to make change for a dollar?
242
>>> count_coins(200)
1463
>>> from construct_check import check
>>> # ban iteration
>>> check(HW_SOURCE_FILE, 'count_coins', ['While', 'For'])
True
"""
def cal(total,spl_coin):
if total==0:
return 1
elif total<0:
return 0
elif spl_coin==None:
return 0
else:
with_coin = cal(total-spl_coin,spl_coin)
without_coin = cal(total,next_smaller_coin(spl_coin))
return with_coin+without_coin
return cal(total,25)Q5: Towers of Hanoi
实现汉诺塔游戏并描述每次移动过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def move_stack(n, start, end):
"""Print the moves required to move n disks on the start pole to the end
pole without violating the rules of Towers of Hanoi.
n -- number of disks
start -- a pole position, either 1, 2, or 3
end -- a pole position, either 1, 2, or 3
There are exactly three poles, and start and end must be different. Assume
that the start pole has at least n disks of increasing size, and the end
pole is either empty or has a top disk larger than the top n start disks.
>>> move_stack(1, 1, 3)
Move the top disk from rod 1 to rod 3
>>> move_stack(2, 1, 3)
Move the top disk from rod 1 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 3
>>> move_stack(3, 1, 3)
Move the top disk from rod 1 to rod 3
Move the top disk from rod 1 to rod 2
Move the top disk from rod 3 to rod 2
Move the top disk from rod 1 to rod 3
Move the top disk from rod 2 to rod 1
Move the top disk from rod 2 to rod 3
Move the top disk from rod 1 to rod 3
"""
assert 1 <= start <= 3 and 1 <= end <= 3 and start != end, "Bad start/end"
def hanoi(n,start,mid,end):
if n == 1:
print_move(start, end)
return
else:
hanoi(n - 1, start,end, mid)
hanoi(1,start,mid,end)
hanoi(n - 1, mid, start,end)
return hanoi(n,start,6-start-end,end)详见五点七边讲解视频