C++で無限の線上でターゲットに到達するための最小の動きを見つけます

無限の数直線に数直線があるとします。 （-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を返します。それ以外の場合は、もう1つの手順を実行します。したがって、合計にn + 1を加算して、再び差を取ります。 n + 1がターゲットの場合は戻り、それ以外の場合はn+2でもう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