红魔咖啡馆


头发越掉越多，头发越掉越少

【CS61A】CS61A——Homework 3

  • ~5.44K 字
  1. 1. Homework 3
    1. 1.1. Q1: Num Eights
    2. 1.2. Q2: Digit Distance
    3. 1.3. Q3: Interleaved Sum
    4. 1.4. Q4: Count Coins
    5. 1.5. Q5: Towers of Hanoi

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)

详见五点七边讲解视频

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
赞助喵
非常感谢您的喜欢！
赞助喵