给定砖块总数T，找出使用给定砖块可以形成的楼梯台阶的数量，如果步骤S有砖块B，那么步骤S+1应该正好有B+1砖块，并且使用的砖块总数应该小于或等于可用砖块的数量。
null
注： 制作楼梯第一步所需的砖数为2，即S=1步必须正好有B=2块砖。
例如：
Input : 15Output : 4Bricks should be arranged in this pattern to solve for T = 15:
![图片[1]-找到楼梯台阶的数量-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_staircase.jpg)
Explanation:Number of bricks at step increases by one.At Step 1, Number of bricks = 2, Total = 2At step 2, Number of bricks = 3, Total = 5At step 3, Number of bricks = 4, Total = 9At step 4, Number of bricks = 5, Total = 14If we add 6 more bricks to form new step, then the total number of bricks available will surpass. Hence, number of steps that can be formed are 4 andnumber of bricks used are 14 and we are left with 1 brick which is useless.Input : 40Output : 7Bricks should be arranged in this pattern to solve for T = 40:
![图片[2]-找到楼梯台阶的数量-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_staircase2.jpg)
Explanation:At Step 1, Number of bricks = 2, Total = 2At step 2, Number of bricks = 3, Total = 5At step 3, Number of bricks = 4, Total = 9At step 4, Number of bricks = 5, Total = 14At step 5, Number of bricks = 6, Total = 20At step 6, Number of bricks = 7, Total = 27At step 7, Number of bricks = 8, Total = 35If we add 9 more bricks to form new step,then the total number of bricks available will surpass.Hence, number of steps that can be formed are 7 and number of bricks used are 35 and we are left with 5 bricks which are useless.
方法： 我们对步数感兴趣，我们知道每一步Si使用的砖数正好是两个。我们可以将这个问题表示为一个等式： n*（n+1）/2=T（对于从1、2、3、4、5开始的自然数序列） n*（n+1）=2*T n-1将代表我们的最终解决方案，因为我们的问题系列从2,3,4,5开始… 现在，我们只需要解这个方程，为此我们可以利用二进制搜索来找到这个方程的解。二进制搜索的上下界是1和T。
以下是上述方法的实施情况：
C++
// C++ program to find the number of steps #include <bits/stdc++.h> using namespace std; // Modified Binary search function // to solve the equation int solve( int low, int high, int T) { while (low <= high) { int mid = (low + high) / 2; // if mid is solution to equation if ((mid * (mid + 1)) == T) return mid; // if our solution to equation // lies between mid and mid-1 if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T) return mid - 1; // if solution to equation is // greater than mid if ((mid * (mid + 1)) > T) high = mid - 1; // if solution to equation is less // than mid else low = mid + 1; } return -1; } // driver function int main() { int T = 15; // call binary search method to // solve for limits 1 to T int ans = solve(1, T, 2 * T); // Because our pattern starts from 2, 3, 4, 5... // so, we subtract 1 from ans if (ans != -1) ans--; cout << "Number of stair steps = " << ans << endl; return 0; } |
JAVA
// Java program to find the number of steps import java.util.*; import java.lang.*; public class GfG { // Modified Binary search function // to solve the equation public static int solve( int low, int high, int T) { while (low <= high) { int mid = (low + high) / 2 ; // if mid is solution to equation if ((mid * (mid + 1 )) == T) return mid; // if our solution to equation // lies between mid and mid-1 if (mid > 0 && (mid * (mid + 1 )) > T && (mid * (mid - 1 )) <= T) return mid - 1 ; // if solution to equation is // greater than mid if ((mid * (mid + 1 )) > T) high = mid - 1 ; // if solution to equation is less // than mid else low = mid + 1 ; } return - 1 ; } // driver function public static void main(String argc[]) { int T = 15 ; // call binary search method to // solve for limits 1 to T int ans = solve( 1 , T, 2 * T); // Because our pattern starts from 2, 3, 4, 5... // so, we subtract 1 from ans if (ans != - 1 ) ans--; System.out.println( "Number of stair steps = " + ans); } } /* This code is Contributed by Sagar Shukla */ |
Python3
# Python3 code to find the number of steps # Modified Binary search function # to solve the equation def solve( low, high, T ): while low < = high: mid = int ((low + high) / 2 ) # if mid is solution to equation if (mid * (mid + 1 )) = = T: return mid # if our solution to equation # lies between mid and mid-1 if (mid > 0 and (mid * (mid + 1 )) > T and (mid * (mid - 1 )) < = T) : return mid - 1 # if solution to equation is # greater than mid if (mid * (mid + 1 )) > T: high = mid - 1 ; # if solution to equation is # less than mid else : low = mid + 1 return - 1 # driver code T = 15 # call binary search method to # solve for limits 1 to T ans = solve( 1 , T, 2 * T) # Because our pattern starts from 2, 3, 4, 5... # so, we subtract 1 from ans if ans ! = - 1 : ans - = 1 print ( "Number of stair steps = " , ans) # This code is contributed by "Sharad_Bhardwaj". |
C#
// C# program to find the number of steps using System; public class GfG { // Modified Binary search function // to solve the equation public static int solve( int low, int high, int T) { while (low <= high) { int mid = (low + high) / 2; // if mid is solution to equation if ((mid * (mid + 1)) == T) return mid; // if our solution to equation // lies between mid and mid-1 if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T) return mid - 1; // if solution to equation is // greater than mid if ((mid * (mid + 1)) > T) high = mid - 1; // if solution to equation is less // than mid else low = mid + 1; } return -1; } // Driver function public static void Main() { int T = 15; // call binary search method to // solve for limits 1 to T int ans = solve(1, T, 2 * T); // Because our pattern starts //from 2, 3, 4, 5... // so, we subtract 1 from ans if (ans != -1) ans--; Console.WriteLine( "Number of stair steps = " + ans); } } /* This code is Contributed by vt_m */ |
PHP
<?php // PHP program to find the // number of steps // Modified Binary search function // to solve the equation function solve( $low , $high , $T ) { while ( $low <= $high ) { $mid = ( $low + $high ) / 2; // if mid is solution // to equation if (( $mid * ( $mid + 1)) == $T ) return $mid ; // if our solution to equation // lies between mid and mid-1 if ( $mid > 0 && ( $mid * ( $mid + 1)) > $T && ( $mid * ( $mid - 1)) <= $T ) return $mid - 1; // if solution to equation is // greater than mid if (( $mid * ( $mid + 1)) > $T ) $high = $mid - 1; // if solution to // equation is less // than mid else $low = $mid + 1; } return -1; } // Driver Code $T = 15; // call binary search // method to solve // for limits 1 to T $ans = solve(1, $T , 2 * $T ); // Because our pattern // starts from 2, 3, 4, 5... // so, we subtract 1 from ans if ( $ans != -1) $ans --; echo "Number of stair steps = " , $ans , "" ; // This code is contributed by aj_36 ?> |
Javascript
<script> // JavaScript program to find the number of steps // Modified Binary search function // to solve the equation function solve(low, high, T) { while (low <= high) { let mid = Math.floor((low + high) / 2); // If mid is solution to equation if ((mid * (mid + 1)) == T) return mid; // If our solution to equation // lies between mid and mid-1 if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T) return mid - 1; // If solution to equation is // greater than mid if ((mid * (mid + 1)) > T) high = mid - 1; // If solution to equation is less // than mid else low = mid + 1; } return -1; } // Driver code let T = 15; // Call binary search method to // solve for limits 1 to T let ans = solve(1, T, 2 * T); // Because our pattern starts from 2, 3, 4, 5... // so, we subtract 1 from ans if (ans != -1) ans--; document.write( "Number of stair steps = " + ans); // This code is contributed by Surbhi Tyagi. </script> |
输出：
Number of stair steps = 4
本文由 阿披实拉吉普特 .
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
