等分正方形边长形成的交点数和区域数

iseemu2009

求正方形边长 n 等分后形成的交点数和区域数

王守恩

交点是这样一串数——有37, 257垫底, 再找来个5——A331449——可惜还没有通项公式。
5, 37, 257, 817, 2757, 4825, 12293, 19241, 33549, 49577, 87685, 101981, 178465, 220113, 286357, 379097, 551669, 606241, 880293, 951445, 1209049, 1507521,

区域是这样一串数——有56, 340垫底, 再找来个4——A255011——可惜还没有通项公式。
4, 56, 340, 1120, 3264, 6264, 13968, 22904, 38748, 58256, 95656, 120960, 192636, 246824, 323560, 425408, 587964, 682296, 932996, 1061232, 1327524, 1634488,

iseemu2009

王守恩 发表于 2025-4-14 16:33
交点是这样一串数——有37, 257垫底, 再找来个5——A331449——可惜还没有通项公式。
5, 37, 257, 817, 275 ...

表中的相关数据不够长，虽没有通项公式，能单独计算边长100等分时的交点数和区域数吗？

iseemu2009

iseemu2009 发表于 2025-4-14 16:36
表中的相关数据不够长，虽没有通项公式，能单独计算边长100等分时的交点数和区域数吗？ ...

iseemu2009

表中计算到了三十六项，按理说当n>3时计数就很困难了，他们难道是对每个1<n<36是挨个画图数出来的吗？我想的是，没有通项公式，但对特殊的n，有单个的计算方法。

mathe

这个题目4n个点连接的线段数目不超过12n^2条，每两条直线交点坐标是有理数，显然这样数目不超过144n^4个，对所有这些交点排序即可获得答案。现在这样的算法在现有计算机水平达到n到100左右是不困难的

iseemu2009

问题的关键是，内部有些点是k条对角线的交点，这个k可以是2、3、4….，如何给出一个算法判断哪些线段可以交于一点是解决本问题的关键。目前世界上还没有找到这个判断法，所以用计算机编程来算交点数实现不了，进而无法求出分割的区域数。

aimisiyou

iseemu2009 发表于 2025-4-14 21:17
问题的关键是，内部有些点是k条对角线的交点，这个k可以是2、3、4….，如何给出一个算法判断哪些线段可以交 ...

暴力搜

iseemu2009

aimisiyou 发表于 2025-4-15 08:30
暴力搜

代码发出来看一看？

iseemu2009

正方形边长2等分形成的交点数和区域数