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


;; Elevamento a potenza: approccio ricorsivo generale

(define power
  (lambda (x y)        ;; x>0, y naturali
    (cond ((= y 0) 1)
          ((odd? y) (* x (power x (- y 1))))
          (else (power (* x x) (/ y 2)))
          )
    ))


;; Elevamento a potenza: approccio iterativo

(define pow
  (lambda (x y)         ;; x>0, y naturali
    (power-iter x y 1)
    ))

(define power-iter       ;; Invariante: p * x^y
  (lambda (x y p)        ;; x>0, y, p naturali
    (cond ((= y 0) p)
          ((odd? y)
           (power-iter x (- y 1) (* x p)))  ;; (px)*x^(y-1)  = p*x^y
          (else  ;; y pari
           (power-iter (* x x) (/ y 2) p))  ;; p*(x^2)^(y/2) = p*x^y
          )
    ))

;; Come si dimostra per induzione che la valutazione dell'espressione
;; (power-iter b e q) termina e il valore calcolato risulta q * b^e ?


;; Problema dei "Percorsi di Manhattan"

(define manhattan
  (lambda (down right)  ;; down, right naturali
    (if (or (= down 0) (= right 0))
        1
        (+ (manhattan (- down 1) right)
           (manhattan down (- right 1)))
        )
    ))


;; Da numero a ordinale corrispondente
;; in Inglese

(define num->ord  ;; k < 100 naturale
  (lambda (k)
    (let ((last-dgt (remainder k 10)))
      (string-append
       (number->string k)
       (cond ((and (> k 10) (< k 20)) "th")
             ((= last-dgt 1) "st")
             ((= last-dgt 2) "nd")
             ((= last-dgt 3) "rd")
             (else "th")
             )
       ))
    ))


;; Gioco della "Torre di Hanoi"
;; Numero complessivo di mosse (perche'?)

(define number-of-moves
  (lambda (height)
    (if (= height 1)
        1
        (+ (* 2 (number-of-moves (- height 1))) 1)
        )
    ))

;; Come si puo' verificare che i valori delle espressioni
;;
;;       (number-of-moves k)
;; e
;;       (- (expt 2 k) 1)
;;
;; sono uguali per qualsiasi k naturale positivo?