找到达到某个总和的最小迭代次数

Question

我试图解决这个问题几个星期,但无法达成解决方案.首先,两个数字X和Y都等于1.只有有效的选项是X+Y或者Y+X一次.我们需要找到需要达到特定数量的最小迭代次数.

例如:如果数字是5

X=1, Y=1; X = X+Y

X=2, Y=1; Y = X+Y

X=2, Y=3; Y = Y+X

X=2, Y=5; Stop answer reached 

我的看法:如果一个数字是奇数,那就说23,递减1.现在值= 22.找到除以22 = 11的最大数字.现在通过加1来达到数字,这样:

X=11; Y=1 ; Y=Y+X

X=11; Y=12; X=X+Y

X=23, answer reached

但是这种方法的问题是我不能递归地达到一个特定的数字,因为即使我达到某一点,比如X =所需的值,Y值也会被错放,我无法重复使用它来达到另一个值

Answer 1

现在我可以给出一个O(nlogn)解决方案.

这种方法似乎是最常见的除数

使用f(x, y)表示此状态的最小迭代次数.f(x-y, y)if x>y或f(x,y-x)if 可以达到此状态x<y.我们可以看到达到状态的方式(x, y)是独一无二的,我们可以O(logn)像gcd一样计算它.

答案是min( f(n, i) | 1 <= i < n)如此复杂O(nlogn)

python代码:

def gcd (n, m):
    if m == 0:
        return n
    return gcd (m, n%m)

def calculate (x, y):
    if y == 0:
        return -1
    return calculate (y, x%y) + x/y

def solve (n):
    x = 0
    min = n
    for i in xrange (1, n):
        if gcd (n, i) == 1:
            ans = calculate (n, i)
            if ans < min:
                min = ans
                x = i
    print min

if __name__ == '__main__':
    solve (5)