我试图对提供给我的一组数字进行逆向工程(f,m),我需要使用下面的算法为每一代找出从1,1开始需要多少代：

x = 1
y = 1
new_generation = y+x
x OR y = new_generation

IE,我不知道X或Y是否更改,其他变量保持不变…对于4和7的最终值,可能的输出列表如下所示：

f = 4
m = 7
[1, 1]
[2, 1, 1, 2]
[3, 1, 2, 3, 3, 2, 1, 3]
[4, 1, 3, 4, 5, 3, 2, 5, 5, 2, 3, 5, 4, 3, 1, 4]
[5, 1, 4, 5, **7, 4**, 3, 7, 7, 5, 2, 7, 7, 2, 5, 7, 7, 3, **4, 7**, 5, 4, 1, 5]

每两组数字(2,1)和(1,2)都是可能的输出.注意**表示答案(在这种情况下,顺序不重要,只要m和f在列表中都具有它们的值).

显然这里有指数级增长,所以我无法(或效率较低)列出并找到答案.相反,我正在使用以下代码来逆转此过程…

def answer(m,f):
    #the variables will be sent to me as a string, so here I convert them...
    m = (int(m))
    f = (int(f))
    global counter
    #While I have not reduced my given numbers to my starting numbers....
    while m != 1 or f != 1:
        counter +=1
        #If M is greater, I know the last generation added F to M, so remove it
        if m > f:
            m = m-f
        #If F is greater, I know the last generation added M to M, so remove it
        elif f > m:
            f = f-m
        else:
            #They can never be the same (one must always be bigger, so if they are the same and NOT 1, it can't be done in any generation)
            return "impossible"
    return str(counter)

print(answer("23333","30000000000"))

这将返回正确的答案(例如,4,7返回“ 4”,这是正确的),但是当我传递更大的数字时,它会花费很长时间(我必须能够处理10 ^ 50,疯狂的数量,我知道！).

我的想法是我应该能够对数字应用一些数学方程式以将其减少,并使它们成倍增加,但是我很难找到一种方法来做到这一点,同时又保持了答案的完整性(例如,如果我用较大的数字除以较小的数字,在较小的数字(7,300000)上,我得到一个非常接近的(但错误的)答案,但是在较小的数字(例如,23333,300000)上,答案甚至没有接近的地方,这是有道理的生成路径的差异).请注意,我还在递归函数(查找代)中使用了非反向方法(构建列表并检查答案；由于明显的原因,速度明显较慢)也进行了尝试

以下是一些测试用例及其答案：

06003

任何帮助深表感谢！附言我正在运行Python 2.7.6

[编辑]

下面的代码按要求工作.

from fractions import gcd

def answer(m,f):
    #Convert strings to ints...
    m = (int(m))
    f = (int(f))

    #If they share a common denominator (GCD) return impossible
    if gcd(m,f) != 1:
        return "impossible"
    counter = 0
    #While there is still a remainder...
    while m != 0 and f != 0:
        if m > f:
            counter += m // f
            #M now equals the remainder.
            m %= f
        elif f > m:
            counter += f // m
            f %= m
    return str(counter - 1)

解决方法:

您采用自上而下的方法在正确的轨道上.如果使用整数除法而不是重复减法,则可以极大地提高它的速度.

def answer(m, f):
    m = int(m)
    f = int(f)
    counter = 0
    while m != 0 and f != 0:
        if f > m:
            m, f = f, m
        print(m, f, counter, sep="\t")
        if f != 1 and m % f == 0:
            return "impossible"
        counter += m // f
        m %= f
    return str(counter - 1)

使用上面的方法,答案(23333,30000000000)产生

30000000000 23333   0
23333   15244   1285732
15244   8089    1285733
8089    7155    1285734
7155    934 1285735
934 617 1285742
617 317 1285743
317 300 1285744
300 17  1285745
17  11  1285762
11  6   1285763
6   5   1285764
5   1   1285765
1285769

和答案(4,7)产生

7   4   0
4   3   1
3   1   2
4