一、题目
题目描述：
小明从糖果盒中随意抓一把糖果，每次小明会取出一半的糖果分给同学们。
当糖果不能平均分配时，小明可以选择从糖果盒中（假设盒中糖果足够）取出一个糖果或放回一个糖果。
小明最少需要多少次（取出、放回和平均分配均记一次），能将手中糖果分至只剩一颗。
二、输入输出
输入描述:
抓取的糖果数（<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。
在递归函数中，我们可以考虑两种情况：
- 如果当前手中的糖果数量是偶数，那么小明可以直接将一半的糖果分给同学们，然后递归调用函数计算剩余糖果的最少操作次数。
- 如果当前手中的糖果数量是奇数，小明需要先进行一次操作，可以选择从糖果盒中取出一个糖果或放回一个糖果，使得剩余糖果数量为偶数。然后再将一半的糖果分给同学们，并递归调用函数计算剩余糖果的最少操作次数。
最终，递归函数的输出就是最少操作次数。
五、参考代码
# -*- 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
