This is an interesting programming

problem know in the literature as Josephus problem. The problem is given as:

problem know in the literature as Josephus problem. The problem is given as:

1. Suppose there are n children standing

in a queue.

in a queue.

2. Students are numbered from 1 to n

in the clockwise direction.

in the clockwise direction.

3. Students choose a lucky number say

m.

m.

They start counting in clockwise

direction from the child designated as 1. The counting proceeds until the mth

child is identified. mth child is eliminated from the queue.

Counting for the next round begins from the child next to the eliminated one

and proceeds until the mth child is identified. This child is then

eliminated and the process continues. After few rounds of counting only one

child is left and this child is declared as winner.

direction from the child designated as 1. The counting proceeds until the mth

child is identified. mth child is eliminated from the queue.

Counting for the next round begins from the child next to the eliminated one

and proceeds until the mth child is identified. This child is then

eliminated and the process continues. After few rounds of counting only one

child is left and this child is declared as winner.

**Also Read: C/C++ TIC-TAC-TOE GAME**

**Also Read: C Program for Tower of Hanoi Problem**

Josephus Problem Animation |

### Implementation

It is required to write a program

to identify a winner of the game. Inputs to the function are two parameters.

to identify a winner of the game. Inputs to the function are two parameters.

n: number of children

m: lucky number

function returns an integer

identifying the winner

identifying the winner

*int winner (int m, int n)*

*{*

*queue*

q;

q;

*int*

i;

i;

*init*

(&q); //create a queue of

n integers, numbered from 1 to n. Number I stands for ith child

(&q); //create a queue of

n integers, numbered from 1 to n. Number I stands for ith child

*for*

(i=1; i<=n; i++)

(i=1; i<=n; i++)

*enqueue (&q, i);*

*for*

(j=1; j<=n; j++) //n-1 iterations

to eliminate n-1 children

(j=1; j<=n; j++) //n-1 iterations

to eliminate n-1 children

*{*

*for*

(i=1; 1<m; i++) //skip m-1

children

(i=1; 1<m; i++) //skip m-1

children

*{*

*x=dequeue*

(&q);

(&q);

*enqueue*

(&q, x);

(&q, x);

*}*

*x=dequeue*

(&q); //remove mth children

(&q); //remove mth children

*}*

*x=dequeue*

(&q); //last child winner

(&q); //last child winner

*return*

(x);

(x);

*}*

*Image Source:**http://img.thedailywtf.com/images/200907/Josephus.gif*

Rahul PathakGood one.. Thanks for sharing

LynnExrmlteey helpful article, please write more.