2269: 蓝桥杯2016年第七届真题-冰雹数(3.14)

解题思路:这个题目思路很清晰,不过好像没法根据直接思路来写python的代码,哪怕优化后也是超时,仅提供可以用其它语言ac的Python版

注意事项:

参考代码:

n = int(input().strip())

ans = []
for i in range(n, 0, -1):#逆序遍历可以减少进入while的次数
    count = 0
    temp = i
    if temp not in ans:#剪枝:如果出现过就不再执行操作了,因为该数字操作后可能出现的数字都已经加入ans中
        while count < 2:#只有当1出现两次时才退出循环,这是避免给1的测试数据无法得出正确答案
            if temp == 1:
                count += 1
            if temp not in ans:#剪枝,同理
                ans.append(temp)
                if temp & 1:#  &1为1是奇数
                    temp = temp * 3 + 1
                else:
                    temp = temp >> 1#右移1位等价于/2
            else:
                break
    else:
        continue
print(max(ans))