免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 直角三角形个数

QQ截图20190207235351.jpg
2019-2-7 23:54

这个怎么数好,请各位赐教,谢谢
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

回复 15# 青青子衿

TOP

OEIS网站太丰富了
4, 44, 200, 596, 1444, 2960, 5520, 9496, 15332, 23596
http://oeis.org/A077435

TOP

回复 13# isee

没所谓,因为那方法只是理论上如此,实际上没啥用。

TOP

回复 10# kuing


叹为观止,都看不动

TOP

谢谢楼上各位,学习了...
原谅我很久没有来论坛,这一个来月忙飞起来,累坏宝宝了,所以,请原谅我吧

TOP

回复 10# kuing

其实也不需要让 `A` 取遍所有点,因为有对称性,只需取一个角以内即可,以 `n=4` 为例,只需让 `A` 取 `(2,1)` 和 `(2,2)` 即可,算出来分别乘以 `8` 和 `4` 再加起来即可。
所以上面的程序是可以优化一下减少计算的,不过懒得弄了,因为估计也没什么卵用,就算只需算 1/8 的点,这种展开式算法应该都会和上次那个整数分拆一样,时间和空间复杂度会非常高,大数肯定算不动的。

TOP

最近展开式灵感爆棚!我又来了!

考虑一般情况,即点阵为 `n\times m` 的情形,以下默认 `x_i\in\{1,2,\ldots,n\}`, `y_i\in\{1,2,\ldots,m\}`。

首先,直角边平行于坐标轴的个数是 `nm(n-1)(m-1)` 这个就不用我说了吧,下面研究直角边不平行于坐标轴的。

设直角顶点的坐标为 `A(x_0,y_0)`,另外两顶点为 `B(x_1,y_1)`, `C(x_2,y_2)` 且 `k_{AB}>0`, `k_{AC}<0`,即 `(x_1-x_0)(y_1-y_0)>0`, `(x_2-x_0)(y_2-y_0)<0`,要垂直,即 `k_{AB}\cdot k_{AC}=-1`,也即 `(y_1-y_0)/(x_1-x_0)+(x_2-x_0)/(y_2-y_0)=0`,于是,构造
\[f(x_0,y_0)=\left( \sum_{(x_1-x_0)(y_1-y_0)>0}x^{(y_1-y_0)/(x_1-x_0)} \right)\left( \sum_{(x_2-x_0)(y_2-y_0)<0}x^{(x_2-x_0)/(y_2-y_0)} \right),\]
设 `f(x_0,y_0)` 展开式中的常数项为 `c(x_0,y_0)`,那么它就是以 `A(x_0,y_0)` 为直角顶点的直角三角形个数,让 `A` 取遍所有点,然后全加起来就是所求。

综上所述,直角三角形个数就是
\[\sum_{x_0=1}^n\sum_{y_0=1}^mc(x_0,y_0)+nm(n-1)(m-1).\]

另外,为便于软件输入,有必要对 `f(x_0,y_0)` 换个写法,即
\begin{align*}
f(x_0,y_0)={}&\left( \sum_{x_1=1}^{x_0-1}\sum_{y_1=1}^{y_0-1}x^{(y_1-y_0)/(x_1-x_0)}+\sum_{x_1=x_0+1}^n\sum_{y_1=y_0+1}^mx^{(y_1-y_0)/(x_1-x_0)} \right)\\
&\times\left( \sum_{x_2=1}^{x_0-1}\sum_{y_2=y_0+1}^mx^{(x_2-x_0)/(y_2-y_0)}+\sum_{x_2=x_0+1}^n\sum_{y_2=1}^{y_0-1}x^{(x_2-x_0)/(y_2-y_0)} \right).
\end{align*}

这样就得到了 Mathematica 的如下代码:
  1. c[x0_, y0_, n_, m_] :=
  2. Coefficient[
  3.   Expand[(Sum[x^((y1 - y0)/(x1 - x0)), {x1, 1, x0 - 1}, {y1, 1, y0 - 1}] +
  4.       Sum[x^((y1 - y0)/(x1 - x0)), {x1, x0 + 1, n}, {y1, y0 + 1, m}])
  5.       (Sum[x^((x2 - x0)/(y2 - y0)), {x2, 1, x0 - 1}, {y2, y0 + 1, m}] +
  6.       Sum[x^((x2 - x0)/(y2 - y0)), {x2, x0 + 1, n}, {y2, 1, y0 - 1}])], x, 0]
  7. cc[m_, n_] :=
  8. Sum[c[x0, y0, n, m], {x0, 1, n}, {y0, 1, m}] + n m (n - 1) (m - 1)
复制代码
然后输入 cc[4,4] 得到 200,看来没写错

cc[4, 5] 得 342
cc[5, 5] 得 596
cc[6, 6] 得 1444
cc[10, 10] 得 15332
cc[20, 20] 得 337960(用时半分多钟
cc[30, 30] 得 1984564(用时约8分钟

等等……
1

评分人数

    • realnumber: 虽然刚开始看,先点个赞威望 + 1
冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做!(粤语)
口号:珍爱生命,远离考试。

TOP

那就三个问题分开算,
$n\times n$如楼上点阵中,以其中三点为三角形顶点.
1.有几个直角三角形?
2.如果(至少有一顶点不同的)两三角形全等,则视为同一个,则有几个直角三角形?
3.如果两三角形相似,视为同一类三角形,则有几类直角三角形?

TOP

回复 7# realnumber

肯定多得多了……
QQ截图20190211134607.png
2019-2-11 13:48
QQ截图20190211135110.png
2019-2-11 13:51
……
边上两个就眼花了,中间的恐怕更花……
冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做!(粤语)
口号:珍爱生命,远离考试。

TOP

改成$5\times5,6\times6,n\times n$每一次n增大,有没新的直角形要计算的?

TOP

回复  lrh2006
唉,还是最后的漏了,还真不止上图中那一种,还有下图绿线的:
同样也是 16 个,补上就是 ...
kuing 发表于 2019-2-9 22:06

绿色的直角三角形可以用这个恒等式去记忆
\[\tan^{-1}\left(1\right)+\tan^{-1}\left(\frac{1}{2}\right)+\tan^{-1}\left(\frac{1}{3}\right)=\frac{\pi}{2}\]

TOP

回复 4# lrh2006

唉,还是最后的漏了,还真不止上图中那一种,还有下图绿线的:
QQ截图20190208012525.png
2019-2-9 22:05

同样也是 16 个,补上就是 200 了
冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做!(粤语)
口号:珍爱生命,远离考试。

TOP

回复 2# kuing
QQ截图20190210023840.jpg
2019-2-10 02:39

貌似落了几个,哈哈。看到答案,分类方法不一样,给你瞧瞧啊

TOP

回复 2# kuing


    嗯嗯,不服气不行,嘿嘿

TOP

分类数呗
两直角边平行于坐标轴的:由于选定任一直角顶点后,另外两顶点都有三种选择,所以这种共 `4^2\times3^2=144`;
斜边平行于坐标轴的:易知只有当斜边长为 `2` 时才行,由此易数出共 `24` 个;
三边都不平行于坐标轴的:貌似就只有这样的
QQ截图20190208012525.png
2019-2-8 01:25

易数出共 `16` 个。
没有了吧?那就是 `184` 咯
冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做!(粤语)
口号:珍爱生命,远离考试。

TOP

返回列表 回复 发帖