Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- /*
- There are n people standing in a circle waiting to be executed.
- The counting out begins at some pouint in the circle and proceeds around the circle in a fixed direction.
- In each step, a certain number of people are skipped and the next person is executed.
- The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed),
- until only the last person remains, who is given freedom.
- Given the total number of persons n and a number k which indicates that k-1 persons are skipped and
- kth person is killed in circle.
- The task is to choose the place in the initial circle so that you are the last one remaining and so survive.
- n = 5, k = 2
- 1| 2 3 4 5 ->
- 1 * 3| 4 5 ->
- 1 * 3 * 5| ->
- * * 3| * 5 ->
- * * 3 * *
- */
- int josephus(int n, int 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;
- }
- // Driver Program to test above function
- int main()
- {
- int k = 2;
- int c = 0;
- for (int i = 2; i < 4294967295 ; i+=2){ //2^32 - 1
- int temp = josephus(i, k);
- if( temp == i>>1 ){
- printf("Number of people %d, chosen place is %d\n", i, temp);
- c++;
- }
- if (c==10)
- break;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment