当前位置:首页 » Project Euler » 详细页

Counting rectangles 题号:85 难度: 15 中英对照

By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.


Solution

枚举矩形所有可能的长n和宽m,然后计算n乘m的矩形包括多少个格子,使格子的数目接近目标数目2000000,最后输出n乘m的面积即可。 首先,n乘m的矩形包括多少个格子呢?用排列组合即可。对于横为n的矩形,其中有n+1个端点,选取其中2个端点的方式数为: $$ C_{n+1}^2 $$ 同理在宽m中也选取2个点,这样的四个点即构成一个满足要求的格子。那么n乘m构成的矩形中包含的格子数目为: $$ (m+1)\*m\*(n+1)\*n/4 $$ 那么,长n和宽m最大为多少?根据上述计算方法,2000乘1的矩形共包含2001000个格子,已经超出目标2000000,所以n和m最大都为2000。

Code


public class No85 {
	public static void main(String[] args) 
	 {
	        long start=System.nanoTime();
	        long result = run();        
	        long end=System.nanoTime();
	        System.out.println(result);
	        System.out.println( (end-start)/1000000 + "ms" );
	 }	
	 public static long run()
	 {
		 int target=2000000;
		 int bestDiff = Integer.MAX_VALUE;
		 int bestArea = -1;
		 //枚举n和m
		 for (int n = 1; n <= 2000; n++) {
			for (int m = 1; m <= 2000; m++) {
				//计算格子数与目标格子数之间的差距
				int diff = Math.abs(numberOfRectangles(n, m) - target);
				//取差距最小的矩形,计算面积
				if (diff < bestDiff) {
					bestDiff = diff;
					bestArea = n * m;
				}
			}
		 }
			return (long)bestArea;
	 }
	 //计算m*n的矩形中格子的个数
	 public static int numberOfRectangles(int m, int n) {
			return (m + 1) * m * (n + 1) * n / 4;  // A bit more than m^2 n^2 / 4
		}
}
2772
12ms