华为OD机试真题e卷------分糖果python

华为OD机试分糖果问题的Python解题思路
问题描述
小明从糖果盒中随意抓取一定数量的糖果，每次可以执行三种操作之一：取出一半糖果并舍去余数；如果当前糖果数目为奇数，则可以从盒子中再拿一个糖果或将手里的一个糖果放回去。目标是最少经过几次这样的操作能够使手中的糖果变为一颗。
为了达到这个目的，采用贪心策略来解决问题[^3]。具体来说，在每一步都尽可能快速地减少糖果的数量直到只剩下一颗为止。当遇到奇数个糖果时，优先考虑加一而不是减一，因为这样可以在下一轮更有效地通过除以2的方式大量削减糖果总数。
贪婪算法分析
对于任意正整数n表示初始糖果数：

如果 n 是偶数，则直接将其除以2；
若 n 为奇数，则判断 (n+1)/2 和 (n−1)/2 的大小关系，选择较小的那个作为下一步的结果，这是因为我们希望更快接近1。

这种做法基于这样一个事实——当我们面对两个连续的奇数值时，较大的那个总是可以通过增加1变成一个小得多的新值（即其半数），而较小的一个则需要两次操作才能完成同样的效果(先减后除)[^4]。
Python代码实现
下面给出了解决上述问题的具体Python程序：
def min_steps_to_one(n):
steps = 0

while n != 1:
if n % 2 == 0:
n //= 2
elif ((n + 1) // 2) < ((n - 1) // 2):
n += 1
else:
n -= 1

steps += 1

return steps

if __name__ == "__main__":
candy_count = int(input().strip())
print(min_steps_to_one(candy_count))
登录后复制
此函数接收一个参数n代表起始的糖果数量，并返回将这些糖果减少到只有一个所需的最小步数。主程序部分读入用户输入的数据并调用该方法打印最终结果。