数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找无限直线上到达目标的最小移动步数
假设我们在无限数轴上有一个数字位置（-inf 到 +inf）。从 0 开始，我们必须通过以下方式移动来到达目标。在第 i 次移动中，我们可以向左或向右移动 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 加到 sum 中，然后再次取差值。如果 n + 1 是目标，则返回，否则再走一步，用 n + 2。
示例
#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
更新于： 2019-12-18
322 次浏览
广告