Chittagong University of Enginnering and Technology, Bangladesh

ACMBEGINNER

 

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

 

            Copyright 2003 M H Rasel and CUET Old Sailor; all rights reserved.

 

            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.

 

Copyright 2003 M H Rasel
[
Webmaster]
Last modified

1