给定一个从-无穷大到+无穷大的数字行。从0开始，可以向左或向右。条件是，在我的行动中，你采取我的步骤。 a） 找出你是否能达到给定的数字x b） 如果我们真的能达到某个给定的数字x，那就找到最理想的方法。例如，3可以通过两个步骤达到，（0，1）（1，3），4可以通过三个步骤达到（0，-1），（-1，1）（1，4）。 资料来源： Flipkart面试问题
null
需要注意的重要一点是，我们可以到达任何目的地，因为移动长度始终为1。在任何一步，我们都可以向前移动i，然后向后移动i+1。 下面是Arpit Thapar建议的递归解决方案 在这里 . 1） 因为从0到+5和-5的距离是相同的，所以我们找到了目的地绝对值的答案。
2） 我们使用一个递归函数作为参数： i） 源顶点 ii）采取的最后一步的价值 iii）目的地
3） 如果在任何点上，源顶点=目标；返回步数。
4） 否则我们可以朝两个可能的方向走。在这两种情况下都采取最少的步骤。 从任何顶点我们都可以到达： （电流源+最后一步+1）和 （电流源-最后一步-1）
5） 如果在任何一点上，我们位置的绝对值超过了我们目的地的绝对值，那么直觉上，从这里不可能有最短的路径。因此我们将步长的值设为INT_MAX，这样当我取两种可能性中的最小值时，这一个就被消除了。
如果不使用最后一步，程序将进入无限递归，并给出运行时错误。
下面是上述想法的实现。请注意，解决方案只计算步骤。
C++
// C++ program to count number of // steps to reach a point #include<bits/stdc++.h> using namespace std; // Function to count number of steps // required to reach a destination // source -> source vertex // step -> value of last step taken // dest -> destination vertex int steps( int source, int step, int dest) { // base cases if ( abs (source) > (dest)) return INT_MAX; if (source == dest) return step; // at each point we can go either way // if we go on positive side int pos = steps(source + step + 1, step + 1, dest); // if we go on negative side int neg = steps(source - step - 1, step + 1, dest); // minimum of both cases return min(pos, neg); } // Driver code int main() { int dest = 11; cout << "No. of steps required to reach " << dest << " is " << steps(0, 0, dest); return 0; } |
JAVA
// Java program to count number of // steps to reach a point import java.io.*; class GFG { // Function to count number of steps // required to reach a destination // source -> source vertex // step -> value of last step taken // dest -> destination vertex static int steps( int source, int step, int dest) { // base cases if (Math.abs(source) > (dest)) return Integer.MAX_VALUE; if (source == dest) return step; // at each point we can go either way // if we go on positive side int pos = steps(source + step + 1 , step + 1 , dest); // if we go on negative side int neg = steps(source - step - 1 , step + 1 , dest); // minimum of both cases return Math.min(pos, neg); } // Driver Code public static void main(String[] args) { int dest = 11 ; System.out.println( "No. of steps required" + " to reach " + dest + " is " + steps( 0 , 0 , dest)); } } // This code is contributed by Prerna Saini |
Python3
# python program to count number of # steps to reach a point import sys # Function to count number of steps # required to reach a destination # source -> source vertex # step -> value of last step taken # dest -> destination vertex def steps(source, step, dest): #base cases if ( abs (source) > (dest)) : return sys.maxsize if (source = = dest): return step # at each point we can go # either way # if we go on positive side pos = steps(source + step + 1 , step + 1 , dest) # if we go on negative side neg = steps(source - step - 1 , step + 1 , dest) # minimum of both cases return min (pos, neg) # Driver Code dest = 11 ; print ( "No. of steps required" , " to reach " ,dest , " is " , steps( 0 , 0 , dest)); # This code is contributed by Sam007. |
C#
// C# program to count number of // steps to reach a point using System; class GFG { // Function to count number of steps // required to reach a destination // source -> source vertex // step -> value of last step taken // dest -> destination vertex static int steps( int source, int step, int dest) { // base cases if (Math.Abs(source) > (dest)) return int .MaxValue; if (source == dest) return step; // at each point we can go either way // if we go on positive side int pos = steps(source + step + 1, step + 1, dest); // if we go on negative side int neg = steps(source - step - 1, step + 1, dest); // minimum of both cases return Math.Min(pos, neg); } // Driver Code public static void Main() { int dest = 11; Console.WriteLine( "No. of steps required" + " to reach " + dest + " is " + steps(0, 0, dest)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to count number // of steps to reach a point // Function to count number // of steps required to reach // a destination // source -> source vertex // step -> value of last step taken // dest -> destination vertex function steps( $source , $step , $dest ) { // base cases if ( abs ( $source ) > ( $dest )) return PHP_INT_MAX; if ( $source == $dest ) return $step ; // at each point we // can go either way // if we go on positive side $pos = steps( $source + $step + 1, $step + 1, $dest ); // if we go on negative side $neg = steps( $source - $step - 1, $step + 1, $dest ); // minimum of both cases return min( $pos , $neg ); } // Driver code $dest = 11; echo "No. of steps required to reach " , $dest , " is " , steps(0, 0, $dest ); // This code is contributed by aj_36 ?> |
Javascript
<script> // JavaScript program to count number of // steps to reach a point // Function to count number of steps // required to reach a destination // source -> source vertex // step -> value of last step taken // dest -> destination vertex function steps(source, step, dest) { // base cases if (Math.abs(source) > (dest)) return Number.MAX_SAFE_INTEGER; if (source == dest) return step; // at each point we can go either way // if we go on positive side let pos = steps(source + step + 1, step + 1, dest); // if we go on negative side let neg = steps(source - step - 1, step + 1, dest); // minimum of both cases return Math.min(pos, neg); } // Driver code let dest = 11; document.write( "No. of steps required to reach " + dest + " is " + steps(0, 0, dest)); // This code is contributed by Surbhi Tyagi. </script> |
输出：
No. of steps required to reach 11 is 5
感谢Arpit Thapar提供上述算法和实现。 优化解决方案： 在一条无限长的线上找到到达目标的最小移动量
本文由Abhay撰稿。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
