[转载] 植树问题 相关搜索: 果树问题

无心人

http://www.eol.cn/zheng_ming_1877/20060309/t20060309_166193.shtml

数学世界三大难题之20棵树问题新突破  
时间：2006-03-09 作者：王兴君

具体就是20棵树每行4棵，最多多少行

因为下面有声明，不得转载
所以就不转帖了

我有疑问
他上面的图里的23行解法是否严格形成23根直线
我去了Mail要坐标
希望能看到回信

有了解的说下

gxqcn

需要说明的是，他那篇里的图(四)是已有成果，也是通过计算机发现的，
而他却标榜为以自己名字命名的图谱，有点不合适。

补记：
　　对不起，是我记混了，已在 12# 作了说明。

无心人

我怀疑他图5的点不重合

mathe

关于图四的结果，有什么链接吗？
图五我也有点怀疑

无心人

没有

GxQ似乎知道

gogdizzy

我大概算了一下坐标。不过没仔细检验共线。

从上到下，从左到右：


                                                                         $(0,120sqrt(3))$





                  $(-90,90sqrt(3))$             $(-30,90sqrt(3))$              $(30,90sqrt(3))$             $(90,90sqrt(3))$

                                                                $(0,80sqrt(3))$
                                                       $(-15,75sqrt(3))$ $(15,75sqrt(3))$
                                                                $(0,72sqrt(3))$

                        $(-60,60sqrt(3))$         $(-20,60sqrt(3))$          $(20,60sqrt(3))$         $(60,60sqrt(3))$      


                                                    $(-15,45sqrt(3))$      $(15,45sqrt(3))$


                              $(-30,30sqrt(3))$                                                $(30,30sqrt(3))$





         $(-120,0)$                                                 $(0,0)$                                                           $(120,0)$

无心人

要不把23根线都算下共线
也好算
$(x_1 - x_0) // (y_1 - y_0)$

无心人

还是等我给作者发的信回信吧
感觉你说的坐标也不对
18，19，20 可能不在一条直线上

gogdizzy

我算了，好象都没有错^_^

mathe

嗯，结果是正确的（程序对所有点用a~t的字母标号，先从上到下，同一行从左到右）:

1. #include <stdio.h>
   
2. #include <assert.h>
   
3. #include <stdlib.h>
   
4. 
   
5. char lines[][5]={
   
6.     "acjr",
   
7.     "agkp",
   
8.     "afis",
   
9.     "ahlq",
   
10.     "admt",
    
11.     "bcde",
    
12.     "bgim",
    
13.     "bkot",
    
14.     "bjps",
    
15.     "ehij",
    
16.     "elnr",
    
17.     "emqs",
    
18.     "ckns",
    
19.     "dlos",
    
20.     "dikr",
    
21.     "cilt",
    
22.     "dhnp",
    
23.     "cgoq",
    
24.     "dfgj",
    
25.     "cfhm",
    
26.     "jklm",
    
27.     "mopr",
    
28.     "jnqt"
    
29. };
    
30. 
    
31. int x[]={0,-90,-30,30,90,0,-15,15,0,-60,-20,20,60,-15,15,-30,30,-120,0,120};
    
32. int y[]={120,90,90,90,90,80,75,75,72,60,60,60,60,45,45,30,30,0,0,0};
    
33. 
    
34. void check_line(int k)
    
35. {
    
36.     int xx[4],yy[4];
    
37.     int dx,dy;
    
38.     int i;
    
39.     for(i=0;i<4;i++){
    
40.         xx[i]=x[lines[k][i]-'a'];
    
41.         yy[i]=y[lines[k][i]-'a'];
    
42.     }
    
43.     dx=xx[1]-xx[0];
    
44.     dy=yy[1]-yy[0];
    
45.     for(i=1;i<3;i++){
    
46.         int ldx,ldy;
    
47.         ldy=yy[i+1]-yy[i];
    
48.         ldx=xx[i+1]-xx[i];
    
49.         if(ldx*dy!=ldy*dx){
    
50.             fprintf(stderr,"Not a line for %s\n",lines[k]);
    
51.         }
    
52.     }
    
53. }
    
54. 
    
55. int main()
    
56. {
    
57.     int i,j;
    
58.     assert(sizeof(lines)/sizeof(lines[0])==23);
    
59.     assert(sizeof(x)/sizeof(x[0])==20);
    
60.     assert(sizeof(y)/sizeof(y[0])==20);
    
61.     for(i=0;i<23;i++){
    
62.         for(j=i+1;j<23;j++){///Check not same lines
    
63.             int k;
    
64.             for(k=0;k<4;k++){
    
65.                 if(lines[i][k]!=lines[j][k])
    
66.                     break;
    
67.             }
    
68.             if(k==4){
    
69.                 fprintf(stderr,"lines[%d]==lines[%d]=%s\n",i,j,lines[i]);
    
70.                 exit(-1);
    
71.             }
    
72.             for(k=0;k<4;k++){
    
73.                 if(lines[i][k]!=lines[i][3-k])
    
74.                     break;
    
75.             }
    
76.             if(k==4){
    
77.                 fprintf(stderr,"lines[%d]==lines[%d]=%s\n",i,j,lines[i]);
    
78.                 exit(-1);
    
79.             }
    
80.         }
    
81.     }
    
82. 
    
83.     for(i=0;i<23;i++){
    
84.         check_line(i);
    
85.     }
    
86.     return 0;
    
87. }

复制代码