题目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 亿的三角形中，找出边长和面积都为整数的近似等边三角形的周长和。

迷雾少年

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

1. //海伦公式求面积 面积是整数返回边长 不是返回0
   
2. /*
   
3. 假设三边长为a,b,c
   
4. p=(a+b+c)/2
   
5. 则面积的平方s^2=p*(p-a)*(p-b)*(p-c)
   
6. 例子:a=3,b=4,c=5
   
7. */
   
8. #include <iostream>
   
9. int getSum(int a,int b,int c)
   
10. {
    
11. 
    
12.         double p=(a+b+c)/2;
    
13.         double s= sqrt(p*(p-a)*(p-b)*(p-c));
    
14.         //判断是否为整数s
    
15.         if((double)(int)s == s)
    
16.         {
    
17.                 return s;
    
18.         }
    
19.         return 0;
    
20. }
    
21. int main()
    
22. {
    
23.         for (int k = 2;k<=433333333;k++)
    
24.         {
    
25.                 int a,b,c,s;
    
26.                 a=k;
    
27.                 b=k;
    
28.                 c=k+1;
    
29.                 s=getSum(a,b,c);
    
30.                 if(s)
    
31.                 {
    
32.                         std::cout<<a<<","<<b<<","<<c<<" S="<<s<<std::endl;
    
33.                 }
    
34.         }
    
35.         return 0;
    
36. }

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 具有整数边长和面积的近似等边三角形个数
   
3. from time import time
   
4. from math import sqrt
   
5. N = 333333334
   
6. def getArea(n):
   
7.     count = 0
   
8.     t = (3 * n - 1) / 2
   
9.     area = sqrt(t * (t - n) * (t - n) * (t - n + 1))
   
10.     if int(area) == area:
    
11.         count += 1
    
12.         print(n, n, n - 1)
    
13.     t = (3 * n + 1) / 2
    
14.     area = sqrt(t * (t - n) * (t - n) * (t - n - 1))
    
15.     if int(area) == area:
    
16.         count += 1
    
17.         print(n, n, n + 1)
    
18.     return count
    
19. 
    
20. def euler094(N):
    
21.     result = 0
    
22.     for n in range(2, N):
    
23.         t = getArea(n)
    
24.         if t > 0:
    
25.             result += t
    
26.     print(result)
    
27. if __name__ == '__main__':
    
28.     start = time()
    
29.     euler094(N)
    
30.     print('cost %.6f sec' % (time() - start))

复制代码

时间太久，算不出来....
楼上没考虑第三边短的情况

QingXin

用python的math.sqrt（）配合海伦公式算面积的时候，有一个被忽略的问题，就是大数据的情况下，python的计算精度问题。
三角形（302828,302828,302829）就是一个很好的例子。

1. import math
   
2. def area(a,b,c):
   
3.         p = (a+b+c)/2
   
4.         s = math.sqrt(p*(p-a)*(p-b)*(p-c))
   
5.         return s
   
6. 
   
7. 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须为完全平方数。

上代码：

1. import math
   
2. 
   
3. pri_sum = 0
   
4. #case1
   
5. 
   
6. for i in range(1,int(math.sqrt(10**9/3/2))+1):
   
7.     test = math.sqrt(3*i*i+2)
   
8.     if round(test)==test:
   
9.         pri_sum+=sum([2*i*i+1,2*i*i+1,2*i*i+2])
   
10. #case2
    
11. 
    
12. for i in range(1,int(math.sqrt(10**9/3/4))+1):
    
13.     test = math.sqrt(3*i*i+1)
    
14.     if round(test)==test:
    
15.         pri_sum+=sum([4*i*i+1,4*i*i+1,4*i*i+2])
    
16. #case3
    
17. 
    
18. for i in range(2,int(math.sqrt(10**9/3/2))+1):
    
19.     test = math.sqrt(3*i*i-2)
    
20.     if round(test)==test:
    
21.         pri_sum+=sum([2*i*i-1,2*i*i-1,2*i*i-2])
    
22. #case4
    
23. 
    
24. for i in range(1,int(math.sqrt(10**9/3/4))+1):
    
25.     test = math.sqrt(3*i*i-1)
    
26.     if round(test)==test:
    
27.         pri_sum+=sum([4*i*i-1,4*i*i-1,4*i*i-2])
    
28. print(pri_sum)

复制代码

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

所找到的三角形为：

1. 5 5 6
   
2. 65 65 66
   
3. 901 901 902
   
4. 12545 12545 12546
   
5. 174725 174725 174726
   
6. 2433601 2433601 2433602
   
7. 33895685 33895685 33895686
   
8. 17 17 16
   
9. 241 241 240
   
10. 3361 3361 3360
    
11. 46817 46817 46816
    
12. 652081 652081 652080
    
13. 9082321 9082321 9082320
    
14. 126500417 126500417 126500416

复制代码

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

jerryxjr1220

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

分析得很到位！给力！

guosl

1. /*
   
2. 应用GPU计算
   
3. 答案：518408346
   
4. 耗时：0.237227秒(P104-100)
   
5. */
   
6. #include<iostream>
   
7. #include<cmath>
   
8. #include <openacc.h>
   
9. using namespace std;
   
10. 
    
11. int main(void)
    
12. {
    
13.   long long sum = 0;
    
14. #pragma acc kernels loop reduction(+:sum)
    
15.   for (long long a = 3; a <= 333333333; a += 2)//枚举等边
    
16.   {
    
17.     for (long long c = a - 1; c <= a + 1; c += 2)//枚举单独的边
    
18.     {
    
19.       long long a2 = a * 2;//两条等边之和
    
20.       long long p2 = a2 + c;//3a-1或3a+1
    
21.       long long s = p2 * (a2 - c);//在面积中去掉平方项后留下的(3a-1)(a+1)或(3a+1)(a-1)
    
22.       long long d = (long long)sqrt((double)s);
    
23.       if (s % d == 0 && s == d * d //s是一个完全平方数
    
24.           && (d * c) % 4 == 0) //根据面积公式d * c应该是4的倍数
    
25.         sum += p2;
    
26.     }
    
27.   }
    
28.   cout << sum << endl;
    
29.   return 0;
    
30. }
    

复制代码