数字のペアから数値を作る最小ステップを見つけよう

Question

数字のペア（a、b）があるとしましょう。与えられたペアから（a + b、b）または（a、a + b）の新しいペアを一度に得ることができます。

最初の数字のペアを（1,1）とします。私たちの仕事は、少なくとも1つの数字がnに等しいペアに（1,1）を変換するのに必要なステップ数を見つけることです。 私は可能なすべてのペアを見つけて解決し、与えられた数が形成されている最小ステップを返しますが、計算にかなりの時間がかかります。これは何とかgcdを見つけることと関連しているに違いないと思います。私は概念のためのいくつかのリンク。 は、ここでの問題を解決するプログラムですが、それはあなたがこれを行うには幅優先探索アルゴリズムを使用することができます...私に

#include <iostream> 
using namespace std; 
#define INF 1000000000 

int n,r=INF; 

int f(int a,int b){ 

    if(b<=0)return INF; 
    if(a>1&&b==1)return a-1; 
    return f(b,a-a/b*b)+a/b; 

} 


int main(){ 

    cin>>n; 
    for(int i=1;i<=n/2;i++){ 
    r=min(r,f(n,i)); 
    } 
    cout<<(n==1?0:r)<<endl; 

} 

Answer 1

クリートされていません。各ステップでは、以前に見たことのないすべてのNEXTステップを生成します。次のステップのセットに結果が含まれている場合、繰り返されない場合は完了です。これを繰り返す回数は最小限の変換回数です。

Answer 2

まず、k-3ステップ後に得られる最大数は、k番目のフィブリノキ数です。マジック率をtとする。

ここで、nで始まる（n、上（n/t））。常に最適な解決策を提供しない場合があり、上部（N/T）を使用して：

If x>y: 
    NumSteps(x,y) = NumSteps(x-y,y)+1 
Else: 
    NumSteps(x,y) = NumSteps(x,y-x)+1 

を反復NumSteps（N、上位（N/T））

PSを算出します。この値を中心に最適な結果を得るためにローカル検索を行うことができます。最適性を保証するために、0からn-1までのすべての値を試すことができます。この場合、最悪の複雑さはO（n^2）です。しかし、最適値が上（n/t）に近い値である場合、解はO（nlogn）

Answer 3

私のアプローチはprojecteuler.netから得たものですシーケンスの用語を抽出し、同じ用語を持つシーケンスをoeisで検索します。これにより、ソリューションのオーダーがさらに速くなります。あなたの場合、シーケンスはおそらく：http://oeis.org/A178031ですが、残念なことにそれは簡単に式を使用することはありません。 ： nの制約が比較的小さいので、（1,1）からペア（a、b）に到達するために必要な最小ステップ数をdpにすることができます。あなたが与えられたペアのための答えを格納2次元配列を取り、その後、あなたがメモ化で再帰を行います

int mem[5001][5001]; 
int solve(int a, int b) { 
    if (a == 0) { 
    return mem[a][b] = b + 1; 
    } 
    if (mem[a][b] != -1) { 
    return mem[a][b]; 
    } 
    if (a == 1 && b == 1) { 
    return mem[a][b] = 0; 
    } 
    int res; 
    if (a > b) { 
    swap(a,b); 
    } 
    if (mem[a][b%a] == -1) { // not yet calculated 
    res = solve(a, b%a); 
    } else { // already calculated 
    res = mem[a][b%a]; 
    } 
    res += b/a; 
    return mem[a][b] = res; 
} 


int main() { 
    memset(mem, -1, sizeof(mem)); 
    int n; 
    cin >> n; 
    int best = -1; 
    for (int i = 1; i <= n; ++i) { 
    int temp = solve(n, i); 
    if (best == -1 || temp < best) { 
     best = temp; 
    } 
    } 
    cout << best << endl; 
} 

実際には、この場合にはそこDPとBFSの間に大きな違いはありませんが、これは一般的ですそのような問題へのアプローチ。お役に立てれば。

編集：aが0の場合、dpに十分大きな値を返します