Fussy's Diary

今日は曇り空のおかげで気温は低かったものの、湿度が異常に高いので結局夜はエアコンのお世話に。しかし、昼間はエアコンいらずでした。

以前からアフリカで流行していたエボラ出血熱、アメリカの医師が感染して、帰国して治療するというニュースが流れていました。アフリカでは流行している地域を封鎖して拡大を防いでいるものの、さらに感染者が増えることが懸念されているようです。シエラレオネの国民的英雄だったカーン医師という方も感染して亡くなったとか。それにしても、危険を承知の上で活動する医師団の方々には頭が下がる思いです。
こうなると、日本に侵入する可能性もゼロとは言えないわけで、外務省も注意喚起を始めた模様。遅い気もしますが。以前、SARS が流行していたときに感染者が国内に滞在していたことに気づかなかったということもありましたが、完全に阻止するというのはやはり難しいもの。もしも国内で感染が見つかったらどう対処しておくかは検討しておいたほうがいいのではないでしょうかね。東電の原発事故で絶対はあり得ないというのは学習済みのはずですからね。  

今日、8 月 2 日は「パンツの日」だそうです。語呂合わせでそうなったらしいです。あと、6 月 2 日が「カレーの日」で 7 月 2 日が「うどんの日」だから 8 月 2 日は「カレーうどんの日」。さらにこれも語呂合わせで「ハーブの日」でもあるようです。いったい、そんな日を決めて何をすればいいのでしょうか。

「数学問題集」からこんな問題をチョイス。相変わらずの逃避行動。

-----

■ 3000 枚のカードに 1 から 3000 まで番号が書かれており、1 を一番上として番号順に積み重なっている。『一番上のカードを一番下に挿入し、次に一番上になったカードを捨てる』 という作業を繰り返したとき、最後に残るカードの数字は何か（コマ大数学科第 6 回ヨセフスの問題・改）

最初の操作は、1 を一番下 ( 3000 の下 ) に挿入して 2 を捨てることになります。次は 3 を下に挿入して 4 を捨てる... ということを繰り返した結果、偶数のカードは全て捨てられることになり、3000 番のカードを捨てれば 1 が再び一番上になります。この時点で、カードは奇数が 1 から順に並んだ状態となります。1 を一番下に挿入して一番上に現れるカードは 3 で、これが捨てられます。以下、5 を下に挿入して 7 を捨てる... ということを繰り返した結果、4n + 1 ( n ≥ 0 ) のカードだけが残った状態で再び 1 が一番上になります。以下、次のようにカードが残ることになります。

一巡目終了 : 2n + 1 が残り、1 が一番上になる。残りの枚数は 1500 枚。
二巡目終了 : 4n + 1 が残り、1 が一番上になる。残りの枚数は 750 枚。
三巡目終了 : 8n + 1 が残り、1 が一番上になる。残りの枚数は 375 枚。

四巡目からは残りの枚数が奇数になります。このとき、四巡目が終了した時点で捨てられるカードが逆転する現象が発生します。四巡目は 16n + 1 が残って 16n + 9 が捨てられる事になりますが、末尾のカードを一番下にしたときに現れるカードは 1 であり、次に捨てられるのはこのカードで、その後に現れるカードは 1 に 16 を加算した 17 です。従って、

四巡目終了 : 16n + 1 が残り、17 が一番上になる。残りの枚数は 187 枚。

となります。1 を捨てたので、端数は消えることに注意してください。つまり、奇数なら増分を加算すればいいので、これを繰り返せば

五巡目終了 : 32n + 1 が残り、17 + 32 = 49 が一番上になる。残りの枚数は 93 枚。
六巡目終了 : 64n + 1 が残り、49 + 64 = 113 が一番上になる。残りの枚数は 46 枚。
七巡目終了 : 128n + 1 が残り、113 が一番上になる。残りの枚数は 23 枚。
八巡目終了 : 256n + 1 が残り、113 + 256 = 369 が一番上になる。残りの枚数は 11 枚。
九巡目終了 : 512n + 1 が残り、369 + 512 = 881 が一番上になる。残りの枚数は 5 枚。
十巡目終了 : 1024n + 1 が残り、881 + 1024 = 1905 が一番上になる。残りの枚数は 2 枚。
十一巡目終了 : 2048n + 1 が残り、1905 が一番上になる。残りの枚数は 1 枚。

よって、最後に残るのは 1905 となります。アルゴリズムとしては、

1. 増分 add を 2、最後に残る番号 head を 1 で初期化する。
2. 枚数を 2 で割り、1 余ったら head に add を加算する。
3. add に 2 を掛ける。
4. 枚数が 1 になるまで 1 から 3 の操作を繰り返す。

ということになります。以下に、実際に配列を使って操作を繰り返す場合と、上記アルゴリズムを使った場合のサンプル・プログラムを示しておきます( C++ で STL を使ってます)。

unsigned int size = 3000; // カードの枚数

// 配列 (vector) を使って実際に操作する

std::vector<unsigned int> data( size );
for ( unsigned int i = 0 ; i < data.size() ; ++i )
data[i] = i + 1;

while ( data.size() > 1 ) {
unsigned int i = data[0];
data.erase( data.begin() );
data.push_back( i );
data.erase( data.begin() );
}
std::cout << data[0] << std::endl;

// 枚数を使ったアルゴリズム

unsigned int add = 2;
unsigned int head = 1;
while ( size > 1 ) {
if ( size & 1 ) head += add;
size /= 2;
add *= 2;
}
std::cout << head << std::endl;