PROG0456 - Heir
A long time ago there lived a rich farmer who had sixteen children, eight by his first wife who was deceased and eight by his second wife. His second wife, however, wanted to ensure that her eldest son would inherit the property of the farmer. That's why one day she made him the following proposal:
Dearest husband, you're getting older. We urgently need to determine who will be your heir. Let us line up the sixteen children in a circle. Starting with one of the children, we can then clockwise remove every tenth child out of the circle until only one child remains to whom you'll leave your property.
The farmer accepted the proposal. However, after the seventh child was removed from the circle the farmer noticed that all children who had previously been removed from the circle were children of his first wife. The farmer stopped the selection, because he could see that the last child he had with his first wife was next in line to be removed from the circle.
The farmer suggested to resume where they had come after the seventh child was removed from the circle, but to begin counting counterclockwise from that point. The woman — forced to decide quickly — agreed because she believed the odds were in her favour. Who eventually became the heir to the farmer?
Assignment
A farmer has $k$ children with each of his
two wives. All the children are placed in a circle, and numbered clockwise
from 1 to $2k$. We start counting clockwise from child number 1, where
each $n$-th child is removed from circle. After $k - 1$ children were
removed from the circle, the continues counterclockwise. The circle gets
smaller and smaller, and the last child that remains is the heir to the
farmer.
Write a function heir to
which the values $k$ and $n$ must be passed, in which you may assume
that $k \geq 2$. The function should return a list indicating the order in
which the children were removed from the circle. The first child removed
is thus first in the list, and the eventual heir last in the list. Use the
serial numbers of the children
as elements in the list.
Example
>>> heir(8, 10) [10, 4, 15, 11, 7, 5, 3, 2, 16, 12, 1, 6, 13, 9, 14, 8] >>> heir(8, 3) [3, 6, 9, 12, 15, 2, 7, 1, 13, 8, 16, 10, 14, 4, 11, 5] >>> heir(10, 5) [5, 10, 15, 20, 6, 12, 18, 4, 13, 3, 16, 7, 14, 1, 8, 9, 2, 17, 11, 19]
Heel lang geleden leefde er eens een rijke boer die zestien kinderen had, acht bij zijn eerste vrouw die overleden was en acht bij zijn tweede vrouw. Zijn tweede vrouw wilde echter alles in het werk stellen opdat haar oudste zoon de eigendommen van de boer zou erven. Daarom deed ze op een dag het volgende voorstel:
Liefste echtgenoot, je wordt al een dagje ouder. We moeten dringend regelen wie je erfgenaam zal worden. Laat ons de zestien kinderen in een cirkel opstellen. Te beginnen bij één van de kinderen kunnen we dan in wijzerzin elk tiende kind uit de cirkel verwijderen, totdat er slechts één kind overblijft aan wie je je eigendommen zult nalaten.
De boer aanvaarde het voorstel, en zo gezegd, zo gedaan. Nadat het zevende kind uit de cirkel was verwijderd, stelde de boer echter met verbazing vast dat alle kinderen die tot dan toe uit de cirkel waren verwijderd, kinderen waren die hij met zijn eerste vrouw had gekregen. De boer legde daarop prompt de selectieprocedure stil, omdat hij ook al in de gaten had gekregen dat het laatste kind dat hij met zijn eerste vrouw had als volgende aan de beurt was om uit de cirkel verwijderd te worden.
De boer stelde voor om de selectieprocedure te hervatten waar ze gekomen waren nadat het zevende kind uit de cirkel was verwijderd, maar om vanaf dat punt in tegenwijzerzin te beginnen tellen. De vrouw — gedwongen om snel te beslissen — ging direct akkoord omdat de kansen 8 tegen 1 waren in het voordeel van haar kant van de familie. Wie werd uiteindelijk de erfgenaam van de boer?
Opgave
Een boer heeft $k$ kinderen bij elk van zijn twee vrouwen. Alle kinderen worden in een cirkel geplaatst, en in wijzerzin genummerd van 1 tot en met $2k$. We beginnen in wijzerzin af te tellen vanaf kind nummer 1, waarbij elk $n$-de kind uit de cirkel wordt verwijderd. Nadat $k - 1$ kinderen uit de cirkel verwijderd werden, wordt verder geteld in tegenwijzerzin. De cirkel wordt steeds kleiner en kleiner, en het laatste kind dat overblijft wordt de erfgenaam van de boer.
Schrijf een functie erfgenaam waaraan de waarden $k$ en $n$ moeten doorgegeven worden, waarbij je er mag van uitgaan dat $k \geq 2$. De functie moet een lijst teruggeven die de volgorde aangeeft waarin de kinderen uit de cirkel verwijderd werden. Het eerst verwijderde kind staat daarbij als eerste in de lijst, en de uiteindelijke erfgenaam als laatste in de lijst. Gebruik de volgnummers waarmee de kinderen in de lijst genummerd werden als elementen in de lijst.
Voorbeeld
>>> erfgenaam(8, 10) [10, 4, 15, 11, 7, 5, 3, 2, 16, 12, 1, 6, 13, 9, 14, 8] >>> erfgenaam(8, 3) [3, 6, 9, 12, 15, 2, 7, 1, 13, 8, 16, 10, 14, 4, 11, 5] >>> erfgenaam(10, 5) [5, 10, 15, 20, 6, 12, 18, 4, 13, 3, 16, 7, 14, 1, 8, 9, 2, 17, 11, 19]
Added by: | Peter Dawyndt |
Date: | 2014-03-21 |
Time limit: | 10s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | PY_NBC |
Resource: | None |