题目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
请按任意键继续.


代码写得好辣鸡

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
//输出p(周长)的解组
int maxx = 0,maxN;

bool isin(vector<string> &result,string str)
{
        for (int n =0;n<result.size();n++)
        {
                if(result[n] == str)
                        return true;
        }
        return false;
}
void calc(int p)
{

        int n = 0;
        int j = 0;
        vector<string> result;
        
                for (int i=1;i<p;i++)
                {
                        for (int b=i;b<p;b++)
                        {
                                int c = p-i-b;
                                if(c<=0)
                                        continue;
                                        int bian[3]={i,b,c};
                                        sort(bian,bian+3); //斜边是bian[2]

                                        if(i+b+c == p)
                                        {

                                        
                                                //直角三角形
                                                if(bian[0]*bian[0] + bian[1]*bian[1] == bian[2]*bian[2])
                                                {
                                                        //
                                                        string temp;
                                                        char buf[20];
                                                        itoa(bian[0],buf,10);
                                                        temp = buf;
                                                        temp+=',';
                                                        itoa(bian[1],buf,10);
                                                        temp += buf;
                                                        temp+=',';
                                                        itoa(bian[2],buf,10);
                                                        temp += buf;
                                                        

                                                        if(!isin(result,temp))
                                                        result.push_back(temp);
                                                }

                                        }

                                }
                        
                }
                
                if(result.size())
                        std::cout<<"周长:"<<p<<endl;
                for (int i = 0; i < result.size(); i++)
                {
                        std::cout<<result[i]<<endl;
                }
                

                if(result.size()>maxx)
                {
                        maxN = p;
                        maxx = result.size();
                }
}
int main(void)
{
        
        for (int i = 2;i<=300;i++)
        {
                calc(i);
        }
        std::cout<<"1000下最多组解的有"<<maxx<<endl;
        std::cout<<"为周长="<<maxN;
        calc(maxN);
        return 0;
}

愤怒的大头菇

import math
def Jie(x):
      list1 = []
      for i in range(1,x):
            temp = math.sqrt(x**2 - i**2)
            if len(str(temp)) == 3 or len(str(temp))==4 or len(str(temp))== 5:
                  total = temp + x + i
                  list1.append([total,temp,x,i])
      return list1
list1 = []
for i in range(1000):
      total  = Jie(i)
      for each in total:
            if each!=[]and each[0]<1000:
                  list1.append(each)
list2=[]                 
for each in list1:
      each.sort()
      if each not in list2:
            list2.append(each)
list3 = []
for each in list2:
      list3.append(each[-1])
list4 = []
for each in list3:
      if each not in list4:
            list4.append(each)
temp = {}.fromkeys([i for i in list4],0)
for each in list3:
      if each in temp:
            temp[each] += 1
first = 0
for each in temp.values():
      if first < each:
            first = each
for each in temp:
      if temp[each] == first:
            print(each)

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

jerryxjr1220

8组不重复解，周长840.

lst=[]
for a in range(1,250):
  for b in range(a,500-a):
    for c in range(b,500):
      if a*a+b*b==c*c:
        p=a+b+c
        lst.append([p,a,b,c])
cal=[]
master = {}
for each in lst:
  if each[0] not in cal:
    cal.append(each[0])
    master[each[0]]= 1
  else:
    master[each[0]]+=1
print (master)

芒果加黄桃

# encoding:utf-8
# 寻找周长1000以下，能够成直角三角形最多的数
from time import time
def euler039():
    maxcount = 0
    result = []
    for p in range(12, 1001):
        count = 0
        tmp = []
        for i in range(int(p / (1 + 2 ** 0.5)) - 1, int(p / 2) + 1):
            for j in range(int(i / (2 ** 0.5)) - 1, i):
                if i ** 2 == j ** 2 + (p - i - j) ** 2:
                    count += 1
                    tmp.append((p, i, j, (p - i - j)))
                    break
        if count > maxcount:
            result = tmp
            maxcount = count
    print(maxcount, result)
if __name__ == '__main__':
    start = time() 
    euler039()
    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

%% Problem39.m
% 最后编辑时间：17-06-14 22:34
% 如果p是直角三角形{a,b,c}的周长,1000以下的p中哪一个具有最多的解? 
% Problem39所用时间为： 2.1683秒
% Problem39的答案为： 840
function Output = Problem39()
tic

Store = [];
for a = 1:250
    for b = a+1:500 - a  %根据楼上老大的解法，这点不懂
        for c = b+1:500
            if c^2 == a^2 + b^2
                Store = [Store,a+b+c];
            end
        end
    end
end

Sta = tabulate(Store);  %找到所有解的比例

Value = Sta(:,1);
Ration = Sta(:,3);

Set = Ration == max(Ration);

Output = Value(Set);
 
