이 블로그는 더 이상 업데이트되지 않습니다.

최신 내용을 확인하시려면 여기를 클릭해주세요.

프로젝트 오일러 57번

  • 2013/09/21
  • Perl

제곱근 2는 다음과 같은 연분수의 형태로 나타낼 수 있습니다.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

위 식을 처음부터 한 단계씩 확장해 보면 아래와 같습니다.

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

그 다음은 99/70, 239/169, 577/408 로 확장이 되다가, 여덟번째인 1393/985 에 이르면 처음으로 분자의 자릿수가 분모의 자릿수를 넘어섭니다.

처음부터 1천번째 단계까지 확장하는 중에, 분자의 자릿수가 분모보다 많아지는 경우는 몇 번이나 됩니까?

처음에는 마법의 함수 eval로 어떻게든 해보려고 했지만, 왠지 찜찜해서 eval을 사용하지 않는 쪽으로 코드를 고쳤다.
분수 덧샘과 나눗셈을 하는 함수를 구현해서 풀었다.