能力值:
( LV12,RANK:650 )
|
-
-
2 楼
只算矩形的话是C(m,2)*C(n,2),加上斜线就数不清了。各种梯形,平行四边形,OMG
|
能力值:
( LV9,RANK:330 )
|
-
-
3 楼
递推吧,假设m*n的格子有F(m,n)个四边形,然后分别考虑F(m+1,n)和F(m,n+1)的递推式。分矩形、四边形和梯形三种情况来考虑,递推式就不难写出了。
有了递推式,解出直接运算的式子也好,用动态规划求解也好,都没有问题了。
|
能力值:
( LV2,RANK:10 )
|
-
-
4 楼
今天上班啥都没干 就研究这个问题,除了穷举(也不简单)没想到其他办法。
|
能力值:
( LV2,RANK:10 )
|
-
-
5 楼
有没有考虑过全部用节点方式来算 比如总共m*n个点 然后0→m的循环中加上0→n的循环 思路就是这样,应该是有办法算出来!
|
能力值:
( LV5,RANK:60 )
|
-
-
6 楼
无头绪,关注中。。。
|
能力值:
( LV12,RANK:650 )
|
-
-
7 楼
最初由 henryouly 发布 递推吧,假设m*n的格子有F(m,n)个四边形,然后分别考虑F(m+1,n)和F(m,n+1)的递推式。分矩形、四边形和梯形三种情况来考虑,递推式就不难写出了。 有了递推式,解出直接运算的式子也好,用动态规划求解也好,都没有问题了。
F(m+1,n)和F(m,n+1)不是只由F(m,n)推出来的,这样的动态规划的状态表示有问题,转移方程列不出来。
|
能力值:
(RANK:1010 )
|
-
-
8 楼
正方形:C(n+1,2)
矩形:C(n+1,2)*C(n+1,2)
三角形一时算不出来,
记得ZOJ上一 个 题是 算上图正方形中的左上三角,
这样的话,三角形个数:
n为偶数:f(n)=n*(n+1)/2 + ( (n-1) + (n-3) + ...+ 1) )
n为奇数:f(n)=n*(n+1)/2 + ( (n-1) + (n-3) + ...+ 2) )
至于两个三角形的话,还需要处理两个三角形(左上和右下)的交接部分。
用递推肯定是能够做出来的。
所以到最后用动态规划也是能够做出来的,只不过在这里用动态规划不划算。
|
能力值:
(RANK:1010 )
|
-
-
9 楼
今天突然想起这个题目
正方形是C(n+1,2)
==>每个正方形中2个三角(不重复)
==》三角形个数2*C(n+1,2)
|
能力值:
( LV6,RANK:90 )
|
-
-
10 楼
根据北极星的思路,从3角形入手,递推3角形个数,等大的2个三角形组成一个四边形。
|
能力值:
(RANK:1010 )
|
-
-
11 楼
最初由 xeno 发布 根据北极星的思路,从3角形入手,递推3角形个数,等大的2个三角形组成一个四边形。
right
|
能力值:
( LV8,RANK:130 )
|
-
-
12 楼
楼上两位的想法不成立
梯形也是四边形,在这题个目里无法用2个三角形组成
|
能力值:
(RANK:1010 )
|
-
-
13 楼
哎,我们的意思是正方形
|
能力值:
( LV8,RANK:130 )
|
-
-
14 楼
最初由 北极星2003 发布 哎,我们的意思是正方形
正方形的话就更搞笑了,斜线可以去掉而根本不用考虑,还有必要用2个三角形去拼吗?
|
能力值:
(RANK:1010 )
|
-
-
15 楼
最初由 heXer 发布
正方形的话就更搞笑了,斜线可以去掉而根本不用考虑,还有必要用2个三角形去拼吗?
哎!!
你还是没明白我的意思
详细的来一遍:
1、确定正方形的个数是C(n+1,2)
2、三角形的个数与正方形的个数存在密切关系
3、每一个正方形都可以划分成两个等大的三角形
4、所以三角形的个数为2*C(n+1,2)
主要是在第三步,靠文字很难说清楚
我的表达能力就只能到这里了
|
能力值:
( LV2,RANK:10 )
|
-
-
16 楼
我也不懂,学习啊
|
能力值:
( LV2,RANK:10 )
|
-
-
17 楼
矩形的个数是:343+216+125+64+27+8+1=784个
平行四边形也可以看出来的,
梯形看不下去了.看起来要分等腰与直角两种..
没前途了,还是等有人写个算法让偶来套用来得轻松
|
能力值:
( LV2,RANK:10 )
|
-
-
18 楼
图中的直线斜率有3种:0,1,inf(无穷大)
所以,四边形中至少有1对平行边(抽屉原理)
我们对四边形分类计算(按斜率分):
0,0,1,1
0,0,inf,inf
1,1,inf,inf
0,0,1,inf 和 0,0,inf,1
inf,inf,0,1 和 inf,inf,1,0
1,1,0,inf 和 1,1,inf,0
对于某种类型,存在相似的多个子类型,画出基本图形,然后用平移的办法计算出可以平移的位置数(也就是个数)。
但是,这个过程很无聊。
|
|
|