Simulation of Josephus Problem using Circular lists

Josephus Problem

Josephus problem is that some soldiers are being surrounded by their enemies and there is only one horse to escape i.e. only one soldier could escape and summon help. The remedy is to arrange soldiers’ names as a circular list. Now, any number say ‘n’ is inputed (selected) where n < number of soldiers. Now count the names in the list clockwise starting from the first name upto n names and delete the nth name. Now, start counting upto n from the person preceding¬† the person deleted and repeat the process till one soldier name remains and that soldier escapes.

Such a problem could be well simulated using a Circular list using the insert() and delafter() functions. The program must accept the number n and a set of names which are inserted in to the circular list. Now, processing is done as described above.

/*Program for JOSEPHUS PROBLEM Simulation*/

#include
#include 

main(){
   void josephus(void);

   /*calls josephus*/
   josephus();
}

void josephus(void){
    struct node{
          char * info
          struct node * next;
    };

    type def struct node * NODEPTR;

    void insert(NODEPTR *p, char * name);
    void delafter(NODEPTR *p, char * name);
    char nam[30]; NODEPTR list = NULL;
    int i,n;
    printf("\nEnter the number n >");
    scanf("%d",&n);
    printf("\nEnter names of soldiers End with 'end'");
    scanf("%s",&nam);

    while(strcmp(nam,"end")){
          insert(&list,nam);
          scanf("%s",&nam);
    }

    printf("\nThe soldiers eliminated from the list are >");
    while(list != list->next){/*repeat until one name is in the list*/
        for(i = 1; i < n; i++){ list = list->next;
        }
        /*for loop only upto < n so list->next points to nth node and delafter(list,nam) 
             deletes the list-next i.e. nth node*/
        printf("\n%s",delafter(list,nam));
    }

    /*Counting and deletion is complete now. Now print the soldiers who escapes*/
   
    printf("\nThe soldier who escapes is %s", list->info);
    freenode(list);
}

void insert (NODEPTR *p, char * name){
     NODEPTR q;
     q = getnode();
     q->info = *name;
     if(*p == NULL){
         *p = q;
     }
     else{
         q->next = (*p)->next;
     }
     (*p)->next = q;
     *p = q; /*implements circular pointer operation*/
      return;     
}

void delafter(NODEPTR *p, char * name){
      NODEPTR q;
      /*if list is NULL or has any item*/
      if((p == NULL) || (p == p->next)){
         printf("\n Void Deletion");
         exit(1);
      }
      q = (*p)->next;
      *name = p->info;
      (*p)->next = q->next;
      freenode(q);
      return(name);
}

NODEPTR getnode(void){
     return ((NODEPTR) malloc(sizeof struct node));
}

void freenode(NODEPTR * p){
   free(p);
}

 

Add a Comment

Your email address will not be published. Required fields are marked *