게으른 요리사의 문제

팬케이크에 할 수 있는 절단 횟수를 나타내는 정수 n이 주어지면 n회 절단으로 만들 수 있는 조각의 최대 수를 구하십시오.
예:

Input : n = 1 Output : 2 With 1 cut we can divide the pancake in 2 pieces Input : 2 Output : 4 With 2 cuts we can divide the pancake in 4 pieces Input : 3 Output : 7 We can divide the pancake in 7 parts with 3 cuts Input : 50 Output : 1276

권장 실습 게으른 요리사의 문제 시도해 보세요!

문자열을 int로 캐스팅

Let f(n) denote the maximum number of pieces that can be obtained by making n cuts. Trivially f(0) = 1 As there'd be only 1 piece without any cut. Similarly f(1) = 2 Proceeding 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    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# 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

 // 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)  'n' ; echo findPieces(2)  'n' ; echo findPieces(3)  'n' ; echo findPieces(50) 'n'; // 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) + '  
');  document.write(findPieces(2) + '  
');  document.write(findPieces(3) + '  
');  document.write(findPieces(50));   </script>

출력 :

int를 문자열로 변환하는 방법

2 4 7 1276

참고자료 : oeis.org