找到将 N 减少到零的最小步数 [英] Find the minimum number of steps to decrease N to zero

问题描述

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

I'm facing some difficulties in the last few days while trying to finish the following task, I hope you guys can assist :

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

I'm given a single number N, and I'm allowed to perform any of the two operations on N in each move :

One - 如果我们取 2 个整数，其中 N = x * y ，那么我们可以将 N 的值更改为 x 和 y 之间的最大值.

One - If we take 2 integers where N = x * y , then we can change the value of N to the maximum between x and y.

两个 - 将 N 的值减少 1.

Two - Decrease the value of N by 1.

我想找到将 N 减少到零的最少步数.到目前为止，这是我所拥有的，我不确定实现该函数以查找除数 (someFindDevisorFunction) 的最佳方法是什么，如果这个 'f' 函数实际上会产生所需的输出.

I want to find the minimum number of steps to reduce N to zero. This is what I have so far, I'm not sure what is the best way to implement the function to find the divisor (someFindDevisorFunction), and if this 'f' function would actually produce the required output.

  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

For example, if I enter the number 150 , the output would be : 75 - 25 - 5 - 4 - 2 - 1 - 0

推荐答案

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

I see this a recursive or iterative problem.

OP 的方法暗示了递归.

OP's approach hints at recursive.

递归解决方案如下:

在每一步，代码都会计算各种备选方案的步数:

At each step, code counts the steps of the various alternatives:

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

下面的编码解决方案效率低下，但它确实探索了所有可能性并得出了答案.

The coded solution below is inefficient, but it does explore all possibilities and gets to the answer.

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 

<小时>

迭代

待定

这篇关于找到将 N 减少到零的最小步数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！