Josephus problem: Difference between revisions
Content added Content deleted
(Updated to work with Nim 1.4: added missing parameter type and replaced ".. <" by "..<".) |
|||
Line 2,627: | Line 2,627: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
===Simulating=== |
|||
{{trans|Python}} |
{{trans|Python}} |
||
Line 2,654: | Line 2,656: | ||
Survivor: 2 |
Survivor: 2 |
||
Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15, 30. |
Prisoner killing order: 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 0, 4, 9, 13, 18, 22, 27, 31, 36, 40, 6, 12, 19, 25, 33, 39, 7, 16, 28, 37, 10, 24, 1, 21, 3, 34, 15, 30. |
||
Survivor: 30</pre> |
|||
===Processing backwards=== |
|||
Another more efficient way but without the killing order: |
|||
<lang Nim>func prisonerPos(n, k: Positive): int = |
|||
## The result is computed backwards. We start from the winner at |
|||
## position 0 on last round and compute its position on previous rounds. |
|||
var pos = 0 |
|||
for i in 2..n: |
|||
pos = (pos + k) mod i |
|||
result = pos |
|||
echo "Survivor: ", prisonerPos(5, 2) |
|||
echo "Survivor: ", prisonerPos(41, 3)</lang> |
|||
{{out}} |
|||
<pre>Survivor: 2 |
|||
Survivor: 30</pre> |
Survivor: 30</pre> |
||