<br />
<b>Deprecated</b>:  The each() function is deprecated. This message will be suppressed on further calls in <b>/home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php</b> on line <b>456</b><br />
;; FUNZIONI RICORSIVE SUI NUMERI NATURALI

;; Struttura del corpo di una f.ne ricorsiva
;; di tipo tail recursion
;; costrutto cond
;; -clausola caso base
;; -clausola caso induttivo (richiamo della
;; f.ne stessa)
;; nota: entrambe le clausole possono 
;; essere piu' di una

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Esercizio: implementare la funzione 
;; fattoriale

;; 1)definizione informale dell'operazione
;; 2)parametri formali ?
;; 3)implementazione (ricordare la struttura 
;; della funzione descritta sopra!)
;; 4)test

;; Definizione? caso base? passo induttivo?

;; fattoriale: number -> number
(define (fattoriale n)
  (cond
    ;; caso base
    [(= n 0) 1] 
    ;; passo induttivo
    [else (* n (fattoriale (- n 1)))]))

;; Domanda: cosa accade se fattoriale
;; non descrive il caso base?
;; risultato incorretto ?
;; la funzione termina ?


;;;;;;;;;;;;;;;
;; Esercizio: implementare la funzione 
;; di Fibonacci definita come segue:
;; Fb(n) = 1 se n=0 oppure se n=1
;; Fb(n) = Fb(n-1) + Fb(n-2)

;; 3)implementazione (ricordare la struttura 
;; della funzione descritta sopra!)
;; 4)test

;; Fb: number -> number 
(define (Fb n)
  (cond
    ;; caso base 
    [(or (= n 0) (= n 1)) 1]
    ;; passo induttivo
    [else (+ (Fb (- n 1)) (Fb (- n 2)))]))


;;;;;;;;;;;;;;;
;; Esercizio: implementare la somma fra 
;; 2 numeri, supponendo di disporre delle
;; sole operazioni di incremento e 
;; decremento di una unita'

;; 1)definizione informale dell'operazione
;; 2)parametri formali ?
;; 3)implementazione (ricordare la struttura 
;; della funzione descritta sopra!)
;; 4)test

;; somma: number number -> number
(define (somma a b)
  ( cond
     ([= b 0] a)
     (else (+ 1 (somma a (- b 1))))))

;;;;;;;;;;;;;;;
;; Esercizio: implementare il prodotto fra 
;; 2 numeri supponendo di disporre della
;; sola operazione di somma (usare la f.ne
;; somma appena definita)

;; 1)definizione informale dell'operazione
;; 2)parametri formali ?
;; 3)implementazione
;; 4)test

;; prodotto: number number -> number
(define (prodotto a b)
  (cond
    [(= b 0) 0]
    [(= b 1) a] 
    ;;esempio di 2 clausole per il caso base
    [else (somma a (prodotto a (- b 1)))]))
   
;;;;;;;;;;;;;;;
;; Esercizio: implementare la funzione
;; fattoriale supponendo di disporre della
;; sola operazione di prodotto definita sopra

;; fatt: number -> number
(define (fatt n)
  (cond
    ;; caso base
    [(= n 0) 1] 
    ;; passo induttivo
    [else 
     (prodotto n (fatt (- n 1)))]))

;; NOTA: fatt utilizza solo le operazioni
;; aritmetiche di incremento e 
;; decremento di una unita'.
;; La complessita' computazionale di fatt 
;; e' sensibilmente piu' elevata di fattoriale.
;; Confrontare il tempo di calcolo necessario
;; per fatt e fattoriale


;;;;;;;;;;;;;;; 
;; Esercizio: implementare somma_n
;; somma_n, dato in input un naturale 
;; restituisce la somma dei primi n numeri
;; naturali

;; 1)definizione informale dell'operazione
;; Prima soluzione, non ricorsiva
;; la somma dei primi n numeri naturali e' 
;; pari a n * (n+1) / 2

;; somma_n: number -> number
(define (somma_n n) (/ (* (+ n 1) n) 2))

;; 1)definizione informale dell'operazione
;; Soluzione ricorsiva
;; somma_nr(n) = ???

;; somma_nr: number -> number
(define (somma_nr n) 
  ( cond
    ([= n 0] 0)
    (else (+ n (somma_n (- n 1))))))

;; suggerimento: verificare il 
;; funzionamento di somma_nr con step
;(somma_nr 4)


;;;;;;;;;;;;;;; Esercizio dato a Lezione
;; Esercizio: implementare una funzione
;; che calcoli b elevato alla n
;; 1)definizione informale dell'operazione
;; 2)parametri formali ?
;; 3)implementazione
;; 4)test

;; 1) come definire b elevato alla n ?


;; esponente: number number -> number
(define (esponente b n) 
  ( cond 
    ([= n 0] 1)
    (else (* b (esponente b (- n 1))))))

;; costruire gli step x (esponente 4 2)
;(esponente 4 2)

;;;;;;;;;;;;;;; 
;; Esercizio: implementare esponente
;; utilizzando solo l'operazione di 
;; incremento e decremento di una unita'
;; Test in classe

;;;;;;;;;;;;;;;
;; Esercizio: implementare la funzione
;; pari? che determini se e' vero che
;; il numero in ingresso n e' pari o no
;; rispondendo con un valore booleano
;; 1)definizione informale dell'operazione
;; 2)parametri formali ?
;; 3)implementazione
;; 4)test

;; 1) come formalizzare la proprieta' di
;; essere numeri pari?

;; pari?: number -> boolean
;(define (pari? n)
;  (or (= n 0) 
;  (cond 
;    ([>= n 2] (pari? (- n 2)))
;    (else false))))

