化学方程式配平

最近学了点数学知识，况且考虑到算法一直是自己的弱项，就写了这个来练习一下……（同时也是受到了XiaoJ的启发）

源代码下载地址：https://naylon.0ginr.com/download/ChemicalEquation.rar

Before：

上百度百科查了一下，化学方程式配平大概有以下几种方法：

1-最小公倍数法

2-观察法

3-奇偶配平法

4-待定系数法

5-化合价法

大概看了看，如果要让计算机求解，4自是最好的选择，可以编写算法，于是选4下手。

PART0：Example

先举个配平的例子，就用H2+O2=H2O吧，比较简单：

先设系数分别为X0, X1, X2，得

X0 H2 + X1 O2 = X2 H2O

于是可得方程组

2X0 = 2X2

2X1 = X2

显然，这样的方程组难以求解，于是设系数X0为1，可得

-2X2 = -2

2X1 – X2 = 0

这样就把配平的问题转化成了解n元线性方程组的问题，接下来就是直观的问题了：如何解？考虑到不同的方程式可能有n个未知数，所以要找一种通用的解n元线性方程组的方法。于是我使用了矩阵行列式的方法（关于行列式的具体内容可以参考附带的ppt，内容较多，不再阐述）。

接上，可得行列式

D = 0 * (-1) – (-2) * 2 = 4

D1 = (-2) * (-1) – (-2) * 0 = 2

D2 = 0 * 0 – (-2) * 2 = 4

于是得解

X0 = 1 (我们自己设的)

X1 = D1 / D = 2 / 4 = 1 / 2

X2 = D2 / D = 4 / 4 = 1

化成整数

X0 = 2

X1 = 1

X2 = 2

正解：2H2+O2=2H2O

PART1：全排列

首先要编写算法求n阶行列式的解，如果是1<=n<=3的话，还可以使用对角线法则，可是n阶的话就要找出行列式的规律，学习了一下附带的ppt，可以看到关键的一页：

“所有不同的三级排列j1j2j3求和”，说明如果要解n阶行列式就需要用到1-n个数的全排列，然后逐一代入上述公式即可得解。

本来以为生成1-n的全排列很容易，打算几分钟搞定，可是实际一尝试才发现没那么简单（算法水平太菜了），上网COPY了一段倒是很好使，不过没注释没说明看不懂，还是想自己原创一种方法，所以不决定采用网上的代码。当日未能得解，很郁闷。于是睡觉之前就一直想该如何实现。果然找到了好方法，跟网上流传的不太一样，暂称之为“插入法”。

插入法的思想是什么呢？

比如1的全排列就是1。1个数。

2的全排列有12，21。2个数。

3的全排列有123，132，213，231，312，321。6个数。

(n的全排列数列一共有n!个)

我就想啊，如果由1阶上升为2阶，2有2个位置可以插入，分别为1的左侧、右侧，可以分别得到21，12。

如果由2阶上升为3阶，那么，针对21，3有3个位置可以插入，可以得到321，231，213；针对12，3也有3个位置可以插入，可以得到312，132，123。.

如果由n-1阶上升为n阶，那么，对于每个n-1阶的全排列数列，n有n个位置可以插入，可以得到n的所有全排列数列。

显然，这种方法可以用一个递归来解决。实现代码如下：

// 插入法核心递归函数
void p_insert_perm(unsigned char m, unsigned char *flist)
{
    unsigned char i = 1;
    unsigned char *list = (unsigned char*)malloc(m + 1);
    memcpy(&list[1], flist, m – 1);
    list[0] = m;
    do {
        if (m < g_n) {
            p_insert_perm(m + 1, list);
        } else {
            add_record(list);
        }
        swap((char*)&list[i – 1], (char*)&list[i]);
    } while (++i <= m);
    free(list);
    return;
}

// 使用插入法生成全排列表
void insert_perm(unsigned char n)
{
    g_n = n;
    g_i = 0;
    unsigned char *list = (unsigned char*)malloc(2);
    list[0] = 1;

p_insert_perm(2, list);

free(list);
}

测试了一下效果还是不错的，效率跟网上的代码也差不多，算是解决了全排列问题。

PART2：SolveDeterminant

这个就简单多了，只要按照全排列数列对系数矩阵进行乘、加运算就行了。

首先定义了一个全排列数列数组，代码如下：

