• 例题

    假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木棒只能由 1 人切分。求最多有 m 个人时，最少要切分几次。譬如 n ＝ 8，m＝ 3 时如图所示，切分 4 次就可以了。
    题目来源：程序员的算法趣题Q4
    C309613F-1270-472C-AE97-D08D15B74712.png
    思路：
    如果人数足够，每次对半切分一定最快。人数不足够时，每人每次只能增加1根木棒。
    也可以逆向思维，想象成m个人黏合长度为1的木棒。
    参考解答：

    1. def split(m, n, current):
    2.     if current >= n:
    3.         return 0
    4.     elif current < m:
    5.         return 1 + split(m, n, 2 * current)
    6.     elif current >= m:
    7.         return 1 + split(m, n, current + m)
    10. def split2(m, n):
    11.     count = 0
    12.     current = 1
    13.     while current < n:
    14.         current += current if current < m else m
    15.         count += 1
    16.     return count