Home\ Tutorial \ Josephus Version 2.0
 JOSEPHUS

Background

Flavius Josephus was a famous historian of the first century. Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend stand in the vicious circle.

```

```

/*          josephus.cpp

Implementation of general josephus algorithm

Compiled : CYGNU & Microsoft Visual C++ 6.0

Permission is granted for use in non-commerical applications

provided this copyright notice remains intact and unchanged.

This program used a circular queue

*/

#include <stdio.h>

#define MAX 150

/** Implementatiom of circular queue  **/

int queue[MAX];

int e,f,r;

/** _f is front; _r is rear & _e is element number **/

/* ************************************************** */

/*   A general push algorithm act over queue    */

/* ************************************************** */

void push(int i)

{

r++;

e++;

if(r>=MAX)

r=1;

queue[r] = i;

}

/* ************************************************** */

/*   A general pop algorithm act over queue     */

/* ************************************************** */

int pop(void)

{

e--;

int i=queue[f];

f++;

if(f>=MAX)

f = 1;

return i;

}

/** End of circular queue **/

/* ***********************************    */

/* A general joshusf function.          */

/* This function start removing        */

/* element from first element          */

/* and return the sirviver                 */

/* ***********************************   */

int joshups(int n,int v)

{   register int i;

e=n;

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

queue[i] = i;

f = 1; // 0 for serviving first element.

r = n; // n+1 for serviving first element.

i = 0;

if(n > 1)

pop();

while(e!=1)

{

if(i!=v)

{

i++;

push(pop());

}

else

{

//         if((pop())==13) /** this if statement and its body (not the pop) is out ofgeneral code **/

//            return -1;

pop();

i = 0;

}

}

return queue[f];

}

/** end of jouishof functionb **/

/*sample main function*/

main(void)

{

int i,m;

scanf("%d",&i);

while(i)

{   m=1;

while((joshups(i,m++)) != 13 );

printf("%d",m);

putchar('\n');

scanf("%d",&i);

}

return 0;

}

Note: This program contain a sample bug. To use this

code you have to debug this.

 Related Problems 151 Power Crisis 440 Eeny Meeny Moo
 ProblemSet Tricks | Reference | Tutorial FAQ|Index|Info Credits|Guestbook|Update