nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるか
与えられた木から・・・の回答例を巡ってたら、「nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかという問題」をScalaで解いてみた - Onion開発停滞日記 > Achiral に Scan とか Pairwise とか条件変化可能な TakeWhile を入れてみた - NyaRuRuの日記 > プログラミング言語が与える影響 (GrayRecord)
と、辿っていって、
nを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかを考えます。
1からnまでのn^2の和の公式は、
Σn^2 = n(n + 1)(2n + 1)/6
なので、nについて解けば、O(1)で回答が出そうなんですが、面倒なので二分探索でいきます。
探査フェーズは2つ。
- 1から2,4,8,16...と2乗しながらn(n + 1)(2n + 1)/6 >= 2000として、大体の範囲(2000の場合17〜32)を求めます。
- そしたら、二分探索開始
- (17 + 32)/2をして17と32の真ん中を求める。真ん中と比較して、
- 2000以上ならば、17〜真ん中にターゲットあり。
- 2000より少なければ、(真ん中 + 1)〜32にターゲットあり。
- 探索できなくなるまで繰り返す。
するっと、
(define (problem x) (define (search1 n f cont) (if (f n) (cont (+ (/ n 2) 1) n) (search1 (* n 2) f cont))) (define (search2 a b f) (if (= a b) a (let ((center (quotient (+ a b) 2))) (if (f center) (search2 a center f) (search2 (+ center 1) b f))))) (define (sum n) (/ (* n (+ n 1) (+ (* n 2) 1)) 6)) (define (cmp n) (>= (sum n) x)) (sum (search1 1 cmp (lambda (a b) (search2 a b cmp))))) (problem 2000) ; 2109 (problem 20000000000000000) ; 20000112783013600 (problem 2000000000000000000000000000000000) ; 2000000000009444638248241095719654
二分探索はえぇぇ。
(二分探索が優勢らしい)