共有回帖数 0 个
-
先贴地址：
技术分析文章：http://hi.baidu.com/naylonslain/blog/item/88375923caadb4e4d6cae246.html
源代码下载地址：http://naylon.0ginr.com/download/ChemicalEquation.rar
如果您关注这个小程序的动态，可以浏览：http://naylon.0ginr.com/?p=15
最近学了点数学知识，况且考虑到算法一直是自己的弱项，就写了这个来练习一下……（同时也是受到了XiaoJ的启发） 源代码下载地址：http://naylon.0ginr.com/download/ChemicalEquation.rar
如果您关注这个小程序的动态，可以浏览：http://naylon.0ginr.com/?p=15
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);
} 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 + j);
k = k * det[j * n + m - 1];
}
if (k != 0) {
k = is_even_array(perm_list, n)? k: k * (-1);
count = count + k;
}
}
return count;
}
PART3：StringAnalyze
字符串分析……就是把用户输入的方程式的系数提出来转换成系数矩阵，然后进行求解，这段代码相对较长，纯体力活，实在没啥意思，就不贴了，大家自己下载看吧……
Problems：
问题还是相当多的：
1、 有些特别复杂的方程式会出错（八成是字符串解析的问题，没啥技术，暂时不想耗费时间修改了）
2、 不支持有机化学（同上）
3、 某些形式特殊的方程式也会出错（比如KClO3=KCl+O2和CH3COOH+NaCl=HCl+CH3COONa，为啥呢？大家按照我开头给的例子列一下方程组就知道了，有两个式子是相同的，所以无法求得正解）
最近还想研究点别的东西，这个小玩意就先告一段落了，毕竟目的只是为了学习相关知识。CUI十分恶心，兴许暑假时会再完善一下，解决上述问题。
最终效果：
我的文笔真的是相当差……希望各位大牛们不吝赐教~偶只是一只算法菜鸟~数学菜鸟~编程菜鸟……但是我会努力学习的！
楼主 2015-11-19 21:08 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
