从上面的问题陈述中，我们的任务是得到最少的步骤，在每个步骤中使用加法或减法可以得到给定的数字 n。我们可以理解，我们需要打印可以执行的最小步骤数以及对任何给定整数 n 的步骤顺序，通过步骤号的加减来达到从 0 开始的数字。
在这个问题集中，我们可以在每一步的当前位置上添加或减去等于步数的数字。例如，我们可以在第 1 步添加 1 或 -1。进一步，我们可以在第 2 步添加 2 或 -2，依此类推。我们可以根据情况在每一步添加或减去数字。
这个问题的主要挑战是我们需要从 0 开始执行最少的步骤来达到 N。让我们通过一个例子更好地理解这个问题。
下面给出的示例将向您说明通过执行上述操作，我们从 0 开始的 2 个步骤可以得到的每个数字。
例如，假设我们有 N=1。
输出
Minimum no of steps: 1 Sequence of steps: 1
说明
我们可以通过两种方式达到 1 -
只需在第 1 步加 1 即可从 0 移动到 1，这需要 1 步。
在步骤 1 中减 1 以从 0 移动到 -1，然后在步骤 2 中加 2 以从 -1 移动到 1，这需要 2 个步骤。
由于问题表明我们需要最少的步数才能达到任意数字 N，因此该输入的所需输出将为 1。
对于，N=3
输出
Minimum no of steps: 2 Sequence of steps: 1 2
说明
我们在步骤 1 中添加 1 以从 0 移动到 1，然后在步骤 2 中添加 2 以从 1 移动到 3。
方法
解决问题的最好方法是首先弄清楚N是正数还是负数。我们必须分别在适当的步数上加上或减去才能解决问题。
如果 N 是正数，则继续添加步数，直到总和大于或等于 N。
同样，如果N是负数，则继续减去步数，直到总和大于或等于N。
如果在上述情况下总和等于 N，则返回步骤数和步骤顺序。主要问题是超过N时的情况处理。
一旦总和超过N，检查(sum-N)是偶数还是奇数。
-
如果 (sum-N) 是偶数，那么我们必须以 (sum-N)/2 步长执行减法才能达到 N。
让我们通过一个合适的例子更好地理解这个案例。
对于，N=8
1+2+3+4=10，超过了8。
因为 10-8=2 这是偶数。所以我们将以 2/2 步长减去，即
第 1 步。因此，步骤的顺序将为 -1 2 3 4 和最小值
到达 N 的步数将为 4。
-
如果(sum-N)是奇数，首先判断上一步总和超过N的数是偶数还是奇数。
如果上一步是奇数，则通过添加下一个步骤编号来执行一个步骤，这将使我们的 (sum-N) 成为偶数，然后执行上述步骤以获得所需的结果。
例如，N=9
1+2+3+4=10，超过了 9。
因为10-9=1，这是一个奇数。下一步是 5，它是一个奇数，因此我们只需执行一步，将 5 加到总和上，得到 15，使得 (sum-N)=6。在步骤 3 中执行减法将得到序列 1 2 -3 4 5，这是所需的输出。
假设上一步是偶数，在这种情况下，我们需要执行两步，将第 i 步相加并减去第 (i+1) 步，得到 (sum- N) 作为偶数以获得所需的步骤序列。
对于 N=5
1+2+3=6，超过5。
由于 (sum-N) =1，所以当 su 超过数字 N 时，我们将考虑最后一步。由于它是偶数，我们将执行两个步骤，即第 4 步和第 5 步。我们的任务是使 (sum-N) 即使如此，通过在第 4 步添加并在第 5 步减去，我们可以使 (sum-N) 即使从总和中减去 1。由于 (sum-N) 等于 0，因此我们得到 N。因此，序列为 1 2 3 4 -5。
示例
下面是该方法的 C++ 代码 -
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void minimumStep(int n){
vector <int> steps; // for storing the sequence
int totalSum=0;
int temp=0;
if(n>=0){ // if n is positive then temp will store positive
temp=1;
} else {
temp=-1; // n is negative then temp will store negative
}
n=abs(n);
int step=0;
for(step=1;totalSum<n;step++){ // for storing the steps till sum is not greater than n
steps.push_back(temp*step);
totalSum=totalSum+step;
}
if(totalSum>temp*n) { //when sum greater than n
if(step%2==0) { //when step is even
totalSum=totalSum-n;
if((totalSum)%2!=0) { // when totalSum-n is odd
steps.push_back(temp*step); //store the addition of next step
steps.push_back((temp*-1)*(step+1)); // store the subtraction of next step
totalSum--; //make totalSum even
}
int check=(totalSum)/2;
check--;
steps[check]=steps[check]*-1;
} else { //when step is odd
totalSum=totalSum-n;
if((totalSum)%2!=0) { // when totalSum-n is odd
steps.push_back(temp*step); //store the next addition value
totalSum+=step;
step++;
}
int check=(totalSum)/2;
check--;
steps[check]=steps[check]*-1;
}
}
//print the minimum number of steps taken
cout<<"The minimum number of steps : "<<steps.size()<<endl;
//print the steps is stored in vector
cout<<"Sequence of steps : ";
for(int i=0;i<steps.size();i++){
cout<<steps[i]<<" ";
}
}
int main(){
int m=17;
minimumStep(m);
return 0;
}
输出
The minimum number of steps : 6 Sequence of steps : 1 -2 3 4 5 6
时间复杂度：O(sqrt(N))
空间复杂度：O(sqrt(N))
结论
在本文中，我们试图解释通过在每一步中添加或减去并打印序列来找出达到 N 的最少步骤的方法。我希望这篇文章可以帮助您更好地学习这个概念。
