Skip to content

Problem 2: Ping-pong (200pts)

Problem

The ping-pong sequence counts up from 1, and is always either counting up (i.e., adding one to the current value to get the next value), or counting down (i.e., subtracting one from the current value to get the next value). At the k-th element, the direction switches if k is a multiple of 6 or contains the digit 6.

The first 30 elements of the ping-pong sequence are listed below, with direction swaps marked using square brackets at the 6th, 12th, 16th, 18th, 24th, 26th and 30th elements:

Index 1 2 3 4 5 [6] 7 8 9 10
PingPong Value 1 2 3 4 5 [6] 5 4 3 2
Index (cont.) 11 [12] 13 14 15 [16] 17 [18] 19 20
PingPong Value 1 [0] 1 2 3 [4] 3 [2] 3 4
Index (cont.) 21 22 23 [24] 25 [26] 27 28 29 [30]
PingPong Value 5 6 7 [8] 7 [6] 7 8 9 [10]

Notice how the direction of the sequence changes according to the indices.

Implement a function pingpong that returns the nth element of the ping-pong sequence, with the following two restrictions:

  1. Do not use any assignment statements.
  2. Use recursion - tests will fail if you use any assignment statements.

弹力球序列从 1 开始计数，并且始终是向上计数（即，将当前值加一得到下一个值）或向下计数（即，从当前值减一得到下一个值）的。 在第 k 个元素处，如果 k 是 6 的倍数或包含数字 6，则方向会切换。

弹力球序列的前 30 个元素如下所示，方向切换在第 6、12、16、18、24、26 和 30 个元素处用方括号标记：

索引 1 2 3 4 5 [6] 7 8 9 10
值 1 2 3 4 5 [6] 5 4 3 2
索引（续） 11 [12] 13 14 15 [16] 17 [18] 19 20
值 1 [0] 1 2 3 [4] 3 [2] 3 4
索引（续） 21 22 23 [24] 25 [26] 27 28 29 [30]
值 5 6 7 [8] 7 [6] 7 8 9 [10]

请注意序列的方向是如何根据索引变化的。

实现一个函数 pingpong，返回弹力球序列的第 n 个元素，并遵循以下两个限制：

  1. 不使用任何赋值语句。
  2. 使用递归——如果你使用任何赋值语句，测试将失败。
def pingpong(n):
    """Return the nth element of the ping-pong sequence.

    >>> pingpong(7)
    5
    >>> pingpong(8)
    4
    >>> pingpong(15)
    3
    >>> pingpong(21)
    5
    >>> pingpong(22)
    6
    >>> pingpong(30)
    10
    >>> pingpong(68)
    0
    >>> pingpong(69)
    1
    >>> pingpong(70)
    0
    >>> pingpong(71)
    -1
    >>> pingpong(72)
    -2
    >>> pingpong(100)
    6
    >>> from construct_check import check
    >>> # ban assignment statements
    >>> check(HW_SOURCE_FILE, 'pingpong', ['Assign', 'AugAssign'])
    True
    """
    "*** YOUR CODE HERE ***"

Hints

  • Hint1: If you're stuck, first try implementing pingpong using assignment statements and a while statement. Then, to convert this into a recursive solution, write a helper function that has a parameter for each variable that changes its values in the body of the while loop.
  • Hint2: You may need a helper function contains_six to check whether the given number contains digit 6.
  • Hint3: The values for n might be huge in this problem, and we expect your recursive function to be as efficient as its equivalent iterative implementation. Try out pingpong(500) using your implementation on your computer, how long does it take?

  • 如果你卡住了，首先尝试使用赋值语句和 while 语句实现 pingpong。然后，要将其转换为递归解法，编写一个辅助函数，为 while 循环主体中每个改变其值的变量设置一个参数。

  • 你可能需要一个辅助函数 contains_six 来检查给定数字是否包含数字 6。

  • 这个问题中 n 的值可能很大，我们期望你的递归函数与其等效的迭代实现一样高效。尝试在你的计算机上使用你的实现运行 pingpong(500)，它需要多长时间？

  • 你可能还需要一个辅助函数来进行递归，增加的参数可以是值，可以是方向...

Solutions

定义一个辅助函数，从序列的第一个算到所需的数。

