Найдите минимальное количество шагов, чтобы уменьшить N до нуля

Question

В последние несколько дней я сталкиваюсь с некоторыми трудностями при попытке выполнить следующее задание. Надеюсь, вы, ребята, можете помочь:

Мне дано одно число N, и мне разрешеноВыполните любую из двух операций над N в каждом движении:

One - Если мы возьмем 2 целых числа, где N = x * y, то мы можем изменить значение N на максимальное значение междуx и y.

Два - Уменьшите значение N на 1.

Я хочу найти минимальное количество шагов для уменьшения N до нуля.Это то, что я имею до сих пор, я не уверен, каков наилучший способ реализовать функцию для нахождения делителя (someFindDevisorFunction), и если эта функция ' f ' фактически выдаст требуемый вывод.

  int f(int n)
{
  int div,firstWay,secondWay;
  if(n == 0)
    return 0;

  div = SomefindDivisorFunction(n);
  firstWay = 1 + f(n-1);
  if(div != 1)
  {
    secondWay = 1 + f(div);
    if (firstWay < secondWay)
        return firstWay;
    return secondWay;
  }

  return firstWay;
}

Например, если я введу число 150, результат будет: 75 - 25 - 5 - 4 - 2 - 1 - 0

Answer 1

Я считаю, что это рекурсивная или итеративная проблема.

Подход OP намекает на рекурсивность.

---

Далее следует рекурсивное решение:

На каждом шаге код считает шаги различных альтернатив:

steps(n) = min(
  steps(factor1_of_n) + 1,
  steps(factor2_of_n) + 1,
  steps(factor3_of_n) + 1,
  ...
  steps(n-1) + 1)

Приведенное ниже кодированное решение неэффективно, ноон исследует все возможности и получает ответ.

int solve_helper(int n, bool print) {
  int best_quot = 0;
  int best_quot_score = INT_MAX;
  int quot;
  for (int p = 2; p <= (quot = n / p); p++) {
    int rem = n % p;
    if (rem == 0 && quot > 1) {
      int score = solve_helper(quot, false) + 1;
      if (score < best_quot_score) {
        best_quot_score = score;
        best_quot = quot;
      }
    }
  }

  int dec_score = n > 0 ? solve_helper(n - 1, false) + 1 : 0;

  if (best_quot_score < dec_score) {
    if (print) {
      printf("/ %d ", best_quot);
      solve_helper(best_quot, true);
    }
    return best_quot_score;
  }
  if (print && n > 0) {
    printf("- %d ", n - 1);
    solve_helper(n - 1, true);
  }
  return dec_score;
}

int main() {
  int n = 75;
  printf("%d ", n);
  solve(n, true);
  printf("\n");
}

Вывод

75 / 25 / 5 - 4 / 2 - 1 - 0 

---

Итеративный

TBD

Answer 2

Если вы начнете искать делитель с 2 и продолжите свой путь вверх, то последняя найденная пара делителей будет включать самый большой делитель.В качестве альтернативы вы можете начать поиск с divisor = N / 2 и работать вниз, когда первый найденный делитель будет иметь самый большой делитель числа N.