大家玩过 俄罗斯方块吧,里面所有的图形都是由四个正方形组成的,我想做一个程序来算出并画出n个相同的正方形可以画出的多边形的数量,旋转后一样的算一个,大神有什么好的算法?
谢谢!
如何计算 随机数量的正方形可以拼成多边形的数量?
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答
- 林深 2016-02-19 09: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.。。类推。
思路图是这样的,程序可以实现,不过挺麻烦的本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报