;; Questo file contiene il codice Scheme che risolve
;; alcuni degli esercizi svolti in classe;
;; altri esempi sono nuovi - 29/11/02


;; Serie armonica: approccio ricorsivo

(define harmonic
  (lambda (n)    ;; n naturale positivo
    (if (= n 1)
        1
        (+ (harmonic (- n 1)) (/ 1 n))
        )
    ))


;; Serie armonica (torre di carte): approccio "iterativo"

(define card-tower
  (lambda (n)    ;; n naturale positivo
    (harmonic-iter 0 n)
    ))

(define harmonic-iter
  (lambda (sum n)
    (if (= n 0)
        sum
        (harmonic-iter (+ sum (/ 1 n)) (- n 1))
        )
    ))


;; Massimo Comun Divisore (MCD)

(define gcd-of
  (lambda (x y)        ;; x, y naturali positivi
    (cond ((= x y) x)
          ((< x y) (gcd-of x (- y x)))
          (else (gcd-of (- x y) y))     ;; x > y
          )
    ))


;; Calcolo del MCD e di una combinazione lineare intera:
;;
;;   (extended-gcd a b)  -->  ( MCD(a,b)  u  v )
;;
;; tale che  MCD(a,b) = ua + vb

(define extended-gcd
  (lambda (x y)                 ;; x, y naturali positivi
    (ext-gcd-iter x y 1 0 0 1)
    ))

(define extd-gcd-iter
  (lambda (x y i j k l)
    (cond ((= x y) (list x i j))
          ((> x y) (extd-gcd-iter (- x y) y (- i k) (- j l) k l))
          (else    (extd-gcd-iter x (- y x) i j (- k i) (- l j)))
          )
    ))


;; Numeri primi

(define prime?
  (lambda (n)      ;; n „ 2 naturale
    (if (even? n)
        (= n 2)    ;; true se e solo se n=2
        (odd-indivisible? n 3 (floor (sqrt n)))
        )
    ))

(define odd-indivisible?  ;; true se e solo se non ci sono divisori
  (lambda (n first last)  ;; dispari di n compresi fra first e last
    (cond ((> first last) #t)
          ((= (remainder n first) 0) #f)
          (else (odd-indivisible? n (+ first 2) last))
          )
    ))