N×N的方格，里面有多少个长方形？

chyanog · 发表于 2013-3-3 16:02:26

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

正方形也算矩形，

wayne · 发表于 2013-3-3 22:15:03

http://oeis.org/A085582
谁能给出个高效的计数方法

chyanog · 发表于 2013-3-3 22:50:55

http://oeis.org/A052149

chyanog · 发表于 2013-3-4 00:17:03

不妨再进一步，空间里n×n×n的立方体是什么情况？

无心人 · 发表于 2013-3-15 21:58:15

这个问题偶想到个好法子计数

无心人 · 发表于 2013-3-15 22:03:59

先定义函数，计算mXn的矩形中，所有以左下角的顶点为左下顶点的矩形的个数，
正好是矩形内部的点，加矩形上，右边上不包含顶点的点，加上右上顶点的个数
let b m n = if m > n then (b n m) else if m <= 0 then 0 else (m-1)*(n-1)+(m-1)+(n-1) + 1

无心人 · 发表于 2013-3-15 22:11:51

然后针对所有非上边，非右边的点，计算这个函数的和

下面函数，计算所有以(0, 0)为左下顶点，非负整数对(x, y)做右上顶点的组成的矩形中，所有格点组成的矩形的个数和

let f x y = if x > y then (f y x) else if x <= 0 then 0 else (sum [s|x0<-[0..x-1], y0<-[0..y-1], let s = b (x-x0) (y-y0)])

无心人 · 发表于 2013-3-15 22:12:19

Prelude> f 1 1
1
Prelude> f 2 2
9

无心人 · 发表于 2013-3-15 22:14:32

Prelude> f 3 3
36
Prelude> f 4 4
100
Prelude> f 3 4
60

其实，边长分别为$x$, $y$的矩形中，格点做定点，且边平行于四个边的矩形个数等于
${xy(x+1)(y+1)}/4$

无心人 · 发表于 2013-3-15 22:23:29

然后是边非平行于坐标轴的点
考虑以矩形内的一个点为坐标原点，且为矩形左下点，第二象限上点为左上点的直线，
斜率$k = - k_1/k_2$

对应垂直于该直线的斜率是$k_2/k_1$

账号		自动登录	找回密码
密码			欢迎注册

[提问] N×N的方格，里面有多少个长方形？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。