腾讯2020届实习编程题1——拆分整数

题目描述

小Q在进行一个对数字进行拆分的游戏，游戏规则如下：
小Q最初只有一个整数N,接下来每一轮中，小Q被允许对现有的每个数进行下面两个操作之一
1、对当前小Q手里的所有数减1
2、把所有数都拆分为更小的两个数之和
但是拆分操作只允许使用至多k次，现在小Q想知道把N完全消去需要多少轮操作。

输入描述
输入一行包含两个整数N, K (1< N< 100,0< K<100）
输出描述:
输出一个整数，表示至少需要的轮数。

解题思路

首先举一个简单的例子，如 N=15, K=4，则拆分过程如下图所示：

需要说明的是拆分的方法是将原来的数除以2，这样会使得拆分后的较大的数相对较小，也因此会使得拆分后最大最小数之间相差1或0，而拆分操作停止的条件是K=0或者出现了1：

• 出现1，则最大的数不过是2，所以执行“减1”操作
• K=0，表示不能执行二拆分，只能进行“减1”操作，至于要采用多少次“减1”操作呢？首先要看最小的数为多少，然后在最小数的基础上+1（最大数）即为操作多少次"减1"。
  代码如下：

def func(num, K):
    count = 0
    flag = 0
    while num > 1 and K != 0:
        count += 1
        K -= 1
        if num % 2 == 1:
            flag = 1
        num = int(num / 2)     # 取拆分后较小的那个数
    count += num + flag
    return count

if __name__ == '__main__':
    while True:
        try:
            num, K = input().split()
            num, K = int(num), int(K)
            print(func(num, K))
        except:
            break