查找在C ++中无限行达到目标的最小移动

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们在无限数行中有一个数字位置。（从-inf到+ inf）。从0开始，我们必须按 移动到目标。在第i步中，我们可以向左或向右移动。我们必须找到所需的最小移动量。假设目标为2，则最小步长为3。从0到1，从1到-1和从-1到2。

为了解决这个问题，我们要记住一些重要的观点。如果目标为负，则将其视为正，因为数字行相同。为了解决问题，想法是尽可能地朝一个方向发展。因此，从0到1，从1到3（1 + 2），从3到6（1 + 2 + 3），依此类推。因此，如果在第n次移动之后找到了目标，则只需返回移动次数。但是，如果基础要大于目标，那么我们就必须找出我们前进的差距。现在我们可以看到，如果将第i步向后移动，则总和为（sum – 2i）。现在，如果sum-2i是目标，那么我们得到了结果。但是差异可以是偶数或奇数。对于偶数，返回n作为结果，否则，我们又走了一步。因此，将n + 1相加，然后再次求和。如果n + 1是目标，则返回，

示例

#include<iostream>
#include<cmath>
using namespace std;
int minStepToTarget(int target) {
   target = abs(target);
   int sum = 0, min_step = 0;
   while (sum < target || (sum - target) % 2 != 0) {
      min_step++;
      sum += min_step;
   }
   return min_step;
}
int main() {
   int target = 11;
   cout << "Minimum step to reach the target is: " << minStepToTarget(target);
}

输出结果

Minimum step to reach the target is: 5

以上是 查找在C ++中无限行达到目标的最小移动 的全部内容， 来源链接： utcz.com/z/316122.html

回到顶部