戦術T2'の実装

前回からの続き。

ソースコードの良い構造とは

コードはなるべく意味の単位で分割されていることが望ましい。そのためには関数を適宜定義したりするのも良いが、最も効果的なのはオブジェクトを用いる方法である。今回はまずオブジェクトを用いないでプログラミングをして、そこから逆にオブジェクトの有用性を考察する。

データ構造

アルゴリズムを決定する上で、データ構造が重要となる。実際、データ構造を決定するとアルゴリズムは自ずと定まる場合が多い。逆に言うとデータ構造について十分な考察をしないまま始めて、後々データ構造を変更するということになると、アルゴリズムの大部分を書き換える必要が出て来る。なのでデータ構造は予め決めておきたいところだが、難しいのはある程度アルゴリズムが決まらないとデータ構造の良し悪しが判断できないという点である。実は、この点もオブジェクトを用いれば解決できる。

戦術T2'はciをPiの最小数として決定する。Piのデータ構造が決まっていれば、Piの最小数を探す方法＝アルゴリズムは自ずと定まってくる。それではPiのデータ構造はどうやって定めるのが良いだろうか。そのためにはPiが他にどんな操作を加えられるのか見てみるのが良い。

PiはP(i-1)からフィードバックf(i-1)によって生成される。*1要はP(i-1)の中でf(i-1)に適合する数だけを集めたのがPiである。

こういう扱われ方をするPiのデータ構造には色々な方法があるだろうが、ここでは次のようにデータ構造setを定める：

[[sign], num, [sign], num, [sign], num, ..., [sign], num]

ただしここでsignはbool型でnumは配列である。

setがどのようにしてPiを表すのか説明する。i番目のnumは自然数iを各桁毎に格納した配列である。i番目のsignはi番目のnumがPiに含まれている場合はTrueで含まれない場合はFlaseである。

例

P1はsetによって次のように表現される：

[[False], [0,0,0], [False], [0,0,1], ..., [True], [0,1,2], ..., [False], [9,9,9]]

データ構造setが集合Piを表す最善のものと言うつもりは全く無い。ただ採用するデータ構造がいかにアルゴリズムに影響するかを見るためには丁度よい。

*1:数学ではこのような動的な記述は嫌われるかもしれない。ただ今は具体的な手順を考察する立場なので、このような動的な記述のほうが役に立つ。