欧拉计划 发表于 2016-8-11 23:21:55

题目94：找出具有整数边长和面积的近似等边三角形

Almost equilateral triangles

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

题目：

容易证明不存在具有整数边长和整数面积的等边三角形。但是 5-5-6 这个近似等边三角形具有整数面积 12。

我们将近似等边三角形定义为有两边相等，并且第三边与其他两边相差不超过 1 的三角形。

对于周长不超过 10 亿的三角形中，找出边长和面积都为整数的近似等边三角形的周长和。

迷雾少年 发表于 2016-8-31 16:12:55

5,5,6 S=12
8,8,9 S=24
65,65,66 S=1848
98,98,99 S=4116
901,901,902 S=351780
1352,1352,1353 S=790920
12545,12545,12546 S=68149872
18818,18818,18819 S=153329064

//海伦公式求面积 面积是整数返回边长 不是返回0
/*
假设三边长为a,b,c
p=(a+b+c)/2
则面积的平方s^2=p*(p-a)*(p-b)*(p-c)
例子:a=3,b=4,c=5
*/
#include <iostream>
int getSum(int a,int b,int c)
{

        double p=(a+b+c)/2;
        double s= sqrt(p*(p-a)*(p-b)*(p-c));
        //判断是否为整数s
        if((double)(int)s == s)
        {
                return s;
        }
        return 0;
}
int main()
{
        for (int k = 2;k<=433333333;k++)
        {
                int a,b,c,s;
                a=k;
                b=k;
                c=k+1;
                s=getSum(a,b,c);
                if(s)
                {
                        std::cout<<a<<","<<b<<","<<c<<" S="<<s<<std::endl;
                }
        }
        return 0;
}

芒果加黄桃 发表于 2017-3-7 17:02:24

# encoding:utf-8
# 具有整数边长和面积的近似等边三角形个数
from time import time
from math import sqrt
N = 333333334
def getArea(n):
    count = 0
    t = (3 * n - 1) / 2
    area = sqrt(t * (t - n) * (t - n) * (t - n + 1))
    if int(area) == area:
      count += 1
      print(n, n, n - 1)
    t = (3 * n + 1) / 2
    area = sqrt(t * (t - n) * (t - n) * (t - n - 1))
    if int(area) == area:
      count += 1
      print(n, n, n + 1)
    return count

def euler094(N):
    result = 0
    for n in range(2, N):
      t = getArea(n)
      if t > 0:
            result += t
    print(result)
if __name__ == '__main__':
    start = time()
    euler094(N)
    print('cost %.6f sec' % (time() - start))
时间太久，算不出来....
楼上没考虑第三边短的情况

QingXin 发表于 2017-3-24 16:39:44

用python的math.sqrt（）配合海伦公式算面积的时候，有一个被忽略的问题，就是大数据的情况下，python的计算精度问题。
三角形（302828,302828,302829）就是一个很好的例子。
import math
def area(a,b,c):
        p = (a+b+c)/2
        s = math.sqrt(p*(p-a)*(p-b)*(p-c))
        return s

print(area(302828,302828,30282))
答案是39709429597.0。但实际上，该三角形底边上的高为262256.45230146387，是个无理数，面积不会是真正的“整数”，这只不过是被python四舍五入了。
所以，这道题的关键在于（1）避开sqrt（）函数直接作用于大的数，（2）将计算次数从上亿次降下来。

对于一个编程渣来讲，最好的办法就是： 编程渣，数学来凑！
不得不承认，我把这道题做成了数学题。后面是长长的数学推理，可跳过。

假定第三边大于三角形的两腰，那么设三边为m，m，m+1。那么根据海伦公式，
p=(m+m+m+1)/2=(3m+1)/2
S= √((3m+1)(m+1)(m+1)(m-1)/16)
所以，m必须是奇数才可以。设m=2k+1，那么代入，有
S=（k+1）√(k（3k+2）)
显然，k与3k+2没有大于2的公因子。
        假设两者互质，那么k和3k+2 都必须同时是完全平方数才能确保面积是整数，可以设k=x^2，检测3x^2+2是否为整数。这时，三角形的三边为2*x^2+1, 2*x^2+1,2*x^2+2，根据边长范围可得，x不大于12910。
        假设两者不互质，那么设k=2y，那么
S=2（2y+1）√(y（3y+1）)
Y与3y+1必然互质，所以y和（3y+1）必须是完全平方数，设y = x^2，检测 3*x^2 + 1 是否为完全平方数即可。此时，三角形的三边为 4^x2+1, 4^x2+1, 4^x2+2，x不大于9129。
同样的，假定第三边小于三角形的两腰时，可以得到后面的结论：
        三角形三边为2*x^2-1, 2*x^2-1,2*x^2-2, x不大于12910，3*x^2-2须为完全平方数。
        三角形三边为4*x^2-1, 4*x^2-1,4*x^2-2, x不大于9129，3*x^2-1须为完全平方数。

上代码：
import math

pri_sum = 0
#case1

for i in range(1,int(math.sqrt(10**9/3/2))+1):
    test = math.sqrt(3*i*i+2)
    if round(test)==test:
      pri_sum+=sum()
#case2

for i in range(1,int(math.sqrt(10**9/3/4))+1):
    test = math.sqrt(3*i*i+1)
    if round(test)==test:
      pri_sum+=sum()
#case3

for i in range(2,int(math.sqrt(10**9/3/2))+1):
    test = math.sqrt(3*i*i-2)
    if round(test)==test:
      pri_sum+=sum()
#case4

for i in range(1,int(math.sqrt(10**9/3/4))+1):
    test = math.sqrt(3*i*i-1)
    if round(test)==test:
      pri_sum+=sum()
print(pri_sum)

计算结果为518408346。可以预见，结果是秒出的。

所找到的三角形为：
5 5 6
65 65 66
901 901 902
12545 12545 12546
174725 174725 174726
2433601 2433601 2433602
33895685 33895685 33895686
17 17 16
241 241 240
3361 3361 3360
46817 46817 46816
652081 652081 652080
9082321 9082321 9082320
126500417 126500417 126500416

做成了数学题，也是醉了。

jerryxjr1220 发表于 2017-10-14 22:06:45

QingXin 发表于 2017-3-24 16:39
用python的math.sqrt（）配合海伦公式算面积的时候，有一个被忽略的问题，就是大数据的情况下，python的计 ...

分析得很到位！给力！

guosl 发表于 2022-1-26 22:17:59

/*
应用GPU计算
答案：518408346
耗时：0.237227秒(P104-100)
*/
#include<iostream>
#include<cmath>
#include <openacc.h>
using namespace std;

int main(void)
{
long long sum = 0;
#pragma acc kernels loop reduction(+:sum)
for (long long a = 3; a <= 333333333; a += 2)//枚举等边
{
    for (long long c = a - 1; c <= a + 1; c += 2)//枚举单独的边
    {
      long long a2 = a * 2;//两条等边之和
      long long p2 = a2 + c;//3a-1或3a+1
      long long s = p2 * (a2 - c);//在面积中去掉平方项后留下的(3a-1)(a+1)或(3a+1)(a-1)
      long long d = (long long)sqrt((double)s);
      if (s % d == 0 && s == d * d //s是一个完全平方数
          && (d * c) % 4 == 0) //根据面积公式d * c应该是4的倍数
      sum += p2;
    }
}
cout << sum << endl;
return 0;
}
页: [1]
查看完整版本: 题目94：找出具有整数边长和面积的近似等边三角形