[转帖+请教]一道题-编程技术-看雪-安全社区|安全招聘|kanxue.com

[转帖+请教]一道题

发表于: 2005-11-30 17:10 7985

[转帖+请教]一道题

UniPho

活跃值

2005-11-30 17:10

7985

求共有多少个四边形?
在驱动网看到的,搬了过来.
我刚学数据结构与算法.不懂
大家看看吧!
好久没来了!希望大家早日解决.
反正我是不会做.

[IMG]

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

收藏・0

免费・0

支持

分享

最新回复 (17)
RoBa 雪币： 519 活跃值： (1223) 能力值： ( LV12，RANK：650 ) 在线值：发帖 75 回帖 857 粉丝 9 关注私信	RoBa 16 2 楼只算矩形的话是C(m,2)*C(n,2)，加上斜线就数不清了。各种梯形，平行四边形，OMG 2005-12-1 21:56 0
henryouly 雪币： 270 活跃值： (312) 能力值： ( LV9，RANK：330 ) 在线值：发帖 17 回帖 103 粉丝 0 关注私信	henryouly 8 3 楼递推吧，假设m*n的格子有F(m,n)个四边形，然后分别考虑F(m+1,n)和F(m,n+1)的递推式。分矩形、四边形和梯形三种情况来考虑，递推式就不难写出了。有了递推式，解出直接运算的式子也好，用动态规划求解也好，都没有问题了。 2005-12-2 01:40 0
datm 雪币： 209 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 3 回帖 106 粉丝 1 关注私信	datm 4 楼今天上班啥都没干就研究这个问题，除了穷举（也不简单）没想到其他办法。 2005-12-2 20:25 0
水の易寒雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 5 回帖 14 粉丝 0 关注私信	水の易寒 5 楼有没有考虑过全部用节点方式来算比如总共m*n个点然后0→m的循环中加上0→n的循环思路就是这样，应该是有办法算出来！ 2005-12-6 15:57 0
笨奔雪币： 415 活跃值： (34) 能力值： ( LV5，RANK：60 ) 在线值：发帖 11 回帖 748 粉丝 1 关注私信	笨奔 1 6 楼无头绪，关注中。。。 2005-12-6 19:55 0
RoBa 雪币： 519 活跃值： (1223) 能力值： ( LV12，RANK：650 ) 在线值：发帖 75 回帖 857 粉丝 9 关注私信	RoBa 16 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)推出来的，这样的动态规划的状态表示有问题，转移方程列不出来。 2005-12-6 20:10 0
北极星2003 雪币： 1852 活跃值： (504) 能力值： (RANK：1010 ) 在线值：发帖 86 回帖 1240 粉丝 12 关注私信	北极星2003 25 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) ) 至于两个三角形的话，还需要处理两个三角形（左上和右下）的交接部分。用递推肯定是能够做出来的。所以到最后用动态规划也是能够做出来的，只不过在这里用动态规划不划算。 2005-12-6 23:04 0
北极星2003 雪币： 1852 活跃值： (504) 能力值： (RANK：1010 ) 在线值：发帖 86 回帖 1240 粉丝 12 关注私信	北极星2003 25 9 楼今天突然想起这个题目正方形是C(n+1,2) ==>每个正方形中2个三角（不重复） ==》三角形个数2*C(n+1,2) 2005-12-12 16:36 0
xeno 雪币： 236 活跃值： (70) 能力值： ( LV6，RANK：90 ) 在线值：发帖 13 回帖 195 粉丝 0 关注私信	xeno 2 10 楼根据北极星的思路，从3角形入手，递推3角形个数，等大的2个三角形组成一个四边形。 2005-12-12 17:17 0
北极星2003 雪币： 1852 活跃值： (504) 能力值： (RANK：1010 ) 在线值：发帖 86 回帖 1240 粉丝 12 关注私信	北极星2003 25 11 楼最初由 xeno 发布根据北极星的思路，从3角形入手，递推3角形个数，等大的2个三角形组成一个四边形。 right 2005-12-12 23:12 0
heXer 雪币： 254 活跃值： (126) 能力值： ( LV8，RANK：130 ) 在线值：发帖 12 回帖 802 粉丝 2 关注私信	heXer 3 12 楼楼上两位的想法不成立梯形也是四边形，在这题个目里无法用2个三角形组成 2005-12-13 10:04 0
北极星2003 雪币： 1852 活跃值： (504) 能力值： (RANK：1010 ) 在线值：发帖 86 回帖 1240 粉丝 12 关注私信	北极星2003 25 13 楼哎，我们的意思是正方形 2005-12-13 14:49 0
heXer 雪币： 254 活跃值： (126) 能力值： ( LV8，RANK：130 ) 在线值：发帖 12 回帖 802 粉丝 2 关注私信	heXer 3 14 楼最初由北极星2003 发布哎，我们的意思是正方形正方形的话就更搞笑了，斜线可以去掉而根本不用考虑，还有必要用2个三角形去拼吗？ 2005-12-13 17:26 0
北极星2003 雪币： 1852 活跃值： (504) 能力值： (RANK：1010 ) 在线值：发帖 86 回帖 1240 粉丝 12 关注私信	北极星2003 25 15 楼最初由 heXer 发布正方形的话就更搞笑了，斜线可以去掉而根本不用考虑，还有必要用2个三角形去拼吗？哎！！你还是没明白我的意思详细的来一遍： 1、确定正方形的个数是C(n+1,2) 2、三角形的个数与正方形的个数存在密切关系 3、每一个正方形都可以划分成两个等大的三角形 4、所以三角形的个数为2*C(n+1,2) 主要是在第三步，靠文字很难说清楚我的表达能力就只能到这里了 2005-12-13 18:38 0
逍遥散人雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 9 回帖 64 粉丝 0 关注私信	逍遥散人 16 楼我也不懂，学习啊 2005-12-14 21:50 0
UniPho 雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 6 回帖 66 粉丝 0 关注私信	UniPho 17 楼矩形的个数是:343+216+125+64+27+8+1=784个平行四边形也可以看出来的, 梯形看不下去了.看起来要分等腰与直角两种.. 没前途了,还是等有人写个算法让偶来套用来得轻松 2005-12-17 14:46 0
JGsHEn 雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 6 粉丝 0 关注私信	JGsHEn 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 对于某种类型，存在相似的多个子类型，画出基本图形，然后用平移的办法计算出可以平移的位置数（也就是个数）。但是，这个过程很无聊。 2005-12-20 10:03 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

返回

UniPho

发帖

回帖

RANK

他的文章

看雪公众号

专注于PC、移动、智能设备安全研究及逆向工程的开发者社区

//