電脳ミツバチのコンピュータ広報室

銀座の屋上菜園を耕しています。コンピュータ畑も耕します。

Josephus problem(ジョセファスの問題)

スポンサーリンク

いまN人が集団自殺しようとしているとして、まず全員が円陣に並び、その円の中のM番目の人を順に処刑する。一人死ぬと取り除かれ、円の大きさが1へることになる。
今N=9(つまり全員で9人)M=5(つまり5番づつ)とする。処刑される順番を求めよ。


解き方
円陣を引き伸ばして考えると全員で9と言うことは最後の一人になるまで9+8+7+6+5+4+3+2+1=45回隣に移動する。そこでいわゆる循環リストを円陣に見立てて割り当てる。

#include<stdio.h>
#include<stdlib.h>
struct node{int key;struct node *next;};
main()
{
	int i,N,M;
	struct node *t,*x;
	scanf("%d %d",&N, &M);
	t=(struct node *)malloc(sizeof *t);
	t->key=1;/*1番目の番号付け*/
	x=t;
	for(i=2;i<=N;i++)
	{
		t->next=(struct node *)malloc(sizeof *t);
		t=t->next;
		t->key=i;/*番号付け2番からN番まで*/
	}
	t->next=x; /*最後の次は最初へ・・循環させる。*/
	
	while(t!=t->next)/*t->next==tとなれば後一人しかいないということ*/
	{
		for(i=1;i<M;i++)
			t=t->next;/*死のルーレットM-1番目でストップ*/
		printf("%d\n",t->next->key); /*次はあなたの番*/
		x=t->next;/*殺人個室へ連れて行かれるところ・・*/
		t->next=t->next->next; /*円の中では彼は居なかったことになる。*/
		free(x); /*殺害*/
	}
	printf("%d\n",t->key);/*最後の一人を表示*/
}

非常に解読が面白いクイズだった。