http://www.geeksforgeeks.org/the-lazy-caterers-problem/
http://www.geeksforgeeks.org/pizza-cut-problem-circle-division-lines/
Given an integer n, denoting the number of cuts that can be made on a pancake, find the maximum number of pieces that can be formed by making n cuts.
https://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence
The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a disk (a pancakeor pizza is usually used to describe the situation) that can be made with a given number of straight cuts. For example, three cuts across a pancake will produce six pieces if the cuts all meet at a common point inside the circle, but up to seven if they do not. This problem can be formalized mathematically as one of counting the cells in an arrangement of lines; for generalizations to higher dimensions, see arrangement of hyperplanes.
http://www.geeksforgeeks.org/pizza-cut-problem-circle-division-lines/
Given an integer n, denoting the number of cuts that can be made on a pancake, find the maximum number of pieces that can be formed by making n cuts.
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 can optimize above formula.
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
int
findPieces(
int
n)
{
// Use the formula
return
(n*(n+1))/2 + 1;
}
The lazy caterer's sequence, more formally known as the central polygonal numbers, describes the maximum number of pieces of a disk (a pancakeor pizza is usually used to describe the situation) that can be made with a given number of straight cuts. For example, three cuts across a pancake will produce six pieces if the cuts all meet at a common point inside the circle, but up to seven if they do not. This problem can be formalized mathematically as one of counting the cells in an arrangement of lines; for generalizations to higher dimensions, see arrangement of hyperplanes.
When a circle is cut n times to produce the maximum number of pieces, represented as p = ƒ(n), the nth cut must be considered; the number of pieces before the last cut is ƒ(n − 1), while the number of pieces added by the last cut is n.
To obtain the maximum number of pieces, the nth cut line should cross all the other previous cut lines inside the circle, but not cross any intersection of previous cut lines. Thus, the nth line itself is cut in n − 1 places, and into n line segments. Each segment divides one piece of the (n − 1)-cut pancake into 2 parts, adding exactly n to the number of pieces. The new line can't have any more segments since it can only cross each previous line once. A cut line can always cross over all previous cut lines, as rotating the knife at a small angle around a point that is not an existing intersection will, if the angle is small enough, intersect all the previous lines including the last one added.
Thus, the total number of pieces after n cuts is