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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 265 / 2進円

2^N の2進数の数字は時計回りに N 桁連続する数字すべてで網羅するように円状に並べることができる。例えば N=3 では回転を無視すると2つの円状の配置が可能である。

f:id:variee:20170506235635g:plain

最初の配置では時計回りの3桁の数列は
000, 001, 010, 101, 011, 111, 110, 100
である。それぞれの円形の配置は全部が 0 であるような数列を最上位にして時計回りに数字をつなげることで, 1つの数に変換できる。N=3 の2つの配置は23と29になる。

  • 00010111(2) = 23
  • 00011101(2) = 29

S(N) を異なる変換した数の合計とすると,
S(3)=23+29=52

S(5) を求めよ。

Problem 265 - Project Euler


第164問と同じような方法(グラフ理論)で解きました。

variee.hatenadiary.com

まず N=3 の場合を考えます。

000の後に1が続くことから 000 → 001 のようなグラフの種をたくさん作って,有向グラフにまとめます。

f:id:variee:20170507000507p:plain

次にハミルトン閉路を求めます。

問題文であげられている2つの配置はこれです。

次は23と29をどう求めるか考えます。リストの中に0と1は次のように収納されています。はじめは0が並ぶので,黄色で塗った2数だけ考えれば十分です。

2進法であることを考えると
23=3*2^3+7
のようにして閉路に対応する数を求められます。


N=5の場合もやることは同じです。

ちなみに N=5 の有向グラフはこうなります。

f:id:variee:20170507003039p:plain