数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[原创] 来点复杂的吧

[复制链接]
 楼主| 发表于 2009-2-19 10:46:28 | 显示全部楼层
能不能用构造法??

先取直线1,然后取2,3
依次的画,直到遇到相交
则判断是非法的解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-19 10:55:32 | 显示全部楼层
同样对于常数项所在列就是columnid[0][0]
对于变量v一次项所在的列就是columnid[0][v]或columnid[v][0].

变量_matrix是系数矩阵,每一行是一条方程,表示这些项乘上对应系数后和必须为0.
而变量_valid如果被置成false就表示方程没有符合果树问题的解.

由于计算过程中会出现很多二次项所有系数都是0,为了提高速度,这些项没有必要保留,所以我提供了一个
left_column数组和lc变量,来收集那些对应列至少有一个非0数据的列(列的编号)
只是现在每次更新它们都要完全扫描一次,其实效率不高.

方程求解过程就是通过高斯消元法构造一些所有非0项都是存在某个变量v的方程.
比如如果我们构造出方程
a*v+b*v1*v+c*v2*v+d*v*v=0
由于所有这些变量必须非0(问题几何意义的要求),
我们可以得到线性关系
a+b*v1+c*v2+d*v=0,从而得到一个线性关系而可以消除一些变量.
由此我们需要一下一些变量来保存一些数据
_t表示所有的方程数目
_m表示所有余下的二次方程(在_matrix前_m行)
而_matrix后_t-_m行由来保存那些已经找到的线性关系.
为此我们需要两个辅助信息row_var和row_evar
其中像上面的关系,其中row_var里面就保存了变量v的编号,也就是这一行中,每一项都可以忽略掉一个v从而形成一个线性组合.
而row_evar表示我们得到这个线性关系后,从前_m中消除的变量的编号.
比如我们得到上面的线性关系后,就可以消除变量v1,于是对应的row_evar就是v1,而这时候前_m行中所有用掉的变量v1就需要全部被消除.

而最后函数simplify_result()中判断一些特殊情况,比如余下只有一条二次方程是一个二次型,那么我们可以判断二次型的$\Delta$是否不小于0来判断是否有实数解.如果没有实数解也可以淘汰.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-19 10:55:45 | 显示全部楼层
拓扑变换有否能判定两点必然在一条直线两边的算法么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-19 10:57:33 | 显示全部楼层
原帖由 无心人 于 2009-2-19 10:35 发表


只看到极端复杂, 呵呵
有否能转化成一个小矩阵,按照矩阵运算处理的思路

比如按18个字母的18 * 14的矩阵
以0, 1表示


7楼的基本就是矩阵元算,几乎是全线性的,不过里面元素不仅仅0,1,而是可能出现有理数,所以我使用了gmp中的有理数来表示
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-20 16:06:02 | 显示全部楼层
Windows版本的,带编译后的程序(不过不带测试数据)

files.zip

127.4 KB, 下载次数: 2, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-20 16:17:10 | 显示全部楼层
需要GMP的DLL??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-20 17:15:17 | 显示全部楼层
一个机房一个月大概是150小时
即7500机时
每机时能计算5个
一个月大概是37500个
==================
呵呵,似乎我在短消息里的说错了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-20 17:42:37 | 显示全部楼层
原帖由 无心人 于 2009-2-20 16:17 发表
需要GMP的DLL??

我静态链接了,不需要DLL
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-20 17:44:26 | 显示全部楼层
我现在将一半的输入数据存放在csdn中了:
http://mathe.download.csdn.net/
有兴趣(也有空闲cpu时间)的朋友也可以自己下载下去帮忙运行部分数据.
当然对于大部分情况,输出是空的.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-20 21:18:01 | 显示全部楼层
呵呵

mathe给我的windows程序可能不如我重新编译的好
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-1-18 03:37 , Processed in 0.060599 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表