найти минимальный шаг, чтобы сделать число из пары чисел

Question

Давайте предположим, что у нас есть пара чисел (a, b).Мы можем получить новую пару (a + b, b) или (a, a + b) из данной пары за один шаг.

Пусть начальная пара чисел будет (1,1).Наша задача - найти число k, то есть наименьшее количество шагов, необходимых для преобразования (1,1) в пару, где хотя бы одно число равно n.Я решил эту проблему, найдя все возможные пары, а затем возвратил минимальные шаги, в которых формируется заданное число, но на его вычисление уходит довольно много времени. Думаю, это должно быть как-то связано с поиском gcd.can кто-нибудь, пожалуйста, помогите или предоставьте мнекакая-то ссылка для концепции.Вот программа, которая решила проблему, но она мне не понятна ...

#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 на минимальном количестве шагов, необходимых для перехода к паре (a, b) из (1,1). Вы берете двумерный массив, в котором хранится ответ для данной пары, а затем делаете рекурсию с памяткой:

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, но это общий подход к таким проблемам. Надеюсь, это поможет.

EDIT: вернуть достаточно большое значение в dp, если a равно нулю

Answer 2

Прежде всего, максимальное число, которое вы можете получить после k-3 шагов - это k-е число фибиночков.Пусть t будет магическим отношением.

Теперь для n начните с (n, upper (n / t)).

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

Итеративно рассчитайте NumSteps (n, upper (n / t)))

PS: использование верхнего (н / т) не всегда дает оптимальное решение.Вы можете сделать локальный поиск вокруг этого значения для получения оптимальных результатов.Для обеспечения оптимальности вы можете попробовать ВСЕ значения от 0 до n-1, в которых сложность наихудшего случая равна O (n ^ 2).Но если оптимальное значение получается из значения, близкого к верхнему (n / t), решение равно O (nlogn)

Answer 3

Вы можете использовать алгоритм поиска в ширину, чтобы сделать это.На каждом шаге вы генерируете все возможные СЛЕДУЮЩИЕ шаги, которые вы не видели раньше.Если набор следующих шагов содержит результат, вы сделали, если не повторить.Количество повторений - минимальное количество преобразований.