数代数

Question

我正试图反向工程给我的一组数字(f，m)，我需要通过以下算法，从1,1开始，从1，1开始，每一代需要多少代：

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

呃，我不知道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”输出："1“f= "4”m= "7“输出："4”f= "4“m= "2”输出：“不可能”

任何帮助都是非常感谢的！我正在运行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

你在正确的轨道上与自上而下的做法，你张贴。如果你使用整数除法而不是重复减法，你可以用一个巨大的因子来加速它。

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)产量

7   4   0
4   3   1
3   1   2
4

Answer 2

这不是Python问题，也不是编程问题。这是一个让你思考的问题。因此，如果你只是从别人那里得到答案，你就不会从练习中得到任何知识或事后的东西。

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

Answer 3

尝试一种递归形式：

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

注意:我是Python3.5编码器，所以我试着追溯我的代码，如果有什么问题请告诉我。

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