使用加法或減法在每一步獲得 N 的最小步數

---

從以上問題陳述中，我們的任務是獲得在每一步使用加法或減法獲得給定數字 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 的最小步數並列印序列的方法。我希望本文能幫助您更好地學習這個概念。