c - 找到将 N 减少到零的最小步数

Question

这几天我在尝试完成以下任务时遇到了一些困难，希望你们能提供帮助:

我得到了一个数字 N，我可以在每一步中对 N 执行以下两个操作中的任何一个:

一个 - 如果我们取 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 

---

迭代

待定