题目91：找出象限内直角三角形的数量
本帖最后由 欧拉计划 于 2016-8-11 23:07 编辑Right triangles with integer coordinates
The pointsare 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 总共运行了10s，最笨的办法，结果14234。
num=0
for x1 in range(0,51):
for y1 in range(0,51):
for x2 in range(0,51):
for y2 in range(0,51):
s1 = x1*x1 + y1*y1
s2 = x2*x2 + y2*y2
s3 = (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
f =
f.sort()
if f >0:
if f + f == f:
num+=1
print(num/2) 14234.0
size = 50
count = 0
counted = []
for x1 in range(0, size + 1):
for y1 in range(0, size + 1):
for x2 in range (0, size + 1):
for y2 in range(0, size + 1):
c2 = x1**2 + y1**2
a2 = (x2 -x1)**2 + (y2-y1)**2
b2 = x2**2 + y2**2
if (c2 == a2 + b2 or a2 == b2 + c2 or b2 == a2 + c2) and a2 != 0 and b2 != 0 and c2 != 0:
count += 0.5
print(int(count)) QingXin 发表于 2016-9-16 14:35
总共运行了10s，最笨的办法，结果14234。
和你的计算原理是一样的，但是比你快1倍的时间。
其实只要边长不为0即可，sort以后再额外判断2次很费时间的 jerryxjr1220 发表于 2016-10-18 11:21
和你的计算原理是一样的，但是比你快1倍的时间。
其实只要边长不为0即可，sort以后再额外判断2次很费时 ...
恩，确实应该一次判断出来，sort搞麻烦了 # encoding:utf-8
# 象限内直角三角形个数
from time import time
def euler090(N=50):
count = 0
# 直角顶点在X轴(1,0)--(50,0)
count += 50 * 50
# 直角顶点在Y轴(0,1)--(0,50)
count += 50 * 50
# 直角顶点在原点(0,0)
count += 50 * 50
for x1 in range(1, 51):
for y1 in range(1, 51):
for x2 in range(0, 51):
for y2 in range(1, 51):
if not(x2 < x1 and y2 > y1):
continue
a = x1 * x1 + y1 * y1
c = x2 * x2 + y2 * y2
b = (x1 - x2) ** 2 + (y1 - y2) ** 2
if c == a + b:
count += 1
for x1 in range(1, 51):
for y1 in range(1, 51):
for x2 in range(1, 51):
for y2 in range(0, 51):
if not(x1 < x2 and y1 > y2):
continue
a = x1 * x1 + y1 * y1
c = x2 * x2 + y2 * y2
b = (x1 - x2) ** 2 + (y1 - y2) ** 2
if c == a + b:
count += 1
print(count)
if __name__ == '__main__':
start = time()
euler090()
print('cost %.6f sec' % (time() - start))
14234
cost 6.564656 sec from time import process_time as t
t1=t()
r=range(50+1)
count=0
for x1 in r:
for x2 in r:
for y1 in r:
for y2 in r:
if x1==x2 and y1==y2 or x1==0==y1 or x2==0==y2:continue
l=sorted([(x1-x2)**2+(y1-y2)**2,x1**2+y1**2,x2**2+y2**2])
if l+l==l:count+=1
print(f'运行结果：{count/2}\n运行时间：{t()-t1}s')运行结果：14234.0
运行时间：24.828125s
本帖最后由 guoquanli 于 2020-2-26 17:33 编辑
/*功能函数，实现直角三角形个数的计算*/
int calNumOfTag(int pointA){
int tagNum = 0;
int count = 0;
for(int x1 = 0; x1 <= pointA; x1++){
for(int y1 = 0; y1<=pointA; y1++){
for(int x2 = 0; x2 <= pointA; x2++){
for(int y2 = 0; y2<= pointA ; y2++){
if((x1 == x2 && y1 == y2)|| (x1 == 0 && y1 == 0) || (x2 ==0 && y2 == 0)){
continue;
}
//count++;
//printf("符合条件的点的集合___%d____:A(%d,%d),B(%d,%d)\n",count,x1,y1,x2,y2);
//printf("*******\n");
int edge_1 = x1*x1 + y1*y1;
//printf("edge_1 = x1*x1 + y1*y1[%d]\n",edge_1);
int edge_2 = x2*x2 + y2*y2;
//printf("edge_2 = x2*x2 + y2*y2[%d]\n",edge_2);
int edge_3 = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 -y1);
//printf("edge_3 = (x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 -y1)[%d]\n",edge_3);
if(edge_1 + edge_2 == edge_3 || edge_1 + edge_3 == edge_2 || edge_3 + edge_2 == edge_1 ){
tagNum++;
//printf("能组成直角三角形的点是:B(%d,%d),C(%d,%d)\n",x1,y1,x2,y2);
}
}
}
}
}
return tagNum/2 ;
答案：14234 应用矢量代数里的叉积和点积来做，速度非常快#include <iostream>
using namespace std;
int main(void)
{
int N = 50;
int nCount = 0;
for (int x1 = 0; x1 <= N; ++x1)
{
for (int y1 = 0; y1 <= N; ++y1)
{
//遍历p1
if (x1 == 0 && y1 == 0)//去掉原点
continue;
for (int x2 = 0; x2 <= N; ++x2)
{
for (int y2 = 0; y2 <= N; ++y2)
{
//遍历p2
if ((x2 == 0 && y2 == 0) //去掉原点
|| (x1*y2 - x2 * y1 >= 0))//始终保持p1到p2为顺时针方向(应用叉积性质)
continue;
if ((y1*y2 == -x1 * x2) //直角在O点(应用内积性质)
|| (y1 * (y2 - y1) == -x1 * (x2 - x1)) //直角在p1点
|| (y2 * (y1 - y2) == -x2 * (x1 - x2)))//直角在p2点
++nCount;
}
}
}
}
cout << nCount << endl;
return 0;
}
页:
[1]