题目39：如果p是直角三角形{a,b,c}的周长，1000以下的p中哪一个具有最多的解？

欧拉计划

Integer right triangles

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

题目：

如果 p 是一个直角三角形的周长，三角形的三边长 {a, b, c} 都是整数。对于 p = 120 一共有三组解：

{20,48,52}, {24,45,51}, {30,40,50}

对于 1000 以下的 p 中，哪一个能够产生最多的解？

迷雾少年

周长:12
3,4,5
周长:24
6,8,10
周长:30
5,12,13
周长:36
9,12,15
周长:40
8,15,17
周长:48
12,16,20
周长:56
7,24,25
周长:60
10,24,26
15,20,25
周长:70
20,21,29
周长:72
18,24,30
周长:80
16,30,34
周长:84
12,35,37
21,28,35
周长:90
9,40,41
15,36,39
周长:96
24,32,40
周长:108
27,36,45
周长:112
14,48,50
周长:120
20,48,52
24,45,51
30,40,50
周长:126
28,45,53
周长:132
11,60,61
33,44,55
周长:140
40,42,58
周长:144
16,63,65
36,48,60
周长:150
25,60,65
周长:154
33,56,65
周长:156
39,52,65
周长:160
32,60,68
周长:168
21,72,75
24,70,74
42,56,70
周长:176
48,55,73
周长:180
18,80,82
30,72,78
45,60,75
周长:182
13,84,85
周长:192
48,64,80
周长:198
36,77,85
周长:200
40,75,85
周长:204
51,68,85
周长:208
39,80,89
周长:210
35,84,91
60,63,87
周长:216
54,72,90
周长:220
20,99,101
周长:224
28,96,100
周长:228
57,76,95
周长:234
65,72,97
周长:240
15,112,113
40,96,104
48,90,102
60,80,100
周长:252
36,105,111
56,90,106
63,84,105
周长:260
60,91,109
周长:264
22,120,122
66,88,110
周长:270
27,120,123
45,108,117
周长:276
69,92,115
周长:280
35,120,125
56,105,119
80,84,116
周长:286
44,117,125
周长:288
32,126,130
72,96,120
周长:300
50,120,130
75,100,125
1000下最多组解的有4
为周长=240周长:240
15,112,113
40,96,104
48,90,102
60,80,100
请按任意键继续.


代码写得好辣鸡

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. #include <string>
   
5. using namespace std;
   
6. //输出p(周长)的解组
   
7. int maxx = 0,maxN;
   
8. 
   
9. bool isin(vector<string> &result,string str)
   
10. {
    
11.         for (int n =0;n<result.size();n++)
    
12.         {
    
13.                 if(result[n] == str)
    
14.                         return true;
    
15.         }
    
16.         return false;
    
17. }
    
18. void calc(int p)
    
19. {
    
20. 
    
21.         int n = 0;
    
22.         int j = 0;
    
23.         vector<string> result;
    
24.        
    
25.                 for (int i=1;i<p;i++)
    
26.                 {
    
27.                         for (int b=i;b<p;b++)
    
28.                         {
    
29.                                 int c = p-i-b;
    
30.                                 if(c<=0)
    
31.                                         continue;
    
32.                                         int bian[3]={i,b,c};
    
33.                                         sort(bian,bian+3); //斜边是bian[2]
    
34. 
    
35.                                         if(i+b+c == p)
    
36.                                         {
    
37. 
    
38.                                        
    
39.                                                 //直角三角形
    
40.                                                 if(bian[0]*bian[0] + bian[1]*bian[1] == bian[2]*bian[2])
    
41.                                                 {
    
42.                                                         //
    
43.                                                         string temp;
    
44.                                                         char buf[20];
    
45.                                                         itoa(bian[0],buf,10);
    
46.                                                         temp = buf;
    
47.                                                         temp+=',';
    
48.                                                         itoa(bian[1],buf,10);
    
49.                                                         temp += buf;
    
50.                                                         temp+=',';
    
51.                                                         itoa(bian[2],buf,10);
    
52.                                                         temp += buf;
    
53.                                                        
    
54. 
    
55.                                                         if(!isin(result,temp))
    
56.                                                         result.push_back(temp);
    
57.                                                 }
    
58. 
    
59.                                         }
    
60. 
    
61.                                 }
    
62.                        
    
63.                 }
    
64.                
    
65.                 if(result.size())
    
66.                         std::cout<<"周长:"<<p<<endl;
    
67.                 for (int i = 0; i < result.size(); i++)
    
68.                 {
    
69.                         std::cout<<result[i]<<endl;
    
70.                 }
    
71.                
    
72. 
    
73.                 if(result.size()>maxx)
    
74.                 {
    
75.                         maxN = p;
    
76.                         maxx = result.size();
    
77.                 }
    
78. }
    
