I understand if you keep flipping the largest pancake, you will eventually put it in order assuming there are only five pancakes.
But when they say this, I get lost and kinda scared.
How is 2(n-2)+1 = 2n-3
Pn <= 2n-3
New to programming, and trying to understand what these numbers mean.
In: 2
>How is 2(n-2)+1 = 2n-3
Pn <= 2n-3
New to programming, and trying to understand what these numbers mean.
Those don’t have anything specifically to do with programming, they’re just mathematical statements about the pancake algorithm.
>2(n-2)+1 = 2n-3
That’s just a mathematical equation.
2(n-2)+1
2n – 4 + 1
2n – 3
>Pn <= 2n-3
This is just a statement that says the pancake number (Pn) for any given number of pancakes (n) will always be less than or equal to 2n-3.
So if you have 7 pancakes, the pancake number will be less than or equal to 2*7-3 = 14-3 = 11.
As far as *why* – let’s go from the very start. A 2-pancake stack.
Obviously, this is simple. Either it’s already sorted, or it’s not. It always takes a maximum of one flip to sort a 2-pancake stack.
Let’s add another pancake then. Now, the biggest pancake is either in the right spot or it’s not. If it *isn’t*, we need to do 2 flips to move it – first we flip it and everything above it so it’s on the top, then we flip the whole stack so it’s on the bottom. Once that pancake is in place, the other two pancakes form a stack of two pancakes – and it’s just like before.
Let’s add another one! Again, the biggest pancake is either in the right spot or it’s not – and if it’s not, it takes two flips to get it to the right spot. Then, the three remaining pancakes form a stack of three… You see the pattern.
____
In the worst case, it takes 2 flips for every pancake past the second, plus an extra flip – so you get your first 2 representing those 2 flips, your (n-2) for “how many pancakes past the second” and your +1 on the end. However, we can expand this out by algebra – when we have multiplication followed by a bracket, we can separate out the bracket and multiply each element that’s been added or subtracted inside. 2(n-2)+1 becomes 2n-2*2+1 which becomes 2n-4+1 which becomes 2n-3 – much easier to look at and calculate.
____
Pn just stands for “how many flips does it take to sort a stack with n pancakes”. You’ll note, however, that we used the worst case scenario before. It’s entirely possible that it could take fewer flips depending on the order of the stack. Hence we say that Pn is less than or equal to 2n-3 – in other words, 2n-3 is the absolute maximum number of flips needed to sort a stack of n pancakes.
Latest Answers