LaFore sees counting off to be stepping over. I.e., starting at 1, counting by two will kill person 4 first. The text does have one example buried in it. This is not intuitive and LaFore seems to be the only author counting this way.
Instructor's output for Josephus permutation cannot be reproduced
-
10-03-2022 - |
Question
I'm in a data structures class and am unable to reproduce the example data given by an instructor. The problem is the classic Josephus problem with a user supplied number of members, step interval, and starting position.
Specifically, I'm told that 99 people, starting on 23, counting off by 5 should leave 84 as the last man standing.
I come up with: 65. I ran again thinking the input may have been 99 people, starting at 5 with an interval of 23. This produced: 42.
My assignment solution involves a circular linked list, however this c code produces the same output in all cases:
#include <stdio.h>
int josephus(int n, long k)
{
if (n == 1)
return 1;
else
/* The position returned by josephus(n - 1, k) is adjusted because the
* recursive call josephus(n - 1, k) considers the original position
* k%n + 1 as position 1 */
return (josephus(n - 1, k) + k-1) % n + 1;
}
int main()
{
int n = 99;
int k = 23;
printf("The chosen place is %d\n", josephus(n, k) + 5);
return 0;
}
Thanks again.
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow