来点复杂的吧

无心人

能不能用构造法？？ 先取直线1，然后取2，3 依次的画，直到遇到相交 则判断是非法的解

mathe

同样对于常数项所在列就是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来判断是否有实数解.如果没有实数解也可以淘汰.

无心人

拓扑变换有否能判定两点必然在一条直线两边的算法么？

mathe

原帖由 无心人 于 2009-2-19 10:35 发表 只看到极端复杂， 呵呵 有否能转化成一个小矩阵，按照矩阵运算处理的思路 比如按18个字母的18 * 14的矩阵 以0, 1表示

7楼的基本就是矩阵元算,几乎是全线性的,不过里面元素不仅仅0,1,而是可能出现有理数,所以我使用了gmp中的有理数来表示

mathe

Windows版本的,带编译后的程序(不过不带测试数据)

无心人

需要GMP的DLL？？

无心人

一个机房一个月大概是150小时 即7500机时 每机时能计算5个 一个月大概是37500个 ================== 呵呵，似乎我在短消息里的说错了

mathe

原帖由 无心人 于 2009-2-20 16:17 发表 需要GMP的DLL？？

我静态链接了,不需要DLL

mathe

我现在将一半的输入数据存放在csdn中了: http://mathe.download.csdn.net/ 有兴趣(也有空闲cpu时间)的朋友也可以自己下载下去帮忙运行部分数据. 当然对于大部分情况,输出是空的.

无心人

呵呵 mathe给我的windows程序可能不如我重新编译的好