果树问题讨论:这两个问题等价么？

mathe

通过射影变换以后得到的方程都是一些关于坐标的二次方程组。实际手工计算结果表明，对于大部分的这些方程组，可以用一种相对简单的方法得出这个方程的解（或得出方程组无解的结论）。如果我们能够让计算机都采用这个方法先处理这些方程组，然后只输出那些不能处理的表达式，那么估计余下的情况会非常少。 只是这个计算方法用C语言写有点复杂，不知道谁是否有兴趣做一下。 下面用例子来说明计算方法: 比如对于例子 ABCD AEFI AGJK BEJL BGMN CFMO CIKN DJNO DKLM EHKO FHLN GILO HIJM 我们首先可以建立仿射坐标系: A=(0,1) B=(1,0), D=(1,D_y,0) E=(E_x,0) G=(0,G_y) J=(0,0) K=(0,1,0) L=(1,0,0) M=(1,M_y,0) 也就是直线DKLM投影到无穷远，然后取J为原点JB为横坐标单位长度，JA为纵坐标单位长度 首先计算机可以找出一些最简单的表达式，直接可以将一个变量用常数或另外一个变量代替: -1*D_Y-1 +1*M_Y+1*G_Y -1*I_X+1*C_X -1*N_X+1*C_X +1*C_X+1*N_Y -1*O_X+1*O_Y -1*H_X+1*E_X +1*O_Y+1*E_X -1*H_Y+1*F_Y -1*N_Y+1*F_Y -1*I_Y+1*G_Y -1*E_X+1*G_Y 经过上面变量替换，余下表达式: +1*F_Y-1+1*C_Y -1*F_X+1*G_Y*F_Y-1*G_Y -1*F_Y-1*G_Y*G_Y-1*G_Y +1*G_Y-1*G_Y*F_Y-1*F_Y -1*G_Y*F_Y-1*G_Y*F_X-1*C_Y+1*F_Y -1*G_Y*F_Y-1*G_Y*G_Y-1*C_Y-1*G_Y -1*G_Y*F_Y-1*G_Y -1*G_Y*G_Y-1*F_Y 需要注意的是，合法的解，要求这些余下的变量都不是0（也就是除了我们事先设置好的点，其他点不会再到坐标轴上） 这里余下的表达式中有两个表达式非常有用，其中之一是 +1*F_Y-1+1*C_Y 因为它是线性的，我们同样可以通过它消除一个变量，而使得所有余下表达式最多还是二次的。 另外一个是 -1*G_Y*F_Y-1*G_Y 这个表达式每一项都有公因子G_Y,由于G_Y不是0，我们可以通过消去G_Y,得到线性表达式 -1*F_Y-1 所以如果我们能够设计一个算法，通过将余下的表达式进行线性组合，而得出上面两类式子中的任何一个，就可以继续化简方程组（消去一些变量） 而这个我们可以通过将上面的这些表达式每一项根据所含未知数进行分类，写成一个矩阵，所有未知数相同的项写在矩阵的同一列。

1	F_Y	C_Y	F_X	G_Y*F_Y	G_Y	G_Y*G_Y	G_Y*F_X
-1	1	1
			-1	1	-1
	-1				-1	-1
	-1			-1	1
	1	-1		-1			-1
		-1		-1	-1	-1
				-1	-1
	-1					-1

然后比如我们要产生一些只包含一次项和常数项的表达式，那么可以将这些项看成常数，其他项看成变量使用高斯消元法进行消元（也就是高斯消元法时避开这些列） 比如我们可以先选择G_Y*F_X列，这个列只有一项非0，所以不会消去任何东西。然后选择G_Y*G_Y列，我们可以使用第三行消去第六和第八行中的G_Y*F_X项，得到:

1	F_Y	C_Y	F_X	G_Y*F_Y	G_Y	G_Y*G_Y	G_Y*F_X
	1	-1		-1			-1
-1	1	1
			-1	1	-1
	-1				-1	-1
	-1			-1	1
	1	-1		-1
				-1	-1
					1

(这时已经可以看出没有非零解了，因为根据最后一行G_Y只能等于0),同样类似，此后我们还可以对G_Y*F_Y这一列采用相同的方法，这样就可以余下尽量多的线性的表达式。 同样类似，如果我们要产生像第二种情况的表达式，比如我们需要产生一个所有项都包含F_Y因子的表达式，我们可以在消元过程避开所有包含F_Y因子的列，即F_Y和G_Y*F_Y列，所以我们先可以对常数项对应的第一项消元，由于这一列只有一个非零数，可以跳过去，然后查看C_Y这一列，消元得到

