Problem 28 - 対角線の和
この問題は面白かった。
1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される:
21 22 23 24 25
20 07 08 09 10
19 06 01 02 11
18 05 04 03 12
17 16 15 14 13対角線上の数字の合計はどちらも101であることが確かめられる.
1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の合計はともにいくつだろうか?
何か法則が見える。
さて法則を見破る。f(n)で、nは偶数とする。
f(1)の時、1
f(3)の時、f(1) + 3 + 5 + 7 + 9
f(5)の時、f(3) + 13 + 17 + 21 + 25
となる。
もうちょい深める。対角線なので、4つづつ増える事を利用してまとめる。
f(1)の時、1
f(3)の時、f(1) + (3 + 9) + (5 + 7) = f(1) + (3 + 9) * 2
f(5)の時、f(3) + (13 + 25) + (17 + 21) = f(3) + (13 + 25) * 2
つまり、f(n) = f(n-2) + (始点+終点)*2である。
始点は、(n - 2)^2 + (n - 1)
終点は、n^2なので、
f(1) = 1
f(n) = f(n-2) + (n^2 + (n - 2)^2 + n - 1) * 2
という式を導き出した。
後はコーディングするだけ。
(define (problem28 n) (define (square n) (* n n)) (define (iter n) (if (= n 1) 1 (+ (* 2 (+ (square n) (square (- n 2)) n -1)) (problem28 (- n 2))))) (iter n)) (problem28 1001) ; 669171001
あってた。ちょっとビックリ。