数代数

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"))

这个 returns 正确答案（例如，4,7 returns "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"

非常感谢任何帮助！ P.S。我是运行Python2.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 2.7.6)

def back():
    global f,m,i
    if f<m:
        s=m//f
        i+=s
        m-=s*f
    elif m<f:
        s=f//m
        i+=s
        f-=s*m
    else:
        return False
    return True
while True:
    f=int(raw_input('f = '))
    m=int(raw_input('m = '))
    i=0
    while True:
        if f==m==1:
            print 'Output:',str(i)
            break
        else:
            if not back():
                print 'Output: impossible'
                break
    print

(Python 3.5.2)

def back():
    global f,m,i
    if f<m:
        s=m//f
        i+=s
        m-=s*f
    elif m<f:
        s=f//m
        i+=s
        f-=s*m
    else:
        return False
    return True
while True:
    f=int(input('f = '))
    m=int(input('m = '))
    i=0
    while True:
        if f==m==1:
            print('Output:',str(i))
            break
        else:
            if not back():
                print('Output: impossible')
                break
    print()

注意：我是一名 Python 3.5 编码员，所以我尝试回溯我的代码，如果有问题请告诉我。

输入格式也不同：现在是 f = "some_int" 而不是 f = some_int，输出格式也类似。

Answer 2

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

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

Answer 3

您发布的自上而下的方法是正确的。如果你使用整数除法而不是重复减法，你可以大大加快速度。

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)

使用上面的方法，answer(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

和answer(4, 7)产生

数代数

counting back generations of a number

python

recursion

loops

mathematical-optimization