懒惰的餐饮服务商的问题-yiteyi-C++库

给定一个整数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

图片[1]-懒惰的餐饮服务商的问题-yiteyi-C++库

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

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>                       

输出：

参考资料： oeis。组织本文由 阿什图什·库马尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章