« Project Euler --- Problem 27 再び | トップページ | 自作の手続きたち »

2009年3月23日 (月)

Project Euler --- Problem 4

問題は「3桁の数の積で表される回文数のうち最大のものはいくらになるか」というものでした。

まず初めに考えつくのが、3 桁 × 3 桁の数のうち回文数になるものを探し出していくというものでしょう。(解答例には「内包表記」が使用されています)

(define palindromic-number? (lambda (n) (palindromic-list? (integer->list n)))) (define problem-004 (lambda () (let ([lst (set-of c (a in (sequence 100 999)) (b in (sequence a 999)) (c is (* a b)) (palindromic-number? c))]) (printf "~d~%" (apply max lst))))) (problem-004)

でもこれは最大のものを 1 つ見つけるために約 400000 回計算することになるので、答えが出るまでにちょっと時間がかかります。


そこで、ちょっと考え方を変えてみます。

ある数の約数を小さい順に並べると、その数の平方根を挟んで近い順から 2 つの数をかけると、すべて元の数になりますよね。

例えば 12 の場合、約数は 1, 2, 3, 4, 6, 12 ですから、

3 x 4 = 12
2 x 6 = 12
1 x 12 = 12

となります。

3 桁 × 3 桁の数は 5 桁か 6 桁になります。

そこで、6 桁または 5 桁の回文数を大きい順に調べていって、その数の平方根を挟んで、3 桁の約数が並んでいるものを探せば、それが答えとなるはずです。

;;; 第 1 引数をもとにして、第 2 引数が #t なら偶数桁、 ;;; それ以外なら奇数桁の回文数を作る。 (define make-palindromic-number (lambda (n . flag) (let* ([flag (if [null? flag] #f (car flag))] [a (integer->list n)] [b (reverse a)]) (list->integer (append a (if flag b (cdr b))))))) (define problem-004 (lambda () ;; その数の平方根を挟んで一番近い 2 つの約数の組を探す。 (define find-divisor (lambda (n) (let loop ([m (isqrt n)]) (if [zero? (remainder n m)] (cons m (/ n m)) (loop (- m 1)))))) (define 3digits-pair? (lambda (pair) (let ([a (car pair)] [b (cdr pair)]) (and (and (> a 99) (< a 1000)) (and (> b 99) (< b 1000)))))) ;; まず、6 桁の回文数を調べる。 ;; もしなければ、5 桁の回文数を調べる。 (let loop ([n 997] [flag #t]) (if [< n 100] (if flag (loop 999 #f) #f) (let* ([p-num (make-palindromic-number n flag)] [pair (find-divisor p-num)]) (if [3digits-pair? pair] (printf "~d~%" p-num) (loop (- n 1) flag))))))) (problem-004)

この方法だと、最初の一つを見つければ計算が終わるので、私のパソコンでも短時間で答えが出ます。

$ time petite --script problem004.ss 906609 (= 913 * 993) real 0m0.355s user 0m0.216s sys 0m0.016s

REPL で実行した場合は次のようになりました。

> (time (problem-004)) 906609 (= 913 * 993) (time (problem-004)) no collections 20 ms elapsed cpu time 20 ms elapsed real time 42936 bytes allocated

ちなみに私のパソコンは Pentium 1500MHz, Ubuntu 8.10 で動いています。


追記:Project Euler - Problem 4 再びも参照してみてください。

« Project Euler --- Problem 27 再び | トップページ | 自作の手続きたち »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/44441659

この記事へのトラックバック一覧です: Project Euler --- Problem 4:

« Project Euler --- Problem 27 再び | トップページ | 自作の手続きたち »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