우연히 구글 코드 잼에서 출제된 재미있는 문제를 발견했다.
출제된 문제에서는
의 결과값에서 마지막 세자리 정수값을 찾는 문제.
예를 들어서 ( 3 + √5)2 인 경우 값은 27.4164079... 이므로 정답은 "027" 이 된다.
첫번째 시도
√5가 2.xxxx 인 점에 착안해서 식을 ( 5 + x)n 로 놓고 시도.
(x는 0보다 크고 1보다 작다)
핵심은 m자리 정수값 x와 m+1 자리에서 처음으로 0이 아닌 값이 등장하는 소수값 y 를 곱할 경우 0보다 작다는 점에 착안함.
(ex : 99 * 0.009 < 1 )
( 5 + x)n 을 변형하면
과 같다.
n+1 개의 각 단항식의 결과값을 정수부분과 소수부분으로 나워서 정수 부분만 더한다...
는게 전략이었으나 n+1 개의 단항식의 소수부분의 총합이 1보다 작음을 증명할 수 없어서(수학 능력 부족-_-) 다른 방법을 모색함..
두번째 시도
이 방법은 첫번째에서 막힌
의 증명을 피하기 위해서 생각해낸 방법으로 더 간단하다.
우선 3 + √5 를 근으로 하는 2차 방정식을 하나 유도해보자.
식1에 3 + √5 를 대입한 후 유리수와 무리수를 분리하면 두개의 식을 얻는다.
두 식으로부터 계산에 편리한 a,b,c 값을 구하면
이므로 식1은 다음과 같다.
이 식을 다음과 같이 변형하면...
식3과 같고 우변의 x에 3 + √5 를 대입해서 정리하면
가 되시겠다.
이제 6√5의 정수부분만 구하면 문제는 초간단 해결!!!!
유효 소수점
식4에서 6√5 의 정수 부분을 구할 때 √5에서 소수점 몇째까지를 구해야 될까?
정수 부분의 자리수를 k 라고 할 때 소수점도 k 자리 만큼만 구하면 된다.
두자리 정수 중 가장 큰 수인 99를 예로 들면 이렇다.
두자리 정수 99와 0.9999999999...를 곱할 경우 정수부분 자리수에 영향을 미치는 소수점은 0.99까지이다.(소수점 두자리까지만 유효)
99 * 0.9 = 89.1
99 * 0.09 = 8.91
99 * 0.009 = 0.891------ dispose!
99 * 0.0009 = 0.0891------ dispose!
.....
세번째 이후의 나머지 소수점의 합은 정수값에 영향을 미치지 못하므로 무시할 수 있다.
√5 = 2.23606797749978969... 이므로 6√5를 곱하면
6 * 0.2 = 1.2 -------- 첫번째 자리까지만 유효
6 * 0.03 = 0.18 ------ dispose!
6 * 0.006 = 0.036 ------ dispose!
6 * 0.0000 = 0.0000 ------ dispose!
6 * 0.00006 = 0.00036 ------ dispose!
....
여기서 1.2가 되는 소수점 첫째자리까지만 유효하다.
√5 의 소수점 구하기
2 < √5 < 3 이므로 2.
2.2 < √5 < 2.3 이므로 2.2
2.23 < √5 < 2.24 이므로 2.23
2.236 < √5 < 2.237 이므로 2.236
이 과정은 √5 와 곱해지는 정수값의 자리수를 보고 필요할때마다 한자리씩 늘려나가면 계산 복잡도를 낮출 수 있다.
정리하면
x3 의 경우 식3의 양변에 x를 곱한다.
32 가 두자리이므로 √5에서 두자리까지만 소수점을 구한 후 곱한다.
143이 구해졌다.
출제된 문제에서는
( 3 + √5 )n -------- 식1
의 결과값에서 마지막 세자리 정수값을 찾는 문제.
예를 들어서 ( 3 + √5)2 인 경우 값은 27.4164079... 이므로 정답은 "027" 이 된다.
첫번째 시도
√5가 2.xxxx 인 점에 착안해서 식을 ( 5 + x)n 로 놓고 시도.
(x는 0보다 크고 1보다 작다)
핵심은 m자리 정수값 x와 m+1 자리에서 처음으로 0이 아닌 값이 등장하는 소수값 y 를 곱할 경우 0보다 작다는 점에 착안함.
(ex : 99 * 0.009 < 1 )
( 5 + x)n 을 변형하면
nCn·5n·x0 + nCn-1·5n-1·x1 + nCn-2·5n-2·x2 + ......+ nC1·51·xn-1 + nC0·50·xn
과 같다.
n+1 개의 각 단항식의 결과값을 정수부분과 소수부분으로 나워서 정수 부분만 더한다...
는게 전략이었으나 n+1 개의 단항식의 소수부분의 총합이 1보다 작음을 증명할 수 없어서(수학 능력 부족-_-) 다른 방법을 모색함..
두번째 시도
이 방법은 첫번째에서 막힌
n+1개의 단항식의 소수부분의 합이 1보다 작다
의 증명을 피하기 위해서 생각해낸 방법으로 더 간단하다.
우선 3 + √5 를 근으로 하는 2차 방정식을 하나 유도해보자.
ax2 + bx +c = 0 --------- 식1
식1에 3 + √5 를 대입한 후 유리수와 무리수를 분리하면 두개의 식을 얻는다.
14a + 3b + c = 0
6a + b = 0
6a + b = 0
두 식으로부터 계산에 편리한 a,b,c 값을 구하면
a = 1, b= -6 , c = 4
이므로 식1은 다음과 같다.
x2 - 6x + 4 = 0 --------- 식2
이 식을 다음과 같이 변형하면...
x2 = 6x - 4 --------- 식3
식3과 같고 우변의 x에 3 + √5 를 대입해서 정리하면
x2 = 6(3 + √5) - 4 = 14 + 6√5 ------ 식4
가 되시겠다.
이제 6√5의 정수부분만 구하면 문제는 초간단 해결!!!!
유효 소수점
식4에서 6√5 의 정수 부분을 구할 때 √5에서 소수점 몇째까지를 구해야 될까?
정수 부분의 자리수를 k 라고 할 때 소수점도 k 자리 만큼만 구하면 된다.
두자리 정수 중 가장 큰 수인 99를 예로 들면 이렇다.
두자리 정수 99와 0.9999999999...를 곱할 경우 정수부분 자리수에 영향을 미치는 소수점은 0.99까지이다.(소수점 두자리까지만 유효)
99 * 0.9 = 89.1
99 * 0.09 = 8.91
99 * 0.009 = 0.891------ dispose!
99 * 0.0009 = 0.0891------ dispose!
.....
세번째 이후의 나머지 소수점의 합은 정수값에 영향을 미치지 못하므로 무시할 수 있다.
√5 = 2.23606797749978969... 이므로 6√5를 곱하면
6 * 0.2 = 1.2 -------- 첫번째 자리까지만 유효
6 * 0.03 = 0.18 ------ dispose!
6 * 0.006 = 0.036 ------ dispose!
6 * 0.0000 = 0.0000 ------ dispose!
6 * 0.00006 = 0.00036 ------ dispose!
....
여기서 1.2가 되는 소수점 첫째자리까지만 유효하다.
√5 의 소수점 구하기
2 < √5 < 3 이므로 2.
2.2 < √5 < 2.3 이므로 2.2
2.23 < √5 < 2.24 이므로 2.23
2.236 < √5 < 2.237 이므로 2.236
이 과정은 √5 와 곱해지는 정수값의 자리수를 보고 필요할때마다 한자리씩 늘려나가면 계산 복잡도를 낮출 수 있다.
정리하면
x3 의 경우 식3의 양변에 x를 곱한다.
x3 = (6x -4)x
= 6x2 - 4x
= 6(6x-4) - 4x
= 32x -24
= 32(3 + √5) - 24
= 72 + 32√5
= 6x2 - 4x
= 6(6x-4) - 4x
= 32x -24
= 32(3 + √5) - 24
= 72 + 32√5
32 가 두자리이므로 √5에서 두자리까지만 소수점을 구한 후 곱한다.
x3 ≒ 72 + 32*2.23 = 143.36
143이 구해졌다.
'Dev' 카테고리의 다른 글
| drawing LineGraph using Javascript (0) | 2008.10.23 |
|---|---|
| 티스토리 메뉴 디자인 (0) | 2008.06.30 |
| useful firefox add-ons (0) | 2008.06.14 |