给定一个整数n,表示一个煎饼上可以切的块数,求出通过切n块可以形成的最大块数。 例如:
null
Input : n = 1Output : 2With 1 cut we can divide the pancake in 2 piecesInput : 2Output : 4With 2 cuts we can divide the pancake in 4 piecesInput : 3Output : 7We can divide the pancake in 7 parts with 3 cutsInput : 50Output : 1276
Let f(n) denote the maximum number of piecesthat can be obtained by making n cuts.Trivially,f(0) = 1 As there'd be only 1 piece without any cut.Similarly,f(1) = 2Proceeding in similar fashion we can deduce the recursive nature of the function.The function can be represented recursively as :f(n) = n + f(n-1)Hence a simple solution based on the above formula can run in O(n).
我们可以优化以上公式。
We now know ,f(n) = n + f(n-1) Expanding f(n-1) and so on we have ,f(n) = n + n-1 + n-2 + ...... + 1 + f(0)which gives,f(n) = (n*(n+1))/2 + 1
因此,通过这种优化,我们可以回答O(1)中的所有查询。 以下是上述理念的实施:
C++
// A C++ program to find the solution to // The Lazy Caterer's Problem #include <iostream> using namespace std; // This function receives an integer n // and returns the maximum number of // pieces that can be made form pancake // using n cuts int findPieces( int n) { // Use the formula return (n * ( n + 1)) / 2 + 1; } // Driver Code int main() { cout << findPieces(1) << endl; cout << findPieces(2) << endl; cout << findPieces(3) << endl; cout << findPieces(50) << endl; return 0; } |
JAVA
// Java program to find the solution to // The Lazy Caterer's Problem import java.io.*; class GFG { // This function returns the maximum // number of pieces that can be made // form pancake using n cuts static int findPieces( int n) { // Use the formula return (n * (n + 1 )) / 2 + 1 ; } // Driver program to test above function public static void main (String[] args) { System.out.println(findPieces( 1 )); System.out.println(findPieces( 2 )); System.out.println(findPieces( 3 )); System.out.println(findPieces( 50 )); } } // This code is contributed by Pramod Kumar |
Python3
# A Python 3 program to # find the solution to # The Lazy Caterer's Problem # This function receives an # integer n and returns the # maximum number of pieces # that can be made form # pancake using n cuts def findPieces( n ): # Use the formula return (n * ( n + 1 )) / / 2 + 1 # Driver Code print (findPieces( 1 )) print (findPieces( 2 )) print (findPieces( 3 )) print (findPieces( 50 )) # This code is contributed # by ihritik |
C#
// C# program to find the solution // to The Lazy Caterer's Problem using System; class GFG { // This function returns the maximum // number of pieces that can be made // form pancake using n cuts static int findPieces( int n) { // Use the formula return (n * (n + 1)) / 2 + 1; } // Driver code public static void Main () { Console.WriteLine(findPieces(1)); Console.WriteLine(findPieces(2)); Console.WriteLine(findPieces(3)); Console.Write(findPieces(50)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // A php program to find // the solution to The // Lazy Caterer's Problem // This function receives // an integer n and returns // the maximum number of // pieces that can be made // form pancake using n cuts function findPieces( $n ) { // Use the formula return ( $n * ( $n + 1)) / 2 + 1; } // Driver Code echo findPieces(1) , "" ; echo findPieces(2) , "" ; echo findPieces(3) , "" ; echo findPieces(50) , "" ; // This code is contributed // by nitin mittal. ?> |
Javascript
<script> // Javascript program to find the solution to // The Lazy Caterer's Problem // This function returns the maximum // number of pieces that can be made // form pancake using n cuts function findPieces(n) { // Use the formula return (n * (n + 1)) / 2 + 1; } // Driver Code document.write(findPieces(1) + "<br/>" ); document.write(findPieces(2) + "<br/>" ); document.write(findPieces(3) + "<br/>" ); document.write(findPieces(50)); </script> |
输出:
2471276
参考资料: oeis。组织 本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END