华为od机试题目 糖果

华为od机试题目 小明从糖果盒中随意抓一把糖果 每次小明会取出一半的糖果分给同学们 当糖果不能平均分配时 小明可以从糖果盒中(假设盒中糖果足够)取出一个或放回一个糖果 小明至少需要多少次(取出放回和平均分配均记一次)能将手中糖果分至只剩一颗

示例： 输入 ：15 输出： 5 输入 ：4 输出：2

解题思路：典型的BFS，每次可以进行的操作有加一 减一 除以二（在糖果数能被2整除的情况下）

import collections
n = int(input())
queue = collections.deque()
queue.append(n)
def bfs(queue,target,depth):#depth即遍历几层后找到了1
    while queue:
        depth += 1
        for i in range(len(queue)):
            cur = queue.popleft()
            if cur == target:
                return depth
            queue.append(cur+1)
            queue.append(cur-1)
            if cur%2 == 0:
                queue.append(cur/2)
print(bfs(queue,1,-1)) #之所以初始的depth为-1是因为第一次手中的糖果数量如果就是目标数量，则需要的操作次数为0