Description

This is an old problem from ancient history, but many aspects of it are still unsolved. There are n numbers 1,2,…,n arranged in a circle in clockwise order. Given a number k ≥ 2, the following step is executed repeatedly, until only one number is left. Move in clockwise direction, jumping over k − 1 remaining numbers, and eliminate the kth remaining number encountered. Initially start with number 1, so that if n ≥ k, the first number eliminated is k. The last number that remains is denoted J(n,k) and is called the Josephus number. For example, J(5,3) = 4 as the numbers are eliminated in the order 3,1,5,2. A program is to be written to compute J(n,k) for given values of n and k.
An easy way of doing this is to just follow the procedure that defines the function. Define a data type called circular list whose value is a circular list of numbers, with a pointer to a position in the list. An operation ++ is defined to move the pointer one place in the list in clockwise order. You also have an operation that gives the size of the list and an operation to initialize the list with numbers 1 to n. Finally, there is an operation to remove the number that the pointer is pointing to, and a method to return the value. Then the program for this can be written as
int J(int n, int k) {
circular_list C; C.initialize(n); while (C.size() > 1) { for (int i = 1; i < k; i++) C++;
C.remove();
} return C.value();
}
If you are unable to do this, you can implement the simple method, which should work correctly for small values of n and k, but you will get only half credit for it. The recursive program is actually much simpler and can be written in 10 lines, if done carefully.
1
Input-Output
Submission
Name your file as RollNo 1.cpp and upload it on moodle. Only the source file should be submitted.
Homework
This method also gives a ‘closed form’ solution for J(n,2). For example, J(2n,2) = 1 and J(2n− 1,2) = 2n− 1 for all n ≥ 1. Can you find a simple way of computing J(n,2) without using recursion?
To know more about this, and thousands of other such problems, read the book Concrete Mathematics: A Foundation for Computer Science, by Graham, Knuth, Patashnik.
2