While recursion is one way of solving the Josephus puzzle – arrays, or rather circular arrays, are another way. The program below, in C, uses arrays to solve the Josephus puzzle, visually depicting what happens.
Here is the first part of the program. The function objects_left()
determines how people people are left in the circle. The procedure print_circle()
, prints out the circle in linear form.
#include <stdio.h>
#define MAXPEOPLE 80
int objects_left(int j[], int m){
int i,sum=0;
for (i=0; i<m; i=i+1)
if (j[i] == 1)
sum = sum + 1;
return sum;
}
void print_circle(int j[], int m){
int i;
for (i=0; i<m; i=i+1)
printf("%d", j[i]);
printf("\n");
}
The next part of the program does the actually processing, using the number of people, and step count provided by the user.
int main (void){
int i,j,pos,MAXP,M;
int josephus[MAXPEOPLE];
printf("Number of people: ");
scanf("%d", &MAXP);
printf("Step count: ");
scanf("%d", &M);
for (i=0; i<MAXP; i=i+1)
josephus[i] = 1;
j = 0;
while (objects_left(josephus,MAXP) > 1) {
pos = 0;
while (pos < M){
if (j >= MAXP)
j = 0;
if (josephus[j] == 1)
pos = pos + 1;
j = j + 1;
}
josephus[j-1] = 0;
printf("Deleting : %d\n",j);
print_circle(josephus,MAXP);
}
for (i=0; i<MAXP; i=i+1)
if (josephus[i] == 1)
printf("The last object = %d\n", i+1);
return 0;
}
Here is what happens:
- Lines 8-9: Set all objects that exist in the array to 1. So for example if the number of people is 12, then the array would look like: 111111111111
- Lines 12-24 (loop): Circle thru the array until the number of objects that remain = 1.
pos
represents the elimination position. The loop uses the functionobjects_left()
as the loop condition. - Line 13: Set the step counter to 0.
- Lines 15-16: Reset
j
if it’s value exceeds the number of people. - Lines 17-18: If the object (i.e. person) exists, increment the object counter.
- Line 19: Increment position counter.
- Line 21: Eliminate the object.
- Lines 25-27: identify the last object.
Here is what the output looks like (the 0’s represent the deleted objects).
Number of people: 41
Step count: 3
Deleting : 3
11011111111111111111111111111111111111111
Deleting : 6
11011011111111111111111111111111111111111
Deleting : 9
11011011011111111111111111111111111111111
Deleting : 12
11011011011011111111111111111111111111111
Deleting : 15
11011011011011011111111111111111111111111
Deleting : 18
11011011011011011011111111111111111111111
Deleting : 21
11011011011011011011011111111111111111111
Deleting : 24
11011011011011011011011011111111111111111
Deleting : 27
11011011011011011011011011011111111111111
Deleting : 30
11011011011011011011011011011011111111111
Deleting : 33
11011011011011011011011011011011011111111
Deleting : 36
11011011011011011011011011011011011011111
Deleting : 39
11011011011011011011011011011011011011011
Deleting : 1
01011011011011011011011011011011011011011
Deleting : 5
01010011011011011011011011011011011011011
Deleting : 10
01010011001011011011011011011011011011011
Deleting : 14
01010011001010011011011011011011011011011
Deleting : 19
01010011001010011001011011011011011011011
Deleting : 23
01010011001010011001010011011011011011011
Deleting : 28
01010011001010011001010011001011011011011
Deleting : 32
01010011001010011001010011001010011011011
Deleting : 37
01010011001010011001010011001010011001011
Deleting : 41
01010011001010011001010011001010011001010
Deleting : 7
01010001001010011001010011001010011001010
Deleting : 13
01010001001000011001010011001010011001010
Deleting : 20
01010001001000011000010011001010011001010
Deleting : 26
01010001001000011000010010001010011001010
Deleting : 34
01010001001000011000010010001010001001010
Deleting : 40
01010001001000011000010010001010001001000
Deleting : 8
01010000001000011000010010001010001001000
Deleting : 17
01010000001000010000010010001010001001000
Deleting : 29
01010000001000010000010010000010001001000
Deleting : 38
01010000001000010000010010000010001000000
Deleting : 11
01010000000000010000010010000010001000000
Deleting : 25
01010000000000010000010000000010001000000
Deleting : 2
00010000000000010000010000000010001000000
Deleting : 22
00010000000000010000000000000010001000000
Deleting : 4
00000000000000010000000000000010001000000
Deleting : 35
00000000000000010000000000000010000000000
Deleting : 16
00000000000000000000000000000010000000000
The last object = 31