Hoe los je het pannenkoekenprobleem op?

Thibault, 18 jaar
3 juni 2015

Ik las over het pannenkoekenprobleem (pancake sorting). Ik snap de probleemstelling wel maar hoe komt men tot de oplossing? De naam van dit probleem spreekt me aan, maar ik ben benieuwd naar de 'oplossing', die ik nergens verstaanbaar vind.
Alvast bedankt!

Antwoord

Er staat nochtans een oplossingsmethode beschreven in de Nederlandse Wikipedia over Pancake sort (onder de hoofding Algoritme). Het idee is om telkens de grootste achteraan te krijgen. Dit kan je doen door vlak na hem te flippen, zodat hij vooraan komt te liggen, en dan het geheel te flippen, zodat hij achteraan komt te liggen. Vanaf dan laat je de grootste gewoon achteraan liggen en je herhaalt het algoritme op de resterende getallen. Een voorbeeldje:

Gegeven de rij (3,2,4,5,1).

1.a. Flip na de grootste: (5,4,2,3,1)

1.b. Flip het geheel: (1,3,2,4,5)

2. De grootste staat nu al achteraan. We laten die voortaan liggen en herhalen het algoritme met de resterende getallen. Nu in dit voorbeeldje staat de tweedegrootste ook al achteraan, dus daar hoeven we niets meer voor te doen. Er blijven nu nog drie getallen over.

3.a. Flip na de derdegrootste: (3,1,2,4,5)

3.b. Flip het geheel (maar 3 getallen): (2,1,3,4,5)

4. De vierdegrootste staat reeds vooraan, dus we moeten enkel de resterende 2 getallen flippen: (1,2,3,4,5)

Klaar.

Nog een voorbeeldje op de rij (4,8,2,3,7,6,1,5):

- (8,4,2,3,7,6,1,5)

- (5,1,6,7,3,2,4,8)

- (7,6,1,5,3,2,4,8)

- (4,2,3,5,1,6,7,8)

- (5,3,2,4,1,6,7,8)

- (1,4,2,3,5,6,7,8)

- (4,1,2,3,5,6,7,8)

- (3,2,1,4,5,6,7,8)

- (1,2,3,4,5,6,7,8)

Deze methode is de eenvoudigste en er bestaan slimmere methodes die minder stappen vergen.

Reacties op dit antwoord

  • 16/06/2015 - Thibault (vraagsteller)

    Dankuwel! Ik vond nog op http://wiskunde.plantyn.com/: 'Het antwoord voor kleine n is gekend, maar voor grote n nog steeds niet.' Over welke kleine en grote n gaat dit? Wat houdt dit juist in?

  • 17/06/2015 - Jan (wetenschapper)

    Voor een gegeven getal n bestaan er n! (n faculteit) verschillende ordeningen van de getallen 1 tot en met n. Deze ordeningen worden ook wel permutaties genoemd. Bij pancake sorting krijg je zulk een permutatie en je moet ze met flips herleiden tot de standaard ordening die de getallen gewoon in hun natuurlijke volgorde ordent. Nu voor elke permutatie van 1,...,n is er een minimaal aantal flips dat je daarvoor nodig hebt. De vraag is nu wat de "moeilijkste" permutatie is van 1,...,n voor pancake sorting, dus die permutatie waarvoor het benodigde aantal flips het grootst is. Het aantal flips dat nodig is om die moeilijkste permutatie te sorteren duiden we aan met f(n). Het is een open probleem om een efficiƫnt uit te rekenen uitdrukking te geven voor die functie f(n). Als je heel veel tijd hebt, of een snelle computer, kan je f(n) berekenen door alle permutaties af te lopen en voor elke permutatie alle mogelijke reeksen van flips uit te proberen. Maar als n groot is zijn er veel te veel mogelijkheden om te onderzoeken en zelfs de snelste supercomputers zullen daar nooit tijd genoeg voor vinden. Daarom dus de vraag of we geen elegante wiskundige uitdrukking voor f(n) kunnen vinden, of toch tenminste een efficiente berekeningsmethode. Dit is echter dus nog onbekend. (En misschien bestaat het helemaal niet.) Het beste wat men voorlopig weet is dat er een vast getal C bestaat zodat f(n) altijd hoogstens C kleiner is dan 18/11 maal n.

Enkel de vraagsteller en de wetenschapper kunnen reageren op een antwoord.

Beantwoord door

 Jan Van den Bussche

informatica bio-informatica ecologie

Universiteit Hasselt
Agoralaan Universitaire Campus-gebouw D BE-3590 Diepenbeek
http://www.uhasselt.be/

Zoek andere vragen

© 2008-2022
Ik heb een vraag wordt gecoördineerd door het
Koninklijk Belgisch Instituut voor Natuurwetenschappen