Project Euler(with Scheme) Problem 76〜80

めっちゃ進むな。
番号が進んでいるだけで実力が伸びているかはあやしいが。

Problem 76

漸化式作るんだろうなぁと思いながら飛ばす。
f(n,k)=nをk個の項で作る場合の数、でやればいいんかな？

Problem 77

(define limit (read))

(define memo-vec (make-vector (+ limit 1) 0))
(vector-set! memo-vec 0 1)
(display "memo-vec made!")
(newline)

(define (primenum-list limit)
  (define (num-gene start end) (if (> start end) '() (cons start (num-gene (+ start 1) end))))
  (define (erat list)
    (define (remove ele lis)
      (if (null? lis) '()
          (if (= 0 (modulo (car lis) ele)) (remove ele (cdr lis))
              (cons (car lis) (remove ele (cdr lis))))))
    (if (null? list) '() (cons (car list) (erat (remove (car list) (cdr list))))))
  (erat (num-gene 2 limit)))

(define (update-prime prime)
  (define (sub i)
    (if (> (+ i prime)  limit) (begin (display prime) (display " is finish!") (newline))
        (let ((past (vector-ref memo-vec (+ i prime))))
          (begin (vector-set! memo-vec (+ prime i) (+ past (vector-ref memo-vec i))) (sub (+ i 1))))))
  (sub 0))

(define (solve list)
  (if (null? list) (begin (display "update OK!") (newline))
      (begin (update-prime (car list)) (solve (cdr list)))))

(define (prime? n)
  (define (sub i)
    (cond  ((> (* i i) n) #f)
           ((= 0 (modulo n i)) #t)
           (#t (sub (+ i 1)))))
  (sub 2))
        

(define (over-5000 vec)
  (define (sub i)
    (if (>= i (vector-length vec)) "dismiss!!"
        (if (or (and (prime? i) (>= (vector-ref vec i) 5001)) (>= (vector-ref vec i) 5000)) i
            (sub (+ i 1)))))
  (sub 0))

(define (over-5 vec)
  (define (sub i)
    (if (>= i (vector-length vec)) "dismiss!!"
        (if (or (and (prime? i) (>= (vector-ref vec i) 6)) (>= (vector-ref vec i) 5)) i
            (sub (+ i 1)))))
  (sub 0))

(define plist (primenum-list limit))
(display "prime-list OK!")
(newline)

(solve plist)
;(over-5 memo-vec)
(over-5000 memo-vec)

普通めの全探索。意外と答え小さいのね。

Problem 78

漸化式立てればいいんでしょう〜多分〜

Problem 79

こういうの、問題文の理解だけでも大変〜

Problem 80

(define (ketasum n) (if (= n 0) 0 (+ (modulo n 10) (ketasum (quotient n 10)))))
(define (ketawa keta num)
  (ketasum (string->number (substring (number->string num) 0 keta))))
(define (search-root-n n bunbo)
  (define (sub left right center)
    (let* ((center-value (/ center bunbo))
           (nijo (* center-value center-value)))
      (cond ((= (+ left 1) right) left)
            ((>= nijo n) (sub left center (quotient (+ center left) 2)))
            (#t (sub center right (quotient (+ center right) 2))))))
  (if (<= n 1) 0 (sub 1 (* n bunbo) (quotient (+ n 1) 2))))

(define (ruijo n m) (cond ((= m 0) 1) ((= m 1) n) (#t (* n (ruijo n (- m 1))))))

;(search-root-n 2 (ruijo 10 200))
;root(2)の頭100桁の和は(ketawa 100 (search-root-n 2 (ruijo 10 200)))
(define (square? n)
  (define (sub i)
    (cond  ((> (* i i) n) #f)
           ((= 0 (modulo n i)) #t)
           (#t (sub (+ i 1)))))
  (if (= n 1) #t (sub 2)))

(define (solve limit)
  (define (sub i sum)
    (if (> i limit) sum
        (sub (+ i 1) (+ sum (if (square? i) 0 (ketawa 100 (search-root-n i (ruijo 10 200))))))))
  (sub 1 0))

(solve 2)
(solve 100)

これは解けているようで解けていません。ただ、root(2)の頭100桁の総和が475なのは合っています。