数长方形
如果数得足够仔细,能看出在一个3乘2的长方形网格中包含有18个不同大小的长方形,如下图所示:
如图
尽管没有一个长方形网格中包含有恰好两百万个长方形,但有许多长方形网格中包含的长方形数目接近两百万,求其中最接近这一数目的长方形网格的面积。
思路
以图中长方形为例,有4条竖线,3条横线,其中两对横线和两对竖线能组成1个长方形,横线间的差就是长方形的高度,竖线之差就是宽度。用SQL表示如下:
with x as(select level x from dual connect by level<=4), y as(select level y from dual connect by level<=3) select (x2.x-x1.x)width,(y2.y-y1.y)hight,count(*) from x x1,x x2,y y1,y y2 where x2.x>x1.x and y2.y>y1.y group by (x2.x-x1.x),(y2.y-y1.y) order by 1,2; WIDTH HIGHT COUNT(*) ----- ---------- ---------- 1 1 6 1 2 3 2 1 4 2 2 2 3 1 2 3 2 1
分析
1x1 : (4-1)(3-1) =6 1x2 : (4-1)(3-2) =3 2x1 : (4-2)(3-1) =4 2x2 : (4-2)(3-2) =2 3x1 : (4-3)(3-1) =2 3x2 : (4-3)(3-2) =1 =(4-1)(3*2-sum(1->2)) +(4-2)(3*2-sum(1->2)) +(4-3)(3*2-sum(1->2)) =(4*3-sum(1->3))(3*2-sum(1->2)) =(12-6)*(6-3) =18
把4 和 3 用m 和 n代替
可以推测:
对于m*n的长方形,和为 (m*(m-1)-(1+m-1)*(m-1)/2)) *(n*(n-1)-(1+n-1)*(n-1)/2)) =m(m-1)n(n-1)/4
如果把直线根数改成长方形的宽度和高度 则
和=m(m+1)n(n+1)/4 设m是宽度和高度中较大者 则和必<=(m(m+1)/2)^2且>=(n(n+1)/2)^2
面积=mn,和最接近20000,实际就是求mn的最小值
解不等式m*m+m-2sqrt(2000000)>=0
,
m>=方程m*m+m-2sqrt(2000000)=0
的较大的根 1/2(-1+sqrt((1+4*2000sqrt(2))
SQL> select 1/2*(-1+sqrt(1+4*2000*sqrt(2)))a from dual; A ---------- 52.6853093
所以m最小值是53,n最大值是53
with m as(select level+52 m from dual connect by level<=100), n as(select level n from dual connect by level<=53) select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000; A ------ -2 with m as(select level+52 m from dual connect by level<=100), n as(select level n from dual connect by level<=53), min_diff as(select min(m*(m+1)*n*(n+1)/4-2e6) a from m,n where abs(m*(m+1)*n*(n+1)/4-2e6)<=1000) select m,n,m*n from m,n where m*(m+1)*n*(n+1)/4-2e6=(select a from min_diff); M N M*N ------ ---------- ---------- 77 36 2772
有些不完备的地方,
1. 不知道怎么证明-2是最接近的。要不就从1、-1开始测试。
2. m的上限怎么确定,这里100是碰巧,如果写成10就不能得到解