1	F_Y	C_Y	F_X	G_Y*F_Y	G_Y	G_Y*G_Y	G_Y*F_X
-1	1			-1			-1
	1	-1		-1			-1
			-1	1	-1
	-1				-1	-1
	-1			-1	1
					-1	-1	1
				-1	-1
	-1					-1

然后接下去式F_x这一列，只有一个非零数跳过，然后看G_Y这一列，消元得到

1	F_Y	C_Y	F_X	G_Y*F_Y	G_Y	G_Y*G_Y	G_Y*F_X
-1	1			-1			-1
	1	-1		-1			-1
	1		-1	1		1
	-1				-1	-1
	-2			-1		-1
	1						1
	1			-1		1
	-1					-1

然后消G_Y*G_Y这一列得到:

1	F_Y	C_Y	F_X	G_Y*F_Y	G_Y	G_Y*G_Y	G_Y*F_X
-1	1			-1			-1
	1	-1		-1			-1
	-1		-1
	1			1	-1
	-2			-1		-1
	1						1
	-1			-2
	1			1

最后消G_Y*F_Y这一列得到

1	F_Y	C_Y	F_X	G_Y*F_Y	G_Y	G_Y*G_Y	G_Y*F_X
-1	2			-1
	2	-1		-1
	-1		-1
	1			1	-1
	-2			-1		-1
	1						1
	-1			-2
	1			1

最后我们可以得到两个所有项都包含F_Y因子的表达式 -1*F_Y-2*G_Y*F_Y=0 1*F_Y+G_Y*F_Y=0 从它们分别得出 -1-2*G_Y=0 1+G_Y=0 当然也得出无解

没——问题

哈 我来啦 mathe写了这么多 我看看

0→∞

找你真难........

无心人

不明白仿射变换看他的叙述白搭 呵呵 看来要看几本高等几何的书

没——问题

膜拜一下诸位 我当时的方案与mathe完全一致 但做到该写mahte所说的方程处理程序时停下了。因为感觉自己写不出高效的东西（虽然我不认为这个方程处理程序很复杂）。包括之前写的生成问题2的解的程序效率也很低。而且，觉得这个方案，面对24条线时，还是感觉很无力。（或许是我太无力 ） 我各方面的能力都太差了，期待mathe等高手的新进展。

mathe

我现在的程序在点的数目达到16以上就处理不了了（主要是中间结果太多），而我的程序要产生所有不等价的最终结果，这个数目也会随着n的增加而快速增加。 所以点的数目比较大的时，可能通过随机产生一些问题二的数据，然后用计算机检验是否合法来产生下界数据可能更加有效一些。没一一问题产生20个点24条直线的数据的程序能够贴上来吗？我想看看能否直接让maxima来处理判断。

没——问题

说过了我那个效率很低..... 只是一个深度优先搜索，在所以排列组合的情况中搜，搜到符合条件就输出 我当时运行一个多小时也没找到25条直线的解，而zgg找到28的 非常想知道zgg是怎么构造的，或许他的方法对你也有帮助 当然，如果前辈一定要看我那堆烂代码，稍后贴上就是（我自己都快看不懂它了）

没——问题

