题目39：如果p是直角三角形{a,b,c}的周长，1000以下的p中哪一个具有最多的解？
Integer right trianglesIf 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 == 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={i,b,c};
sort(bian,bian+3); //斜边是bian
if(i+b+c == p)
{
//直角三角形
if(bian*bian + bian*bian == bian*bian)
{
//
string temp;
char buf;
itoa(bian,buf,10);
temp = buf;
temp+=',';
itoa(bian,buf,10);
temp += buf;
temp+=',';
itoa(bian,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<<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()
return list1
list1 = []
for i in range(1000):
total= Jie(i)
for each in total:
if each!=[]and each<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(,0)
for each in list3:
if each in temp:
temp += 1
first = 0
for each in temp.values():
if first < each:
first = each
for each in temp:
if temp == first:
print(each)
写的好纠结，最多的解有8组，周长是840 本帖最后由 永恒的蓝色梦想 于 2020-7-2 18:40 编辑
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()
cal=[]
master = {}
for each in lst:
if each not in cal:
cal.append(each)
master]= 1
else:
master]+=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 = ;
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
用的matlab
结果是：
>> Untitled
ans =
840
时间已过 0.029216 秒。
>> 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 for each in result)
print("最多解为：{}\n用时：{} 秒".format(max_result, time.process_time())) 840
Process returned 0 (0x0) execution time : 0.034 s
Press any key to continue.
https://wx3.sinaimg.cn/mw690/0081qlg6ly1ghocfd1813j318d0av76h.jpg
#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;
}
#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组 /*
应用本原直角三角形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;
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的直角三角形的个数
++j;
}
}
}
}
}
//求出可以构成最多直角三角形的边长
int nMaxCount = 0, nVal;
for (int i = 12; i <= 1000; i += 2)
{
if (nCount > nMaxCount)
{
nMaxCount = nCount;
nVal = i;
}
}
cout << nVal << endl;
return 0;
}
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 += 1
except KeyError:
p_list = 1
print(max(p_list, key=lambda x: p_list))
print("It costs %f s" % (t.perf_counter() - start))
840
It costs 4.748411 s $ 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}");
}
页:
[1]