科学技術計算というよりも、数理パズルをプログラミングで解いたりする。
今取り組んでる数理パズルなんだが、自然数nについて、いくらでも大きなnでも思考できるパズルなんです。
魔方陣のように既知のアルゴリズムが存在しているものでは無いものにチャレンジしている最中なのです。
n = 1 のとき、考えるまでも無く解は1個しかない。
n = 2 のとき、解は1個であるのは自明である。
n = 3 のとき、これも解は1個であるのは自明である。
n = 4 のとき、解が2個見つかる。
n = 5 のとき、解が1個しか見つからない。
n = 6 のとき、解が5個見つかる。
n = 7 のとき、解が1個も見つからない。
n = 8 のとき、解が6個見つかる。
n = 9 のとき、解が4個見つかる。
n = 10 のとき、解が6個見つかる。
n = 11 のとき、解が1個も見つからない。
n = 12 のとき、解が18個見つかる。
n = 13 のとき、解が1個も見つからない
n = 14 のとき、解が20個見つかる。
…
と解の個数に脈略が見えない。
紙と鉛筆で解を求めようとすると、n = 6 くらいが限度だろう。
n = 7 が解無しである事を紙と鉛筆で証明するのは不可能だと思う。
こんな難問はプログラミングで解かせるに限る。
と意気込んだものの、試行錯誤の末に、ある程度高速に解を求める事が出来る様にはなったが、…
n < 11 は1秒未満で全ての解を表示出来た。
n = 11 のとき、約2.4秒
n = 12 のとき、約24秒
n = 13 のとき、約4分
n = 14 のとき、約40分
とnが1増えるに連れ、約10倍の時間が掛かっていることが判った。
n = 15 は 400分 = 6時間40分
n = 16 は 4000分 = 2.{7}日
これくらいまでは耐えられるが、
n = 17 は 約1ヶ月
n = 18 は 約10ヶ月
とさすがに耐えられない。
といいつつ、n = 17 を仕掛け、既に2個の解を見つけ出した。
そろそろ、新しいアルゴリズムを探さないといけない段階に来ているんだろう。
さすがに、これくらい時間が掛かるプログラムなので、途中経過をハートビート（つまりプログラムが生きているかどうかの確認の為）のように表示させることとなる。
さて、私は未だにDOS窓で動作するコマンド系のプログラムしか書かない。（JavaやJavaScriptは除く）
DOS全盛の頃は、BIOSをつつく、
#define inkey() (bdos(0x06,0xff,0)&0x00ff)
というようなBASICのINKEY$のような役目のマクロを使っていた。
Windowsになってからは、この方法は使えず、
if ( kbhit() ) {
key = getch();
…
}
といった方法もあるのだが、こいつが時間が掛かりすぎる為、使うのを躊躇ってしまう。
あとは、標準出力とエラー出力を使い分けて、
fprintf(stdout, "解 hogehoge\n", ...);
fprintf(stderr, "途中経過 hogehoge 適当なスペース\r", ...);
のように\nと\rとする。
つまり、途中経過の表示は同じ行に上書きされるのね。
stdoutとstderrで思い出したのが、stdprn
DOS全盛の頃、ダンジョン系のゲームで、地図やメモを拾うとラインプリンタから印刷されるというのを作ったが、日の目を見ることは無かった。
しかしprintfは遅い。
何日にも及ぶプログラムの途中経過に使いたくはない。
n = 17 のプログラムが終了したら紹介するかな。
年間中になるか、年明けになるか、…
Doblog 2008/12/03 00:00:00
今取り組んでる数理パズルなんだが、自然数nについて、いくらでも大きなnでも思考できるパズルなんです。
魔方陣のように既知のアルゴリズムが存在しているものでは無いものにチャレンジしている最中なのです。
n = 1 のとき、考えるまでも無く解は1個しかない。
n = 2 のとき、解は1個であるのは自明である。
n = 3 のとき、これも解は1個であるのは自明である。
n = 4 のとき、解が2個見つかる。
n = 5 のとき、解が1個しか見つからない。
n = 6 のとき、解が5個見つかる。
n = 7 のとき、解が1個も見つからない。
n = 8 のとき、解が6個見つかる。
n = 9 のとき、解が4個見つかる。
n = 10 のとき、解が6個見つかる。
n = 11 のとき、解が1個も見つからない。
n = 12 のとき、解が18個見つかる。
n = 13 のとき、解が1個も見つからない
n = 14 のとき、解が20個見つかる。
…
と解の個数に脈略が見えない。
紙と鉛筆で解を求めようとすると、n = 6 くらいが限度だろう。
n = 7 が解無しである事を紙と鉛筆で証明するのは不可能だと思う。
こんな難問はプログラミングで解かせるに限る。
と意気込んだものの、試行錯誤の末に、ある程度高速に解を求める事が出来る様にはなったが、…
n < 11 は1秒未満で全ての解を表示出来た。
n = 11 のとき、約2.4秒
n = 12 のとき、約24秒
n = 13 のとき、約4分
n = 14 のとき、約40分
とnが1増えるに連れ、約10倍の時間が掛かっていることが判った。
n = 15 は 400分 = 6時間40分
n = 16 は 4000分 = 2.{7}日
これくらいまでは耐えられるが、
n = 17 は 約1ヶ月
n = 18 は 約10ヶ月
とさすがに耐えられない。
といいつつ、n = 17 を仕掛け、既に2個の解を見つけ出した。
そろそろ、新しいアルゴリズムを探さないといけない段階に来ているんだろう。
さすがに、これくらい時間が掛かるプログラムなので、途中経過をハートビート（つまりプログラムが生きているかどうかの確認の為）のように表示させることとなる。
さて、私は未だにDOS窓で動作するコマンド系のプログラムしか書かない。（JavaやJavaScriptは除く）
DOS全盛の頃は、BIOSをつつく、
#define inkey() (bdos(0x06,0xff,0)&0x00ff)
というようなBASICのINKEY$のような役目のマクロを使っていた。
Windowsになってからは、この方法は使えず、
if ( kbhit() ) {
key = getch();
…
}
といった方法もあるのだが、こいつが時間が掛かりすぎる為、使うのを躊躇ってしまう。
あとは、標準出力とエラー出力を使い分けて、
fprintf(stdout, "解 hogehoge\n", ...);
fprintf(stderr, "途中経過 hogehoge 適当なスペース\r", ...);
のように\nと\rとする。
つまり、途中経過の表示は同じ行に上書きされるのね。
stdoutとstderrで思い出したのが、stdprn
DOS全盛の頃、ダンジョン系のゲームで、地図やメモを拾うとラインプリンタから印刷されるというのを作ったが、日の目を見ることは無かった。
しかしprintfは遅い。
何日にも及ぶプログラムの途中経過に使いたくはない。
n = 17 のプログラムが終了したら紹介するかな。
年間中になるか、年明けになるか、…
Doblog 2008/12/03 00:00:00