1. #include <stdio.h>
2. #include <iostream.h>
3. #define N 60+20
4. struct sd
5. {
6. long int father;
7. int brother;
8. int me;
9. char str[4];
10. }date[2147483647];// ^Q^
11. int line_num,point_num=0;
12. char line_list[24][4],n_free[20],y_free[20];
14. int main(int argc, char *argv[])
15. {
16. long int end_line=0,i,now_line=0,e;
17. int j,k,max,m,f,n,y,x,c,a,b,d,w;
18. FILE* f_out;
19. f_out=fopen("d:\\date_out.txt","w");
20. date[end_line].father=-1;
21. for(w=0;w<4;w++)
22. line_list[0][w]=date[end_line].str[w]='A'+w;
24. for(now_line=0;;)
25. {
26. for(i=now_line,j=1;i>0;j++)
27. {
28. for(k=0;k<4;k++)line_list[j][k]=date[i].str[k];
29. i=date[i].father;
30. }
31. line_num=j;
32. for(m=0,point_num=0;m<line_num;m++)for(j=0;j<4;j++)
33. {
34. max=line_list[m][j];
35. if(max>point_num)point_num=max;
36. }
37. for(k=point_num,f=0,n=0,y=0;k>64;k--)
38. {
39. for(m=0;m<line_num;m++)for(j=0;j<4;j++)
40. if(k==line_list[m][j])f++;
41. if(f>1)f=0,n_free[n]=k,n++;
42. if(f==1)f=0,y_free[y]=k,y++;
43. }
44. for(m=0;m<line_num;m++)for(j=0;j<4;j++)for(k=0;k<y;k++)
45. if(y_free[k]==line_list[m][j]){
46. n_free[n]=y_free[k];
47. n++;
48. k=y;
49. j=4;
50. }
51. e=end_line+1,d=0;
52. for(x=4;x>=0;x--)//搜索下一层//囧现在是从4到0，如果从0到4...
53. {
54. j=point_num;
55. switch(x)
56. {
57. case 0:
58. if((point_num-x<=N)&&(x<=n))
59. {
60. date[++end_line].father=now_line;
61. for(w=0;w<4;w++)
62. date[end_line].str[w]=++j;
63. date[end_line].me=(++d);
64. }
65. break;
66. case 1:
67. if((point_num-x<=N)&&(x<=n))for(k=0;k<n;k++)
68. {
69. date[++end_line].father=now_line;
70. date[end_line].str[0]=n_free[k];
71. for(w=1;w<4;w++)
72. date[end_line].str[w]=++j;
73. date[end_line].me=(++d);
74. j=point_num;
75. }
76. break;
77. case 2:
78. if((point_num-x<=N)&&(x<=n))for(k=0,c=0;k<n-1;k++)for(m=k+1;m<n;m++)
79. {
80. for(y=0;y<line_num;y++)
81. {
82. for(f=0;f<4;f++)
83. if(n_free[k]==line_list[y][f]||n_free[m]==line_list[y][f])
84. c++;
85. if(c>1)
86. y=line_num;
87. else
88. c=0;
89. }
90. if(c>1)
91. c=0;
92. else{
93. date[++end_line].father=now_line;
94. date[end_line].str[0]=n_free[k];
95. date[end_line].str[1]=n_free[m];
96. date[end_line].str[2]=++j;
97. date[end_line].str[3]=++j;
98. date[end_line].me=(++d);
99. j=point_num;
100. }
101. }
102. break;
103. case 3:
104. if((point_num-x<=N)&&(x<=n))for(k=0,c=0;k<n-2;k++)for(m=k+1;m<n-1;m++)for(a=m+1;a<n;a++)
105. {
106. for(y=0;y<line_num;y++)
107. {
108. for(f=0;f<4;f++)
109. if(n_free[k]==line_list[y][f]||n_free[m]==line_list[y][f]||n_free[a]==line_list[y][f])c++;
110. if(c>1)
111. y=line_num;
112. else
113. c=0;
114. }
115. if(c>1)
116. c=0;
117. else{
118. date[++end_line].father=now_line;
119. date[end_line].str[0]=n_free[k];
120. date[end_line].str[1]=n_free[m];
121. date[end_line].str[2]=n_free[a];
122. date[end_line].str[3]=++j;
123. date[end_line].me=(++d);
124. j=point_num;
125. }
126. }
127. break;
128. case 4:
129. if((point_num-x<=N)&&(x<=n))for(k=0,c=0;k<n-3;k++)for(m=k+1;m<n-2;m++)for(a=m+1;a<n-1;a++)for(b=a+1;b<n;b++)
130. {
131. for(y=0;y<line_num;y++)
132. {
133. for(f=0;f<4;f++)
134. if(n_free[k]==line_list[y][f]||n_free[m]==line_list[y][f]||n_free[a]==line_list[y][f]||n_free[b]==line_list[y][f])c++;
135. if(c>1)
136. y=line_num;
137. else
138. c=0;
139. }
140. if(c>1)
141. c=0;
142. else{
143. date[++end_line].father=now_line;
144. date[end_line].str[0]=n_free[k];
145. date[end_line].str[1]=n_free[m];
146. date[end_line].str[2]=n_free[a];
147. date[end_line].str[3]=n_free[b];
148. date[end_line].me=(++d);
149. }
150. }
151. break;
152. }
153. }
154. for(i=e;i<=end_line;i++)
155. date[i].brother=date[end_line].me;
156. if(d==0)
157. {
158. while(date[now_line].me==date[now_line].brother)
159. now_line=date[now_line].father;
160. now_line++;
161. end_line=now_line+(date[now_line].brother-date[now_line].me);
162. d=1;
163. if(now_line==1)
164. exit(0);
165. }
166. else
167. now_line=e;
168. if(line_num>23)//输出符合条件的解
169. {
170. for(y=0;y<line_num;y++)
171. {
172. for(f=0;f<4;f++)
173. fprintf(f_out,"%c",line_list[y][f]);//输出到文件
174. fprintf(f_out," ");
175. }
176. fprintf(f_out,"\n");
177. // cout<<line_num<<' ';
178. // if(line_num>24)break;//找到大于24的解就退出
179. }
180. }
181. return 0;
182. }
183. /*************************************************************
184. /*第03行‘#define N 60+20’处的20表示最大点数，可更改
185. /*第97行‘if(line_num>24)’处的line_num表示线的条数，条件可更改
186. /*

复制代码

没——问题

。。。。。。。

0→∞

59楼什么意思？