----- 20/12/00 -----

>vorrei sapere come risolvere i seguenti esercizi ...
>- Dimostrare per induzione che la procedura Hanoi richiede 2^k-1 mosse.

Per dimostrare che la procedura di Hanoi di livello n richiede 2^n-1 mosse
s procede per induzione semplice sul numero naturale positivo n.

- caso base: n = 1

  se la torre e' alta 1, basta ovviamente una sola mossa e 2^1-1 = 1.

- ipotesi induttiva:

  supponiamo che per spostare una torre di altezza n-1 occorrano
  2^(n-1) - 1 mosse, dove n > 1.

- passo induttivo: n > 1

  per spostare una torre alta n da A a B, si sposta una torre alta n-1
  da A a C, poi si sposta il disco piu' grande da A a B, quindi si sposta
  la torre alta n-1 da C a B; in tutto si sono fatte:

  (2^(n-1) - 1) + 1 + (2^(n-1) - 1) = 2 * (2^(n-1)) - 2 + 1 = 2^n-1 mosse.

>- Scrivere una procedura iterativa per la rappresentazione dei numeri in base 2.

Per esempio:

(define bin-rep
  (lambda (n)  ;; n naturale
    (bin-iter n "")
    ))

(define bin-iter
  (lambda (n rep)  ;; n naturale, rep stringa
    (if (= n 0)
        rep  ;; la rappresentazione rep e' completa
        (bin-iter (quotient n 2)
                  (string-append (bin-digit (remainder n 2)) rep))
        )
    ))  ;; bin-digit definita come negli esempi delle pagine del corso


>- Determinare una procedura per contare quanti "1" ci sono nella
>rappresentazione di un numero in base 2.

per esempio:

(define conta-bit-1
  (lambda (n)  ;; n naturale
    (if (< n 2)
        n  ;; una cifra binaria: se n=1 c'e' un 1 altrimenti nessuno
        (+ (conta-bit-1 (quotient n 2))
             ;; conta gli "1" in tutte le cifre tranne l'ultima
           (remainder n 2)  ;; aggiunge 1 se l'ultima cifra e' "1"
        )
    ))

----- * -----