约瑟夫问题

July 8th, 2014

linked list

C

struct node {
  item item;
  struct node* next;
}

struct node* head = malloc(sizeof(*head));
head->item = 1;
head->next = head;

C full-edition

// josephus_problem.c
#include <stdio.h>
#include <stdlib.h>

typedef struct node* link;
struct node {
  int item;
  link  next;
};

int main(int argc, char *argv[]) {
  int i, N = atoi(argv[1]), M = atoi(argv[2]);
  link head = malloc(sizeof(struct node)), x;
  head->item = 1;
  head->next = head;

  for (i = 2, x = head; i <= N; i++) {
    x = (x->next = malloc(sizeof *x));
    x->item = i;
  }
  x->next = head;

  while(x != x->next) {
    for (i = 1; i < M; i++) x = x->next;
    printf("%d ", x->next->item);
    x->next = x->next->next;
  }

  printf("\nLeft: %d\n", x->item);
}

Javascript

construct function

function Node(item, next) {
  this.item = item;
  this.next = next;
}

var head = new Node(1);
head.next = head;

Python

class Node():
  def __init__(self, item, next):
    self.item = item
    self.next = mext
  }

head = Node(1)
head.next = head

Java

class Node {
  int item;
  Node next;
}

Node head = new Node();
head.item = 1;
head.next = head;