Questo documento propone alcuni esercizi in preparazione alla
prova di accertamento della prima parte del corso di Programmazione.
Molti degli esercizi sono tratti dal testo del corso
"Concrete Abstraction", capp. 1-5.


1.
Completa il seguente programma per calcolare il quadrato di un
numero naturale.

(define square
  (lambda (n)
    (if (= n 0)
        0
        (if (even? n)
            (___ (square (/ n 2))
                 ___________)
            (+ (square (- n 1))
               (- (+ n n) 1))))))


2.
Scrivi una procedura in Scheme per calcolare la rappresentazione
in base due di un numero intero (positivo, nullo o negativo). Il
risultato deve essere di tipo stringa.


3.
Scrivi una procedura in Scheme che, dato un numero naturale,
determina quante cifre "1" contiene la sua rappresentazione in
base due.


4.
Scrivi una procedura a valori booleani in Scheme che, dato un
numero naturale, determina se la sua rappresentazione in base
due contiene piu' cifre "0" o piu' cifre "1".


5.
Dimostra per induzione che il valore calcolato dalla seguente
procedura in Scheme, in funzione degli argomenti x > 0 ed n >= 0,
(n naturale) e':  (x^(n+1) - 1) / (x - 1).

(define geom
  (lambda (x n)
    (if (= n 0)
        1
        (+ (expt x n) (geom x (- n 1))))))


6.
Dimostra per induzione che il valore calcolato dalla seguente
procedura in Scheme, in funzione degll'argomento naturale n >= 0,
e':  n / (n + 1).

(define f
  (lambda (n)
    (if (= n 0)
        0
        (+ (f (- n 1))
           (/ 1 (* n (+ n 1)))))))


7.
Scrivi una procedura in Scheme basata sull'approccio iterativo
(cioe' sulla ricorsione di coda) che, dato un numero naturale
positivo n, determina la massima potenza k di due tale che n
e' divisibile per 2^k (2 alla k).


8.
Scrivi una versione che genera un processo iterativo (con
ricorsione di coda) del seguente programma in Scheme per
calcolare la massima potenza k di b tale che b^k <= n.

(define closest-power
  (lambda (b n)
    (if (< n b)
        0
        (+ 1 (closest-power b (quotient n b))))))


9.
Per b > 0 e per n intero, valgono le seguenti proprieta'
(x^y significa x elevato alla y):

  (i)    b^n = 1            se n = 0;
  (ii)   b^n = b^(n-1) * b  se n > 0;
  (iii)  b^n = b^(n+1) / b  se n < 0.

Scrivi una procedura in Scheme che calcola l'elevamento a
potenza intera sulla base delle proprieta' (i), (ii) e (iii).
Scrivi anche una versione basata sull'approccio iterativo.


10.
Quante moltiplicazioni vengono effettuate, in funzione di n,
per calcolare (bar n) ?

(define bar
  (lambda (n)
    (cond ((= n 0) 5)
          ((= n 1) 7)
          (else (* n (bar (- n 2)))))))


11.
Considera la seguente definizione:

(define compute
  (lambda (a b)  ;; a, b > 0 naturali
    (cond ((> a b) 0)
          ((= a b) a)
          (else
           (let ((m (quotient (+ a b) 2)))
             (+ (compute a m) (compute (+ m 1) b)))
           ))
    ))

Cosa calcola  (compute 1 n)  in funzione di n?
Dimostra per induzione l'affermazione fatta.


12.
La seguente procedura in Scheme e' progettata per calcolare
un punto di minimo di una funzione f, il cui dominio e' incluso
nell'insieme dei naturali, nell'intervallo [a, b].
Completa la definizione compilando le parti mancanti.

(define integer-in-range-where-smallest
  (lambda (f a b) 
    (if (= a b)
        a
        (let ((smallest-place-after-a 
               ______________))
          (if _________
              a
              smallest-place-after-a)))))



13.
Considera Il seguente programma in Scheme.

(define make-scaled
  (lambda (scale f)
    (lambda (x)
      (* scale (f x)))))

(define add-one
  (lambda (x)
    (+ 1 x)))

(define mystery
  (make-scaled 3 add-one))

Qual e' il risultato della valutazione di  (mystery 4) ?
E di  ((make-scaled 2 (make-scaled 2 3 add-one)) 4) ?


14.
Definisci una procedura a valori booleani in Scheme che verifica
se una funzione f, con dominio l'insieme dei naturali, e' crescente
nell'intervallo [a, b].


15.
Considera le definizioni:

(define f
  (lambda (m b)
    (lambda (x) (+ (* m x) b))))

(define g (f 3 2))

Per ciascuna delle seguenti espressioni, indica se il risultato
e' un numero, una procedura, oppure se si verifica un errore.

  (i)    f
  (ii)   g
  (iii)  (* (f 3 2) 7)
  (iv)   (g 6)
  (v)    (f 6)
  (vi)   ((f 4 7) 5)


16.
Considera la seguente procedura in Scheme:

(define positive-integer-upto-where-smallest
  (lambda (n f) ; return an integer i such that
                ; 1 <= i <= n and for all integers j
                ; in that same range, f(i) <= f(j)
    (define loop
      (lambda (where-smallest-so-far next-to-try)
        (if (> next-to-try n)
            where-smallest-so-far
            (loop (if (< (f next-to-try)
                         (f where-smallest-so-far))
                      next-to-try 
                      where-smallest-so-far)
                  (+ next-to-try 1)))))
    (loop 1 2)))

Durante la valutazione di  (positive-integer-upto-where-smallest n f)
quante volte, in funzione di n, viene applicata la funzione f?
Riusciresti a scrivere una nuova versione che permetta di ottenere
lo stesso risultato con un minor numero di applicazioni ("usi") di f?