;; NOTA: osservare gli operatori di 
;; or nell'espressione

;; Domanda: come implementereste la 
;; funzione dispari?
(define (dispari? n)
  (or (= n 1) 
  (cond 
    ([>= n 3] (dispari? (- n 2)))
    (else false))))

;;;;;;;;;;;;;;;
;; Funzione pari: Soluzione alternativa
;; un numero e' pari se e' 0 oppure 
;; se n-1>0 e n-1 e' dispari, n e' 
;; dispari se n=1 oppure se n-1 e' pari
;; esempio di mutua ricorsione

(define (pari2nd? n)
  (cond
    [(= n 0) true]
    [else (dispari2nd? (- n 1))]))

(define (dispari2nd? n)
  (cond
    [(= n 0) false]
    [(= n 1) true]
    [else (pari2nd? (- n 1))]))

;; Notare la mutua ricorsione e le
;; condizioni di terminazione
;; nella funzione dispari2nd?,
;; altrimenti dispari2nd? 0, pari? 1
;; non terminerebbero

;;;;;;;;;;;;; Lezione del 24/10/01
;;;;;;;;;;;;;;;
;; Esercizio: implementare la f.ne
;; pari con la definizione:
;; 0 e' pari
;; n e' pari se n-1 non lo e'

(define (pari? n) 
  (cond
    [(= n 0) true]
    [else (not (pari? (- n 1)))]))
          
;;;;;;;;;;;;;;; 
;; Esercizio
;; Implementare la funzione esponente
;; ottimizzata:
;; b^n = (b^(n/2))^2 se n pari
;; b^n = b * b^(n-1) se n dispari
;; Attenzione: come scrivere (b^(n/2))^2?
;; come prodotto (b^(n/2)*b^(n/2) )? 
;; come quadrato (square b(n/2)) ?
;; analizzare quale scelta ottimizza la 
;; computazione
(define (esponente2 b n)
   (cond 
   [(= n 0) 1]
   [(
     pari? n) (square 
               (esponente2 b (/ n 2)))]
   [else (* b (esponente2 (- n 1)))]))

;;;;;;;;;;;;;;; 
;; Esercizio: determinare se un numero e' 
;; un multiplo dell'altro
;; multiplo?: number number -> boolean

(define (multiplo? a b)
  (cond
    [(= a b) true]
    [(> b a) false]
    [else (multiplo? (- a b) b)]))

;; Soluzine alternativa
(define (multiplo2? a b)
  (mult? a b b))

(define (mult? a sp b)
  (cond
    [(= a sp) true]
    [(> sp a) false]
    [else (mult? a (+ sp b) b)]))

;(multiplo2? 6 2)

;;;;;;;;;;;;;;; 
;; Esercizio: determinare il resto della
;; divisione intera fra due naturali
;; resto: number number -> number


;;;;;;;;;;;;;;;
;; Esercizio
;; Implementare l'espressione di >=
;; supponendo di avere solo inc 
;; e dec unitario 
;; definizione della relazione >=?

(define (maggioreouguale? a b)
  (cond 
    [(= a b) true]
    [(= a 0) false]
    [else (maggioreouguale? (- a 1) b)]))

;;;;;;;;;;;;;;; 
;; Esercizio:
;; Implementare una funzione che esegue il 
;; confronto di > fra 2 numeri supponendo di 
;; avere solo inc e dec unitario
;; e l'operatore di uguaglianza
;; esempio: (maggiore? 3 7) -> false
;; esempio: (maggiore? 7 3) -> true
;; esempio: (maggiore? 7 7) -> false

;; Domanda: come definire la relazione?

;; Soluzione
;; (maggiore? 0 b) -> false, per ogni b
;; (maggiore? a b) -> true se esiste un
;; numero a' t.c. vale 0<=a'< a, a'=b,
;; false altrimenti

(define (maggiore? a b)
  (cond
    [(= a 0) false]
    [else (maggioreouguale? (- a 1) b)]))

;; funzione che testa la seconda
;; clausola formalizzata sopra

;; soluzione alternativa:
;; evito il caso che siano uguali
;; confrontando (a-1) invece che a con b
(define (magg? a b)
  (cond
    [(= a 0) false]
    [(= (- a 1) b) true]
    [else (magg? (- a 1) b)]))


 ;; ordine delle clausole: la seconda 
 ;; clausola non puo' essere invertita
 ;; con la prima provare (maggiore? 1 0)
 ;; con le clausole invertite


;;;;;;;;;;;;;;; 
;; Esercizio: implementare la funzione
;; MCD (Massimo Comune Divisore)

;; definizione della relazione?

;; Algoritmo di Euclide
;; MCD(a,b)=a, se a=b
;; MCD(a,b)= MCD(a-b,b) se a>b
;; MCD(a,b)= MCD(a,b-a) se a<b
; .... implementare
(define (MCD a b)
  (cond 
    [(= a b) a]
    [(> a b) (MCD (- a b) b)]
    [else (MCD b (- b a))]))

;;;;;;;;;;;;;;; 
;; Esercizio: implementare la funzione
;; mcm (minimo comune multiplo)

;; mcm (a b) = (a*b)/MCD(a,b)
(define (mcm a b)
  (/ (* a b) (MCD a b)))

;;;;;;;;;;;;;;; 
;; Esercizio: determinare se, dato
;; un numero n, questo e' primo
;; primo?: number -> boolean

;; prim? number number -> boolean
(define (prim? n1 n2)
  (cond 
    ([or (= n2 1) (= n1 1)] true) 
    (else (and 
           (not (= (remainder n1 n2) 0)) 
           (prim? n1 (- n2 1))))))

;; primo? number -> boolean
(define (primo? n)
  ( prim? n (- n 1)))