79. int main(void)
    
80. {
    
81.        
    
82.         for (int i = 2;i<=300;i++)
    
83.         {
    
84.                 calc(i);
    
85.         }
    
86.         std::cout<<"1000下最多组解的有"<<maxx<<endl;
    
87.         std::cout<<"为周长="<<maxN;
    
88.         calc(maxN);
    
89.         return 0;
    
90. }

复制代码

愤怒的大头菇

1. import math
   
2. def Jie(x):
   
3.       list1 = []
   
4.       for i in range(1,x):
   
5.             temp = math.sqrt(x**2 - i**2)
   
6.             if len(str(temp)) == 3 or len(str(temp))==4 or len(str(temp))== 5:
   
7.                   total = temp + x + i
   
8.                   list1.append([total,temp,x,i])
   
9.       return list1
   
10. list1 = []
    
11. for i in range(1000):
    
12.       total  = Jie(i)
    
13.       for each in total:
    
14.             if each!=[]and each[0]<1000:
    
15.                   list1.append(each)
    
16. list2=[]                 
    
17. for each in list1:
    
18.       each.sort()
    
19.       if each not in list2:
    
20.             list2.append(each)
    
21. list3 = []
    
22. for each in list2:
    
23.       list3.append(each[-1])
    
24. list4 = []
    
25. for each in list3:
    
26.       if each not in list4:
    
27.             list4.append(each)
    
28. temp = {}.fromkeys([i for i in list4],0)
    
29. for each in list3:
    
30.       if each in temp:
    
31.             temp[each] += 1
    
32. first = 0
    
33. for each in temp.values():
    
34.       if first < each:
    
35.             first = each
    
36. for each in temp:
    
37.       if temp[each] == first:
    
38.             print(each)

复制代码

写的好纠结，最多的解有8组，周长是840

jerryxjr1220

8组不重复解，周长840.

1. lst=[]
   
2. for a in range(1,250):
   
3.   for b in range(a,500-a):
   
4.     for c in range(b,500):
   
5.       if a*a+b*b==c*c:
   
6.         p=a+b+c
   
7.         lst.append([p,a,b,c])
   
8. cal=[]
   
9. master = {}
   
10. for each in lst:
    
11.   if each[0] not in cal:
    
12.     cal.append(each[0])
    
13.     master[each[0]]= 1
    
14.   else:
    
15.     master[each[0]]+=1
    
16. print (master)

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 寻找周长1000以下，能够成直角三角形最多的数
   
3. from time import time
   
4. def euler039():
   
5.     maxcount = 0
   
6.     result = []
   
7.     for p in range(12, 1001):
   
8.         count = 0
   
9.         tmp = []
   
10.         for i in range(int(p / (1 + 2 ** 0.5)) - 1, int(p / 2) + 1):
    
11.             for j in range(int(i / (2 ** 0.5)) - 1, i):
    
12.                 if i ** 2 == j ** 2 + (p - i - j) ** 2:
    
13.                     count += 1
    
14.                     tmp.append((p, i, j, (p - i - j)))
    
15.                     break
    
16.         if count > maxcount:
    
17.             result = tmp
    
18.             maxcount = count
    
19.     print(maxcount, result)
    
20. if __name__ == '__main__':
    
21.     start = time()
    
22.     euler039()
    
23.     print('cost %.6f sec' % (time() - start))
    

复制代码

8 [(840, 348, 252, 240), (840, 350, 280, 210), (840, 357, 315, 168), (840, 364, 336, 140), (840, 370, 350, 120), (840, 375, 360, 105), (840, 394, 390, 56), (840, 401, 399, 40)]
cost 5.641026 sec

