查找迭代最低数量达到一定数额

本文介绍了查找迭代最低数量达到一定数额的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图解决这个问题，因为几个星期，但无法到达的解决方案。 开始时你有两个数字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)