연분수3 [C/C++] 프로젝트 오일러 #64 홀수 주기의 제곱근 프로젝트 오일러 #64 는 연분수로 제곱근을 표현하는 문제입니다. 문제의 난이도는 20%입니다. 알고리즘적으로 어려운 것보다는 수학적 개념의 어려움이 있었던 문제라고 봅니다. 제곱근을 연분수로 표현하는 문제는 #57번(http://sdev.tistory.com/237)에 이미 나왔었습니다. 문제의 링크는 아래와 같습니다.https://projecteuler.net/problem=64 연분수로 표현할 때, 중요한 점은 분자는 항상 1이 되어야 한다는 것입니다.예를 들어서 7의 제곱근인 7은 다음과 같이 표현할 수 있습니다. 7=2+7−2 위 식은 너무나도 당연한 것이겠지만요. 우리는 이것을 이용해서 연분수를 만들 수가 있습니다. .. 2016. 6. 22. [C++/Python] 프로젝트 오일러 #57 : 제곱근의 수렴 이번 문제는 수학 문제인 듯 보이지만, 그냥 단순 계산 문제입니다.프로젝트 오일러 사이트 난이도 평가 5% 문제네요. 문제의 내용은 2의 제곱근을 구할 때, 연분수 전개를 할 수가 있습니다. 연분수 전개에 관련해서는 펠의 방정식(http://sdev.tistory.com/213) 글을 참조하세요. 2=1+12+12+12+⋯=[1;2―] 와 같이 2의 제곱근을 표시할 수 있습니다. 이 문제에서는 이것이 중요한 것이 아니고, 이 연분수 전개를 할 때, 분수로 표현하게 되면, 분모와 분자가 모두 정수가 되는데, 분자의 정수부가 분보의 정수부보다 자릿수가 많은 것이 몇개가 있는 가가.. 2016. 6. 14. 펠의 방정식(Pell's Equation) - 3 연분수 전개로 당연한 식이지만, 다음과 같은 형식의 식을 만들었습니다.d=r+sdp+qd 첫번째로는 과연 저 형식의 식과 펠의 방정식은 무슨 관계인가입니다.d=7일 때, p=1,q=1,r=7,s=1라는 것도 저 식을 만족합니다. 왜 하필이면, 복잡한 연분수 계산을 통해서 저 수를 얻어야 하는 것입니다. 그리고 펠의 방정식과 무슨 관계인가입니다. 위 식에서 분모를 유리화하면 다음과 같은 식을 얻습니다.d=r+sdp+qd=pr−dqs+(ps−qr)dp2−dq2 분모를 유리화하면 .. 2015. 5. 23. 이전 1 다음 728x90
