2 guoguo66 guoguo66 于 2016.02.19 15:35 提问

如何计算 随机数量的正方形可以拼成多边形的数量?

大家玩过 俄罗斯方块吧,里面所有的图形都是由四个正方形组成的,我想做一个程序来算出并画出n个相同的正方形可以画出的多边形的数量,旋转后一样的算一个,大神有什么好的算法?
谢谢!

1个回答

leilba
leilba   Rxr 2016.02.19 17:56
已采纳

我没有想到什么太好的方法,不过递推和暴力剪枝可以试一下。
我的思路是这样的:
首先确定这个是可以通过递推做的,因为n=4组成的所有的多边形可以由n=3组成的所有多边形的基础上再添加一个正方形推出来的。
所以,我们可以从n=1的时候出发。
1.n=1,就只有一种多边形,毫无问题。
2.n=2,从n=1的基础上再添加一个正方形,我们可以放置的位置为 上下左右 4个方向,各自加入1个正方形,这样获得了4个新的多边形,然后进行旋转去重,去掉重复的,这样就得到了n=2的答案。
3.n=3,从n=2的基础上再添加一个正方形,对每一个可以防止新的正方形的位置尝试放置正方形,这样总共可以获得6个新的多边形,然后再进行旋转去重,就可以得到n=3的答案。
4.。。类推。
图片说明
思路图是这样的,程序可以实现,不过挺麻烦的

guoguo66
guoguo66 谢谢谢谢,跟我想的一样,到5个方块的时候就已经很麻烦了,我努力试试
接近 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!