数学算法失败但似乎正确

Question

我遇到了一个问题，其中在 A 和 B 中提供了一个函数。这些是 1、1 的目标数字，其中 B 只能增加 A，A 只能增加 B（例如，1 1 -> 2 1 或 1 2。2 1 -> 3 1 或 2 3。2 3 -> 5 3 或 2 5)。这将创建一个二叉树。在问题中，给定目标数，我需要找到达到该数已经过去的"minimum"代数，或者该数是否可以达到（例如，2 4 是不可能达到的）。这是我想出的解决方案，它通过了我抛给它的每个测试用例：

import math

def answer(M, F):
    m = int(M)
    f = int(F)
    numgen=0
    if f==1 and m==1:
        return "0"
    while f>=1 and m>=1:
        if f > m:
            m, f = f, m
        if f==1:
            return str( numgen + m - 1 )
        if m>f:
            numgen += math.floor( m / f )
            m = m % f
    return "impossible"

我正在半代码打高尔夫球，我觉得我的解决方案非常优雅且相当高效。我在十代内抛给它的所有东西都是正确的，如果我抛出大量数字（输入的上限规定为 10^50），这些也能正常工作。当提交并运行针对未知测试用例时，五个中的三个失败。本质上，我的问题更想知道这里失败的情况是什么。

我有一些无法证明但相当肯定是准确的假设：

二叉树中没有重复项。我还没有找到任何案例，我怀疑它在数学上是可以证明的。
可以在不影响世代数的情况下对树的左右两半进行镜像 - 这个实际上已经得到了很好的证明。
只有一条路线可以到达任何给定的组合（没有重复的属性二叉树）- 这依赖于假设 1，但如果假设 1 为真，那么这也必须是是的。
两个数字中的一个总是素数。这并没有真正影响算法，我也没有证明，但似乎总是如此。一个有趣的花絮。

这个方案哪里错了？

Answer 1

老实说，您的解决方案太复杂了。看看这个：

def answer(M, F):
    my_bombs = [int(M), int(F)]
    my_bombs.sort()
    generations = 0
    while my_bombs != [1, 1]:
        if my_bombs[0] == 1:
            return str(generations + my_bombs[1] - 1)
        if my_bombs[0] < 1 or my_bombs[0] == my_bombs[1]:
            return "impossible"
        print(my_bombs, generations)
        n = my_bombs[1] // my_bombs[0]
        my_bombs[1] -= my_bombs[0] * n
        generations += n
        my_bombs.sort()
    return str(generations)

Answer 2

您没有说明您使用的是 Python 2 还是 Python 3，但是 math.floor( m / f ) 仅在 Python 3 中才有意义。那里 m / f 是一个浮点数，不精确。你最好简单地使用整数除法：numgen += m // f。一个重要的例子是 M, F = str(10**30), '3'，你计算 333333333333333316505293553666 但用整数除法你会得到 333333333333333333333333333335.

数学算法失败但似乎正确

Mathematical algorithm failing but seems correct

python

algorithm

math

primes

binary-tree