给定N，打印最小步数的序列，其中N可以从0开始使用步数的加法或减法获得。
null
笔记 ：在每一步中，我们可以从当前位置加上或减去一个与步数相等的数字。例如，在步骤1中，我们可以添加1或-1。类似地，在第2步中，我们添加2或-2，以此类推。
下图显示了通过执行指定的操作，可以在3个步骤中从0到达的所有可能位置。
![图片[1]-在每一步中使用加法或减法可以获得N的最小步数-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Screen-Shot-2018-06-27-at-12.06.16-PM.png)
例如：
Input: n = -4Output: Minimum number of Steps: 3 Step sequence: 1 -2 -3Explanation: Step 1: At step 1 we add 1 to move from 0 to 1.Step 2: At step 2 we add (-2) to move from 1 to -1.Step 3: At step 3 we add (-3) to move from -1 to -4.Input: n = 11Output: Minimum number of steps = 4 Step sequence: 1 -2 3 4 5
方法： 解决上述问题的方法是标记步数，如果N分别为正或负，我们必须在其中进行减法或加法。如果N为正，则在每一步添加数字，直到总和超过N。一旦总和超过N，则检查sum-N是否为偶数。如果sum-N是偶数，则在步骤编号（sum-N）/2处进行减法。如果sum-N是奇数，那么检查sum超过N的最后一步是偶数还是奇数。如果是奇怪的，再执行一个步骤，否则执行两个步骤。如果任何一步的总和=N，那么每一步的加法或减法都会给出答案。
设N=11，则1+2+3+4+5=15超过11。减去15-11得到4，这相当于在第2步执行减法。因此，步骤的顺序是1-2 3 4 5
设N=12，则1+2+3+4+5=15超过11。减去15-12得到3，这在任何步骤都无法执行。所以再加上两个步骤，一个是6 th 步骤7 th 步目标是使sum-N为偶数，因此在第6步执行加法，在第7步执行减法，这两个步骤结合起来可以从总和中减去1。现在sum-N是偶数，14-12=2，这相当于在步骤1执行减法。因此，步骤的顺序是-1 2 3 4 5 6-7
设N=20，则1+2+3+4+5+6超过20。减去21-20得到1，所以7加21得到28。在下一步执行加法，因为（sum-n）是奇数。sum-N给出8，这相当于在第4步执行减法。因此，步骤的顺序是1 2 3-4 5 6 7。
以下是上述方法的说明：
C++
// C++ program to print the sequence // of minimum steps in which N can be // obtained from 0 using addition or // subtraction of the step number. #include <bits/stdc++.h> using namespace std; // Function to return the vector // which stores the step sequence vector< int > findSteps( int n) { // Steps sequence vector< int > ans; // Current sum int sum = 0; // Sign of the number int sign = (n >= 0 ? 1 : -1); n = abs (n); int i; // Basic steps required to get sum >= required value. for (i = 1; sum < n; i++) { ans.push_back(sign * i); sum += i; } cout << i << endl; // Reached ahead of N if (sum > sign * n) { // If the last step was an odd number if (i % 2) { sum -= n; // sum-n is odd if (sum % 2) { ans.push_back(sign * i); sum += i++; } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } else { sum -= n; // sum-n is odd if (sum % 2) { // since addition of next step and subtraction // at the next next step will give sum = sum-1 sum--; ans.push_back(sign * i); ans.push_back(sign * -1 * (i + 1)); } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } } // returns the vector return ans; } // Function to print the steps void printSteps( int n) { vector< int > v = findSteps(n); // prints the number of steps which is the size of vector cout << "Minimum number of Steps: " << v.size() << "" ; cout << "Step sequence:" ; // prints the steps stored // in the vector for ( int i = 0; i < v.size(); i++) cout << v[i] << " " ; } // Driver Code int main() { int n = 20; printSteps(n); return 0; } |
JAVA
// Java program to print the // sequence of minimum steps // in which N can be obtained // from 0 using addition or // subtraction of the step // number. import java.util.*; class GFG { // Function to return the // Arraylist which stores // the step sequence static ArrayList<Integer> findSteps( int n) { // Steps sequence ArrayList<Integer> ans = new ArrayList<Integer>(); // Current sum int sum = 0 ; // Sign of the number int sign = (n >= 0 ? 1 : - 1 ); n = Math.abs(n); int i; // Basic steps required to // get sum >= required value. for (i = 1 ; sum < n; i++) { ans.add(sign * i); sum += i; } System.out.println( i ); // Reached ahead of N if (sum > sign * n) { // If the last step // was an odd number if (i % 2 != 0 ) { sum -= n; // sum-n is odd if (sum % 2 != 0 ) { ans.add(sign * i); sum += i++; } // subtract the // equivalent sum-n ans.set((sum / 2 ) - 1 , ans.get((sum / 2 ) - 1 ) * - 1 ); } else { sum -= n; // sum-n is odd if (sum % 2 != 0 ) { // since addition of next // step and subtraction at // the next next step will // give sum = sum-1 sum--; ans.add(sign * i); ans.add(sign * - 1 * (i + 1 )); } // subtract the // equivalent sum-n ans.set((sum / 2 ) - 1 , ans.get((sum / 2 ) - 1 ) * - 1 ); } } // returns the Arraylist return ans; } // Function to print the steps static void printSteps( int n) { ArrayList<Integer> v = findSteps(n); // prints the number of steps // which is the size of Arraylist System.out.println( "Minimum number " + "of Steps: " + v.size()); System.out.print( "Step sequence:" ); // prints the steps stored // in the Arraylist for ( int i = 0 ; i < v.size(); i++) System.out.print(v.get(i) + " " ); } // Driver Code public static void main(String args[]) { int n = 20 ; printSteps(n); } } // This code is contributed // by Arnab Kundu |
C#
// C# program to print the // sequence of minimum steps // in which N can be obtained // from 0 using addition or // subtraction of the step // number. using System; using System.Collections.Generic; class GFG { // Function to return the // Arraylist which stores // the step sequence static List< int > findSteps( int n) { // Steps sequence List< int > ans = new List< int >(); // Current sum int sum = 0; // Sign of the number int sign = (n >= 0 ? 1 : -1); n = Math.Abs(n); int i; // Basic steps required to // get sum >= required value. for (i = 1; sum < n; i++) { ans.Add(sign * i); sum += i; } Console.WriteLine( i ); // Reached ahead of N if (sum > sign * n) { // If the last step // was an odd number if (i % 2 != 0) { sum -= n; // sum-n is odd if (sum % 2 != 0) { ans.Add(sign * i); sum += i++; } // subtract the // equivalent sum-n ans[(sum / 2) - 1]= ans[(sum / 2) - 1] * -1; } else { sum -= n; // sum-n is odd if (sum % 2 != 0) { // since addition of next // step and subtraction at // the next next step will // give sum = sum-1 sum--; ans.Add(sign * i); ans.Add(sign * -1 * (i + 1)); } // subtract the // equivalent sum-n ans[(sum / 2) - 1]= ans[(sum / 2) - 1] * -1; } } // returns the Arraylist return ans; } // Function to print the steps static void printSteps( int n) { List< int > v = findSteps(n); // prints the number of steps // which is the size of Arraylist Console.WriteLine( "Minimum number " + "of Steps: " + v.Count); Console.Write( "Step sequence:" ); // prints the steps stored // in the Arraylist for ( int i = 0; i < v.Count; i++) Console.Write(v[i] + " " ); } // Driver Code public static void Main(String []args) { int n = 20; printSteps(n); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to print the sequence // of minimum steps in which N can be // obtained from 0 using addition or // subtraction of the step number. // Function to return the vector // which stores the step sequence function findSteps(n) { // Steps sequence var ans = []; // Current sum var sum = 0; // Sign of the number var sign = (n >= 0 ? 1 : -1); n = Math.abs(n); var i; // Basic steps required to get sum >= required value. for (i = 1; sum < n; i++) { ans.push(sign * i); sum += i; } document.write( i + "<br>" ); // Reached ahead of N if (sum > sign * n) { // If the last step was an odd number if (i % 2) { sum -= n; // sum-n is odd if (sum % 2) { ans.push(sign * i); sum += i++; } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } else { sum -= n; // sum-n is odd if (sum % 2) { // since addition of next step and subtraction // at the next next step will give sum = sum-1 sum--; ans.push(sign * i); ans.push(sign * -1 * (i + 1)); } // subtract the equivalent sum-n ans[(sum / 2) - 1] *= -1; } } // returns the vector return ans; } // Function to print the steps function printSteps(n) { var v = findSteps(n); // prints the number of steps which is the size of vector document.write( "Minimum number of Steps: " + v.length + "<br>" ); document.write( "Step sequence:" ); // prints the steps stored // in the vector for ( var i = 0; i < v.length; i++) document.write( v[i] + " " ); } // Driver Code var n = 20; printSteps(n); // This code is contributed by itsok. </script> |
Python3
# Python3 program to pr the sequence # of minimum steps in which N can be # obtained from 0 using addition or # subtraction of the step number. # Function to return the # which stores the step sequence def findSteps( n): # Steps sequence ans = [] # Current sum sum = 0 # Sign of the number sign = 1 if n > = 0 else - 1 n = abs (n) i = 1 # Basic steps required to get sum >= required value. while sum <n : ans.append(sign * i) sum + = i i + = 1 print (i) # Reached ahead of N if ( sum > sign * n) : # If the last step was an odd number if (i % 2 ) : sum - = n # sum-n is odd if ( sum % 2 ) : ans.append(sign * i) sum + = i i + = 1 # subtract the equivalent sum-n ans[ int (( sum / 2 ) - 1 )] * = - 1 else : sum - = n # sum-n is odd if ( sum % 2 ) : # since addition of next step and subtraction # at the next next step will give sum = sum-1 sum - = 1 ans.append(sign * i) ans.append(sign * - 1 * (i + 1 )) # subtract the equivalent sum-n ans[ int (( sum / 2 ) - 1 )] * = - 1 # returns the return ans # Function to pr the steps def prSteps(n): v = findSteps(n) # prs the number of steps which is the size of print ( "Minimum number of Steps:" , len (v)) print ( "Step sequence:" ,end = "") # prs the steps stored # in the for i in range ( len (v)): print (v[i],end = " " ) # Driver Code if __name__ = = '__main__' : n = 20 prSteps(n) |
输出：
7Minimum number of Steps: 7Step sequence:1 2 3 -4 5 6 7
时间复杂性： O（sqrt（N）） 辅助空间： O（sqrt（N）） 注： sum=i*（i+1）/2等于或大于N，表示i为sqrt（N）。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
