今日は循環リスト構造を用いてJosephusuの問題を解きます。
線形リストについては前回の記事で軽くやったのでそちらもよかったら是非
また一番下に全体のコードを貼っておくので参考にどうぞ。
Josephusの問題とは
ｎ人の人間が円を描くように並び、処刑されるのを待っている。最初の人をスキップし、さらに ｋ−２人をスキップし（つまり、ｋ−１人をスキップして ｋ番目の人に到達する）、ｋ番目の人を処刑する。そしてそこから、再度 ｋ−１人をスキップして ｋ番目の人を処刑する。これを延々と続け（円は徐々に小さくなっていく）、最後に残った1人を釈放する。
問題は、ｎとｋが与えられたとき、起点をどこにしたら特定の人を最後まで残せるかである。
wikipedia内「ヨセフスの問題」より引用
つまり円に並んだｎ人の人間を１番目から数えてk人目を処刑、次はそこから数えてk人目を処刑って感じで最後に残るのは誰？って話です。
今回はこの問題を循環リストを用いて解いていきます。
コードの実装
リスト用の構造体
とりあえずリスト用に構造体を作っておきます。
何番目の人間なのかのデータを格納するint型と、
次の要素を指すポインタを持つ構造体を定義しときます。
typedef struct list{
int date;
struct list *next;
}list;要素を削除していく関数
このコードの主な部分となる関数を作っていきます。
まず思いつくのは
- 仮引数はリストを指すポインタ※
- ポインタをnextを使ってk回分走査していく
- 止まったところの要素を削除する
って感じ。
と思ったのですが、今回は仮引数はリストを指すポインタではだめですね。
二回目以降は削除された場所からのスタートなのでそれを記憶して置かなければなりません。
なので仮引数にはポインタのポインタを渡して、リストを指すポインタ自体も関数で変更する感じです。
また何人ずつ処刑するかも渡しておきましょう。
ポインタの走査は削除したいところの一個手前で止めて、ポインタを繋ぎ変えます。ここらへんも前回の記事で紹介したので確認をどうぞ。
コードです。
int Josephus(list **p,int s){
int i,l;
list *k;
for(i=0; i<s; i++){
*p = (*p)->next;
}
k = (*p)->next;
l = k->date;
(*p)->next = k->next;
return l;
}
だれが殺されたか分かるように、殺された人の番号が反るようにしました。
main関数
mainでは循環リストを実装していきます。
基本的にはforループで値を入れ、ポインタでつないでいきます。
最後の部分だけ先頭にもどるようにつなぎます。
さらに注意で、
上のJosephus関数では処刑する人までポインタを移動するとき、直前に処刑された人から数えることを前提で作ってます。
２回目以降はこれで問題ないのですが、１回目の処刑は直前に処刑された人がいないので一個ずれてしまいます。
なので対策として循環リストの先頭の前に、一個ダミーを置きます。
最初にダミーへのポインタを関数に渡すことによって１回目でもうまく動作します。
またダミーにはポインタを向けないので、ダミーに戻ってくることは無いです。
下に貼ってあるコードではlist型のstartがダミーです。
実際に動かしてみた
動かしてみます。
9人が2人ずつ処刑される場合は
最後に残るのは３番目
あってますね、おｋです。
てことで完成です。
ではまた〜
#include <stdio.h>
typedef struct list{
int date;
struct list *next;
}list;
int Josephus(list **p,int s){
int i,l;
list *k;
for(i=0; i<s; i++){
*p = (*p)->next;
}
k = (*p)->next;
l = k->date;
(*p)->next = k->next;
return l;
}
int main(void) {
list A[9],start;
int i;
for(i=0; i<8; i++){
A[i].date = i+1;
A[i].next = &A[i+1];
}
A[8].date = 9;
A[8].next =&A[0];
start.next = &A[0];
list *head = &start;
for(i=0; i<9; i++){
printf("%d\n",Josephus(&head,2));
}
return 0;
}
コメント