查找迭代最低数量达到一定数额 [英] Find minimum number of iterations to reach a certain sum

问题描述

我试图解决这个问题，因为几个星期，但无法到达的解决方案。 开始时你有两个数字X和Y都等于1。只有有效的选项有 X + Y 或 Y + X 的时间。我们需要找到最小数量的迭代需要达到一个具体的数字。

I'm trying to solve this problem since weeks, but couldn't arrive to a solution. You start with two numbers X and Y both equal to 1. Only valid options are X+Y or Y+X at a time. We need to find minimum number of iterations need to reach a specific number.

，例如：如果数字为5

eg : if the number is 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的，这样达到多少：

My take : If a number is odd let's say 23, decrement by 1. Now value = 22. Find the largest number that divides 22 = 11. Now reach the number by adding 1's so that:

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

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

X=23, answer reached

不过，这种方法的问题是我不能递归达到一个具体的数字，因为即使我到某一点时，说X =所需的值，Y值被放错位置，我不能再使用它来达到另一个值

But the problem with this approach is I cannot recursively reach a specific number, as even if I reach a certain point, say X = required value, the Y value gets misplaced and I cant reuse it to reach another value

推荐答案

现在我可以给一个 O（nlogn）解决方案。

Now I can give an O(nlogn) solution.

该方法好像最大公约数

使用 F（X，Y） EX preSS迭代的最小数量的这种状态。这种状态可以通过达到F（XY，Y）如果 X＆GT; Y 或 F （X，YX）如果 X＆LT; Y 。我们可以看到的方式来达到国家（X，Y）是独一无二的，我们可以在计算呢O（LOGN）如 GCD 。

Use f(x, y) express the minimum number of iterations to this state. This state can be reached by f(x-y, y) if x>y or f(x,y-x) if x<y. We can see that the way to reach state (x, y) is unique, we can calculate it in O(logn) like gcd.

答案是：分（F（N，I）| 1＆LT; = I n种）所以复杂性是 O（nlogn）

The answer is min( f(n, i) | 1 <= i < n) so complexity is O(nlogn)

蟒蛇code：

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)

这篇关于查找迭代最低数量达到一定数额的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！