a*****y
发帖数: 1488 | 1 100x100的棋盘，里面有多少个长方形？可以overlap. |
z****n
发帖数: 1379 | 2 长度可以从1到100，宽度可以从1到100，这就有10000种大小的长方形，每种大小的
长方形可以有多种，例如长100，宽99的可以有两种，加一下吧，手算的话可能需要
一些数列公式
【在 a*****y 的大作中提到】
: 100x100的棋盘，里面有多少个长方形？可以overlap.
|
p*****n
发帖数: 368 | 3 C(100, 2)^2?
【在 a*****y 的大作中提到】
: 100x100的棋盘，里面有多少个长方形？可以overlap.
|
P**l
发帖数: 3722 | |
d**e
发帖数: 6098 | 5 这是错的 :)
=====================================
可能比较啰嗦，我的解法如下，请指正。
看成平面是由两顶点(0,0),(100,100)组成的正方形。
假设小长形的左下角顶点由(0,0)开始，底边长a向x方面由1开始增长到100，当a=1时，
另一边长向y方面由1增长到100，但不算正方形，所以一共有99个，所以当一底边在x轴
时，一共有99*100个。同理当一底边在y轴时，也有99*100个,但重复计算了"一边在x轴
另一边在y轴"，所以减去99个。
最后归结为：这个100*100的平面上，至少有一底边在平面边上的长方形一共有
99*100*2-99个
然后再求(1,1)，(100,100)组成的平面拥有的长方形个数，一直到{(99,99),(100,100)
}的平面。
（100，100）是固定点，变的是左下顶点（x,y)，而且x=y。
sum from x=0 to 99 {(99-x)*(100-x)*2-(99-x)}
【在 a*****y 的大作中提到】
: 100x100的棋盘，里面有多少个长方形？可以overlap.
|
a*****y
发帖数: 1488 | 6 第一行：
含有第一个格子的长方形一共有： 100x100
含有第二个格子但不含第一个的有： 100x99
含有第三个格子但不含第一和第二个的有： 100x98
以此类推，含有第一行的总格子数为： 100x(1+2+3...+100) = 100x5050
第二行：
类似，但是 99 x (1+2+3+...100) = 99X5050
以此类推：
(1+2+3...100)^2 = 25502500
这个对吗？ |
a*****y
发帖数: 1488 | 7 按照定义，正方形属于长方形。
如果不算正方形，稍微难一点。
100)
【在 d**e 的大作中提到】
: 这是错的 :)
: =====================================
: 可能比较啰嗦，我的解法如下，请指正。
: 看成平面是由两顶点(0,0),(100,100)组成的正方形。
: 假设小长形的左下角顶点由(0,0)开始，底边长a向x方面由1开始增长到100，当a=1时，
: 另一边长向y方面由1增长到100，但不算正方形，所以一共有99个，所以当一底边在x轴
: 时，一共有99*100个。同理当一底边在y轴时，也有99*100个,但重复计算了"一边在x轴
: 另一边在y轴"，所以减去99个。
: 最后归结为：这个100*100的平面上，至少有一底边在平面边上的长方形一共有
: 99*100*2-99个
|
d**e
发帖数: 6098 | 8 正方形也算的话好像也一样，只是公式变一下。
sum from x = 0 to 99 {(100-x)^2 * 2 - (100 - x)}
但是想知道我的解法对不对。
【在 a*****y 的大作中提到】
: 按照定义，正方形属于长方形。
: 如果不算正方形，稍微难一点。
:
: 100)
|
d**e
发帖数: 6098 | 9 觉得你的解法和我的一样。
不过我没算最后的结果，x太大了，呵呵 :)
【在 a*****y 的大作中提到】
: 第一行：
: 含有第一个格子的长方形一共有： 100x100
: 含有第二个格子但不含第一个的有： 100x99
: 含有第三个格子但不含第一和第二个的有： 100x98
: 以此类推，含有第一行的总格子数为： 100x(1+2+3...+100) = 100x5050
: 第二行：
: 类似，但是 99 x (1+2+3+...100) = 99X5050
: 以此类推：
: (1+2+3...100)^2 = 25502500
: 这个对吗？
|
a*****y
发帖数: 1488 | 10 如果不算正方形，可以这样算。
类似的思路，但只算正方形。
第一行，
含有第一个格子的正方形： 100
含有第二个格子但不含第一个格子的正方形： 99
类推：
第二行
含有第一个格子但不含第一行的： 99
类推：
最后：
如果f(n) = 1+2+...+n
总正方形数：f(1)+f(2)+f(3)...+f(100) = 171700
那100x100的格子里非正方形的长方形一共有
25502500 － 171700 ＝ 25330800
【在 a*****y 的大作中提到】
: 第一行：
: 含有第一个格子的长方形一共有： 100x100
: 含有第二个格子但不含第一个的有： 100x99
: 含有第三个格子但不含第一和第二个的有： 100x98
: 以此类推，含有第一行的总格子数为： 100x(1+2+3...+100) = 100x5050
: 第二行：
: 类似，但是 99 x (1+2+3+...100) = 99X5050
: 以此类推：
: (1+2+3...100)^2 = 25502500
: 这个对吗？
|
|
|
a*****y
发帖数: 1488 | 11 手边有matlab，计算机算啊。
这个面试的时候可以的吧？
【在 d**e 的大作中提到】
: 觉得你的解法和我的一样。
: 不过我没算最后的结果，x太大了，呵呵 :)
|
a*****y
发帖数: 1488 | 12 sum from x = 0-99
(100-x)^2*2-(100-x) = 671650
你这个数比我算的小了很多，我看看哪里错了。
【在 d**e 的大作中提到】
: 正方形也算的话好像也一样，只是公式变一下。
: sum from x = 0 to 99 {(100-x)^2 * 2 - (100 - x)}
: 但是想知道我的解法对不对。
|
d**e
发帖数: 6098 | 13 真的错了，有一步考虑错了，才发现。
让我再想想。
【在 a*****y 的大作中提到】
: sum from x = 0-99
: (100-x)^2*2-(100-x) = 671650
: 你这个数比我算的小了很多，我看看哪里错了。
|
a*****y
发帖数: 1488 | 14 C(100, 2)^2 = 24502500
C(101, 2)^2 =25502500
我算的：25502500
这个C(101,2)^2是怎么想的？
【在 P**l 的大作中提到】
: C(101,2)^2?
|
P**l
发帖数: 3722 | 15 101条边里面选2条当长方形的边
所有长方形都有了
【在 a*****y 的大作中提到】
: C(100, 2)^2 = 24502500
: C(101, 2)^2 =25502500
: 我算的：25502500
: 这个C(101,2)^2是怎么想的？
|
a*****y
发帖数: 1488 | 16 正确答案可能是 C(101,2)^2
选长方形其实可以看成选两个顶点。第一个顶点有 C(101,2) 种选择。 第二个顶点有
C(101,2) 种选择，相乘就可以了。但是两个顶点应该不能是一个点，所以最后应该比
这个小才对。可是为什么是正确的呢？
【在 d**e 的大作中提到】
: 真的错了，有一步考虑错了，才发现。
: 让我再想想。
|
a*****y
发帖数: 1488 | 17 哪里来的101条边？
【在 P**l 的大作中提到】
: 101条边里面选2条当长方形的边
: 所有长方形都有了
|
P**l
发帖数: 3722 | 18 100×100的格子
每维都有101条边。。
【在 a*****y 的大作中提到】
: 哪里来的101条边？
|
a*****y
发帖数: 1488 | 19 这个。。。
100个格子有101个点我明白，怎么有101条边呢？
【在 P**l 的大作中提到】
: 100×100的格子
: 每维都有101条边。。
|
i*****e
发帖数: 5233 | 20 101个node 中选取两个点 这两点间的部分作为 长 或者宽
于是长的选取方式数等价于 x1+x2+x3=100 x1>=0 x2>0 x3>=0的解的组数 这个等
于
C(101,2)
【在 a*****y 的大作中提到】
: 这个。。。
: 100个格子有101个点我明白，怎么有101条边呢？
|
|
|
d**e
发帖数: 6098 | 21 这个好！！！！
我居然还想那么复杂。
【在 P**l 的大作中提到】
: 100×100的格子
: 每维都有101条边。。
|
a*****y
发帖数: 1488 | 22 多谢，现在明白了。
每维有 C(101,2) 种方式选取长或宽。
如果问题改成问100x100的格子里有多少正方形呢？
【在 i*****e 的大作中提到】
: 101个node 中选取两个点 这两点间的部分作为 长 或者宽
: 于是长的选取方式数等价于 x1+x2+x3=100 x1>=0 x2>0 x3>=0的解的组数 这个等
: 于
: C(101,2)
|
i*****e
发帖数: 5233 | 23 可以按对角线考虑 1 + 3 + 6 + 10
第i项是 i(i+1)/2
多谢，现在明白了。
每维有 C(101,2) 种方式选取长或宽。
如果问题改成问100x100的格子里有多少正方形呢？
【在 a*****y 的大作中提到】
: 多谢，现在明白了。
: 每维有 C(101,2) 种方式选取长或宽。
: 如果问题改成问100x100的格子里有多少正方形呢？
|
h**6
发帖数: 4160 | 24 可以按照边长来分类：
边长为1的正方形有100^2个
边长为2的正方形有99^2个
边长为3的正方形有98^2个
……
边长为100的正方形有1^2个
总数为1^2+2^2+...+100^2 = 100*(100+1)*(2*100+1)/6 = 338350
【在 a*****y 的大作中提到】
: 多谢，现在明白了。
: 每维有 C(101,2) 种方式选取长或宽。
: 如果问题改成问100x100的格子里有多少正方形呢？
|
x********o
发帖数: 3525 | 25 错
【在 p*****n 的大作中提到】
: C(100, 2)^2?
|
x********o
发帖数: 3525 | 26 正解
【在 P**l 的大作中提到】
: C(101,2)^2?
|
s*****e
发帖数: 36 | 27 Is there something wrong in my solution?
I think 100*100 blocks have 101*101 points in total.
Then we pick two of them to form a rectangle.
For the first one we have C(101*101,1). For the second one we have C(101*101
-101*2+1,1)=C(100^2,1) since we can not choose the poinsts in the same row/
column of the first one. And the order is not important. So I will have C(
101^2,1)*C(100^2,1)/2=(101*100)^2/2.
C(101,2)^2=(101*100)^2/4.
Can somebody let me know where my solution is wrong? Thanks. |
d**e
发帖数: 6098 | 28 应该是对的。但可以不那么复杂。前面有人给了答案。
横竖都是101条线，竖取两条，横取两条，所以就是 C(101,2)^2
101
【在 s*****e 的大作中提到】
: Is there something wrong in my solution?
: I think 100*100 blocks have 101*101 points in total.
: Then we pick two of them to form a rectangle.
: For the first one we have C(101*101,1). For the second one we have C(101*101
: -101*2+1,1)=C(100^2,1) since we can not choose the poinsts in the same row/
: column of the first one. And the order is not important. So I will have C(
: 101^2,1)*C(100^2,1)/2=(101*100)^2/2.
: C(101,2)^2=(101*100)^2/4.
: Can somebody let me know where my solution is wrong? Thanks.
|
s*****e
发帖数: 36 | 29 C(101,2)^2 seems right. Found where I am wrong. A rectangle has four points.
The other diagnal pair can not form the same rectangle either. |
c**y
发帖数: 172 | 30 Below is my code. However, (101,2)^2 looks the simplest.
#include
#include
#include
using namespace std;
int countRect(int x, int y) {
if ((x == 0) || (y == 0)) {
return 0;
} else if ((x == 1) && (y > 1)) {
return y;
} else if ((x > 1) && (y == 1)) {
return x;
} else {
return (x * y);
}
}
int countAllRect(int n, int m) {
if ((n <= 0) || (m <= 0)) {
return 0;
} else if ((n == 1) && (m > 1)) {
|
|
|
c**y
发帖数: 172 | 31 First choose a horizontal line, which has C(101,2) possibilities.
Second choose a vertical line, which also has C(101,2) possibilities.
Then a unique rectangle is determined by the two lines.
有
【在 a*****y 的大作中提到】
: 正确答案可能是 C(101,2)^2
: 选长方形其实可以看成选两个顶点。第一个顶点有 C(101,2) 种选择。 第二个顶点有
: C(101,2) 种选择，相乘就可以了。但是两个顶点应该不能是一个点，所以最后应该比
: 这个小才对。可是为什么是正确的呢？
|
