algorithm - 找到从一对数字中生成数字的最小步骤

Question

假设我们有一对数字 (a, b)。我们可以在一个步骤中从给定的对中得到一个新的对 (a + b, b) 或 (a, a +⟩b)。

令初始的一对数字为 (1,1)。我们的任务是找到数字 k，即，将 (1,1) 转换为至少有一个数字等于 n 的对所需的最少步骤数。 我通过找到所有可能的对来解决它，然后返回形成给定数字的最小步骤，但是计算需要很长时间。我想这一定与找到 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

我解决这类问题的方法(我从 projecteuler.net 得到的)是计算序列的前几项，然后在 oeis 中搜索具有相同项的序列。这可以使解决方案的速度提高一个数量级。在您的情况下，序列可能是:http://oeis.org/A178031但不幸的是它没有易于使用的公式。 : 由于 n 的约束相对较小，您可以执行 dp从 (1,1) 到 (a,b) 对所需的最少步数。您采用一个二维数组来存储给定对的答案，然后使用内存进行递归:

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 为零，则在 dp 中返回一个足够大的值