Home > Articles, Data Structures & Algorithms > Implementation of a circular list for solving the problem of Josephus.

Implementation of a circular list for solving the problem of Josephus.

For the representation of individuals arranged in a circle, we create a circular linked list with a combination of each person to the person on his left in the circle. The integer i represents the i-th person in the circle. After you create a circular list of one node for 1, we insert its unique node to nodes 2 to N. We end up with a cycle from 1 to N, with x indicating the node N. Then, starting from 1 we omit M-1 nodes, we define the pointer of the (M-1)-th node to omit the M-th, and continue that way until only one node remains in the list.

You should know that the implementation of the algorithm does not take into account issues of data input validation or proper management of dynamic memory (e.g. avoiding memory leaks) because it is only necessary to highlight the logic of the algorithm.

#include <iostream>
#include <cstdlib>
using namespace std;

struct node {
  int item; node * next;

  node (int x, node * t) {
    item = x; next = t;
  }
};

typedef node * plink;

int
main (int argc, char *argv[]) {
  int i, N, M;

  if (!argv[1] || !argv[2])
    return EXIT_FAILURE;

  N = atoi (argv[1]);
  M = atoi (argv[2]);

  plink t = new node (1, 0);
  t->next = t;
  plink x = t;

  for (i = 2; i <= N; i++)
    x = (x->next = new node (i, t));

  while (x != x->next) {
    for (i = 1; i < M; i++)
      x = x->next;

    x->next = x->next->next;
  }

  cout << x->item << endl;

  return EXIT_SUCCESS;
}
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: