「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。今月(2022年10月)からは多忙につき、日々の投稿数を減らします。

MENU

アルゴリズムの学習(004/XXX)

 コンピュータ科学を学ぶべくアルゴリズムを学んでいく。参考として定番書であり古典的名著でもある

を用いる。実装には勉強もかねてC#を使う。

5. 異性体の数え上げ

 飽和鎖式炭化水素C_nH_{2(n+1)}の構造異性体の数を数え上げる。水素原子の位置は自然に決まるため、炭素原子のみ考える。
 炭素原子は1個以上4個以下の別の炭素原子と結合できる。ただし結合が環をつくってはならない。

考え方
 結合の手が1本余った基を考える。基はこの余った手で他の炭素原子と結合できる。特殊の場合として炭素原子が0個の場合も考える。
 空を含む基をちょうど3個持ってきて、別に用意した1個の炭素原子の4本の手のうち3本と結合させると新しい基ができる。

 空の基を0番の基とし、空でない基には以下のようにして番号1,2,3,\cdotsを振る。すなわち新しい基はそれを作るのに用いた3個の基の番号(i,j,k)を指定することで定まる。ただし曖昧さを無くすべくi\geq j\geq kと仮定する。このような組(i,j,k)の可能な値を辞書式順序に並び替えてこれらの基にそれぞれ1,2,\cdotsと番号を振る。
 n個の基の炭素原子の数をsize[n]とし、n番の基の最も長い鎖の炭素原子数をlength[n]とする。n番の基が組(i,j,k)で表されるならば、


\begin{aligned}
size[]&=size[i]+size[j]+size[k]+1,\\
length[n]&=length[i]+1
\end{aligned}

が成り立つ。基が生成できたところでこれをつなげば求める構造が得られる。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace isomers
{
    class Program
    {
        public const int C = 17;
        public const int L = 2558;

        static void Main(string[] args)
        {
            // メモ:定数の定義:[改訂新版]C#ポケットリファレンス P.54

            var size = new int[L];
            var length = new int[L];
            var count = new int[C + 1];

            int i, j, k, h, len, n, si, sj, sk, sh;

            n = 0;
            size[0] = 0;
            length[0] = 0;

            len = 0; // 46行でエラーを起こし得るため、とりあえず値を追加する

            for (i = 0; i < L; i++)
            {
                len = length[i] + 1; if (len > C / 2) break;
                si = size[i] + 1; if (si + len > C) continue;

                for (j = 0; j <= i; j++)
                {
                    sj = si + size[j]; if (sj + len > C) continue;

                    for (k = 0; k <= j; k++)
                    {
                        sk = sj + size[k]; if (sk + len > C) continue;
                        if (++n >= L) Environment.Exit(1);
                        size[n] = sk;
                        length[n] = len;
                    }
                }
            }

            if (len <= C / 2) Environment.Exit(1);

            for (i = 0; i <= n; i++)
            {
                si = size[i];

                for (j = 0; j <= i; j++)
                {
                    if (length[i] != length[j]) continue;
                    sj = si + size[j]; if (sj > C) continue;
                    count[sj]++;

                    for (k = 0; k <= j; k++)
                    {
                        sk = sj + size[k] + 1; if (sk > C) continue;

                        for (h = 0; h <= k; h++)
                        {
                            sh = sk + size[h];
                            if (sh <= C) count[sh]++;
                        }
                    }

                }
            }

            for(i = 1; i <= C; i++)
            {
                Console.WriteLine("炭素原子が{0}個のものは{1}種類あります。", i, count[i]);
            }
        }
    }
}

 結果は以下のとおり:

     
プライバシーポリシー お問い合わせ