Problem 56 - Google
そういえば、googleって数の大きさだったっけ。
Google (10^100)は非常に大きな数である: 1の後に0が100個続く. 100^100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である.
a, b < 100について自然数a^bを考える. 桁の和の最大を答えよ.
力づくなら簡単なんだけど。
(define (number->list n . base) (letrec ((b (if (null? base) 10 (car base))) (iter (lambda (acc n) (let ((q (quotient n b)) (m (cons (modulo n b) acc))) (if (zero? q) m (iter m q)))))) (iter '() n))) (define (problem56 n) (letrec ((iter (lambda (a b sum) (cond ((zero? a) sum) ((zero? b) (iter (- a 1) n sum)) (else (let* ((x (expt a b)) (s (apply + (number->list x)))) (iter a (- b 1) (if (> s sum) s sum)))))))) (iter (- n 1) (- n 1) 0))) (problem56 100) ; 972
100^2回の演算回数を必要としてしまう。
100から下っていけば、答えはすぐに求まるはずなので、終了条件をどう絞るかというのがポイントになるみたい。
ちと考えてみる。
終了条件を絞る
a^bが、999だとすると、数値の合計は27になる。つまり、合計が28なら4桁以上であることがわかる。
処理すべき桁数がわかるので、処理を打ち切って、次に進む事が出来る。
(define (problem56 n) (letrec ((iter (lambda (a b sum) (let* ((x (expt a b)) (s (apply + (number->list x)))) (if (< (/ (log x) (log 10)) (/ sum 9)) (if (= b n) sum (iter (- a 1) n sum)) (iter a (- b 1) (if (> s sum) s sum))))))) (iter (- n 1) (- n 1) 0))) (problem56 100) ; 972
かなり絞れたけど、まだまだ重い。