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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
正方形组合而成的多边形的顶点排序算法
在开发现在的项目中碰到一个关于算法的难题,就是“正方形组合而成的多边形的顶点排序算法”。为什么要将多边形的顶点排序呢?因为需要使用PNPoly的算法来判断点是否在多边形内。而PNPoly的算法唯一要求的就是多边形的顶点有序数组,至于是逆时针还是顺时针其实都无所谓了。起初碰到这个问题的时候我百度了一下发现了凸包的概念,以及计算凸包的常用算法(详情点击这里:凸包)。但使用极角来排序多边形顶点的方法在项
ArcGIS--如何计算落在每个多边形内的点的数量?
原来考虑的是Spatial Join,后来发现不用那么复杂的办法。以随机点和渔网为例,如下图所示即可实现需求:渔网数据集右击,Join and Relates→Join,按下图操作即可。650) this.width=650;" title="捕获.PNG" alt="183414482.png" src="http://img1.51cto.com/attachment/201312/18341
计算三角形的数量
题目描述 有一次,老师给小明N根小木棒,要他从中选出K根,使这K根当中的任意三根都能拼成一个三角形。老师告诉他,构成一个三角形的条件是:任意两边之和大于第三边,任意两边之差小于第三边。 小明思考后,发现将这些小木棒按长短顺序排列后,很容易解决问题。 输入 输入二行 第一行一个整数表示:N(3≤N≤500) 第二行输入N个整数,相互之间用一个空格隔开 输出 输出:
Java 算长方形、正方形、三角形的面积
设计一个程序,用于根据用户输入的命令行参数数量来计算长方形、正方形、三角形的面积。如果输入的参数为一个、二个、三个则它们应分别对应正方形、长方形、三角形,如果没有参数,则通过异常处理方法现实错误消息。(用于计算面积的方法是一个重载的方法。提示:定义一个抽象的父类,并提供一个抽象的方法area(). 再派生出三个子类,重写area()方法,然后在main方法中用多态来实现具体的面积函数的调用)。
n*m 的点阵中正方形的个数
n×nn\times n 点阵中内接正方形个数)如上图所示,边长为 n 的正方形的内接正方形必须满足 a2+b2=c2a^2+b^2 = c^2 且 a+b=na+b = n ,同时,要求顶点必须为点阵中的点,故 a,b 的取值均为整数。以 n=10 的点阵举例,其取值的可能情况为 [0, 10] , [1, 9] , …, [9, 1], [10, 0] ([A, B]表示 a = A,b=B 的
正方形个数
题目描述 给定n个点,求可以组成的正方形的个数。(这些正方形可以倾斜) 数据范围:n 输入格式 1811.in 有多组测试数据。 对于每一组数据: 第1行为一个整数n。表示点的个数 第2至n+1行,每行两个数Xi,Yi,表示每个点的坐标。 当n=0时,输入结束。 输出格式 1811.out 对于每组数据,输出一个整数。为组成正方形的个数 输入样例 1811.in 4 1
正方形数量问题终极解答
废了不少脑细胞 public static int newsquareCount(int a , int b){ int k=a<b?a:b; return k*(k+1)*(2*k+1)/6+(Math.abs(a-b)*k*(k+1)/2); }
viterbi解码
包含,随机序列生成,卷积编码,viterbi译码,误码率计算。可以改寄存器数量和随机序列长度
Django 中随机获取指定数量数据
写之前说下csdn终于改版了。不容易啊。 下面就直接发代码了 class RandomManager(models.Manager): def get_queryset(self): return super(RandomManager, self).get_queryset().order_by('?') 使用的时候 class TrainWord
hdu6055(计算几何)计算n个整数点中有多少个正方形
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6055题意: 有n个整数点,问这些点能组成多少个正多边形。加以推导,我们可以知道,只有是正方形时,才能使得所有的端点为整数点。思路: 枚举正方形的一条边,另一条边可以根据这条边推导求得。 已知a(x1, y1), b(x2, y2), 则 c(x1+(y2-y1), y1-(x2-x1)) d(