特定の合計に達するための最小反復回数を確認

Question

私はこの問題を数週間から解決しようとしていますが、解決策には到達できませんでした。 2つの数字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 

私のテイク：数はのは、今すぐ値= 22が今= 11 22を分割最大数を探す1で23、デクリメントを言わせ奇数の場合

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

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

X=23, answer reached 

しかし、私は特定のポイントに到達しても、X =必要な値を言うように、このアプローチの問題は、私は再帰的に特定の数に達することができないで、Yの値が取得されますように、1つのを追加することにより、数に到達私はそれを再利用して別の値に達することはできません

Answer 1

今、私はO(nlogn)のソリューションを提供できます。

方法はgreatest common divisor

使用f(x, y)のように思えるが、この状態にイテレーションの最小数を表します。 の場合は、x>yまたはf(x,y-x)の場合は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) 

Answer 2

数字がそれほど大きくない（たとえば1000未満）場合は、breadth-first searchを使用できます。

各頂点が数字のペアである(X,Y)であり、そのような各頂点から頂点への2つのエッジが(X+Y,Y)と(X,X+Y)である有向グラフを考えてみましょう。必要なポジションに達するまで、(0,0)からそのグラフ上のBFSを実行します。