论坛 › 难题征解 › 果树问题讨论:这两个问题等价么？

无心人 发表于 2008-8-15 16:43:02

呵呵
学好C语言不一定能学会写这些数学计算程序
数据结构，算法，技巧，优化等都要学习
甚至要学一种汇编语言
另外，还可能要明白linux怎么用
好多大型计算程序仅有linux版本

你照mathe懂的努力就可以了

mathe 发表于 2008-8-18 09:57:18

现在终于写C++程序实现了51#所说的功能。
通过这个程序，可以证明n=13时候10条直线无解，所以只能最多9条。
同样，在n=14的时候，程序过虑结果是11条直线只余下一个结果:
ABCD AEFM AGHN BEIN BJKM CFJN CGLM DHIM DKLN EHJL FGIK

solve([+1+1*M_Y+1/2*M_Y*M_Y],)
+1*L_X+1/2*M_Y
-2+1*L_Y-1*M_Y
-2+1*K_Y
+1*J_X+1*M_Y
+1+1*K_X+1*M_Y
-1+1*I_X-1*M_Y
-1+1*F_Y-1*M_Y
-2+1*D_Y-2*M_Y
-1+1*C_Y-1*M_Y
-2+1*J_Y-1*M_Y
-2+1*H_Y-1*M_Y
-1+1*D_X
-1+1*C_X
A=(0,1,0) B_x=1 B_y=0 E=(1,0,0) F=(1,F_y,0) G_x=0 G_y=1 H_x=0 I_y=0 M=(1,M_y,0) N_x=0 N_y=0

其中余下的二次方程:
solve([+1+1*M_Y+1/2*M_Y*M_Y],)
显然没有实数解，所以证明了n=14时最多10条直线。
n=14对应的10条直线可以有解:
ABDEAFGHBIJNCDIKCFLNDGMNEFJMEHKNGJKLHILM

-3/4+1*L_X
-1/4+1*M_X
+2+1*N_Y
+1/2+1*M_Y
-2+1*H_Y
-1/2+1*L_Y
-1/2+1*I_X
+1/4+1*G_X
-3/2+1*F_Y
-1+1*B_Y
-1/2+1*J_Y
-1/2+1*G_Y
-1/4+1*J_X
-1/4+1*F_X
A_x=0 A_y=1 B_x=0 C_x=1 C_y=0 D_x=0 D_y=0 E=(0,1,0) H=(1,H_y,0) I_y=0 K=(1,0,0) N=(1,N_y,0)
这个图我还没有画出来，不知道是否是合理的解

mathe 发表于 2008-8-18 09:59:10

上面的例子显然不行，有重复点（A和B坐标相同），使用另外一个例子可以得到结果:
-3/4+1*L_X
-1/4+1*M_X
-2/3+1*N_Y
-1/6+1*M_Y
+2/3+1*H_Y
+1/6+1*L_Y
-1/2+1*I_X
-5/4+1*F_X
-1/2+1*G_Y
+1/3+1*B_Y
-1/6+1*J_Y
-1/6+1*F_Y
-3/4+1*J_X
-3/4+1*G_X
A_x=0 A_y=1 B_x=0 C_x=1 C_y=0 D_x=0 D_y=0 E=(0,1,0) H=(1,H_y,0) I_y=0 K=(1,0,0) N=(1,N_y,0)

mathe 发表于 2008-8-18 10:20:48

n=15时，13条直线所有581种情况程序过滤后只余下一种情况:
ABCIADJKAELMBEJNBFLOCEKOCGMNDFGIDHNOFHKMGHJLIJMOIKLN

solve([+1+1*O_Y+1*O_Y*O_Y],)
+1+1*G_X
-1+1*M_Y-1*O_Y
+1+1*M_X+1*O_Y
-1+1*F_Y-2*O_Y
+1*O_X+1*O_Y
+1+1*L_Y+1*O_Y
-1+1*G_Y-1*O_Y
+1*H_Y-1*O_Y
+1*D_Y-1*O_Y
+1+1*H_X+1*O_Y
+1+1*F_X+1*O_Y
+1*C_X+1*O_Y
+1+1*I_Y
+1*E_X+1*O_Y
-1+1*C_Y-1*O_Y
A_x=0 A_y=1 B_x=1 B_y=0 D_x=0 E_y=0 I=(1,I_y,0) J_x=0 J_y=0 K=(0,1,0) L=(1,L_y,0) N=(1,0,0)
其中，方程：
solve([+1+1*O_Y+1*O_Y*O_Y],)
显然也没有实数解。
所以对于n=15,我们也证明了最多12条直线,这个也是walframe给出的下界。具体构造我先不给出了，等到加强一下程序（比如会出现重复点的情况也先让计算机淘汰了再说）

mathe 发表于 2008-8-18 10:24:59

n=16时，我前面的程序只产生了所有大于等于17条直线的模板，总数很少，才13种，全部无解，所以我们证明了对于n=16,最多16条直线，wolfram给出16个点时下界为15，所以我们知道16个点时，最多15或16条直线。

mathe 发表于 2008-8-18 10:29:13

不过$n>=17$时，我的程序已经不能产生所有的直线模板了（由于2G文件大小的限制）。

0→∞ 发表于 2008-8-18 10:51:32

不能使用两个文件么？

0→∞ 发表于 2008-8-18 11:02:57

数据不能随时产生随时处理么？（牺牲时间换取空间）

mathe 发表于 2008-8-18 11:44:44

当然可以，不过那样又要修改代码了。暂时还没有时间考虑这个问题。
不过现在感觉我那个解方程的代码有memory leak,运行一段时间后程序会out of memory.

无心人 发表于 2008-8-18 12:46:04

呵呵
你把磁盘分区改成NTFS就能支持4G文件了

查看完整版本: 果树问题讨论:这两个问题等价么？