最速アルゴリズム
昨日、某東大生と一緒にCのアルゴリズムを考えてた。
課題「条件(????*????==????????)を満たす16個の16進数の組み合わせの数を答えよ。ただし、16個の?に入る値はすべて異なるものとする」
そんな数列の作り方なんてちっともおぼえてねーよぅ。いろいろ悩んだ結果、東大生のとこの環境では30秒くらいで計算が終了するようになった。修正当初は3分だったから、大幅な改善といえる。さて、これを5秒くらいまで縮めるにはどうすればいいのかにゃー。
会社にて
作ってみた。答え合ってるかな？ CPUは3GHz。メモリは512の環境。一応できたけど、ソースはfor文の8重ネストという、卒倒しそうな糞コード。もっといい数列の作り方がある気がするが、めんどくせーのでこれでいーや。
結果・・・1304個。 実行時間 10秒。
改良点・・・同じ答えになる計算を変数に格納して計算コストを低減。積算の項1と項2が逆になるケースを省略して計算回数を半減。左辺の２項のどちかの最上位が0または1のケース、もしくは最下位が0または1のケースを計算対象から除外。
