« 「コード・トライアスロン2」の高度じゃないコード | トップページ | 「マイナー・ゲーム問題」の高度じゃないコード »

2016年5月25日 (水)

「レッド・アンド・ホワイト問題」の高度じゃないコード

非常に遅ればせながらの「高度じゃないコード」シリーズその12、「レッド・アンド・ホワイト問題」です。

数学の問題をプログラミングで解こう!「レッド・アンド・ホワイト」問題解説

最初には1箇所だった赤マスがルールに従って1秒毎に変化していきます。その時、n秒後(1 ≦ n ≦ 108)の赤マスの数を答えろという問題です。
イメージがわきにくいので、まずは1秒~32秒のパターンを調べてみました。0が白マスで1が赤マスです。

01秒101
02秒10001
03秒1010101
04秒100000001
05秒10100000101
06秒1000100010001
07秒101010101010101
08秒10000000000000001
09秒1010000000000000101
10秒100010000000000010001
11秒10101010000000001010101
12秒1000000010000000100000001
13秒101000001010000010100000101
14秒10001000100010001000100010001
15秒1010101010101010101010101010101
16秒100000000000000000000000000000001
17秒10100000000000000000000000000000101
18秒1000100000000000000000000000000010001
19秒101010100000000000000000000000001010101
20秒10000000100000000000000000000000100000001
21秒1010000010100000000000000000000010100000101
22秒100010001000100000000000000000001000100010001
23秒10101010101010100000000000000000101010101010101
24秒1000000000000000100000000000000010000000000000001
25秒101000000000000010100000000000001010000000000000101
26秒10001000000000001000100000000000100010000000000010001
27秒1010101000000000101010100000000010101010000000001010101
28秒100000001000000010000000100000001000000010000000100000001
29秒10100000101000001010000010100000101000001010000010100000101
30秒1000100010001000100010001000100010001000100010001000100010001
31秒101010101010101010101010101010101010101010101010101010101010101
32秒10000000000000000000000000000000000000000000000000000000000000001

すると面白いことがわかります。この中で1(赤マス)の数が2つしかないのは1秒・2秒・4秒・8秒・16秒・32秒、つまり2のべき乗秒です。そして、それより1秒前は1(赤マス)と0(白マス)が交互に並びます。そうして調べていくと、秒数を2進数にした時の1の数を m とすると、2m が1(赤マス)の数があることがわかります。

ということで、それをコーディングしたのが次の Ruby(32) のコードです。

とうの昔に Ruby(26) のコードが発表されていますが・・・。

|

« 「コード・トライアスロン2」の高度じゃないコード | トップページ | 「マイナー・ゲーム問題」の高度じゃないコード »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/99795/63681506

この記事へのトラックバック一覧です: 「レッド・アンド・ホワイト問題」の高度じゃないコード:

« 「コード・トライアスロン2」の高度じゃないコード | トップページ | 「マイナー・ゲーム問題」の高度じゃないコード »