题目91：找出象限内直角三角形的数量

欧拉计划

Right triangles with integer coordinates

The points are plotted at integer co-ordinates and are joined to the origin, O(0,0), to form ΔOPQ.

There are exactly fourteen triangles containing a right angle that can be formed when each co-ordinate lies between 0 and 2 inclusive; that is,

Given that , how many right triangles can be formed?

  题目：

点 位于整数点坐标上，并且与原点 O(0,0) 相连接形成三角形 ΔOPQ。

当横纵坐标都位于 0 到 2 之间时（包括 0 和 2），也就是 时，一共可以形成 14 个直角三角形。

给定 , 一共能形成多少个直角三角形？

丹小怪

51

QingXin

总共运行了10s，最笨的办法，结果14234。

1. num=0
   
2. for x1 in range(0,51):
   
3.     for y1 in range(0,51):
   
4.         for x2 in range(0,51):
   
5.             for y2 in range(0,51):
   
6.                 s1 = x1*x1 + y1*y1
   
7.                 s2 = x2*x2 + y2*y2
   
8.                 s3 = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
   
9.                 f = [s1,s2,s3]
   
10.                 f.sort()
    
11.                 if f[0] >0:
    
12.                     if f[0] + f[1] == f[2]:
    
13.                         num+=1
    
14.                         
    
15. print(num/2)

复制代码

jerryxjr1220

14234.0
[Finished in 5.1s]

1. size = 50
   
2. count = 0
   
3. counted = []
   
4. for x1 in range(0, size + 1):
   
5.     for y1 in range(0, size + 1):
   
6.         for x2 in range (0, size + 1):
   
7.             for y2 in range(0, size + 1):
   
8.                 c2 = x1**2 + y1**2
   
9.                 a2 = (x2 -x1)**2 + (y2-y1)**2
   
10.                 b2 = x2**2 + y2**2
    
11.                 if (c2 == a2 + b2 or a2 == b2 + c2 or b2 == a2 + c2) and a2 != 0 and b2 != 0 and c2 != 0:
    
12.                         count += 0.5
    
13. print(int(count))

复制代码

jerryxjr1220

QingXin 发表于 2016-9-16 14:35
总共运行了10s，最笨的办法，结果14234。

和你的计算原理是一样的，但是比你快1倍的时间。
其实只要边长不为0即可，sort以后再额外判断2次很费时间的

QingXin

jerryxjr1220 发表于 2016-10-18 11:21
和你的计算原理是一样的，但是比你快1倍的时间。
其实只要边长不为0即可，sort以后再额外判断2次很费时 ...

恩，确实应该一次判断出来，sort搞麻烦了

芒果加黄桃

1. # encoding:utf-8
   
2. # 象限内直角三角形个数
   
3. from time import time
   
4. 
   
5. def euler090(N=50):
   
6.     count = 0
   
7.     # 直角顶点在X轴(1,0)--(50,0)
   
8.     count += 50 * 50
   
9.     # 直角顶点在Y轴(0,1)--(0,50)
   
10.     count += 50 * 50
    
11.     # 直角顶点在原点(0,0)
    
12.     count += 50 * 50
    
13.     for x1 in range(1, 51):
    
14.         for y1 in range(1, 51):
    
15.             for x2 in range(0, 51):
    
16.                 for y2 in range(1, 51):
    
17.                     if not(x2 < x1 and y2 > y1):
    
18.                         continue
    
19.                     a = x1 * x1 + y1 * y1
    
20.                     c = x2 * x2 + y2 * y2
    
21.                     b = (x1 - x2) ** 2 + (y1 - y2) ** 2
    
22.                     if c == a + b:
    
23.                         count += 1
    
24.     for x1 in range(1, 51):
    
25.         for y1 in range(1, 51):
    
26.             for x2 in range(1, 51):
    
27.                 for y2 in range(0, 51):
    
28.                     if not(x1 < x2 and y1 > y2):
    
29.                         continue
    
30.                     a = x1 * x1 + y1 * y1
    
31.                     c = x2 * x2 + y2 * y2
    
32.                     b = (x1 - x2) ** 2 + (y1 - y2) ** 2
    
33.                     if c == a + b:
    
34.                         count += 1
    
35.     print(count)
    
