找到最小迭代次数以达到一定的总和

一尘不染

找到最小迭代次数以达到一定的总和

algorithm

自数周以来，我一直在努力解决此问题，但无法解决。开始时你有两个数字，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值也放错了位置，我无法重用它来达到另一个值

阅读 305

2020-07-28

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

2020-07-28