找到将 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

如果您开始寻找一个包含 2 的除数，然后继续查找，那么您找到的最后一对除数将包含最大的除数。或者，您可以使用 divisor = N/2 开始搜索并向下搜索，当找到的第一个除数将是 N.

的最大除数时

Answer 2

我认为这是一个递归或迭代问题。

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

迭代

待定

Answer 3

 int minmoves(int n){
    if(n<=3){
        return n;
    }
    int[] dp=new int[n+1];
    Arrays.fill(dp,-1);
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    dp[3]=3;
    int sqr;
    for(int i=4;i<=n;i++){
        sqr=(int)Math.sqrt(i);
        int best=Integer.MAX_VALUE;
        while(sqr >1){
            if(i%sqr==0){
                int fact=i/sqr;
                best=Math.min(best,1+dp[fact]);
            }
            sqr--;
        }
        best=Math.min(best,1+dp[i-1]);
        dp[i]=best;
    }
    return dp[n];
}

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

Find the minimum number of steps to decrease N to zero

c

recursion

minimum