Josephus problem: Difference between revisions
→{{header|Fōrmulæ}}
Line 2,223:
{{FormulaeEntry|page=https://formulae.org/?script=examples/Josephus_problem}}
'''Solution:'''
We start with two lists. The first one contains initially the prisoners (their number), and the second one contains the kills, and it is initially empty.
On every kill, the number of the killed prisoner is deleted from the first list, and it is (striked out) appended to the second one, in order to show the order of kills.
In order to leave more than one survivor, the cycle is repeated n-s times, where n is the number of prisoners and s is the number of survivors.
At the end, the two lists are retrieved.
Even when Fōrmulæ is 1-based, the list is filled starting with the 0 prisoner, in order to the results can be compared with other languages (mostly 0-based).
[[File:Fōrmulæ - Josephus problem 01.png]]
'''Case 1.''' 5 prisoners, killing every 2:
[[File:Fōrmulæ - Josephus problem 02.png]]
[[File:Fōrmulæ - Josephus problem 03.png]]
'''Case 2.''' 41 prisoners, killing every 3:
[[File:Fōrmulæ - Josephus problem 04.png]]
[[File:Fōrmulæ - Josephus problem 05.png]]
'''Case 3.''' The captors may be especially kind and let m survivors free, and Josephus might just have m - 1 friends to save.:
[[File:Fōrmulæ - Josephus problem 06.png]]
[[File:Fōrmulæ - Josephus problem 07.png]]
'''Case 4. Larger example.''' 23,482 prisoners, killing every 3,343, leaving 3 survivors. Only the survivors are shown (the first element of the resulting list is extracted):
[[File:Fōrmulæ - Josephus problem 08.png]]
[[File:Fōrmulæ - Josephus problem 09.png]]
'''Drawing history'''
The following function creates a raster graphics of size n squares width, and n + 1 squares height, where n is the number of prisoners. The size of the square is defines as pixels.
The horizontal axis (right to left) is the number of the prisoner. The vertical axis (top to bottom) is the number of cycle.
An alive prisoner is drawn as green, a dead one is drawn as black.
[[File:Fōrmulæ - Josephus problem 10.png]]
'''Example 1.''' Drawing for the case 5 prisoners, killing every 2 (cell size is 20x20 pixels):
[[File:Fōrmulæ - Josephus problem 11.png]]
[[File:Fōrmulæ - Josephus problem 12.png]]
'''Example 2.''' Drawing for the case 41 prisoners, killing every 3 (cell size is 5x5 pixels):
[[File:Fōrmulæ - Josephus problem 13.png]]
[[File:Fōrmulæ - Josephus problem 14.png]]
=={{header|Go}}==
| |||