從上面的問題陳述中，我們的任務是得到最少的步驟，在每個步驟中使用加法或減法可以得到給定的數字 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 的最少步驟的方法。我希望這篇文章可以幫助您更好地學習這個概念。
以上是用加法或減法每一步得到N的最小步驟數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
