Project Euler(with Scheme) Problem 28〜31

続けてるってば！！！

Problem 28

普通に足し込むコード。

(define (taken n list)
  (define (sub counter wa lis)
    (cond ((null? lis) wa)
          ((= counter 0) (sub n (+ wa (car lis)) (cdr lis)))
          (#t (sub (- counter 1) wa (cdr lis)))))
  (sub n 0 list))

(define (generate start end)
  (if (> start end) '()
      (cons start (generate (+ start 1) end))))

(define (nijo n) (* n n))

(define (gene n) (generate (+ (nijo (- (* 2 n) 3)) 1) (nijo (- (* 2 n) 1))))

(define (calc n)
  (if (= n 1) 1
      (taken (- (* n 2) 3) (generate (+ (nijo (- (* 2 n) 3)) 1) (nijo (- (* 2 n) 1))))))

(define (solve n)
  (define (sub i)
    (if (> i n) 0
        (+ (calc i) (sub (+ i 1)))))
  (sub 1))

(display (solve 501))
(newline)

解きながら途中で気づいた(が、書き直すの面倒だからやらなかった)のですが、螺旋の各階層において
右上＋右下　＝　左下＋左上
になりますね。それを利用するともっとはやい(O(n))。僕の上記コードはO(n^2)かと。

Problem 29

今日も元気に全探索。キレイではないにせよ、スムーズに詰まらず全探索は書けるようになったかな。

(define (insert n orderedlist)
  (cond ((null? orderedlist) (cons n orderedlist))
        ((< n (car orderedlist)) (cons n orderedlist))
        ((= n (car orderedlist)) orderedlist)
        (#t (cons (car orderedlist) (insert n (cdr orderedlist))))))

(define (beki a b)
  (if (= b 0) 1
      (* a (beki a (- b 1)))))

(define (kosu list)
  (if (null? list) 0 (+ 1 (kosu (cdr list)))))

(define (solve astart aend bstart bend)
  (define (sub a b list)
    (if (> a aend) (kosu list)
        (sub (if (= b bend) (+ a 1) a) (if (= b bend) bstart (+ b 1)) (insert (beki a b) list))))
  (sub astart bstart '()))

;(display (solve 2 5 2 5))
;(newline)

(display (solve 2 100 2 100))
(newline)

Problem 30

(define (5josu n)
  (define (5josum i)
    (define (5jo n) (* n n n n n))
    (if (= i 0) 0
        (+ (5jo (modulo i 10)) (5josum (quotient i 10)))))
  (= n (5josum n)))
;true or false

(define (solve n)
  (if (= n 1) 0
      (+ (if (5josu n) n 0) (solve (- n 1)))))

(display (solve 1000000))
(newline)

Problem 31

;帰納的に書きたいよう・・・関数型なんだし
;(func 残額 残っているコインのリスト)みたいに書けないだろうか
;1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p)→200を作る

(define (solve left coins)
  (cond ((= left 0) 1)
        ((null? coins) 0);left > 0
        ((< left 0) 0)
        (#t (+ (solve(- left (car coins)) coins) (solve left (cdr coins))))));coins is not null and left > 0

(display (solve 200 '(1 2 5 10 20 50 100 200)))
(newline)

めちゃくちゃキレイに書けたぞい！！！！！オラァ！！！！！！！
くぅ〜帰納的〜〜〜！関数型ぁ〜〜〜〜！！！

これで、学生時代に解いた問題に追いつきました。
というかこの問題とかは確実にJavaで全探索で、という芸のない解き方をしていたので、成長が感じられる。
ここからは未知の問題ですが、頑張ってSchemeで解いていくぞ〜！！！