출처 : http://euler.synap.co.kr/prob_detail.php?id=39
세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있다.
{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마인가?
52개의 풀이가 있습니다.
[Python]
import math
def Star(n):
a = 0
c = 0.0
p =n/2
_list = []
while a < p:
a += 1
for b in range(a,p-a):
c = math.sqrt(a*a + b*b)
if c % 1 == 0:
_list.append( a+b+c )
return max(set(_list),key=_list.count)
print Star(1000)
print Star(10000)
840.0
5040.0
```
포트란입니다 그냥 무식하게 반복문 돌렸습니다
출력은 둘레 840일 때 16가지 입니다만 a, b가 대칭인 경우를 생각해보면 8가지 같습니다
program codingdojo451
integer p, a, b, c, count, mcount, mnum
mcount=0
do p=3, 1000
count=0
do a=1, p-2
do b=1, p-a-1
c=p-a-b
if(a**2 + b**2 .EQ. c**2) then
count=count+1
end if
end do
end do
if(count .GT. mcount) then
mcount=count
mnum=p
end if
end do
print *,mcount,mnum
pause
end program codingdojo451
직각삼각형의 다음과 같은 두가지 법칙을 이용하여 문제를 풀어 보았습니다.
python 2.7
import math
def right_triangle(n):
found = []
count = 0
for a in range(3, n+1, 3):
if a in found: continue
for b in range(1, n+1-a):
c = math.sqrt(a**2+b**2)
if a+b+c == n:
found+=[a,b,c]
count+=1
return count
m = -1
found = -1
for i in range(1, 1001):
v = right_triangle(i)
if v > m:
m = v
found = i
print found, m
대략 30초정도 걸리네요. 더 좋은 알고리즘을 연구해 봐야 할 것 같습니다.
세 변의 길이를 a,b,c라 하고 둘레를 p라 하면 a^2+b^2 = c a+b+c = p
이로부터 c = p-a-b이므로 a^2+b^2 = (p-a-b)
그런데 a^2+b^2 = ((a+b)^2 + (a-b)^2)/2
이로부터 2c^2 = (a+b)^2 + (a-b)^2 = (p-c)^2 + (p-c-2b)^2 이 식을 정리하면 c = - (2b^2 - 2bp - p^2) / (2b-2p)
a+b = p-c에 위의 c를 대입하면 a+b = (p^2 - 2b^2) / (2p-2b) b를 우변으로 이항하면 a = p(2b-p) / 2(b-p)
따라서 a,b,c를 모두 p와 b의 식으로 나타낼 수 있음.
따라서 루프는 p와 b에 대해서 두개만 돌리면 됨.
#include <stdio.h>
int main(void) {
int p;
int a, b, c;
int max_p[2]={-1, -1};
for(p=3; p <= 1000; ++p){
int cnt = 0;
for(b = p-1; b >= 0; --b){
c = - ((2*b*b) - 2*(b*p) + p*p) / (2*(b - p));
a = p*(2*b-p)/(2*(b-p));
if(a > b) break;
if(a>0 && c>0 && a+b+c == p){
cnt++;
}
}
if(cnt > max_p[1]) {
max_p[0] = p;
max_p[1] = cnt;
}
}
printf("%d\n", max_p[0]);
return 0;
}
[Python 2.7.3] 위에 좋은 알고리즘이 많아 약간 무식(?) 하지만 적절히 loop를 최소화하는 방법을 써보았습니다. 빗변 c는 a,b보다 작지않으며, 닮은꼴 삼각형을 배제시키기위해서 b 가 a보다 클때만 연산을 수행하면 중복 연산을 피할 수 있다고 생각했습니다. a+b+c가 1000 이상이면 c를 더 이상 진행 시킬 필요가 없고, b,c의 loop 시작 index를 아래 코드처럼 정의하면1000^3 보다는 훨씬 적은 횟수로 돌 수 있네요.
pp = [0]*1001
for a in range(1,1000) :
for b in range(a,1000) :
for c in range(b,1000) :
_sum = a+b+c
if _sum <= 1000 :
if (c*c)==(a*a+b*b) :
temp = pp[_sum]
pp[_sum] = temp+1
print "a,b,c = ",a,b,c
print "pp and sum",pp[a+b+c], a+b+c
else :
break
temp = max(pp)
for i in range(1001) :
if temp==pp[i] :
print i,temp
제 노트북에서 18초 나오네요..
840 8
18.0680000782
C언어로 작성했습니다.
/*
사용한 조건:
a^2 + b^2 = c^2
a + b > c
그리고 a, b, c 중 하나는 반드시 3의 배수다.
여기서 둘레 p = a + b + c라고 한다면,
a^2 + b^2 = (p - a - b)^2
이고, 위의 식을 a에 대해 정리한다면,
a = (2bp - p^2) / 2(b-p) --- (1)
그리고 이 식과 p = a + b + c를 a + b > c에 대입하면
p(2b-p)/2(b-p) > p/2 - b
이고, 이 식을 정리하면
b(2b-p)<0
따라서 유효한 b의 범위는...
0 < b < p/2 --- (2)
그리고 여기서 이대로만 루프를 돌린다면 만일 p = 12인 경우
(a, b, c)의 집합이 (3, 4, 5), (4, 3, 5)가 나와 동일한 삼각형에 대해 중복 연산을 하게 되므로 쓸데없는 루프를 돌게 됩니다.
따라서 저는 a < b라는 조건을 추가했습니다.
a < b
위의 식에 (1) 식을 넣는다면
p(2b-p)/2(b-p) < b
위의 식을 정리하여 b의 범위를 구한다면
(2-2^0.5)p/2 < b < (2+2^0.5)p/2
가 나오는데, 이 때 (2)번 식에서 나타나는 b의 범위와 겹치는 부분만 따진다면
(2-2^0.5)p/2 < b < p/2 -- (3)
이 됩니다.
또한 a, b, c 중 하나는 반드시 3의 배수이므로, 가장 작은 3의 배수인 3을 포함하는 세 정수의 조합은
(3, 4, 5)이므로 p의 가능한 최소값은 3+4+5인 12가 됩니다.
따라서 저는 p는 12부터 1000까지 루프를 돌고, b는 (2-2^0.5)p/2 < b < p/2의 범 위내에서 루프를 돌게 했습니다.
Microsoft Visual Studio 2013로 작성했습니다.
*/
#include <stdio.h>
#include <math.h>
int main(void) {
unsigned int threshold = 0;
printf("Input the threshold : ");
scanf_s("%u", &threshold); // MSVS 2013에서는 scanf를 쓰지 못하게 함.
if (threshold == 0 || threshold < 12) {
printf("Invalid value.");
return -1;
}
unsigned int result[2] = { 0 };
unsigned int loopCount = 0;
float sqrt_2 = (float)sqrt(2);
for (size_t p = 12; p <= threshold; p++) {
size_t b_limit = p / 2;
if (p % 2 != 0) {
b_limit++;
}
float b_limit_lower_llf = (2 - sqrt_2) / 2.0f * (float)p;
size_t b_limit_lower = (size_t)b_limit_lower_llf;
if (b_limit_lower < b_limit_lower_llf) {
b_limit_lower++;
}
unsigned int match_count = 0;
float llf_a = 0;
size_t a = 0;
for (size_t b = b_limit_lower; b < b_limit; b++) {
llf_a = (float)p * (2 * (float)b - (float)p) / (2 * ((float)b - (float)p));
a = (size_t)llf_a;
if (llf_a == a) {
match_count++;
}
loopCount++;
}
if (match_count > result[1]) {
result[0] = p;
result[1] = match_count;
}
}
printf("Circumference with the most right triangles with integer sides = %u\n", result[0]);
printf("Count of created triangles with the conditions = %u\n", result[1]);
printf("Total loop count = %u\n", loopCount);
return 0;
}
/* 수행 결과:
Input the threshold : 1000
Circumference with the most right triangles with integer sides = 840
Count of created triangles with the conditions = 8
Total loop count = 103396
계속하려면 아무 키나 누르십시오 . . .
*/
그래도 약간 마음에 들지 않아 다른 방법을 좀 찾아봤습니다. 이번에는 검색 방법 자체를 다르게 했습니다. 또한 더블 링크드 리스트를 썼기 때문에, C로 짠 버전도 있지만 너무 길어서 생략하고, C++에서 STL 라이브러리를 이용한 버전만 올립니다. 탐색에 사용한 방법은 아래의 링크에 있습니다. http://ko.wikipedia.org/wiki/피타고라스_수
//
// main.cpp
// CodingDoJang-451-CPP
//
// Created by Chrome-MBPR on 7/2/14.
// Copyright (c) 2014 cr2025x1. All rights reserved.
//
#include <iostream>
#include <list>
#include <cmath>
using namespace std;
struct PT {
size_t a;
size_t b;
size_t c;
bool primitive;
};
typedef struct PT PT;
class cPT_pair {
protected:
size_t _p;
list<PT> _pt_List;
public:
const size_t &p;
const list<PT> &pt_List;
cPT_pair() : p(_p), pt_List(_pt_List) {
setP(_p);
}
void setP(size_t p) {
this->_p = p;
}
list<PT>* set_pt_List() {
return &_pt_List;
}
};
class cPT_pair_set : public list<cPT_pair*> {
public:
virtual ~cPT_pair_set() {
for (list<cPT_pair*>::iterator itr = this->begin(); itr != this->end(); advance(itr, 1)) {
delete *itr;
}
}
};
void print_cPTList(list<cPT_pair*>* cPTList, bool primitive_mark);
int main(int argc, const char * argv[])
{
size_t threshold = 0;
cout << "Input the threshold: ";
cin >> threshold;
cout << "Searching primitive Pythagorean triples..." << endl;
cPT_pair_set* cPTList = new cPT_pair_set;
size_t loopCount_1st = 0;
// 짝수인 p만이 자연수인 피타고라스 수의 합이 될 수 있다. (p = 2m^2 + 2mn)
for (size_t p = 12; p <= threshold; p += 2) {
// a^2 + b^2 = c^2이고 서로소인 (a, b, c)는 아래와 같이 m, n을 통해 표현할 수 있다.
// a = m^2 - n^2
// b = 2mn
// c = 2m^2 - n^2
// m>n, m, n은 자연수, m+n은 홀수
//
// p = a + b + c
// = 2m^2 + 2mn
// n = p/(2m) - m
// n은 자연수이므로 p/(2m)-m > 0, 식을 정리하면
// -(p/2)^0.5 < m < (p/2)^0.5
// 또한 m > n이므로 p/(2m)-m < m, 식을 정리하면
// m < -p^0.5/2 or m > p^0.5/2
// 두 범위의 교차부분은 0.5p^0.5 < m < (p/2)^0.5
//
// 즉 m은 저 범위 내에서 루프를 돌린다.
// 이렇게 만들어진 a, b, c는 원시 피타고라스 수가 된다.
// 원시 피타고라스 수: a, b, c의 최대공약수가 1인 피타고라스 수. ex. (3, 4, 5), (5, 12, 13),
size_t m_LowerBound = (size_t)floor((pow(p, 0.5f) / 2.0f));
size_t m_UpperBound = (size_t)ceil(pow(p / 2.0f, 0.5f));
size_t n = 0;
for (size_t m = m_LowerBound + 1; m < m_UpperBound; m++) {
loopCount_1st++;
if (p % (2 * m) != 0) {
// n이 자연수가 될 수 없음.
continue;
}
n = p / (2 * m) - m;
if ((m + n) % 2 == 0) {
// m + n이 홀수가 아니다.
continue;
}
if ((m > 1 && n > 1) && (m % n == 0 || n % m == 0)) {
// m과 n이 서로소가 아니다.
continue;
}
size_t m_2 = m * m;
size_t n_2 = n * n;
size_t a = m_2 - n_2;
size_t b = 2 * m * n;
size_t c = m_2 + n_2;
PT newPT;
newPT.a = a;
newPT.b = b;
newPT.c = c;
newPT.primitive = true;
unsigned char isNewNodeNeeded = 1;
list<cPT_pair*>::iterator lastNode = cPTList->end();
advance(lastNode, -1);
if (cPTList->size() > 0) {
cPT_pair* last_cPT_pair = *lastNode;
if (last_cPT_pair->p == p) {
isNewNodeNeeded = 0;
last_cPT_pair->set_pt_List()->push_back(newPT);
}
}
if (isNewNodeNeeded) {
cPT_pair* new_cPT_pair = new cPT_pair;
new_cPT_pair->setP(p);
new_cPT_pair->set_pt_List()->push_back(newPT);
cPTList->push_back(new_cPT_pair);
}
}
}
// 찾아낸 원시 피타고라수 수들을 출력
cout << "Printing found primitive Pythagorean triples..." << endl;
cout << "p : circumference of the right triangle" << endl;
print_cPTList(cPTList, false);
size_t cPT_pair_listCount = cPTList->size();
cout << "Total count of found p with Pythagorean triples = " << cPT_pair_listCount << endl;
cout << "Total loop count during the search for primitive Pythagorean triples = " << loopCount_1st << endl;
// 원시형이 아닌 피타고라스 수에 대한 탐색
cout << "Searching and adding non-primitive Pythagorean triples..." << endl;
size_t loopCount_2nd = 0;
size_t maxP[2] = { 0 }; // [0] = 현재까지 가장 많은 피타고라스 수를 가지는 p, [1] = [0]에 있는 p가 가진 피타고라스 수 세트의 개수
size_t p_threshold = threshold;
// p의 초기 값을 짝수로 짜맞춘다.
if (p_threshold % 2 != 0) {
p_threshold--;
}
// 위에서 구한 원시 피타고라스 수를 가지고 있는 링크드 어레이에 원시형이 아닌 피타고라스 수들을 추가시킨다.
list<cPT_pair*>::iterator insertionPoint = cPTList->end();
advance(insertionPoint, -1);
size_t foundCount = 0;
for (size_t p = p_threshold; p >= 12; p -= 2) {
foundCount = 0;
// 삽입 지점(insertion point)을 항상 현재 p보다 높은 값과 낮은 값끼리의 경계점에 둔다. 만일 현재 p와 같은 값을 가진 노드가 있다면 그 노드를 삽입지점으로 고르며, 없다면 현재 p보다 작은 값 중 가장 큰 값을 가지는 노드를 고른다.
// 위의 알고리즘 결과로 나오는 리스트의 각 노드의 p는 앞에서 뒤로 오름차순이다.
while ((*insertionPoint)->p > p) {
advance(insertionPoint, -1);
}
// 삽입 지점 노드를 기준으로, 앞쪽을 향해 노드들을 순차적으로 읽어나가 노드의 p값을 비교한다.
// 삽입 지점 노드와 그 앞의 노드들은 모두 모두 원시 피타고라스 수만을 담고 있다.
list<cPT_pair*>::iterator current_cPT_pairNode = insertionPoint;
bool isWritingNodeDecided = false;
list<cPT_pair*>::iterator writingNode;
list<PT>* writingPTList = nullptr;
while (1) {
isWritingNodeDecided = false;
cPT_pair* current_cPT_pair = *current_cPT_pairNode;
loopCount_2nd++;
// 원시 피타고라스 수를 가지는 둘레값이 현재 p값의 약수라면, 현재 p값을 둘레값으로 나눈 값을 원시 피타고라스 수에 곱한다면 현재 p값을 둘레로 가지는 피타고라스 수(원시는 아닌)가 나온다.
if (p % current_cPT_pair->p == 0) {
size_t commonDivisor = p / current_cPT_pair->p;
if (commonDivisor == 1) {
// 1배수다 == 현재 검사 중인 노드의 p값과 현재 p값은 같다. 이 때는 아래의 작업을 할 경우 기존 값과 중복되는 똑같은 값이 추가 저장되므로, 값을 추가 저장하는 아래의 작업을 하면 안 된다.
foundCount++;
}
else {
if (isWritingNodeDecided == false) {
isWritingNodeDecided = true;
// 삽입지점에 현재의 p값을 가진 노드가 있다. 노드를 추가 삽입할 필요성이 없으므로 이 노드를 그대로 활용한다.
if ((*insertionPoint)->p == p) {
writingNode = insertionPoint;
}
else {
// 현재의 p값을 가지는 노드가 없으므로, 노드를 삽입지점의 뒷편에 추가 삽입한다.
cPT_pair* new_cPT_pair = new cPT_pair;
new_cPT_pair->setP(p);
writingNode = insertionPoint;
advance(writingNode, 1);
cPTList->insert(writingNode, new_cPT_pair);
advance(writingNode, -1);
}
writingPTList = (*writingNode)->set_pt_List();
}
// 현재 읽어들인 노드가 가지고 있는 원시 피타고라스 수 세트에 구해둔 배수를 곱해 현재 p값을 둘레로 가지는 비원시 피타고라스 수 세트를 만들어 현재 p값을 가지고 있는 기록 중인 노드의 하위 링크드 리스트에 추가한다.
const list<PT>& currentPTList = current_cPT_pair->pt_List;
for (list<PT>::const_iterator currentPTNode = currentPTList.cbegin();
currentPTNode != currentPTList.cend();
advance(currentPTNode, 1)) {
PT currentPT = *currentPTNode;
PT newPT;
newPT.a = currentPT.a * commonDivisor;
newPT.b = currentPT.b * commonDivisor;
newPT.c = currentPT.c * commonDivisor;
newPT.primitive = 0;
writingPTList->push_back(newPT);
foundCount++;
}
}
}
// 읽어낸 노드의 바로 앞 노드를 지정한다. 위에서 삽입한 노드들은 모두 삽입지점의 뒤에 추가되었다.
// 따라서 그 어떤 루프도 이전 루프에서 추가한 비원시 피타고라스 수가 담긴 노드를 접근하게 되는 비효율적인 경우가 생기지 않는다.
if (current_cPT_pairNode == cPTList->begin()) {
// 맨 앞 노드임을 의미하므로, 현재 p값에 대한 작업을 중지한다.
break;
}
else {
advance(current_cPT_pairNode, -1);
}
}
// 가장 많은 피타고라스 수를 가진 둘레값을 현재 값과 비교해 저장
if (maxP[1] < foundCount) {
maxP[0] = p;
maxP[1] = foundCount;
}
}
cout << "Printing found entire Pythagorean triples..." << endl;
cout << "p : circumference of the right triangle" << endl;
print_cPTList(cPTList, 1);
cout << "Total loop count during the search for all Pythagorean triples = " << loopCount_2nd << endl;
cout << "Circumference P with the most Pythagorean triples = " << maxP[0] << "(" << maxP[1] << " sets)" << endl;
cout << "Total loop during entire operations = " << loopCount_1st + loopCount_2nd << endl;
delete cPTList;
return 0;
}
void print_cPTList(list<cPT_pair*>* cPTList, bool primitive_mark) {
for (list<cPT_pair*>::iterator current_cPT_pairNode = cPTList->begin();
current_cPT_pairNode != cPTList->end();
advance(current_cPT_pairNode, 1)) {
cPT_pair* current_cPT_pair = *current_cPT_pairNode;
const list<PT>& currentPTList = current_cPT_pair->pt_List;
for (list<PT>::const_iterator currentPTNode = currentPTList.cbegin();
currentPTNode != currentPTList.cend();
advance(currentPTNode, 1)) {
cout << "p = " << current_cPT_pair->p << ", (a, b, c) = (" << currentPTNode->a << ", " << currentPTNode->b << ", " << currentPTNode->c << ")";
if (currentPTNode->primitive && primitive_mark) {
cout << " (primitive)";
}
cout << endl;
}
}
}
/*
실행결과:
Input the threshold: 1000
Searching primitive Pythagorean triples...
Printing found primitive Pythagorean triples...
p : circumference of the right triangle
(중략)
Total count of found p with Pythagorean triples = 75
Total loop count during the search for primitive Pythagorean triples = 2169
Searching and adding non-primitive Pythagorean triples...
Printing found entire Pythagorean triples...
p : circumference of the right triangle
(중략)
p = 840, (a, b, c) = (399, 40, 401) (primitive)
p = 840, (a, b, c) = (390, 56, 394)
p = 840, (a, b, c) = (350, 120, 370)
p = 840, (a, b, c) = (252, 240, 348)
p = 840, (a, b, c) = (105, 360, 375)
p = 840, (a, b, c) = (315, 168, 357)
p = 840, (a, b, c) = (140, 336, 364)
p = 840, (a, b, c) = (210, 280, 350)
(중략)
Total loop count during the search for all Pythagorean triples = 18409
Circumference P with the most Pythagorean triples = 840(8 sets)
Total loop during entire operations = 20578
Program ended with exit code: 0
*/
최대한 더블 링크드 리스트의 장점을 살려서 썼습니다. 복사 작업 등을 제외하고 조건에 맞는 숫자를 찾기 위해 도는 루프의 수를 이번에는 20578회로 줄일 수 있었습니다. 2013년 후기형 맥북 프로 레티나 15인치 기준으로 거의 시작 직후에 답이 나오네요.
Xcode 5.1.1로 작성하였습니다.
#python 3.2.5
def calc_c(a, b):
assert(a > 0)
if b < a:
return False
assert(a <= b)
sq = a*a + b*b
sqa = a**a
for c in range(a, sq):
if sq == c*c:
return c
return False
def calc_b(L, a):
numerator = L*L - 2*L*a
if numerator < 0: return False
denominator = 2 * (L - a)
if 0 == numerator % denominator:
return numerator//denominator
return False
def abr(L):
rt = []
hL = (L // 2) * 2
for a in range(1, hL):
b = calc_b(L, a)
if not b: continue
c = calc_c(a, b)
if not c: continue
#yield a
rt.append((a, b, c))
return rt
def main():
rt = dict(len=1, lst=[])
L = 0
for l in range(1, 1001):
tmp = abr(l)
if len(tmp) > L:
L = len(tmp)
rt['len'] = l
rt['lst'] = tmp
print(L, rt['len'], rt['lst'])
'''
8
840
[(40, 399, 401), (56, 390, 394), (105, 360, 375), (120, 350, 370), (140, 336, 364), (168, 315, 357), (210, 280, 350), (240, 252, 348)]
'''
python 2.7.8
angle_tri = list()
def is_angle_tri(length_list):
left_clause = 0
right_clause = 0
max_num = max(length_list)
max_num_index = length_list.index(max_num)
for i in range(3):
if i == max_num_index:
left_clause = length_list[i] ** 2
else:
right_clause += length_list[i] ** 2
if left_clause == right_clause:
return True
return False
def is_duple(length_list):
if set(length_list) in map(set,angle_tri):
return True
return False
maxv = 0
max_n = 0
for n in range(3,1001):
angle_tri = list()
for i in range(1,n+1):
for j in range(1,n+1):
if is_angle_tri([i,j,n-i-j]) and not is_duple([i,j,n-i-j]):
angle_tri.append([i,j,n-i-j])
print n
if maxv < len(angle_tri):
maxv = len(angle_tri)
max_n = n
print 'max = %d' % max_n
1부터 p 까지 i와 j의 이중 반복문을돌려서 계산했습니다. i와 j가 정해졌다면 나머지 한숫자는 자연스럽게 p-i-j 이기때문에 이중반복문을 사용하였습니다. 근데 좀 오래걸리는군요.. 더좋은알고리즘이 분명있을텐데말이죠..흠 생각해봐야겠군요 어쨋든 답은 840입니다.
def tri(abc):
if abc[2]*abc[2] == abc[0]*abc[0] + abc[1]*abc[1] :
return True
else :
return False
def max_tri(num):
data = []
answer = []
for i in range(1, num):
for j in range(i, int(num/2)):
k = num - i - j
data = [i, j, k]
data = sorted(data)
if (tri(data)) & (data not in answer):
answer.append(data)
return len(answer)
max_nm = 0
final = 0
for i in range(3, 1001):
tmp = max_tri(i)
if max_nm < tmp :
max_nm = tmp
final = i
print (final)
Java 사용. 맨위 답이 정말 소름끼치내요.. 많이 배워갑니다. 결과 값 둘레는 840 이며 개수는 8 Roop = 16099676
/*
세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은
아래와 같이 세 개가 있다.
{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마인가?
*/
public class Fifth {
//A^2 + B^2 = C^2
//A+B > C
//A+B+C < 1000
/*
삼각형을 만드는 조건 (A< B <C)
A+B > C 이기 때문에
C+C < A+B+C < C+C+C
@ 2C < A+B+C < 3C 이고 A+B+C = P 이므로
P/3 < C < P/2 이다.
*/
public static void main(String[] args){
int A,B,C,P;
int roopCount = 0;
int resultP = 0;
int resultN = 0;
for(P=3; P< 1000; P++){
int number = 0;
for(C = P/3+1; C < (int)Math.ceil(((double)P/2.0));C=C+1){
for(A = 1; A<= (P-C)/2; A++){
B = P-C-A;
if(A*A + B*B == C*C && B >= A){
number++;
}
roopCount++;
}
}
if(resultN < number){
resultP = P;
resultN = number;
}
}
System.out.println("결과 값 둘레는 " + resultP + " 이며 개수는 " + resultN);
System.out.println("Roop = " + roopCount);
}
}
#include <stdio.h>
int main() {
int count = 0, max = 0, max_p = 0;
int p, a, b, c;
for(p = 1; p <= 1000; p++) {
count = 0;
for(a = 1; a <= p-2; a++) {
for(b = 1; b <= p-a-1; b++) {
c = p - a - b;
if(a*a + b*b == c*c)
count++;
}
}
if(count > max) {
max_p = p;
max = count;
}
}
printf("%d", max_p);
}
부끄럽네요 ㅠ
def core01(n):
#result=dict()
result=list()
for i in range(2,int(n/2+1)):
for j in range(int(i/2**0.5),i):
k=(i**2-j**2)**0.5
if k%1==0 :
k=int(k)
result.append(i+j+k)
return max(set(result),key=result.count)
print(core01(1000))
python 3.4.2 가장 긴변 c 설정하고 두번째 긴변b은 c/1.414 에서 c 까지 범위가 설정되므로 a 는 대충 정수 나오면 결과에 더하는 방식으로 이중 for 문 돌렸습니다.
Perl
use strict;
use warnings;
my ($n,$h,%c,%p);
my ($mp,$m)=(0,0);
$n=$ARGV[0] // 1000;
$h=int($n/2);
for my $x (3..$h){
for my $y ($x..$h){
my $s = sqrt($x**2+$y**2);
if ($s==int($s)){
my $z = $s;
last if $x+$y+$z>$n;
$p{$x+$y+$z}++;
}
}
}
for(keys %p){
if($m<$p{$_}){
$mp=$_;
$m=$p{$_}
}
}
print $mp;
zer6six님 코드를 자바식으로 약간 변형해서 풀어봤습니다. p값을 1부터 1000까지 연산했으며(그래서인지 약간 느린듯;), 직각삼각형의 갯수는 리스트를 따로 뽑아서 비교하지 않고 루프마다 그때그때 갯수의 크기를 비교해서 최대로 많은 경우를 찾았습니다.
package triangle;
public class Triangle {
public void tri(int p){
int max_cont = 0; // 가장 많이 생성된 직각삼각형의 갯수
int max_p = 0; // 가장 많은 직각삼각형을 만드는 p값
for(int i = 1; i <= p; i++){
int cont = 0;
for(int a = 1; a < p/2; a++){
for(int b = 1; b < a; b++){
double c = Math.sqrt(Math.pow(a, 2) + Math.pow(b, 2));
if(c%1 == 0 && a+b+c == i){
cont++;
}
}
}
if(max_cont <= cont){max_cont = cont; max_p = i;}
}
System.out.println(max_p + ", " + max_cont);
}
public static void main(String[] args){
Triangle test = new Triangle();
test.tri(1000);
}
}
static void exce64()// 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?
{
double a = 1, b = 1;
int n = 1000 + 1;
int[] cnt = new int[n];
int max = 0,ans = 0;
while (a < n - 1 && a + b + Math.sqrt(a * a + b * b) < n)
{
while (b < n - 1 && a + b + Math.sqrt(a * a + b * b) < n)
{
if (Math.sqrt(a * a + b * b) == (int) Math.sqrt(a * a + b * b))
{
cnt[(int) (a + b + (int) (Math.sqrt(a * a + b * b)))]++;
}
b++;
}
a++;
b = a;
}
for (int i = 0; i < n; i++)
if (max < cnt[i])
{
max = cnt[i];
ans = i;
}
System.out.println(ans);
}
pythaSet=set([])
for a in range(1,500):
for b in range(1,500):
c=int((a*a+b*b)**0.5)
if a+b+c > 1000: break
if a*a + b*b == c*c :pythaSet.add(frozenset([a,b,c]))
girthDic = {}
m = 0
for s in pythaSet:
l=sum(s)
girthDic[l] = girthDic.get(l,0)+1
if girthDic[l] > m:
m = girthDic[l]
mostFrequent = l
print mostFrequent,girthDic[mostFrequent]
예전에 풀어봤던 문제라... a, b, c (a < b < c 라 가정하면)가 삼각형의 둘레이고, 이들이 직각삼각형을 이루는 자연수가 되므로 a, b, c 의 범위는 생각보다 매우 좁게 한정됩니다. b 는 c 보다는 클 수 없으므로 최대 500이하, a는 b 보다 클 수 없습니다. 따라서 최대 499 이 점을 이용해서 루프의 수를 한정하면 답은 꽤 빠르게 풀립니다.
def eu39():
borderlines = [0] * 1001
for b in range(1, 501):
for a in range(1, b):
c_square = a**2 + b**2
c = c_square ** 0.5
if a+b+c > 1000:
break
elif (c == int(c)):
borderlines[a+b+(int(c))] += 1
return borderlines.index(max(borderlines))
%time print(eu39())
840
CPU times: user 108 ms, sys: 862 µs, total: 109 ms
Wall time: 108 ms
전체 탐색을 활용해서 해결했습니다. 직각삼각형의 두 변의 길이 a,b (1 <= a,b <= 1000)를 정해준뒤에 이에 대응하는 세번째 변의 길이 c의 값을 피타고라스 정리로 찾아주고, c가 자연수이고 a+b+c <= 1000일때 p = a+b+c의 값이 몇번 등장하는지 체크해준뒤에 등장하는 모든 p에 대해서 가장 많이 등장했던 p를 찾아주면 됩니다.10^6번만 탐색해주면 모든 가능한 p와 p의 빈도를 알 수 있으므로 고속으로 해결 가능합니다. [C++]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <algorithm>
using namespace std;
bool isPerfectSquare(int x){
return (sqrt(x) == floor(sqrt(x)));
}
int main(){
map<int,int> mp;
for (int a = 1; a <= 1000; a++){
for (int b = 1; b <= 1000; b++){
int cSquared = a*a+b*b;
if (isPerfectSquare(cSquared)){
if (a+b+sqrt(cSquared) <= 1000) mp[a+b+sqrt(cSquared)]++;
}
}
}
int maxP = 0, ans;
for (map<int,int>::iterator it = mp.begin(); it != mp.end(); it++){
if (it->second > maxP){
maxP = it->second;
ans = it->first;
}
}
printf("%d\n",ans);
return 0;
}
p와 a가 결정되면 a^2 + b^2 = c^2와 a + b + c = p의 두 식을 연립하여 나머지 둘을 구할 수 있습니다. 따라서 루프는 두번만 돌립니다.
from time import time
def get(p):
result = {}
for a in range(1, int(p/2)+1):
b = (p**2 - 2*a*p)/(2*p - 2*a)
if b != 0 and b%1 == 0 and a**2 + b**2 != 0:
result[tuple(sorted((a, int(b), int((a**2+b**2)**0.5))))] = 1
return sorted(result.keys(), key = lambda x: x[0])
if __name__ == '__main__':
to = 10000; M = 0; P = 0; t = time()
for x in range(1, to + 1):
temp = len(get(x))
if temp > M:
M = temp; P = x
print(P, '\n', time()-t)
1000
840
0.25725746154785156
10000
9240
24.068172931671143
멀티프로세스 개량버전
from time import time
from multiprocessing import Pool
def get(p):
result = {}
for a in range(1, p//2 if p%2 == 0 else p//2+1):
b = (p**2 - 2*a*p)/(2*p - 2*a)
if b%1 == 0:
result[(a, int(b)) if a<int(b) else (int(b), a)] = 1
return len(result)
if __name__ == '__main__':
to = (x for x in range(1, 20000+1))
M = 0; P = 0; t = time()
with Pool() as pool:
for i, x in enumerate(pool.map(get, to)):
if x > M:
M = x; P = i+1
print(P, '\n', time()-t)
10000
9240
6.248987436294556
20000
18480
24.001494884490967
파이썬 3.5.1
Delphi 2010
procedure TfmQ2.Button6Click(Sender: TObject);
var
M, M2: array [0 .. 1000] of Integer;
i, j, k, nn: Integer;
sList: TStringList;
s: string;
begin
// 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?
for i := 1 to 1000 do
begin
M[i] := 0;
M2[i] := i * i; // i^2
end;
sList := TStringList.create;
try
for i := 1 to 500 do
for j := i to 500 do
for k := j + 1 to 500 do
begin
nn := i + j + k;
if (nn <= 1000) and (M2[i] + M2[j] = M2[k]) then
begin
sList.Add(format('%d, (%d, %d, %d)', [nn, i, j, k]));
Inc(M[nn]);
end;
end;
k := 0;
j := 0;
for i := 1 to 1000 do
begin
if k < M[i] then
begin
k := M[i];
j := i;
end;
end;
s := format('%d, ', [j]);
Memo1.Lines.Clear;
for i := 0 to sList.Count - 1 do
if Pos(s, sList[i]) = 1 then
Memo1.Lines.Add(sList[i]);
Memo1.Lines.Add('가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는? ' + IntToStr(k));
Memo1.Lines.Add('');
finally
sList.Free;
end;
end;
Ruby
a+b < c 일 때. a * (2a-p) < 0. 따라서 0 < a < p/2, 0 < b <= a, c = sqrt(a^2 + b^2)
find_circum = ->p_len,circums=Hash.new(0) do
cnt = ->a,b,c { circums[a+b+c] += 1 if (a+b+c <= p_len) && (c%1 == 0) }
(1...p_len/2).each {|a| (1..a).each {|b| cnt[a,b,(a**2+b**2)**0.5] } }
circums.max_by(&:last)
end
Test
expect( find_circum[120] ).to eq [120, 3]
expect( find_circum[1000] ).to eq [840, 8]
public void CodingDojang064()
{
int Count = 0;
int result = 0;
int temp = 0;
for (int p = 1; p < 1001; p++)
{
for (int a = 1; a * 2 < p; a++)
{
for (int b = 1; b < a; b++)
{
for (int c = 1; c <= b; c++)
{
if ((a + b + c == p) && (a * a == b * b + c * c))
{
Count++;
}
}
}
}
if (temp < Count)
{
temp = Count;
result = p;
}
Count = 0;
}
Console.WriteLine(result);
}
대략 13초 정도 걸리는 군요.. 루프 범위 최적화가 매우 중요한듯 합니다.
int[] CNTS = new int[1001];
int ANS;
for (int i = 0; i <= 1000;i++ )
{
for (int j = 0; j <= 1000-i; j++)
{
for (int k = 0; k <= 1000-i; k++)
{
if(i+j+k<=1000)
{
if (i<k&&j<k&&(i*i)+(j*j)==(k*k)&&i+j>k)
{
CNTS[(i+j+k)]++;
}
}
}
}
}
ANS = Array.IndexOf(CNTS, CNTS.Max());
tri,result = list(), 0
result_list = list()
for p in range(3,1001):
a,b = 1,1
while p-a != 2:
b += 1
if a+b > (p-a-b):
tri = [a,b,p-a-b]
if p-a-b == 1:
a += 1
b = 1
if a**2 +b**2 == (p-a-b)**2:
result += 1
result_list.append((result,p))
result = 0
_dict = dict(result_list)
print(_dict[max(_dict.keys())])
#### 2017.01.28 D-389 ####
진짜 극한으로 오래걸리는 코드..ㅎㅎ 일단 푸는것에 집중했으니깐 다음에 다시 도전.
다른 분들과 답은 같고.. 4중 루프나 됩니다 .. 7초 정도 걸리는 듯?
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int p;
void main() {
int max = 0;
for(int p=3;p<=1000;p++) {
int count = 0;
for(int a = 1;a<p;a++) {
for(int b= 1;b<p-a; b++) {
if(b>=a) break;
for(int c=p-a-b ;c>0; c--) {
if(c>=a) break;
if(c>=b) break;
if(p== a+b+c && a*a == b*b+c*c)
count++;
}
}
}
if(count > max) {
max = count;
printf("p:%d count : %d\n",p, count);
}
}
}
MATLAB 입니다. a와 b 길이 조합에 대해서 meshgrid로 c와 둘레길이를 계산한 후 histogram counting 하는 방식입니다. O(N^2) 인듯 합니다. 1000개의 경우 0.1 sec 1e4 개인 경우 14 sec 정도 걸리네요. a길이는 최대둘레/3 b길이는 a길이이상부터 최대둘레/2 까지 했습니다. 1000개에 대해서 답은 840이고, 만족하는 조합갯수는 8개로 나오네요.
clear all
close all
clc
tic
%% max perimeter value
max_peri=1000;
%% setting range
edge_a_set=(1:floor(max_peri/3));
edge_a_len=length(edge_a_set);
edge_b_a_diff_set=(0:floor(max_peri/2));
edge_b_len=length(edge_b_a_diff_set);
[aa b_a_diff]=meshgrid(edge_a_set,edge_b_a_diff_set);
bb=aa+b_a_diff;
%% calculate the length of the longest edge (c) and the corresponding perimeter
cc=sqrt(aa.^2+bb.^2);
perimeter=aa+bb+cc;
%% histogram
result_peri_hist=zeros(max_peri,1);
combination_set=cell(max_peri,1);
for edge_a_idx=1:edge_a_len
for edge_b_idx=1:edge_b_len
perimeter_val=perimeter(edge_b_idx,edge_a_idx);
if perimeter_val - 10*floor(perimeter_val/10) == 0 % 자연수이고
if perimeter_val<=max_peri % 최대 길이 초과하지 않는 조합
result_peri_hist(perimeter_val)=result_peri_hist(perimeter_val)+1;
combination_set{perimeter_val}(result_peri_hist(perimeter_val),1)=aa(edge_b_idx,edge_a_idx);
combination_set{perimeter_val}(result_peri_hist(perimeter_val),2)=bb(edge_b_idx,edge_a_idx);
combination_set{perimeter_val}(result_peri_hist(perimeter_val),3)=cc(edge_b_idx,edge_a_idx);
combination_set{perimeter_val}(result_peri_hist(perimeter_val),4)=perimeter(edge_b_idx,edge_a_idx);
end
end
end
end
%% show result
[q1,q2]=max(result_peri_hist);
disp(['최대 조합 갯수를 갖는 둘레길이 : ' num2str(q2)]);
disp(['만족하는 조합 갯수 : ' num2str(q1)]);
disp(sprintf('조합 \t a \t b \t c'));
for p=1:q1
disp(sprintf(' \t %d \t %d \t %d',...
combination_set{q2}(p,1),...
combination_set{q2}(p,2),...
combination_set{q2}(p,3)));
end
toc
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import static java.util.stream.Collectors.toList;
public class RightAngledTriangle {
public static void main(String[] args) {
final int n = 1001;
final Map<Integer, Set<List<Integer>>> t = new ConcurrentHashMap<>();
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
for (int l = 1; l <= n; l++) {
if ((j * j) + (k * k) == l * l && (j + k + l) <= n) {
int sum = j + k + l;
if (t.containsKey(sum)) {
Set<List<Integer>> tt = t.get(sum);
tt.add(Arrays.asList(new Integer[]{j, k, l}).stream().sorted().collect(toList()));
} else {
Set<List<Integer>> ttt = new HashSet<>();
ttt.add(Arrays.asList(new Integer[]{j, k, l}).stream().sorted().collect(toList()));
t.put(sum, ttt);
}
}
}
}
}
System.out.println(t.keySet().stream().reduce((a, b) -> t.get(a).size() > t.get(b).size() ? a : b).get());
}
}
python 3.6 Special Pythagorean triplet 문제와 거의 똑같은 문제네요.
미지수가 3개, 식은 2개니 값이 식만으로는 산출이 안되고 범위를 정해서 구해야 하죠. a+b+c = p, a+b > c 이므로(삼각형이니까) c < p/2 이며 즉, a < b < c < (p/2, 3 to 500) 입니다.
범위는 정해졌고, 어떤 것을 구하냐 인데. a, b 를 c 로 정리를 하면 c - b = a^2 / (p-a), c - a = b^2 / (p-b) 입니다. a term 으로 쓰든 b term 으로 정리하든 식은 같습니다. 그리고 이 모두 자연수이어야 하므로 식에서 나오는 두 수중 작은 것이 a, 큰 것이 b 가 됩니다. 그러면 c 는 당연이 p-(a+b) 입니다.
max p 는 p_set 이라는 list 안에 직각삼각형이 나오는 p 와 그때의 a & b 를 list 로 묶어서 넣은 다음 max(p_set, key=len) 으로 찾으면 a,b 가 가장 많은 list 가 리턴되며 이때 첫번째 값이 답입니다.
from math import ceil
def find_max_p_set(n):
p_set = []
for p in range(3,n+1):
a_b = [i for i in range(1,ceil(p/2)) if (i**2 / (p-i)) % 1 == 0]
if len(a_b):
p_set.append([p]+a_b)
return max(p_set, key=len)[0]
>>> find_max_p_set(1000)
840
일단 세 변이 모두 자연수여야 하기 때문에 피타고라스 수인 세 수의 쌍의 리스트를 모두 만듭니다. 그 다음 p를 1부터 1000까지 변화시키면서 리스트에 해당되는(세 수의 합이 p인 쌍)쌍을 출력합니다. 1000까지 완료하였을 경우, 가장 많은 리스트들이 있는 p가 답입니다.
package codingdojang;
import java.util.Scanner;
public class ex64 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int max = 0;
int count = 0;
int index = 0;
for(int p=0; p<=1000; p++) {
for(int a=1; a<=p; a++) {
for(int b=a;b<=p-a;b++) {
for(int c=b; c<=p-a-b;c++) {
if(a*a+b*b == c*c && a+b+c == p) {
System.out.println(p+" = "+"{"+a+","+b+","+c+"}");
count++;
}
}
}
}
if(max < count) {max = count; index = p;}
count = 0;
}
System.out.println(index);
}
}
파이썬 3.6
def triangles(p):
c,tmp,triangle = 0,[],[]
for a in range(1,int(p/2)+1):
for b in range(1,int(p/2)+1):
c = p-(a+b)
if c**2 == a**2 + b**2:
tmp = [a,b,c]
tmp.sort()
if tmp not in triangle:
triangle.append(tmp)
if len(triangle) != 0:
len_list.append(len(triangle))
p_list.append([p,len(triangle)])
def main(n):
for p in range(3,n+1):
triangles(p)
print(p_list[len_list.index(max(len_list))][0])
if __name__ == "__main__":
len_list,p_list =[],[]
n = 1000
main(n)
*결과값
840
def triangle(n):
result = list()
for i in range(3, n+1):
result.append(0)
for j in range(math.ceil(i/3), math.ceil(i/2)):
a = (i*i-2*j*i)/(2*(i-j))
if a.is_integer() and a > 0:
result[-1] += 1
return result.index(max(result))+3
Map<Integer,Integer> map = new HashMap<>();
int ans = 0;
for (int p=4; p<1000; p++) {
int cnt = 0;
for (int a=1; a<p; a++) {
for (int b=1; b<p; b++) {
if (a+b+Math.sqrt(a*a + b*b) == p)
cnt++;
}
}
map.put(cnt, p);
ans = Math.max(ans, cnt);
}
System.out.println(map.get(ans) + " : " + ans);
```// p를 키로, 그에 해당하는 만들 수 있는 직각삼각형의 개수를 값으로 맵에 넣었습니다.
// 840일 때 16개 만들 수 있네요. 대칭을 생각해보면 8개가 정확할 듯해요
public static boolean Lan(int a,int b, int c)
{
a*=a;
b = (int) Math.pow(b, 2);
c = (int) Math.pow(c, 2);
if(a+b==c && a<b)
return true;
else
return false;
}
int p=1000;
int b,c;
int count;
int max = 0;
int temp = 0;
while(p!=0)
{
count=0;
for(int a=1;a<p;a++)
{
b=0;
while(a+b!=p)
{
b++;
c=p-(a+b);
if(Lan(a,b,c)==true)
{
count++;
}
if (count > max) {
max = count;
temp = p;
}
}
}
p--;
}
System.out.println("최종 둘레: "+temp);
public class pratice {
public static void main(String[] args) {
int anw[] = { 0, 0 };
for (int p = 1; p < 1001; p++) {
int count = 0;
for (int i = 1; i < p / 2 + 1; i++)
for (int j = 1; j < i; j++)
if (Math.pow(i, 2) == Math.pow(j, 2) + Math.pow(p - i - j, 2) && p - i - j > j)
count++;
anw[1] = count > anw[0] ? p : anw[1];
anw[0] = count > anw[0] ? count : anw[0];
}
System.out.println(anw[1] + " " + anw[0] + "개");
}
}
Python 3.6
s = {}
p = 1000
for i in range(1,p//2):
for j in range(i,p//2):
k = (i**2+j**2)**0.5
if i+j+k > p: break
if k%1 == 0:
if i+j+k in s.keys(): s[i+j+k] += 1
else: s[i+j+k] = 1
maxt = 0
for i in s:
if s[i] > maxt:
maxt = s[i]
p = i
print(f'p = {int(p)}, {maxt}개의 삼각형')
p = 840, 8개의 삼각형
a > b >= c 이면,
a > b + c 이므로 1000 / 3 < a < ceil(1000 / 2)
b * b >= a * a / 2 이므로 sqrt(a*a / 2) <= b < a
from math import ceil, sqrt
def richest_p(p_max):
p = [0 for x in range(p_max + 1)]
for a in range(ceil(p_max / 3), ceil(p_max / 2)):
for b in range(ceil(sqrt(a * a / 2)), a):
c = sqrt(a * a - b * b)
if c.is_integer() and a + b + c <= p_max:
p[a + b + int(c)] += 1
return max(enumerate(p), key = lambda x: x[1])[0]
print(richest_p(1000))
print(richest_p(10000))
p=0
c=1
cnt=[0 for i in range(1000)]
while c<=500:
c_s = c**2
for i in range(c):
for j in range(c):
if c_s == i**2 + j**2:
if c+i+j <=1000:
cnt[a+i+j] +=1
else:
None
c+=1
max_value=-1
max_p=0
for i in range(1000):
if cnt[i]>max_value:
max_value = cnt[i]
max_p = i
print(max_p)
from math import sqrt
n=[]
roun=1000
count=0
for a in range(roun//2+1):
for b in range(roun//2+1):
c=a**2+b**2
if a+b+sqrt(c)<=roun and c%1==0:
n.append(a+b+sqrt(c))
for p in range(roun//2+1):
if count<n.count(p*2):
count=n.count(p*2)
result=p*2
print(result)
엄청 느리긴 한데 빠르게 할 방법이 생각이 안나서..
import pandas as pd
#둘레값이 들어오면 둘레값과 직각 삼각형의 갯수를 반환하는 함수
def distin(cir):
cnt = 0
for num1 in range(1, cir):
for num2 in range(num1,cir):
num3 = cir-(num1+num2)
if (num3 >=num2) and (num3**2 == num1**2+num2**2):
cnt += 1
return cnt, cir
#만들어깆는 직각 삼각형의 갯수가 가장 많을때를 찾는 함수
def main(last):
box= pd.Series()
for ma_num in range(1,last+1):
ma_cnt,ma_cir = distin(ma_num)
box['{}'.format(ma_cir)] = ma_cnt
for box_cir,box_cnt in box.items():
if box_cnt == max(box):
print('둘레의 길이가 {}일때 {}개의 직각삼각형이 만들어 집니다.'.format(box_cir,box_cnt))
main(1000)
#가장많은 직각삼각형이 만들어지는 둘레(<=1000)의 길이는?
ls=[1,1,1]
l=ls[0]+ls[1]+ls[2]
tri=[]
while l<=1000:
count=0
for ls[0] in range(1,l//3+1):#세변의 길이
for ls[1] in range((l-ls[0])//2,1,-1):
if ls[0]<ls[1]:
ls[2]=l-ls[0]-ls[1]
else:
break
#직각삼각형 조건
if ls[2]**2==ls[0]**2+ls[1]**2 and ls[2]<(ls[0]+ls[1]):
count+=1
#print('둘레의 길이:',l,'피타고라스의 수',ls)
tri.append(count)#l=3일때 부터 조건을 만족하는 삼각형의 개수를 리스트로 작성
l+=1
k=0#만들어지는 삼각형개수가 최대인 둘레의 길이
k0=[]
t0=[]
while k<len(tri)-1:
if tri[k]<tri[k+1] and tri[k+1]>=4:
k0.append(k+4)
t0.append(tri[k+1])
#print('둘레의 길이:',k+4,'삼각형의 개수:',tri[k+1])
k+=1
p0=t0.index(max(t0))
p=k0[p0]
print('가장 많은 직각삼각형이 만들어지는 둘레의길이: ',p)
#정답은 840
Starleaguer님의 풀이에 있는 댓글을 보고 삼각형의 한 변의 길이는 전체 변의 길이의 1/2를 넘을 수 없다를 알게되었습니다.
저는 c 에 집중을 하므로써 이차방정식을 동원해 풀었는데 시간은 생각보다 만족스럽게 나온 것 같네요.
from math import sqrt
def plen(p):
a = 0
for c in range(int(p/3),int(p/2)):
if ((p**2)/2 - p*c) > 0:
x = (p-c)**2-4*((p**2)/2 - p*c)
if x > 0 and sqrt(x)%1 == 0:
a += 1
return a
ans = 0
M = 0
for x in range(1,1000+1):
if plen(x) > M:
M,ans = plen(x),x
print(ans,M)
결과
1000
=================== RESTART: C:/Users/user/Desktop/plen.py ===================
840 8
0.13785004615783691
>>>
10000
=================== RESTART: C:/Users/user/Desktop/plen.py ===================
9240 20
12.96798324584961
>>>
maxcount=0
maxp=0
for p in range(1,1001):
count=0
for a in range(1,p//3+2):
for b in range(a,p//2+2):
if a**2+b**2==(p-a-b)**2:
count+=1
if count>maxcount:
maxcount=count
maxp=p
print(maxp, maxcount)
mx = 0
for p in range(1, 1001) :
cou = 0
for cc in range(1, int(p/2)+1) :
for aa in range(1, int((p-cc)/2)+1) :
if aa**2 + (p-cc-aa)**2 == cc**2 :
cou += 1
if cou >= mx :
mx = cou
print(p)
print(mx, " DONE")
결과
p = 840, mx = 8
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
int main(){
int a,b,c,p,temp,cnt=0;
int M=INT_MIN;
for(p=1;p<=1000;p++){
cnt=0;
for(a=1;a<=p-2;a++){
for(b=1;b<=p-a-1;b++){
c=p-a-b;
if(pow(a,2)+pow(b,2)==pow(c,2))
cnt++;
}
}
if(M<cnt){
temp = p;
M = cnt;
}
}
cout<<temp;
}
시간이 좀 걸려서 나오지만 pow를 사용했다는 것에 만족,,,
Python 3
직각삼각형 각 변의 길이(자연수) a, b, c에 대해 다음의 조건을 만족하는 경우를 찾습니다.
p = a + b + c >= 123 <= a <= b < p/2c = sqrt(a^2 + b^2) b = (2pa - p^2) / (2a - 2p)p = 12..1000, a = 3..p/2 범위에 대해 상기 조건을 만족하는 자연수를 찾습니다.
def main():
max_p = 0
max_count = 0
for p in range(12, 1000 + 1):
count = get_rtri_count(p)
if count > max_count:
max_count = count
max_p = p
print(f"max count = {max_count} at p = {max_p}")
# 직각 삼각형의 개수
def get_rtri_count(p):
count = 0
for a in range(3, p // 2 + 1):
b = (2 * p * a - p ** 2) / (2 * a - 2 * p)
c = (a ** 2 + b ** 2) ** 0.5
if b == int(b) and c == int(c) and a <= b:
count += 1
return count
if __name__ == '__main__':
main()
파이썬 입니다.
pita = []
## c가 빗변, c>b>=a
for c in range(1,1000):
for b in range (1,c):
a = (c**2-b**2)**0.5
if a-int(a)==0 and a <= b and a+b+c<=1000 :
pita.append(int(a+b+c))
else:
pass
pitas = sorted(pita)
vs = {}
for i in range(0,len(pitas)-1):
if pitas[i+1] != pitas[i]:
num = pitas.count(pitas[i])
vs[pitas[i]] = num
if pitas[-1] != pitas[-2]:
vs[pitas[-1]] = 1
maximum = max(vs.values())
vsvalue = list(vs.values())
vskeys = list(vs.keys())
for i in range(0,len(vsvalue)-1):
if vsvalue[i] == maximum:
print(vskeys[i])
import math
def Tri(n):
a = 0
c = 0.0
p =n/2
_list = []
while a < p:
a += 1
for b in range(a,int(p-a)+1):
c = math.sqrt(a*a + b*b)
if c % 1 == 0:
_list.append( a+b+c )
return int(max(set(_list),key=_list.count))
print (Tri(1000))
------------------------------------------
a={}
for w in range(1,1001):
count=0
for i in range(1,((w+1)//2+1)//2+1):
for j in range(1,(w+1)//2+1):
q=w-i-j
if i**2+j**2==q**2:
count+=1
if count!=0:
a[w]=count
print(max(a,key=a.get))
아래식에서 위의식으로 바꿨습니다 확실히 실행속도가 다르군요
// Rust
fn triangle() {
let mut max_count = 0;
let mut max_p = 0;
for p in (6..=1000).rev() {
let mut count = 0;
for b in (2..p/2).rev() {
for a in (1..b).rev() {
if ((p - a - b) as u32).pow(2) ==
(a as u32).pow(2) + (b as u32).pow(2) { count += 1;}
}
}
if count > max_count {
max_p = p;
max_count = count;
}
}
println!("{:?}", max_p);
}
from math import *
def triangle(p):
arr=[]
for a in range(1,p+1):
for b in range(a,p-a+1):
c=p-(a+b)
if c==sqrt(a**2+b**2):
arr.append([a,b,c])
return arr
arr1=[]
for p in range(3,1000):
if len(triangle(p))!=0:
arr1.append([len(triangle(p)),p,triangle(p)])
arr1.sort()
arr1.reverse()
print(arr1[0][1])
시간은 좀 걸리네요.. 최적화는 좀더 고민해볼게요~!
def rec(n):
s=[]
for a in range(1,n):
for b in range(a,n-a):
c = n-a-b
if c > b-1 and c**2 == a**2+b**2:
s.append([a,b,c])
return len(s)
p=1
max_len = 1
for i in range(1000):
if rec(i) > max_len:
p=i
max_len = rec(i)
print(p)
## (x+y)^2 = (x-y)^2 + 4xy ==> 둘레길이: 2x + 2root(xy)
def countRightTriangle(L):
count=0
x = 2
TLS = []
while x < L//2:
for y in range(1, x):
if x*y == (L//2-x)**2:
t = sorted([x-y, int((4*x*y)**0.5), x+y])
if t not in TLS:
TLS.append(t)
count += 1
x += 1
return count
mL, mcnt = 1, 0
for L in range(4, 1000+1, 2):
cnt = countRightTriangle(L)
if cnt > mcnt:
mcnt = cnt
mL = L
print('둘레가 {0} 일 때, {1}개로 가장 많이 만듬'.format(mL, mcnt))