99.07.13 deepgreen 更新履歴 99.07.13 恐れ入りますが､固定ピッチのフォントで表示してください。 記述ミスを訂正（Bitmap形式からNodeMatrix形式への変換） 記述ミスを訂正（NodeMatrix形式からBitmap形式への変換） アルカンの構造異性体の数をパズル的に（シラミツブシに）解く方法です。 □ 解法の概要 大きさＮ(炭素数がＮという意味）のアルカンの構造異性体が既知として、（Ｎ＋１）の 大きさのアルカンの構造異性体を求めるという方法です。 ＋−−−−−＋ ＋−−−−−＋ ｜アルカンの｜ ＋−−−−−−−−−＋ ｜アルカンの｜ ｜構造異性体｜ ｜・（Ｎ＋１）を生成｜ ｜構造異性体｜ ｜のBitmap ｜−−＞ ｜・ 標準形式に変換 ｜−−＞ ｜のBitmap ｜ ｜（Ｎ） ｜ ｜・ 重複検査 ｜ ｜（Ｎ＋１）｜ ｜ ｜ ＋−−−−−−−−−＋ ｜ ｜ ＋−−−−−＋ ＋−−−−−＋ □ アルカン構造体の表現法 [例題パターン］ Ｃ３ ｜ Ｃ１−Ｃ２−Ｃ４−Ｃ７ ｜ Ｃ５ ｜ Ｃ６ （その１）NodeMatrix形式 炭素（ここではＮｏｄｅと呼ぶ）に番号をつけ、各Ｎｏｄｅ間の接続状態を２次元配列 Node[][]で以下のように表現する。 ｉ番目のＮｏｄｅには、 Node[i][0] ：Ｎｏｄｅ（ｉ）に接続しているＮｏｄｅの数（１〜４） Node[i][j] ：Ｎｏｄｅ（ｉ）に接続している他Ｎｏｄｅの番号 ｊは、１− Node[i][0]まで (例）例題パターンのNodeMatrix表現 ［０］［１］［２］［３］［４］ Ｎｏｄｅ［１］ １ ２ ［２］ ３ １ ３ ４ ［３］ １ ２ ［４］ ３ ２ ５ ７ ［５］ ２ ４ ６ ［６］ １ ５ ［７］ １ ４ この表現法は、取り扱いは易しいが、必要とするスペースが大きいので大量のパタ ーンを格納するには向きません。 （その２）Bitmap形式 各Ｎｏｄｅの接続数が１〜４であることに着目し、接続数の列として表現する。 この方法は、２ビット＊Ｎで１つのパターンを表現できます。 接続数 ビットパターン １ ００ ２ ０１ ３ １０ ４ １１ 表記法 Ｌ，Ｄ，Ｕ，Ｒが既にビットパターンに変換済とすると、全体のＢｉｔｍａｐ表現 を以下のようにします。 Ｕ ｜ Ｌ−Ｃ−Ｒ ＝＝＝＞ Ｌ （Ｃの接続数） Ｄ Ｕ Ｒ ｜ Ｄ （例） (1) Ｃ−Ｃ−Ｃ−Ｃ ＝＝＞ ０００１０１００ (2) Ｃ−Ｃ−Ｃ−Ｃ ＝＝＞ ０００１１００１００００ ｜ Ｃ ｜ Ｃ どこを始点にとるかによって表現は変わりますので、例題パターンのいくつかの表現 を以下に示します。 (3) Ｃ１を始点とした場合 ００１０００１００１００００ (4) Ｃ６を始点とした場合（その１） ０００１１０１０００００００ (5) Ｃ６を始点とした場合（その２） ０００１１０００１０００００ いくつかの表現パターンのうち、Bitmapが最小となるパターンを標準形と定義する。 こうする事で１つの構造体に１つのパターンを対応させることができます。 この表現法の長所は、コンパクト性と標準形の判断基準の容易性にあります。反面、 取り扱いは難しくなっています。たとえば、(3)の表現から(5)の標準形に変換する のはちょっと面倒です。 □ Bitmap形式からNodeMatrix形式への変換 (1) ビットパターンを２ビットずつ区切って順番にＮｏｄｅ番号とする (2) ｐｒｅ，ｃｕｒの２つのポインタを使ってＮｏｄｅのリンクをはる ・ｐｒｅはリンク元のＮｏｄｅを指すようにする ・ｃｕｒの指すビットパターンが０１のときは、ｐｒｅとのリンクをはるだけ ・ｃｕｒの指すビットパターンが１０，１１のときは、ｐｒｅとのリンクをはるとともに ｃｕｒの位置をスタックする （１１のときは２度スタックする） ・ｃｕｒの指すビットパターンが００のときは、ｐｒｅとのリンクをはり、スタックから ｐｒｅをリストアする ０００１１０１０００００００ わかりやすく書くと −−−−−−−−−− ０００１１０（１０００００）００ ｜ ｜ ｜ ｜ ｜ ｐ ｑ ａ ｂ ｃ ｐ ｑ ａ ｂ ｃ ｂはｑ（ｃはｐ）とのリンクをはらなければならない。そのために、ｑの時点でｃｕｒの 位置をスタックしておき、ａのところでスタックからｐｒｅにリストアする □ NodeMatrix形式からBitmapt形式への変換 ｃ ｜ ａ−Ｘ−ｂ ｜ ｄ (1) 指定された始点から Node[][0] >= 2 となる NodeＸをサーチし、ａの部分のBitmapを作成する (2) 再帰呼び出しを使って、ｂ，ｃ，ｄのBitmapを作成する (3) ａを先頭とする最小のBitmapを作成する 例えば、ｃ＜ｂ＜ｄの場合は、 ａ 11 ｃ ｂ ｄ となる □ 全体のアルゴルズム (1) Bitmap形式からNodeMatrix形式に変換する。 (2) NodeMarix上で大きさ(N+1)に拡張する。 (3) NodeMatrixのterminal(Node[i][0]=1のもの)を捜す。 (4) 上記のterminalを始点として、NodeMatrix形式をBitmap形式に変換する (5) (3),(4)をすべてのterminalについて実施し、最小のBitmap形式(標準形）を得る。 (6) (5)で得られた標準形が既にresult[]に登録されているかどうかを調べる。 未登録の場合は、登録する。 (7)(2)-(6)をすべてのNodeについて実施する。