a*****y 发帖数: 1488 | 1 100x100的棋盘,里面有多少个长方形?可以overlap. |
z****n 发帖数: 1379 | 2 长度可以从1到100,宽度可以从1到100,这就有10000种大小的长方形,每种大小的
长方形可以有多种,例如长100,宽99的可以有两种,加一下吧,手算的话可能需要
一些数列公式
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 100x100的棋盘,里面有多少个长方形?可以overlap.
|
p*****n 发帖数: 368 | 3 C(100, 2)^2?
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这是错的 :) : ===================================== : 可能比较啰嗦,我的解法如下,请指正。 : 看成平面是由两顶点(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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 按照定义,正方形属于长方形。 : 如果不算正方形,稍微难一点。 : : 100)
|
d**e 发帖数: 6098 | 9 觉得你的解法和我的一样。
不过我没算最后的结果,x太大了,呵呵 :)
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一行: : 含有第一个格子的长方形一共有: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一行: : 含有第一个格子的长方形一共有: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 觉得你的解法和我的一样。 : 不过我没算最后的结果,x太大了,呵呵 :)
|
a*****y 发帖数: 1488 | 12 sum from x = 0-99
(100-x)^2*2-(100-x) = 671650
你这个数比我算的小了很多,我看看哪里错了。
【在 d**e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 正方形也算的话好像也一样,只是公式变一下。 : sum from x = 0 to 99 {(100-x)^2 * 2 - (100 - x)} : 但是想知道我的解法对不对。
|
d**e 发帖数: 6098 | 13 真的错了,有一步考虑错了,才发现。
让我再想想。
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : C(101,2)^2?
|
P**l 发帖数: 3722 | 15 101条边里面选2条当长方形的边
所有长方形都有了
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 真的错了,有一步考虑错了,才发现。 : 让我再想想。
|
a*****y 发帖数: 1488 | 17 哪里来的101条边?
【在 P**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 101条边里面选2条当长方形的边 : 所有长方形都有了
|
P**l 发帖数: 3722 | 18 100×100的格子
每维都有101条边。。
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哪里来的101条边?
|
a*****y 发帖数: 1488 | 19 这个。。。
100个格子有101个点我明白,怎么有101条边呢?
【在 P**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 100×100的格子 : 每维都有101条边。。
|
i*****e 发帖数: 5233 | 20 101个node 中选取两个点 这两点间的部分作为 长 或者宽
于是长的选取方式数等价于 x1+x2+x3=100 x1>=0 x2>0 x3>=0的解的组数 这个等
于
C(101,2)
【在 a*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个。。。 : 100个格子有101个点我明白,怎么有101条边呢?
|
|
|
d**e 发帖数: 6098 | 21 这个好!!!!
我居然还想那么复杂。
【在 P**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 100×100的格子 : 每维都有101条边。。
|
a*****y 发帖数: 1488 | 22 多谢,现在明白了。
每维有 C(101,2) 种方式选取长或宽。
如果问题改成问100x100的格子里有多少正方形呢?
【在 i*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢,现在明白了。 : 每维有 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 多谢,现在明白了。 : 每维有 C(101,2) 种方式选取长或宽。 : 如果问题改成问100x100的格子里有多少正方形呢?
|
x********o 发帖数: 3525 | 25 错
【在 p*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : C(100, 2)^2?
|
x********o 发帖数: 3525 | 26 正解
【在 P**l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 正确答案可能是 C(101,2)^2 : 选长方形其实可以看成选两个顶点。第一个顶点有 C(101,2) 种选择。 第二个顶点有 : C(101,2) 种选择,相乘就可以了。但是两个顶点应该不能是一个点,所以最后应该比 : 这个小才对。可是为什么是正确的呢?
|