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);/*最後の一人を表示*/ }
非常に解読が面白いクイズだった。