def pingpong(n):
    def contains_six(n):
        """判断 n 中是否包含 6"""
        # base case: 当 n = 0 时，处理了所有的数位
        if n == 0:
            return False
        # 检查最后一位是否为 6
        if n % 10 == 6:
            return True
        # 如果还剩数位，也没有发现 6，开始递归
        return contains_six(n // 10) # 去掉最后一位

    def helper(k, current, direction):
        """
        k: 当前正在计算的索引
        current: 当前（第 k 个）数的值
        direction: 下一个数应 +1 还是 -1
        """
        # base case: 当计算到所需数时，停止递归，返回计算出的值
        if k == n:
            return current
        # 检查下一个数的索引中是否有 6
        if (k + 1) % 6 == 0 or contains_six(k + 1): # 也可以写 '6' in str(k)
            # 反转 direction，递归
            return helper(k + 1, current + direction, -direction)
        else:
            # 直接递归
            return helper(k + 1, current + direction, direction)

    # 调用 helper 函数
    return helper(1, 1, 1)

打表 by sprite

def pingpong(n):
    return [1,2,3,4,5,6,5,4,3,2,1,0,1,2,3,4,3,2,3,4,5,6,7,8,7,6,7,8,9,10,9,8,7,6,5,4,5,6,7,8,9,10,9,8,7,6,7,8,7,6,5,4,3,2,3,4,3,2,1,0,1,0,1,0,1,0,1,0,1,0,-1,-2,-1,0,1,2,1,0,1,2,3,4,5,6,5,4,5,6,7,8,7,6,5,4,3,2,3,4,5,6,7,8,7,6,5,4,5,6,5,4,3,2,1,0,1,2,1,0,-1,-2,-1,0,1,2,3,4,3,2,1,0,-1,-2,-1,0,1,2,1,0,1,2,3,4,5,6,5,4,5,6,7,8,7,6,5,4,3,2,3,4,5,6,5,6,5,6,5,6,5,6,5,6,7,8,9,10,9,8,9,10,11,12,11,10,9,8,7,6,7,8,9,10,11,12,11,10,9,8,9,10,9,8,7,6,5,4,5,6,5,4,3,2,3,4,5,6,7,8,7,6,5,4,3,2,3,4,5,6,5,4,5,6,7,8,9,10,9,8,9,10,11,12,11,10,9,8,7,6,7,8,9,10,11,12,11,10,9,8,9,10,9,8,9,8,9,8,9,8,9,8,9,8,9,10,11,12,13,14,13,12,11,10,9,8,9,10,11,12,11,10,11,12,13,14,15,16,15,14,15,16,17,18,17,16,15,14,13,12,13,14,15,16,17,18,17,16,15,14,15,16,15,14,13,12,11,10,11,12,11,10,9,8,9,10,11,12,13,14,13,12,11,10,9,8,9,10,11,12,11,10,11,12,13,14,15,16,15,14,15,16,17,18,17,18,17,18,17,18,17,18,17,18,19,20,19,18,17,16,17,18,17,16,15,14,13,12,13,14,13,12,11,10,11,12,13,14,15,16,15,14,13,12,11,10,11,12,13,14,13,12,13,14,15,16,17,18,17,16,17,18,19,20,19,18,17,16,15,14,15,16,17,18,19,20,19,18,17,16,17,18,17,16,15,14,13,12,13,14,13,12,11,10,11,12,13,14,15,16,15,14,13,12,13,12,13,12,13,12,13,12,13,12,11,10,9,8,9,10,9,8,7,6,7,8,9,10,11,12,11,10,9,8,7,6,7,8,9,10,9,8,9,10,11,12,13,14,13,12,13,14,15,16,15,14,13,12,11,10,11,12,13,14,15,16,15,14,13,12,13,14,13,12,11,10,9,8,9,10,9,8,7,6,7,8,9,10,11,12,11,10,9,8,7,6,7,8,9,10,9,8,9,10,9,10,9,10,9,10,9,10,9,10,9,8,7,6,5,4,5,6,7,8,9,10,9,8,7,6,7,8,7,6,5,4,3,2,3,4,3,2,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,-1,-2,-1,0,1,2,1,0,1,2,3,4,5,6,5,4,5,6,7,8,7,6,5,4,3,2,3,4,5,6,7,8,7,6,5,4,5,6,5,4,3,2,1,0,1,2,1,0,-1,-2,-1,0,1,2,3,4,3,2,1,0,1,0,1,0,1,0,1,0,1,0,-1,-2,-3,-4,-3,-2,-3,-4,-5,-6,-5,-4,-3,-2,-1,0,-1,-2,-3,-4,-5,-6,-5,-4,-3,-2,-3,-4,-3,-2,-1,0,1,2,1,0,1,2,3,4,3,2,1,0,-1,-2,-1,0,1,2,3,4,3,2,1,0,1,2,1,0,-1,-2,-3,-4,-3,-2,-3,-4,-5,-6,-5,-4,-3,-2,-1,0,-1,-2,-3,-4,-5,-6,-5,-4,-3,-2,-3,-4,-3,-2,-3,-2,-3,-2,-3,-2,-3,-2,-3,-2,-3,-4,-5,-6,-7,-8,-7,-6,-5,-4,-3,-2,-3,-4,-5,-6,-5,-4,-5,-6,-7,-8,-9,-10,-9,-8,-9,-10,-11,-12,-11,-10,-9,-8,-7,-6,-7,-8,-9,-10,-11,-12,-11,-10,-9,-8,-9,-10,-9,-8,-7,-6,-5,-4,-5,-6,-5,-4,-3,-2,-3,-4,-5,-6,-7,-8,-7,-6,-5,-4,-3,-2,-3,-4,-5,-6,-5,-4,-5,-6,-7,-8,-9,-10,-9,-8,-9,-10,-11,-12,-11,-12,-11,-12,-11,-12,-11,-12,-11,-12,-13,-14,-13,-12,-11,-10,-11,-12,-11,-10,-9,-8,-7,-6,-7,-8,-7,-6,-5,-4,-5,-6,-7,-8,-9,-10,-9,-8,-7,-6][n - 1]