【华为机试】2023年真题B卷（python）-分糖果

一、题目

题目描述：

小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。
当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。
小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。

二、输入输出

输入描述:
抓取的糖果数（<10000000000）：
15
输出描述:
最少分至一颗糖果的次数：
5

三、示例

示例1?

输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
15
输出：
5
备注：
解释：
(1)15+1=16;
(2)16/2=8;
(3)8/2=4;
(4)4/2=2;
(5)2/2=

四、解题思路

根据题目描述，小明每次取出一半的糖果分给同学们，直到糖果不能平均分配为止。在这个过程中，小明可以选择从糖果盒中取出一个糖果或放回一个糖果。我们需要计算小明最少需要多少次操作，才能将手中的糖果分至只剩一颗。

我们可以使用递归来解决这个问题。递归函数的输入参数为当前手中的糖果数量，输出为最少操作次数。递归的终止条件是手中的糖果数量为1，此时不需要进行任何操作，返回0。

在递归函数中，我们可以考虑两种情况：

1. 如果当前手中的糖果数量是偶数，那么小明可以直接将一半的糖果分给同学们，然后递归调用函数计算剩余糖果的最少操作次数。
2. 如果当前手中的糖果数量是奇数，小明需要先进行一次操作，可以选择从糖果盒中取出一个糖果或放回一个糖果，使得剩余糖果数量为偶数。然后再将一半的糖果分给同学们，并递归调用函数计算剩余糖果的最少操作次数。

最终，递归函数的输出就是最少操作次数。

五、参考代码?

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-分糖果.py
@Time    :   2023/12/24 12:44:51
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''

# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict

def min_operations(candies):
    if candies == 1:  # 终止条件：手中的糖果数量为1，不需要进行任何操作
        return 0
    
    if candies % 2 == 0:  # 当前糖果数量为偶数
        return 1 + min_operations(candies // 2)  # 一次操作后递归调用函数
    
    # 当前糖果数量为奇数
    return 1 + min(min_operations(candies + 1), min_operations(candies - 1))
    # 选择从糖果盒中取出一个糖果或放回一个糖果，使得剩余糖果数量为偶数
    # 然后递归调用函数


candies = int(input())
result = min_operations(candies)
print(result)  # 输出：5