数学の勉強で昔こんな問題に挑戦したことがあります。 堀江 伸一 3*3*10＾10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。 答えは答えを１０億7だったかそんな数で割った余りを答えよという問題。 １０億段とか1000兆段とかそういうちいさな段数でなく10001桁段です。 とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。 上面に出っ張りの飛び出た、下面に穴ぼこのあいた２段で可能なものを全て作ります。 それを二セット作り全組み合わせで4段を作ります。 4段の全ての組から二つ選び組み合わせたもので8段を作り、同じように8段を組み合わせて16段を作ります。 これを10＾10000段の直前まで作りつづけます。 10＾10000段を２進数になおしたときあるｎ桁目に１のビットが立ってたら、２^n段を作れた時にそれをどんどんアセンブリして積み重ねていけば答えが出ます 細部は覚えてませんが大体この方法で６時間半パソコンに計算させて正しい答えが出ました。 なぜ２段から計算を始めたかというと10＾10000を２進数になおしたとき１段単独からのアッセンブリーがないことを利用して考えることが容易な２段から作った覚えがあります。 当時書いたときは１段から計算を始めるとプログラムが複雑になるような気がしたからです。 アセンブルするときに上面の凸凹が512通りのサブセット、下面の凸凹が512通りのサブセット、結合部の上面の凹凸が決まれば結合部下面の形が決まるので512通りのサブセット。 一つ結合するときにＢｉｇＯ(512＾３)、必要な段数は10＾10000=2^37000くらいなのでこの結合を３７０００回する必要があります。 BigO(512＾３*37000)の計算です。 実際は上面と下面に制約があるのでもうすこし計算量が落ちてました。 それと当時コードを書いたときは試行錯誤の残るもう少し非効率で多少無駄も入ったコードも書いていた覚えもあります。 計算に6時間半かかったのは仕方なかったのですが。 正しいコードを書くと、３０秒で答えが出るそうなのでもっと高度な発想が必要だった問題のようです。 正しい答えが出るからって計算に６時間半もかかっては不正解となったものでした。 ちなみに私は創価学会の方から小学校の足し算と掛け算を何とかできるレベルの人間だとという悪いうわさを流されていますが。 本物の堀江伸一はこういう問題を趣味で解いている人間だったりします。