渡风

此代码使用matlab编程
Problem39所用时间为： 2.1683秒
Problem39的答案为： 840

1. %% Problem39.m
   
2. % 最后编辑时间：17-06-14 22:34
   
3. % 如果p是直角三角形{a,b,c}的周长,1000以下的p中哪一个具有最多的解?
   
4. % Problem39所用时间为： 2.1683秒
   
5. % Problem39的答案为： 840
   
6. function Output = Problem39()
   
7. tic
   
8. 
   
9. Store = [];
   
10. for a = 1:250
    
11.     for b = a+1:500 - a  %根据楼上老大的解法，这点不懂
    
12.         for c = b+1:500
    
13.             if c^2 == a^2 + b^2
    
14.                 Store = [Store,a+b+c];
    
15.             end
    
16.         end
    
17.     end
    
18. end
    
19. 
    
20. Sta = tabulate(Store);  %找到所有解的比例
    
21. 
    
22. Value = Sta(:,1);
    
23. Ration = Sta(:,3);
    
24. 
    
25. Set = Ration == max(Ration);
    
26. 
    
27. Output = Value(Set);
    
28. 
    
29. toc
    
30. disp('此代码使用matlab编程')
    
31. disp(['Problem39所用时间为： ',num2str(toc),'秒'])
    
32. disp(['Problem39的答案为： ',num2str(Output)])
    
33. end
    

复制代码

najin

用的matlab
结果是：
>> Untitled

ans =

   840

时间已过 0.029216 秒。
>>

久疤K

najin 发表于 2017-9-30 10:59
用的matlab
结果是：
>> Untitled

额，为啥这么快。。。

王小召

最多解为：8
用时：7.80005 秒

1. import time
   
2. 
   
3. 
   
4. def cal_result():
   
5.     result = []
   
6.     for p in range(12, 1000):
   
7.         count = 0
   
