; 블로그 host 자리비운단 글을 올린지 얼마 안되서 슬쩍 들어와볼수있게 됐네요^^
; 앞으로도 이렇게 가끔 들어올수 있을듯 생각이되는군요
; plt scheme 의 개발환경 DrScheme에서 language를 standard(R5RS)로 맞춘후 테스트
; 정수 1에서 n 까지 숫자를 f(n)에 n이하의 수에1이 들어가는 갯수를 k라 할때, f(n) = k
; f(13) = 6 => 1,10,11,12,13 (총 1이 6개)
; n = k 이 되는 최초의 n은 1일때가 된다. 두번째로 n = k가 되는 n을 구하라
(define (num-of-1 n)
(define (next n) (truncate (/ n 10)))
(let loop ((n n) (cnt 0))
(if (<= n 0) cnt
(if (= 1 (remainder n 10)) (loop (next n) (+ cnt 1))
(loop (next n) cnt)))))
; 규칙을 생각하면 f(n)의 값은 (f(n - 1) + (n에 있는 1의 개수)) 의 값이다
; 그러니까 무조건 1부터 계속 중복 계산을 할 필요 없이
; 그 앞항의 값을 계산해놓구 더해가면 된다
(define (glat max-try)
(define (calcul-k i k) (+ k (num-of-1 i)))
(define (how-many-found i k cnt)
(if (= i k) (+ cnt 1)
cnt))
(define (solve i k cnt)
(if (> i max-try) -1
(let* ((new-k (calcul-k i k)) (new-cnt (how-many-found i new-k cnt)))
(if (= 2 new-cnt) i
(solve (+ i 1) new-k new-cnt)))))
(solve 1 0 0))
(define (test ans max-try)
(if (= ans (glat max-try)) 'ok
'failed))
(test 199981 200000)
; 앞으로도 이렇게 가끔 들어올수 있을듯 생각이되는군요
; plt scheme 의 개발환경 DrScheme에서 language를 standard(R5RS)로 맞춘후 테스트
; 정수 1에서 n 까지 숫자를 f(n)에 n이하의 수에1이 들어가는 갯수를 k라 할때, f(n) = k
; f(13) = 6 => 1,10,11,12,13 (총 1이 6개)
; n = k 이 되는 최초의 n은 1일때가 된다. 두번째로 n = k가 되는 n을 구하라
(define (num-of-1 n)
(define (next n) (truncate (/ n 10)))
(let loop ((n n) (cnt 0))
(if (<= n 0) cnt
(if (= 1 (remainder n 10)) (loop (next n) (+ cnt 1))
(loop (next n) cnt)))))
; 규칙을 생각하면 f(n)의 값은 (f(n - 1) + (n에 있는 1의 개수)) 의 값이다
; 그러니까 무조건 1부터 계속 중복 계산을 할 필요 없이
; 그 앞항의 값을 계산해놓구 더해가면 된다
(define (glat max-try)
(define (calcul-k i k) (+ k (num-of-1 i)))
(define (how-many-found i k cnt)
(if (= i k) (+ cnt 1)
cnt))
(define (solve i k cnt)
(if (> i max-try) -1
(let* ((new-k (calcul-k i k)) (new-cnt (how-many-found i new-k cnt)))
(if (= 2 new-cnt) i
(solve (+ i 1) new-k new-cnt)))))
(solve 1 0 0))
(define (test ans max-try)
(if (= ans (glat max-try)) 'ok
'failed))
(test 199981 200000)
