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

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

正方形也算矩形，

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的立方体是什么情况？
http://my-sort.googlecode.com/files/2013-03-04_001604.jpg

无心人 发表于 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 , y0<-, 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$
页: [1] 2 3 4
查看完整版本: N×N的方格，里面有多少个长方形？