题目85：考察矩形网格里的矩形数量
本帖最后由 欧拉计划 于 2016-8-9 17:36 编辑Counting rectangles
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.
题目：
仔细数的话可以看出一个 3×2 的矩形网格里包含 18 个矩形：
虽然没有哪个矩形网格包含正好两百万个矩形，找出包含最接近两百万个矩形的矩形网格的面积。
36 77 8
# ((1+m)*m/2)*((1+n)*n/2) = 2000000 ->n*m*(n+1)*(m+1) = 8000000
nearest = 1000000
for i in range(1,1000):
for j in range(1,1000):
near = abs(8000000 - i*j*(i+1)*(j+1))
if nearest > near:
nearest = near
neari = i
nearj = j
print (neari,nearj,nearest) # encoding:utf-8
# 找出包含最接近200万个矩形的面积
from time import time
def euler085(N=2000000):
a, b, t = 0, 0, N
for i in range(1, int((4 * N) ** 0.25 + 1)):
for j in range(1, int(((4 * N) / i ** 2) ** 0.5 + 1)):
tmp = (i * (i + 1) * j * (j + 1) / 4)
ifabs(tmp - N) < t:
t = abs(tmp - N)
a, b = i, j
if tmp > N and abs(tmp - N) > t:
break
print(a, b, int(t))
if __name__ == '__main__':
start = time()
euler085()
print('cost %.6f sec' % (time() - start))
36 77 2
cost 0.006001 sec def f(x):
return x * (x + 1) // 2
target = int(2*10**6)
curr = 0
ans = 0
for i in range(1, 999999999999):
a = f(i)
for j in range(1, i + 1):
b = f(j)
if abs(curr - target) > abs(a * b - target):
curr = a * b
ans = i * j
if a * b > target:
break
if a > target:
break
print(ans)
https://github.com/devinizz/project_euler/blob/master/page02/85.py 2772
Process returned 0 (0x0) execution time : 0.029 s
Press any key to continue.
#include<iostream>
#include<cstdlib>
using namespace std;
const int M = 2001;
const int STANDARD = 2e6;
int Cn_2(int n){
return n*(n-1)/2;
}
int main(){
int dif = 2e6;//已经充分大
int ans;
for (int m = 1;m <= M;m++){
for (int n = m;n <= M;n++){
int t = Cn_2(n+1) * Cn_2(m+1);//矩形总个数公式
if (abs(t-STANDARD) < dif){dif = abs(t-STANDARD); ans = m*n;}
if (t > STANDARD) break;//由组合数的递增可知，后面的总个数必然不会更接近2e6
}
}
cout << ans << endl;
return 0;
}
本帖最后由 永恒的蓝色梦想 于 2021-6-24 17:23 编辑
C++ 0ms/*
m
┏━━━━━━━━━┓
┃ ┃
n ┃ ┃
┃ ┃
┗━━━━━━━━━┛
(m(m+1)/2)(n(n+1)/2)=2e6
m(m+1)n(n+1)=8e6
m(m+1)=8e6/n(n+1)
m=(sqrt(3.2e7/n(n+1)+1)-1)/2
=sqrt(8e6/n(n+1)+0.25)-0.5
*/
#include<iostream>
#include<limits>
#include<cmath>
int main() {
using namespace std;
ios::sync_with_stdio(false);
const int UPPER_BOUND = ceil(sqrt(4e6 + 0.25) - 0.5);//n=1
int n, m, temp, s = 0, diff, min_diff = numeric_limits<int>::max();
double m_;
for (n = 1; n <= UPPER_BOUND; n++) {
temp = n * (n + 1);
m = m_ = sqrt(8e6 / temp + 0.25) - 0.5;
diff = abs(8000000 - m * (m + 1) * temp);
if (diff < min_diff) {
min_diff = diff;
s = m * n;
}
m = ceil(m_);
diff = abs(8000000 - m * (m + 1) * temp);
if (diff < min_diff) {
min_diff = diff;
s = m * n;
}
}
cout << s << endl;
return 0;
} /*
答案：2772
耗时：0.015695秒
0.0043418秒（六核）
*/
#include <iostream>
#include <algorithm>
#include <omp.h>
using namespace std;
int main(void)
{
double t = omp_get_wtime();
long long nArea = 0, nCount = 0;
#pragma omp parallel for shared(nArea,nCount) collapse(2)
for (int m = 1; m <= 100; ++m)//枚举大矩形
{
for (int n = 1; n <= 100; ++n)
{
long long nCount1 = 0;
for (int l = 0; l <= m - 1; ++l)//枚举矩形的左上点
{
for (int u = 0; u <= n - 1; ++u)
nCount1 += (m - l)*(n - u);
}
if (abs(nCount1 - 2000000) < abs(nCount - 2000000))//选择矩形数最靠近2000000的大矩形
{
#pragma omp critical
{
//保留结果
//防止其它线程已经改写了数据，再次确认
if (abs(nCount1 - 2000000) < abs(nCount - 2000000))
{
nCount = nCount1;
nArea = m;
nArea *= n;
}
}
}
}
}
t = omp_get_wtime() - t;
cout << nArea << endl << t << endl;
return 0;
}
页:
[1]