Disc03

2022.03.12

题目链接
主要是recursion,前面做的都比较顺,最后一题卡了好久,看了答案之后发现并没有完全用recursion
还以为不能用iteration,摔桌子

def multiply(m, n):
    """
    >>> multiply(5, 3)
    15
    """
    if n == 1:
        return m
    else:
        return m + multiply(m, n-1)

def is_prime(n):
    """
    >>> is_prime(7)
    True
    >>> is_prime(10)
    False
    >>> is_prime(1)
    False
    """
    def prime_helper(n, m):
        if m == 0:
            return 0
        elif n%m == 0:
            return m
        else:
            return prime_helper(n,m-1)
    if prime_helper(n, n-1) != 1:
        return False
    else:
        return True

def make_func_repeater(f, x):
    """
    >>> incr_1 = make_func_repeater(lambda x: x + 1, 1)
    >>> incr_1(2) #same as f(f(x))
    3
    >>> incr_1(5)
    6
    """
    def repeat(f, n):
        if n == 1:
            return f
        else:
            return f(repeat(f,n-1))    
    return repeat(f, x)

def count_stair_ways(n):
    """
    >>> count_stair_ways(5)
    8
    """
    if n == 0:
        return 1
    elif n < 0:
        return 0
    else:
        return count_stair_ways(n-1)+count_stair_ways(n-2)

def count_k(n, k):
    """
    >>> count_k(3, 3) # 3, 2 + 1, 1 + 2, 1 + 1 + 1
    4
    >>> count_k(4, 4)
    8
    >>> count_k(10, 3)
    274
    >>> count_k(300, 1) # Only one step at a time
    1
    """
    if n == 0:
        return 1
    elif n < 0:
        return 0
    else:
        total = 0
        i = 1
        while i <= k:
            total += count_k(n-i, k)
            i += 1
        return total

发表评论