資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告