toc
disp('此代码使用matlab编程')
disp(['Problem39所用时间为： ',num2str(toc),'秒'])
disp(['Problem39的答案为： ',num2str(Output)])
end

najin

用的matlab
结果是：
>> Untitled

ans =

   840

时间已过 0.029216 秒。
>>

久疤K

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

额，为啥这么快。。。

王小召

最多解为：8
用时：7.80005 秒

import time


def cal_result():
    result = []
    for p in range(12, 1000):
        count = 0
        for x in range(int(p//3), p):
            for y in range(x-1, 0, -1):
                if x + y >= p:
                    break
                else:
                    z = p - x - y
                    if z <= y:
                        if x**2 == y**2 + z**2:
                            count += 1
                    else:
                        break
        if count != 0:
            result.append((p, count))
    return result

result = cal_result()
max_result = max(each[1] for each in result)
print("最多解为：{}\n用时：{} 秒".format(max_result, time.process_time()))

debuggerzh

840

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

                               
登录/注册后可看大图

#include<iostream>
#include<cmath>
using namespace std;

int sol(int p,int x){
  int res = 0;
  for (int i = 2;i <= sqrt(x);i++){
    if (x % i == 0){
      if (x / i < p && i < p) res++;
    }
  }
  return res;
}

int main(){
  int ans;
  int max_sol = 0;
  for (int p = 10;p <= 1000;p+=2){
    int t = sol(p,p*p/2);
    if (t > max_sol) {max_sol = t;  ans = p;}
  }
  cout << ans << endl;
  return 0;
}

a1351468657

#include <stdio.h>

main()
{
        int i, j, k, a, b, c, max = 0, count = 0, num;
        
        for (i = 120; i < 1000; i++)
        {
                j = i / 3;//a不可能超过i的三分之一
                for (a = 10; a <= j; a++)
                {
                        k = i / 2;//b不可能超过i的二分之一
                        for (b = a; b <= k; b++)
                        {
                                c = i - a - b;
                                if (a * a + b * b == c * c)
                                {
                                        count++;
                                }
                                if (a * a + b * b > c * c)
                                {
                                        break;
                                }
                        }                
                }
                if (max < count)
                {
                        max = count;
                        num = i;        
                }
                count = 0;        
        }
        printf("%d %d\n", num, max);
        
}

840 8组

guosl

/*
应用本原直角三角形a=x^2 - y^2,b=2*x*y,c=x^2 + y^2的公式来枚举
答案：840
耗时：0.0000257秒
*/
#include <iostream>
#include <cmath>
using namespace std;

int nCount[1001];

int gcd(int x, int y)
{
  if (y == 0)
    return x;
  int z = x % y;
  while (z != 0)
  {
    x = y;
    y = z;
    z = x % y;
  }
  return y;
}

int main(void)
{
  for (int i = 6; i <= 500; ++i)//搜索边长为2*i的本原直角三角形
  {
    for (int x = 2; x < sqrt((double)i); ++x)//枚举大参数
    {
      if (i % x == 0)
      {
        int y = i / x;
        y -= x;//求出小参数
        //检查这两个参数是否可以构成本原直角三角形
        if (x > y && gcd(x, y) == 1 && ((x - y) & 1) != 0)
        {
          int k = 2 * i;
          int j = 1;
          while (k * j <= 1000)
          {
            ++nCount[k * j];//计数边长为k*j的直角三角形的个数
            ++j;
          }
        }
      }
    }
  }
  //求出可以构成最多直角三角形的边长
  int nMaxCount = 0, nVal;
  for (int i = 12; i <= 1000; i += 2)
  {
    if (nCount[i] > nMaxCount)
    {
      nMaxCount = nCount[i];
      nVal = i;
    }
  }
  cout << nVal << endl;
  return 0;
}

B1tetheDust

import time as t

start = t.perf_counter()
p_list = {}
for a in range(1, 333):
    for b in range(a, int(1000 - a / 2)):
        for c in range(b, (1000 - a - b)):
            if a + b < c:
                break
            elif a ** 2 + b ** 2 == c ** 2:
                try:
                    p_list[a + b + c] += 1
                except KeyError:
                    p_list[a + b + c] = 1

print(max(p_list, key=lambda x: p_list[x]))
print("It costs %f s" % (t.perf_counter() - start))

840
It costs 4.748411 s

mathtimes

$ time ./main
8 840

real        0m0.034s
user        0m0.034s
sys        0m0.000s

fn f(x: usize) -> usize {
    let mut count = 0;
    for i in 1..x/3 {
        for j in i..x/2 {
            if i*i + j*j == (x-i-j)*(x-i-j) {
                count += 1;
            }
        }
    }
    count
}

fn main () {
    let mut max=0;
    let mut max_i = 0;
    for i in 1..1000 {
        if f(i) > max {
            max = f(i);
            max_i = i;
        }
    }
    println!("{max} {max_i}");
}