论坛 › 编程擂台 › 计算一个数，呵呵。

zgg___ 发表于 2007-12-27 16:49:15

计算一个数，呵呵。

这个问题来自智星，恰好过了整整的一年，真是光阴似箭，人都变老了。问题如下：
我们将采取下面的步骤来在一个平面内画出一些点和直线。第一步，我们选取平面上的4个点，这4个点之间不存在任何的特殊的位置关系（它们不共线，不共圆，不构成平行四边形的顶点……）；第二步，过上一步的4个点做所有能做的直线，我们将得到6条直线，我们叫做4点生6线；第三步，上一步得到的6条直线共有 7个交点，于是我们称之为6线生7点；第四步，7点生9线；第五步，9线生13点……这样我们可以得到一个数列，类似于：4，6，7，9，13，25…… 的样子，问这个数列的第10项是什么？

mathe 发表于 2007-12-27 17:27:18

挺有意思，不过好像递增速度不快，为什么只要求计算第10项，是不是后面增加的很快？:loveliness:

dean_cn 发表于 2007-12-27 17:29:49

:hug: 6线怎么有7点

mathe 发表于 2007-12-27 17:54:37

四条边的延长线有两个交点。

zgg___ 发表于 2007-12-28 17:29:33

是的，数列在后面就递增的较快了。
这个问题带有射影几何的味道，另一方面，和矢量叉乘的那种分配性也可能相关。（这纯粹是联想，呵呵）
还记得那道过空间一点许多直线，每个直线都有100个垂线的问题么，这个问题就是在看了那个问题之后杜撰的。

mathe 发表于 2007-12-28 18:38:03

是的，很显然可以转化为对偶问题，也就是点线可以互换。
其实也可以用集合和元素的关系来描述

mathe 发表于 2007-12-28 18:48:17

<PRE>考虑一个思路，首先我们给出下面一个4×6的矩阵（空格代表0）
1       1   1
1               1   1
    1   1       1
    1       1       1
显然矩阵行的数目就是数列第一项，列的数目是数列的第二项
接下去我们查看任何两列之间如果没有公共元素，我们就添加一行，这一行只有那两列有数据1得到：
1       1   1
1               1   1
    1   1       1
    1       1       1
1   1
            1   1
      1         1
可以得到一个7×6的矩阵
7就是数列下一项
而下一步查看每两行之间，如果哪两行没有公共元素，就添加一列，只有这两行对应位置有数字:
1       1   1
1               1   1
    1   1       1
    1       1       1
1   1                   1       1
            1   1       1   1
      1         1       1   1
可以得到一个7×9的矩阵
呵呵，转化成这样一个问题应该更加容易分析了</PRE>

mathe 发表于 2007-12-29 09:29:55

弄错了，上面的问题不等价，最多只能给出一个上界

mathe 发表于 2007-12-29 10:24:35

射影几何里面有个定理:
如果两个三角形对应顶点的连线交于一点，那么它们对应边（包括延长线）的交点（如果存在）必然三点共线。
同样逆命题也成立（逆命题就是它的对偶命题，所以从射影几何的角度，证明了一个命题，另外一个命题自然成立）。

很显然，使用这个定理，我们可以找到很多三点共线和三线共点的情况。只是这个用计算机来搜索，好像复杂度挺高的，比较难做。
而我上面那个上界问题，显然容易解决多了，只牵涉到一些稀疏矩阵两行交和两列交运算

查看完整版本: 计算一个数，呵呵。