36. if __name__ == '__main__':
    
37.     start = time()
    
38.     euler090()
    
39.     print('cost %.6f sec' % (time() - start))

复制代码

14234
cost 6.564656 sec

永恒的蓝色梦想

1. from time import process_time as t
   
2. t1=t()
   
3. r=range(50+1)
   
4. count=0
   
5. for x1 in r:
   
6.   for x2 in r:
   
7.     for y1 in r:
   
8.       for y2 in r:
   
9.         if x1==x2 and y1==y2 or x1==0==y1 or x2==0==y2:continue
   
10.         l=sorted([(x1-x2)**2+(y1-y2)**2,x1**2+y1**2,x2**2+y2**2])
    
11.         if l[0]+l[1]==l[2]:count+=1
    
12. print(f'运行结果：{count/2}\n运行时间：{t()-t1}s')

复制代码

运行结果：14234.0
运行时间：24.828125s

guoquanli

1. /*功能函数，实现直角三角形个数的计算*/
   
2. int calNumOfTag(int pointA){
   
3.         int tagNum = 0;
   
4.         int count = 0;
   
5.         for(int x1 = 0; x1 <= pointA; x1++){
   
6.                 for(int y1 = 0; y1<=pointA; y1++){
   
7.                         for(int x2 = 0; x2 <= pointA; x2++){
   
8.                                 for(int y2 = 0; y2<= pointA ; y2++){
   
9.                                         if((x1 == x2 && y1 == y2)|| (x1 == 0 && y1 == 0) || (x2 ==0 && y2 == 0)){
   
10.                                                 continue;
    
11.                                         }
    
12.                                         //count++;
    
13.                                         //printf("符合条件的点的集合___%d____:A(%d,%d),B(%d,%d)\n",count,x1,y1,x2,y2);
    
14.                                         //printf("*******\n");
    
15.                                         int edge_1 = x1*x1 + y1*y1;
    
16.                                         //printf("edge_1 = x1*x1 + y1*y1[%d]\n",edge_1);
    
17.                                         int edge_2 = x2*x2 + y2*y2;
    
18.                                         //printf("edge_2 = x2*x2 + y2*y2[%d]\n",edge_2);
    
19.                                         int edge_3 = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 -y1);
    
20.                                         //printf("edge_3 = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 -y1)[%d]\n",edge_3);
    
21.                                         if(edge_1 + edge_2 == edge_3 || edge_1 + edge_3 == edge_2 || edge_3 + edge_2 == edge_1 ){
    
22.                                                 tagNum++;
    
23.                                                 //printf("能组成直角三角形的点是:B(%d,%d),C(%d,%d)\n",x1,y1,x2,y2);
    
24.                                         }
    
25.                                 }
    
26.                         }
    
27.                 }
    
28.         }
    
29.         return tagNum/2 ;
    

复制代码

答案：14234

guosl

应用矢量代数里的叉积和点积来做，速度非常快

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main(void)
   
5. {
   
6.   int N = 50;
   
7.   int nCount = 0;
   
8.   for (int x1 = 0; x1 <= N; ++x1)
   
9.   {
   
10.     for (int y1 = 0; y1 <= N; ++y1)
    
11.     {
    
12.       //遍历p1
    
13.       if (x1 == 0 && y1 == 0)//去掉原点
    
14.         continue;
    
15.       for (int x2 = 0; x2 <= N; ++x2)
    
16.       {
    
17.         for (int y2 = 0; y2 <= N; ++y2)
    
18.         {
    
19.           //遍历p2
    
20.           if ((x2 == 0 && y2 == 0) //去掉原点
    
21.             || (x1*y2 - x2 * y1 >= 0))//始终保持p1到p2为顺时针方向(应用叉积性质)
    
22.             continue;
    
23.           if ((y1*y2 == -x1 * x2) //直角在O点(应用内积性质)
    
24.             || (y1 * (y2 - y1) == -x1 * (x2 - x1)) //直角在p1点
    
25.             || (y2 * (y1 - y2) == -x2 * (x1 - x2)))//直角在p2点
    
26.             ++nCount;
    
27.         }
    
28.       }
    
29.     }
    
30.   }
    
31.   cout << nCount << endl;
    
32.   return 0;
    
33. }

复制代码