8.         for x in range(int(p//3), p):
   
9.             for y in range(x-1, 0, -1):
   
10.                 if x + y >= p:
    
11.                     break
    
12.                 else:
    
13.                     z = p - x - y
    
14.                     if z <= y:
    
15.                         if x**2 == y**2 + z**2:
    
16.                             count += 1
    
17.                     else:
    
18.                         break
    
19.         if count != 0:
    
20.             result.append((p, count))
    
21.     return result
    
22. 
    
23. result = cal_result()
    
24. max_result = max(each[1] for each in result)
    
25. print("最多解为：{}\n用时：{} 秒".format(max_result, time.process_time()))

复制代码

debuggerzh

840

Process returned 0 (0x0)   execution time : 0.034 s
Press any key to continue.

                               
登录/注册后可看大图

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. 
   
5. int sol(int p,int x){
   
6.   int res = 0;
   
7.   for (int i = 2;i <= sqrt(x);i++){
   
8.     if (x % i == 0){
   
9.       if (x / i < p && i < p) res++;
   
10.     }
    
11.   }
    
12.   return res;
    
13. }
    
14. 
    
15. int main(){
    
16.   int ans;
    
17.   int max_sol = 0;
    
18.   for (int p = 10;p <= 1000;p+=2){
    
19.     int t = sol(p,p*p/2);
    
20.     if (t > max_sol) {max_sol = t;  ans = p;}
    
21.   }
    
22.   cout << ans << endl;
    
23.   return 0;
    
24. }
    

复制代码

a1351468657

1. #include <stdio.h>
   
2. 
   
3. main()
   
4. {
   
5.         int i, j, k, a, b, c, max = 0, count = 0, num;
   
6.        
   
7.         for (i = 120; i < 1000; i++)
   
8.         {
   
9.                 j = i / 3;//a不可能超过i的三分之一
   
10.                 for (a = 10; a <= j; a++)
    
11.                 {
    
12.                         k = i / 2;//b不可能超过i的二分之一
    
13.                         for (b = a; b <= k; b++)
    
14.                         {
    
15.                                 c = i - a - b;
    
16.                                 if (a * a + b * b == c * c)
    
17.                                 {
    
18.                                         count++;
    
19.                                 }
    
20.                                 if (a * a + b * b > c * c)
    
21.                                 {
    
22.                                         break;
    
23.                                 }
    
24.                         }               
    
25.                 }
    
26.                 if (max < count)
    
27.                 {
    
28.                         max = count;
    
29.                         num = i;       
    
30.                 }
    
31.                 count = 0;       
    
32.         }
    
33.         printf("%d %d\n", num, max);
    
34.        
    
35. }

复制代码

840 8组

guosl

1. /*
   
2. 应用本原直角三角形a=x^2 - y^2,b=2*x*y,c=x^2 + y^2的公式来枚举
   
3. 答案：840
   
4. 耗时：0.0000257秒
   
5. */
   
6. #include <iostream>
   
7. #include <cmath>
   
8. using namespace std;
   
9. 
   
10. int nCount[1001];
    
11. 
    
12. int gcd(int x, int y)
    
13. {
    
14.   if (y == 0)
    
15.     return x;
    
16.   int z = x % y;
    
17.   while (z != 0)
    
18.   {
    
19.     x = y;
    
20.     y = z;
    
21.     z = x % y;
    
22.   }
    
23.   return y;
    
24. }
    
25. 
    
26. int main(void)
    
27. {
    
28.   for (int i = 6; i <= 500; ++i)//搜索边长为2*i的本原直角三角形
    
29.   {
    
30.     for (int x = 2; x < sqrt((double)i); ++x)//枚举大参数
    
31.     {
    
32.       if (i % x == 0)
    
33.       {
    
34.         int y = i / x;
    
35.         y -= x;//求出小参数
    
36.         //检查这两个参数是否可以构成本原直角三角形
    
37.         if (x > y && gcd(x, y) == 1 && ((x - y) & 1) != 0)
    
38.         {
    
39.           int k = 2 * i;
    
40.           int j = 1;
    
41.           while (k * j <= 1000)
    
42.           {
    
43.             ++nCount[k * j];//计数边长为k*j的直角三角形的个数
    
44.             ++j;
    
45.           }
    
46.         }
    
47.       }
    
48.     }
    
49.   }
    
50.   //求出可以构成最多直角三角形的边长
    
51.   int nMaxCount = 0, nVal;
    
52.   for (int i = 12; i <= 1000; i += 2)
    
53.   {
    
54.     if (nCount[i] > nMaxCount)
    
55.     {
    
56.       nMaxCount = nCount[i];
    
57.       nVal = i;
    
58.     }
    
59.   }
    
60.   cout << nVal << endl;
    
61.   return 0;
    
62. }
    

复制代码

B1tetheDust

1. import time as t
   
2. 
   
3. start = t.perf_counter()
   
4. p_list = {}
   
5. for a in range(1, 333):
   
6.     for b in range(a, int(1000 - a / 2)):
   
7.         for c in range(b, (1000 - a - b)):
   
8.             if a + b < c:
   
9.                 break
   
10.             elif a ** 2 + b ** 2 == c ** 2:
    
11.                 try:
    
12.                     p_list[a + b + c] += 1
    
13.                 except KeyError:
    
14.                     p_list[a + b + c] = 1
    
15. 
    
16. print(max(p_list, key=lambda x: p_list[x]))
    
17. print("It costs %f s" % (t.perf_counter() - start))
    

复制代码

840
It costs 4.748411 s

mathtimes

1. $ time ./main
   
2. 8 840
   
3. 
   
4. real        0m0.034s
   
5. user        0m0.034s
   
6. sys        0m0.000s

复制代码

1. fn f(x: usize) -> usize {
   
2.     let mut count = 0;
   
3.     for i in 1..x/3 {
   
4.         for j in i..x/2 {
   
5.             if i*i + j*j == (x-i-j)*(x-i-j) {
   
6.                 count += 1;
   
7.             }
   
8.         }
   
9.     }
   
10.     count
    
11. }
    
12. 
    
13. fn main () {
    
14.     let mut max=0;
    
15.     let mut max_i = 0;
    
16.     for i in 1..1000 {
    
17.         if f(i) > max {
    
18.             max = f(i);
    
19.             max_i = i;
    
20.         }
    
21.     }
    
22.     println!("{max} {max_i}");
    
23. }

复制代码