The Short Circuit

Mike Morgan's technical journal

Just some hack code I threw together for evalating the Josephus Problem.

The Josephus problem described in Concrete Mathematics can be stated in an equivalent yet family friendly form as follows: n players stand in a circle to play a game of “Josephus tag”. When the game starts, the first player tags the second player, and then the third person tags the fourth, and so on and so forth. When a player is tagged, he is out. After the first round, subsequent rounds ensue until the last survivor, who declares herself the winner.

For a game with n players, which position should one select to ensure survival and hence victory?

This program will spew the order of the players who are out in reverse order, allowing you to analyze the results in an effort to find patterns for the last survivor, the second to the last survivor, and so on. For exmaple, here are the rusults for the Josephus problem with 2 through 9 players. Looking at the n=9 case, player 3 is the winner, while player 7 was the last to be tagged.

Reverse Order Out    2:     1    2
Reverse Order Out    3:     3    1    2
Reverse Order Out    4:     1    3    4    2
Reverse Order Out    5:     3    5    1    4    2
Reverse Order Out    6:     5    1    3    6    4    2
Reverse Order Out    7:     7    3    5    1    6    4    2
Reverse Order Out    8:     1    5    7    3    8    6    4    2
Reverse Order Out    9:     3    7    9    5    1    8    6    4    2

Source code is below the fold. As always, for legal reasons, it is provided as is.

/* Josephus.cpp : Defines the entry point for the console application. */
/* Released to the public domain at:  http://sc.morganisms.net/?p=541 */

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 40
int _tmain(int argc, _TCHAR* argv[])
{
  bool      *still_in = NULL;
  unsigned  *order_out= NULL;
  int       n;
  int       i;
  int       j;
  unsigned  oo_cnt;
  bool      change_made;

  for(n=2;n<=MAX_N;n++){
    /* get memory for in/out and order out arrays */
    still_in  = (bool *)malloc(n * sizeof(bool));
    order_out = (unsigned *)malloc(n * sizeof(unsigned));
    if(still_in ==NULL || order_out==NULL){
      printf("Error:  Could not allocate memory.\n");
      /* free memory */
      if(still_in != NULL)
        free(still_in);
      if(order_out != NULL)
         free(order_out);
    }
    else{
      /* Initialize the memory */
      for(i=0;i<n;i++){
        still_in[i]  = true;
        order_out[i] = 0;
      }
      oo_cnt = 0; /* reset the order out counter */
      /* Play Josephus tag */
      do{
        /* change_made = false; */
        for(i=0;i<n;i++){
          if(still_in[i]){
            /*  this place can tag next guy, we need to find next guy */
            change_made = false;
            for(j=1;j<n && !change_made;j++){
              if(still_in[(i+j)%n]){
                /* we found the next guy, tag him and set his flag to false */
                still_in[(i+j)%n]=false;
                order_out[oo_cnt++]=((i+j)%n)+1;
                change_made = true;
              }
            }
          }
        }
      }while(change_made);
      /* find survivor */
      for(i=0;i<n;i++){
        if(still_in[i]){
          order_out[oo_cnt++]=i+1;
        }
      }
      printf("Reverse Order Out %4d:  ",n);
      for(i=n-1;i>=0;i--){
        printf("%4d ",order_out[i]);
      }
      printf("\n");
    }
    /* free memory */
    if(still_in != NULL)
      free(still_in);
    if(order_out != NULL)
      free(order_out);
  }
  return 0;
}

References

No Comments »

No comments yet.

RSS feed for comments on this post. TrackBack URL

Leave a comment



© 2017 The Short Circuit | Entries (RSS) and Comments (RSS) |