这是技术问题吗？一道数学题？ Python 个问题？

Question

首先，我想说我不是在找人做“我的功课”我已经投入了一些时间思考和解决这个问题我只是不确定我是否只是打了一个 Python 边缘，或者如果我遗漏了一些非常大的数字（超过 10**256）。所以，我正在解决 Google Foobar 挑战 #4，其中指出：

燃油喷射完美

Lambda 指挥官请求您帮助改进 LAMBCHOP 末日装置的自动量子反物质燃料喷射系统。这是您近距离了解 LAMBCHOP 的绝好机会 - 并且可能会在您看到它时偷偷进行一些破坏 - 所以您很高兴地接受了这份工作。

量子反物质燃料以小颗粒形式出现，这很方便，因为 LAMBCHOP 的许多运动部件都需要一次为一个颗粒提供燃料。但是，小兵会将颗粒散装倾倒到燃料入口中。您需要找出最有效的方法来对颗粒进行分类并将其一次转移为一个颗粒。

燃料控制机制有三个操作：

添加一颗燃料颗粒
移除一颗燃料芯块
将整组燃料颗粒除以 2（由于将量子反物质颗粒切成两半时释放的破坏性能量，安全控制只会在颗粒数量为偶数时才允许这种情况发生）

编写一个名为solution(n)的函数，它接受一个正整数作为字符串和returns将颗粒数转换为1所需的最少操作次数。燃料摄入量控制面板只能显示一个长达 309 位数字的数字，因此不会有比您用那么多数字表达的更多的颗粒。

例如：

解法(4) returns 2: 4 -> 2 -> 1

解决方案(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1

我的解决方案：

def solution(n):
    
    n = int(n)
    operations = 0

    # Handling edge cases here:
    # n(3)=2, n(2)=1 and n(1)=0
    if (n >= 1) and (n <= 3):
        return n - 1
    
    while n > 1:
    
        # Any even number will be divided by two
        # until we get an odd number. Since we are
        # guaranteed the number is divisible by
        # two we use floor division to avoid stack
        # overflow with strings of 309 digits.
        if n % 2 == 0:
            n = n // 2

        # Any odd number has two even neighbors:
        # a) One can be divided by two just ONCE, and
        # b) The other can be divided by two MORE than once
        # We will always take option b) for path optimization:
        elif (n-1) % 4 == 0:
            n -= 1
        else:
            n += 1

        operations += 1
 
    return operations

现在，我的代码通过了 10 个案例中的 8 个。我检查并重新检查...并再次检查代码，数学看起来很完美，在某些时候我决定做一些我一开始不想做的事情：Google 其他答案来找出问题所在。所以我发现了这个：

cnt=0
def divide(x):
    global cnt
    while(x>1):
        if (x & 1==0):
            #Dividing even number by two by shifting binary digits one step to the right.
            x=x>>1
        else:
            a=x+1
            b=x-1
            #counters ac & bc will be used to count trailing 0s
            ac=bc=0
            #count trailing 0's for x+1
            while(a & 1==0):
                a=a>>1
                ac+=1
            #count trailing 0's for x-1
            while(b & 1==0):
                b=b>>1
                bc+=1
            #go with x+1 if it has more trailing 0s in binary format. Exception is number 
            #3 as b10 can be divided in less steps than b100.
            #edge case 3 identified by manually testing numbers 1-10.
            if (ac>bc and x!=3):
                x+=1
            else:
                x-=1
        cnt+=1

def solution(n):
    global cnt
    n=int(n)
    divide(n)
    return cnt

来源：

现在，真正奇怪的事情来了，第二个代码似乎使用了与我类似的方法（寻找二进制中最大数量的尾随零与寻找可以被除以的数字有点相同不止一次而不是一次），并且两个代码对于 1 到 10^256 之间的任何整数都达到完全相同的解决方案，现在在 10^256 到 10^257 之间的某个点发生了一些非常奇怪的事情：我的代码给出了答案'n' 操作，而另一个解决方案给出了 'n-1' 操作的输出。现在我们知道 256 是数字计算机的 'magic' 数字，互联网本身 (IPv4) 就是建立在这个数字之上的。我刚才是不是弄坏了什么东西？

现在，谁能告诉我为什么使用脚本会得到不同的结果？我错过了什么吗？我在这里失去了理智。

Answer 1

您的代码看起来会得到 12 的错误结果。
12 -> 6 -> 3 -> 4 -> 2 -> 1 代替 12 -> 6 -> 3 -> 2 -> 1.

你的 3 的特殊大小写需要在循环内，而不是在循环外。

并回答你的其他问题。 256是特殊的。 2^256 或 10^256 没有什么特别的。

这是技术问题吗？一道数学题？ Python 个问题？

Is this a technical issue? a Math issue? A Python issue?

python

algorithm

math

numbers

mathematical-optimization

燃油喷射完美