懒惰的餐饮服务商的问题

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


输出:

2471276

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

© 版权声明
THE END
喜欢就支持一下吧
点赞12 分享