首页
社区
课程
招聘
[转帖+请教]一道题
发表于: 2005-11-30 17:10 8001

[转帖+请教]一道题

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

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

收藏
免费 0
支持
分享
最新回复 (17)
雪    币: 519
活跃值: (1223)
能力值: ( LV12,RANK:650 )
在线值:
发帖
回帖
粉丝
2
只算矩形的话是C(m,2)*C(n,2),加上斜线就数不清了。各种梯形,平行四边形,OMG
2005-12-1 21:56
0
雪    币: 270
活跃值: (312)
能力值: ( LV9,RANK:330 )
在线值:
发帖
回帖
粉丝
3
递推吧,假设m*n的格子有F(m,n)个四边形,然后分别考虑F(m+1,n)和F(m,n+1)的递推式。分矩形、四边形和梯形三种情况来考虑,递推式就不难写出了。
有了递推式,解出直接运算的式子也好,用动态规划求解也好,都没有问题了。
2005-12-2 01:40
0
雪    币: 209
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
4
今天上班啥都没干  就研究这个问题,除了穷举(也不简单)没想到其他办法。
2005-12-2 20:25
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
有没有考虑过全部用节点方式来算   比如总共m*n个点   然后0→m的循环中加上0→n的循环   思路就是这样,应该是有办法算出来!
2005-12-6 15:57
0
雪    币: 415
活跃值: (34)
能力值: ( LV5,RANK:60 )
在线值:
发帖
回帖
粉丝
6
无头绪,关注中。。。
2005-12-6 19:55
0
雪    币: 519
活跃值: (1223)
能力值: ( 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)推出来的,这样的动态规划的状态表示有问题,转移方程列不出来。
2005-12-6 20:10
0
雪    币: 1852
活跃值: (504)
能力值: (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) )
至于两个三角形的话,还需要处理两个三角形(左上和右下)的交接部分。
用递推肯定是能够做出来的。
所以到最后用动态规划也是能够做出来的,只不过在这里用动态规划不划算。
2005-12-6 23:04
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
9
今天突然想起这个题目
正方形是C(n+1,2)
==>每个正方形中2个三角(不重复)
==》三角形个数2*C(n+1,2)
2005-12-12 16:36
0
雪    币: 236
活跃值: (70)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
10
根据北极星的思路,从3角形入手,递推3角形个数,等大的2个三角形组成一个四边形。
2005-12-12 17:17
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
11
最初由 xeno 发布
根据北极星的思路,从3角形入手,递推3角形个数,等大的2个三角形组成一个四边形。


right
2005-12-12 23:12
0
雪    币: 254
活跃值: (126)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
12
楼上两位的想法不成立
梯形也是四边形,在这题个目里无法用2个三角形组成
2005-12-13 10:04
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
13
哎,我们的意思是正方形
2005-12-13 14:49
0
雪    币: 254
活跃值: (126)
能力值: ( LV8,RANK:130 )
在线值:
发帖
回帖
粉丝
14
最初由 北极星2003 发布
哎,我们的意思是正方形


正方形的话就更搞笑了,斜线可以去掉而根本不用考虑,还有必要用2个三角形去拼吗?
2005-12-13 17:26
0
雪    币: 1852
活跃值: (504)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
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 )
在线值:
发帖
回帖
粉丝
16
我也不懂,学习啊
2005-12-14 21:50
0
雪    币: 200
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
17
矩形的个数是:343+216+125+64+27+8+1=784个
平行四边形也可以看出来的,
梯形看不下去了.看起来要分等腰与直角两种..
没前途了,还是等有人写个算法让偶来套用来得轻松
2005-12-17 14:46
0
雪    币: 200
活跃值: (10)
能力值: ( 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

对于某种类型,存在相似的多个子类型,画出基本图形,然后用平移的办法计算出可以平移的位置数(也就是个数)。

但是,这个过程很无聊。
2005-12-20 10:03
0
游客
登录 | 注册 方可回帖
返回
//