从算法到程序之计数问题

Posted on 2016-03-19

计数问题有时候也很磨人,输出和输出的内在联系往往需要思考与推导。 假设给定正整数n,计算出由n^2个带有对角线的小方块构成的正方形图案,求该图案中具有的凸四边形个数。

问题示意图

可以看到主要含有以上6种图形,這六种图形所占有的方格当然是有重叠的,互相包含,交错次啊能排列组合得出,应当从加法原理的角度去构思,這里我们可以观察在高度一定情况下的凸四边形个数,总结,然后计算k(k在1~n范围内)个高度下中的总数量 下面我们来k归纳一下 k=1时:图形就看成是n排高度为1的图形组成de

所以该情况下,矩形数目为n(n+1)/2+3n(n-1)/2=2n^2-n,那么n排组成的 就是2n^3-n^2个矩形啦。 当高度k=2呐!這时候所有的图形都出现了!

n(n+1)/2+3(n-1)(n-2)/2+5n-2       (A式) 這样的图形有多少呢,n-1,因为是可以覆盖的,所以高度为2下共有A*(n-1)个凸四边形(等腰梯形這里主要看对角长斜线) k=3时

最后我们终于可以总结归纳出来一般性规律了 除了高度为1的情况下,其它的情况所有的图形都出现了:

矩形:n(n+1)/2 水平平行四边形:(n-k)(n-k+1)/2 竖直平行四边形:(k-1)(2n-k+2)/2 水平梯形:(n-k)(n-k+1) 竖直梯形:(k-1)(2n-k+2) 等腰梯形:2(n-k+1)(k-1) 那么图形中含有多少个高度为k的子图形呢?n-k+1啦 所以最终的结果就是(n-k+1)与上述所有图形数目的乘积了。 代码写起来当然不难。数学太多啦

int countingQuadrangles(int n){
	int k,count=0;
	count=n*(2*n*n-n);/*高为1*/
	for(k=2;k<=n;k++){/*高为k*/
		count+=(n-k+1)*(
			n*(n+1)/2/*矩形个数*/
			+3*(n-k+1)*(n-k)/2/*水平平行四边形、直梯形*/
			+3*(k-1)*(2*n-k+2)/2/*竖直梯形、平行四边形*/
			+2*(n-k+1)*(k-1)/*等腰梯形*/
			);
	}
	return count;
}

蚊子再小也是肉~
本站总访问量 本站访客数