「どうしても解けなかった数学の練習問題」の編集履歴（バックアップ）一覧はこちら
どうしても解けなかった数学の練習問題 - (2013/05/23 (木) 16:09:18) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
数学の勉強で昔こんな問題に挑戦したことがあります。
堀江 伸一
3*3*10＾10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。
答えは答えを１０億7だったかそんな数で割った余りを答えよという問題。
１０億段とか1000兆段とかそういうちいさな段数でなく10001桁段です。
とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。
上面に出っ張りの飛び出た、下面に穴ぼこのあいた２段で可能なものを全て作ります。
その２段から二つ選び（同じものを二つ選んでもよい）可能な4段全てを作ります。
4段でも同様に8段を作り、同じように8段を組み合わせて16段を作ります。
これを10＾10000段の直前まで作りつづけます。
10＾10000段を２進数になおしたときあるｎ桁目に１のビットが立ってたら、２^n段を作れた時にそれをどんどんアセンブリして積み重ねていけば答えが出ます
細部は覚えてませんが大体この方法で６時間半パソコンに計算させて正しい答えが出ました。
なぜ２段から計算を始めたかというと10＾10000を２進数になおしたとき１段単独からのアッセンブリーがなかったからです。
考えることが容易な２段から作った覚えがあります。
当時書いたときは１段から計算を始めるとプログラムが複雑になると考えてたようです。
例えば１０段を２進数で表すと1010段ですが、これは８段と２段を組みあわせれば１０段となります。
組み合わせた後、上面と下面にでこぼこのないセットの組み合わせ数を出力すれば答えとなります。
アセンブルするときに上面の凸凹が512通りのサブセット、下面の凸凹が512通りのサブセット、結合部の上面の凹凸が決まれば結合部下面の形が決まるので512通りのサブセット。
一つ結合するときにＢｉｇＯ(512＾３)、必要な段数は10＾10000=2^37000くらいなのでこの結合を３７０００回する必要があります。
BigO(512＾３*37000)の計算です。
当時コードを書いたときは試行錯誤の残る多少非効率で無駄も入ったコードも書いていた覚えもあります。
実際は上面と下面に制約があるのでもうすこし計算量が落ちてましたが、６時間半もパソコンを回したのを覚えています。
正しいコードだと、３０秒で答えが出るそうなのでもっと高度な発想が必要な問題だったようです。
正しい答えが出るからって計算に６時間半もかかっては不正解となったものでした。
ちなみに私は創価学会の方から小学校の足し算と掛け算までしかできない人間だとという悪いうわさを流されていますが。
本物の堀江伸一はこういう問題を趣味で解いている人間だったりします。
http://www14.atwiki.jp/c21coterie/pages/597.html
さて昔書いたコードを見ると。
とにかく自分で考えついたものを試しては駄目を繰り返しそのあと答えにたどり着いた試行錯誤の跡が残りまくりの酷いコード。
どうしてこんな、意味不明で効率の悪いコードをたくさん書いたのだろう？
今書きなおすなら。
dp[2][612][512]でブロックタワーの組み合わせを動的計画法で求める。
最初の１段を再帰で求めて作って、あとは４重ループ。
一番外は約3７０００回段を組み合わせていくループ。
その中に上面、下面、結合部面でブロックを結合する３重ループ。
それと、結合後、作ったブロックタワーを答えのためにアセンブリするコードも同じ要領で書くと。
アセンブリするコードと２倍段を作っていくコードは処理はほぼ共通だから、関数化すれば。
計算量は落とす方法は未だによくわからないが、今ならずっとシンプルに書けるなこれ。
すこしは勉強が進んでるのかもしれない。
数学の勉強で昔こんな問題に挑戦したことがあります。
堀江 伸一
3*3*10＾10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。
答えは答えを１０億7だったかそんな数で割った余りを答えよという問題。
１０億段とか1000兆段とかそういうちいさな段数でなく10001桁段です。
とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。
上面に出っ張りの飛び出た、下面に穴ぼこのあいた２段で可能なものを全て作ります。
その２段から二つ選び（同じものを二つ選んでもよい）可能な4段全てを作ります。
4段でも同様に8段を作り、同じように8段を組み合わせて16段を作ります。
これを10＾10000段の直前まで作りつづけます。
10＾10000段を２進数になおしたときあるｎ桁目に１のビットが立ってたら、２^n段を作れた時にそれをどんどんアセンブリして積み重ねていけば答えが出ます
細部は覚えてませんが大体この方法で６時間半パソコンに計算させて正しい答えが出ました。
なぜ２段から計算を始めたかというと10＾10000を２進数になおしたとき１段単独からのアッセンブリーがなかったからです。
考えることが容易な２段から作った覚えがあります。
当時書いたときは１段から計算を始めるとプログラムが複雑になると考えてたようです。
例えば１０段を２進数で表すと1010段ですが、これは８段と２段を組みあわせれば１０段となります。
組み合わせた後、上面と下面にでこぼこのないセットの組み合わせ数を出力すれば答えとなります。
アセンブルするときに上面の凸凹が512通りのサブセット、下面の凸凹が512通りのサブセット、結合部の上面の凹凸が決まれば結合部下面の形が決まるので512通りのサブセット。
一つ結合するときにＢｉｇＯ(512＾３)、必要な段数は10＾10000=2^37000くらいなのでこの結合を３７０００回する必要があります。
BigO(512＾３*37000)の計算です。
当時コードを書いたときは試行錯誤の残る多少非効率で無駄も入ったコードも書いていた覚えもあります。
実際は上面と下面に制約があるのでもうすこし計算量が落ちてましたが、６時間半もパソコンを回したのを覚えています。
正しいコードだと、３０秒で答えが出るそうなのでもっと高度な発想が必要な問題だったようです。
正しい答えが出るからって計算に６時間半もかかっては不正解となったものでした。
ちなみに私は創価学会の方から小学校の足し算と掛け算までしかできない人間だとという悪いうわさを流されていますが。
本物の堀江伸一はこういう問題を趣味で解いている人間だったりします。
http://www14.atwiki.jp/c21coterie/pages/597.html
さて昔書いたコードを見ると。
とにかく自分で考えついたものを試しては駄目を繰り返しそのあと答えにたどり着いた試行錯誤の跡が残りまくりの酷いコード。
どうしてこんな、意味不明で効率の悪いコードをたくさん書いたのだろう？
今書きなおすなら。
dp[2][612][512]でブロックタワーの２倍段の組み合わせを動的計画法で求めるか。
最初の１段を再帰で求めて作って、あとは４重ループ。
一番外は約37000回、２倍段を作るループ。
その中に上面、下面、結合部面でブロックを結合する３重ループ。
それと、結合後、作ったブロックタワーを答えのためにアセンブリするコードも同じ要領で書くと。
アセンブリするコードと２倍段を作っていくコードは処理はほぼ共通だから、関数化すれば。
計算量は落とす方法は未だによくわからないが、今ならずっとシンプルに書けるなこれ。
すこしは勉強が進んでるのかもしれない。
