제곱근 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을 사용하지 않는 쪽으로 코드를 고쳤다.
분수 덧샘과 나눗셈을 하는 함수를 구현해서 풀었다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#!/usr/bin/env perl use 5.010; use strict; use warnings; use Math::BigInt; my $c = 0; my ($k, $K) = (Math::BigInt->new(1), Math::BigInt->new(2)); my ($o, $t) = (Math::BigInt->new(1), Math::BigInt->new(2)); for (1..1000) { ($k, $K) = dv(($o, $o), sm(($t, $o), ($k, $K))); my ($n, $N) = sm(($o, $o), ($k, $K)); $c++ if (length($n->bstr()) > length($N->bstr())); } say $c; sub sm { my($a, $A, $b, $B) = @_; return ((Math::BigInt->new($a)->bmul(Math::BigInt->new($B)))->badd(Math::BigInt->new($b)->bmul(Math::BigInt->new($A))), Math::BigInt->new($A)->bmul(Math::BigInt->new($B))) } sub dv{ my($a, $A, $b, $B) = @_; return ((Math::BigInt->new($a)->bmul(Math::BigInt->new($B))), (Math::BigInt->new($b)->bmul(Math::BigInt->new($A)))) } |