読者です 読者をやめる 読者になる 読者になる

CodeIQ 挑戦の記録 :「レッド・アンド・ホワイト」問題

CodeIQというサイトで問題に挑戦した記録です。

問題文を要約すると下記の通り

  • マス目が直線上に限りなく並んでいる(初期状態は全て白色)
  • このうちの1つを赤色に塗る。
  • 次のルールに従いマス目の色を塗り替える時、n秒後の赤色のマス目の個数を解答する。
  • 1秒ごとに下記の通り変化する
    左右のマス目が白赤または赤白のマス目->赤色に塗る。
    左右のマス目が白白または赤赤のマス目->白色に塗る。

方針

題意に従い、二次元配列を使って状態の変化を表示してみる。
赤色のマス目を「1」で、白色のマス目を空白で表示すると、パスカルの三角形に似た図形が表示される。

f:id:ibeckuu:20160518025212j:plain

この図形は、パスカルの三角形の奇数部分を塗りつぶしてできる「シェルピンスキーのギャスケット」と同様のものである。

パスカルの三角形には様々な規則性が隠れているが、n行目(最初を0行目とする)に含まれる奇数の個数はnを2進法で表記した時の1の個数を{p}とすると{2^p}に等しい事が知られている。

[パスカルの三角形と2進法]
http://www7b.biglobe.ne.jp/~fukagawa/documents/mod2pascal.pdf

実装

上記の性質を用いて解答する。(Ruby・27文字)

なお、標準入力からの数値を2進法で文字列化する時に、Rubyではsprintfが使えるが、これの代わりに「%」で書式文字列が使えるのでこれを利用して2進法表記の文字列とし、その中の1を数えている。

p 2**(("%b"%gets).count'1')


おまけ

上記の規則性に気づく前に提出した1回目の解法

この三角形は0行目が1が1個、1行目が1が2個の2行でなる三角形が2行ごとに2倍ずつ繰り返し現れ、 2のべき乗行目に2に戻る事を繰り返している。
これより、与えられた数をその数より小さい最大の2のべき乗で引いていき、その回数の2倍を解答とする。

n=gets.to_i;a=1;while n>0;a*=2;n-=2**Math.log2(n).floor;end;p a

では、


Sponsored Link