반응형 제곱근3 [Python] 프로젝트오일러 #80 제곱근 확장(수학) 이번 문제는 난이도 20%입니다. 사실 이 문제의 뜻을 정확하게 파악하는데 좀 문제가 있습니다. 영어권 사용자들에게도 헷갈리는 문제이기도 하죠. https://projecteuler.net/problem=80 일단 중요한 것은 이 문제를 풀기 위해서는 큰 정수 계산을 할 수 있거나, 높은 정밀도의 실수 연산이 필요합니다. 이미 알고있는 32비트 실수형이나 64비트 실수형은 정밀도가 그렇게 높지 않습니다. 32비트 실수형은 유효자리수가 6자리정도이고, 64비트 실수형은 유효자리수가 15자리 정도입니다. 그런데 이 프로그램은 100자리 이상의 유효자리수를 요구합니다. 일단 문제를 해석하면, \(\sqrt{2}\)와 같은 자연수의 제곱근은 무한소수로 표현됩니다. \( \sqrt{2} = 1.4142135623.. 2022. 9. 13. 프로젝트 오일러 #64 홀수 주기의 제곱근 프로젝트 오일러 #64 는 연분수로 제곱근을 표현하는 문제입니다. 문제의 난이도는 20%입니다. 알고리즘적으로 어려운 것보다는 수학적 개념의 어려움이 있었던 문제라고 봅니다. 제곱근을 연분수로 표현하는 문제는 #57번(http://sdev.tistory.com/237)에 이미 나왔었습니다. 문제의 링크는 아래와 같습니다. https://projecteuler.net/problem=64 연분수로 표현할 때, 중요한 점은 분자는 항상 1이 되어야 한다는 것입니다. 예를 들어서 7의 제곱근인 \( sqrt{7} \)은 다음과 같이 표현할 수 있습니다. \[ \sqrt{7} = 2 + \sqrt{7} - 2 \] 위 식은 너무나도 당연한 것이겠지만요. 우리는 이것을 이용해서 연분수를 만들 수가 있습니다. 일단 .. 2016. 6. 22. 57. 프로젝트 오일러 #57 : 제곱근의 수렴 이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.프로젝트 오일러 사이트 난이도 평가 5% 문제네요. 문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다. 연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요. 와 같이 2의 제곱근을 표시할 수 있습니다. 이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가 문제입니다. 연분수 전개를 분수로 만들면 되는 것이지만, 연분수 전개 자체가 상당히 큰 자릿수가 나옵니다. 물론 double 형을 이용해서 근사치로 계산해도 되겠지만, .. 2016. 6. 14. 이전 1 다음 728x90
