python - 数代数

Question

我正在尝试对给我的一组数字 (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) 答案是不接近，这是有道理的，因为生成路径的差异)。请注意，我还在递归函数(查找世代)中尝试过此操作并使用非反向方法(构建列表并检查答案；由于显而易见的原因，速度明显变慢)

---

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

f = "1"
m = "2"
Output: "1"

f = "4"
m = "7"
Output: "4"

f = "4"
m = "2"
Output: "impossible"

非常感谢任何帮助!附言我正在运行 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)

Answer 1

这不是 Python 问题，也不是真正的编程问题。这是一个旨在让您思考的问题。因此，如果您只是从其他人那里得到答案，您将不会从练习中获得任何知识或后见之明。

只需在您的 while 循环中添加一个 print(m, f) 并观察小输入的数字变化情况。例如，尝试使用 (3, 100) 之类的东西:您没有看到任何可以加快速度的方法，而不是从更大的数字中重复删除 3 吗？