数学の勉強で昔こんな問題に挑戦したことがあります。 堀江 伸一 3*3*10＾10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。 答えは答えを１０億7だったかそんな数で割った余りを答えよという問題。 １０億段とか１００段とかそういうちいさな段数でなく10001桁段です。 とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。 上下に出っ張りのはみでた一段を組み立て、それを二つつくり二つを組み合わせて２段を作り。 ２段を二つ組み合わせて4段を作り。 これを10＾10000段の直前まで作る。 10＾10000段を２進数になおしたとき１のビットが立ってたらその段数を作れた時に順にアセンブリしていけば答えが出ます。 細部は覚えてませんが大体この方法で６時間半の計算で答えが出ました。 アセンブルするときに上面の凸凹が512通り位、下面の凸凹が５１２通り、真中の凸凹は結合部の上面が決まれば結合部下面の形が決まるので。 一つ結合するときに512*512*512、必要な段数は10＾10000=2^37000くらいなのでこの結合を３７０００回する必要があります。 実際は上面と下面に制約があるのでもうすこし計算量が落ちると思いますし、当時コードを書いたときはもう少し非効率で無駄なコードを書いていた覚えもあります。 数時間かかるのは仕方ないような気がします。 正しいコードを書くと、３０秒で答えが出るそうなのでもっと高度な発想が必要なようです。