unsigned char **perm_list = 0;

long solve_det(char *det, unsigned char n)
{
    unsigned long i = 0;
    long k = 1, count = 0;
    unsigned char j = 0, m = 0;

    for (; i < g_amount; i++) {
        for (k = 1, j = 0; j < n; j++) {
            m = *(unsigned char*)((unsigned char*)perm_list[i] + j);
            k = k * det[j * n + m – 1];
        }
        if (k != 0) {
            k = is_even_array(perm_list[i], n)? k: k * (-1);
            count = count + k;
        }
    }

return count;
}

PART3：StringAnalyze

字符串分析……就是把用户输入的方程式的系数提出来转换成系数矩阵，然后进行求解，这段代码相对较长，纯体力活，实在没啥意思，就不贴了，大家自己下载看吧……

Problems：

问题还是相当多的：

有些特别复杂的方程式会出错（八成是字符串解析的问题，没啥技术，暂时不想耗费时间修改了）
不支持有机化学（同上）
某些形式特殊的方程式也会出错（比如KClO3=KCl+O2和CH3COOH+NaCl=HCl+CH3COONa，为啥呢？大家按照我开头给的例子列一下方程组就知道了，有两个式子是相同的，所以无法求得正解）

最近还想研究点别的东西，这个小玩意就先告一段落了，毕竟目的只是为了学习相关知识。CUI十分恶心，兴许暑假时会再完善一下，解决上述问题。

最终效果：

我的文笔真的是相当差……希望各位大牛们不吝赐教~偶只是一只算法菜鸟~数学菜鸟~编程菜鸟……但是我会努力学习的！

[2011.07.06]再谈行列式的求解

嗯，上次弄的化学方程式配平就是用的解行列式的方法。

当时只学到皮毛，看明白了n阶行列式的性质就忙着写代码了，所以是直接通过性质来求解，后来在C语言吧发帖交流，得到了炮姐、良化等人的指点，发现原来这样解是效率最低最挫的…Orz。

于是某日抽空去图书馆，又看了看线代的书，看到了行列式展开，效果貌似很不错，今儿就优化了一下代码。

贴一段关键的，恒按第一行展开，递归咯：

char* get_cofactor(char *det_orginal, unsigned char row, unsigned char line, unsigned char n)
{
    // 将原来的n阶行列式复制到一块新的临时内存里
    char *det = (char*)malloc(n * n);
    memcpy(det, det_orginal, n * n);

// 消去行
memcpy(&det[(row – 1) * n], &det[row * n], (n – row) * n);

    // 消去列
    unsigned char i = 1;
    for (; i <= n; i++) {
        memcpy(&det[(i – 1) * n + line – 1], &det[(i – 1) * n + line], n – line);
    }

    // 得到余子式
    char* cofactor = (char*)malloc((n – 1) * (n – 1));
    for (i = 1; i <= n – 1; i++) {
        memcpy(&cofactor[(i – 1) * (n – 1)], &det[(i – 1) * n], n – 1);
    }

free(det);
return cofactor;
}

long solve_det(char *det, unsigned char n)
{
    if (n == 2) {
        return (det[0] * det[3] – det[1] * det[2]);
    } elseif (n > 2) {
        long S = 0;
        for (unsigned char i = 1; i <= n; i++) {
            char* cofactor = get_cofactor(det, 1, i, n);
            long M = solve_det(cofactor, n – 1);
            long A = ((1 + i) % 2 == 0)? M: -M;
            S += A * det[i – 1];
            free(cofactor);
        }
        return S;
    }

return 0;
}

然后XiaoJ帮忙测试了一下，效率大致比以前快了4倍（本身就大大减少了约1/3的计算量，而且不用生成全排列表，估计阶数越高的话相对来讲会更快）。

XiaoJ 还提出了一个问题，说malloc应该验证一下是否返回NULL，不过我认为不必要，记得在C语言吧的精品里看到过关于这个的讨论，里面总结了只有在系统资源不足无法正常工作时才会出现这种情况（我觉得人为地拦截也有可能，几率很小而已），所以由此引发的问题并不是我的程序的错误，则不作处理。

一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

化学方程式配平

3 comments

发表回复取消回复

近期文章

分类

链接表

化学方程式配平

3 comments

发表回复 取消回复

近期文章

分类

链接表

发表回复取消回复