«

»

19

化学方程式配平

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

 源代码下载地址:http://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:

问题还是相当多的:

  1. 有些特别复杂的方程式会出错(八成是字符串解析的问题,没啥技术,暂时不想耗费时间修改了)
  2. 不支持有机化学(同上)
  3. 某些形式特殊的方程式也会出错(比如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语言吧的精品里看到过关于这个的讨论,里面总结了只有在系统 资源不足无法正常工作时才会出现这种情况(我觉得人为地拦截也有可能,几率很小而已),所以由此引发的问题并不是我的程序的错误,则不作处理。

3 comments

  1. Extreme

    一定要支持下算法作品!Naylon牛开始研究算法了~膜拜!

    [回复]

  2. Clarkok

    啊啊,WolframAlpha毫无压力。不过话说这写成代码果然需要技术

    [回复]

  3. Aslan

    Alaiazaam-informatkon found, problem solved, thanks!

    [回复]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>