Making The Road Wiki

#include <iostream>
#include "Node.h"
using namespace std;
using namespace algo; 
/**
 * ジョセファスの問題
 * P.24
 */
void josephus_problem() {
  int N, M;
  Node<int> *t, *x;
  cout << "Enter the total number of people(N) : ";
  cin >> N;
  cout << "Who attempts suicide first?(M) : ";
  cin >> M;
  t = new Node<int>;
  t->key = 1;
  x = t;
  for (int i = 2; i <= N; i++) {
    t->next = new Node<int>;
    t = t->next;
    t->key = i;
  }
  t->next = x;
  cout << "The sequence of suicide is as follows : ";
  while (t != t->next) {
    for (int i = 1; i < M; i++) {
      t = t->next;
    }
    cout << t->next->key << " ";
    x = t->next;
    t->next = x->next;
    delete x;
  }	
  cout << t->key << endl;
}

> Enter the total number of people(N) : 9 <Enter>
> Who attempts suicide first?(M) : 5 <Enter>
> The sequence of suicide is as follows : 5 1 7 4 3 6 9 2 > 8