Monthly Archives: gennaio 2015

Aritmetica: potenza

Iterativa

MN = Pot(M, N) = M*M*...*M (N fattori)

Ricorsiva

  • M0 = 1, per N = 0
  • MN = M*MN-1, altrimenti

oppure

  • Pot(M, N) = 1, per N = 0
  • Pot(M, N) = M*Pot(M, N-1), altrimenti

Aritmetica: prodotto

Iterativo

  • M*N = 0, per N = 0
  • M*N = M+M+...+M (N addendi), altrimenti

Oppure

  • M*N = 0, per N = 0
  • M*N = INCREMENTAN(0, m), altrimenti

Oppure

  • Prod(M, N) = 0, per N = 0
  • Prod(M, N) = Prod(M, N-1)+M, altrimenti

Esempio

M=5, N=3

Prod(5, 3) = Prod(5, 3-1)+5 = Prod(5, 2)+5 = 10+5 = 15
Prod(5, 2) = Prod(5, 2-1)+5 = Prod(5, 1)+5 = 5+5 = 10
Prod(5, 1) = Prod(5, 1-1)+5 = Prod(5, 0)+5 = 0+5 = 5
Prod(5, 0) = 0

Aritmetica: somma

Iterativa

Osserva le diverse versioni

  1. M+N = M+1 ... +1 (N volte)
  2. M+N = ((...((M+1)+1)...)+1)
  3. Somma(M, N) = Successivo(Successivo(...Successivo(M)...))
  4. Somma(M, N) = SuccessivoN(M)

apri M dita della mano destra
apri N dita della mano sinistra
mentre la mano sinistra non è chiusa esegui
inizio
   apri un dito a destra
   chiudi un dito a sinistra
fine
la risposta è nella mano destra

Ricorsiva

  • Somma(M, N) = M, per N = 0
  • Somma(M, N) = 1+Somma(M, N-1), altrimenti

Esempio

M=5, N=3

Somma(5, 3) = 1+Somma(5, 2) = 1+7 = 8
Somma(5, 2) = 1+Somma(5, 1) = 1+6 = 7
Somma(5, 1) = 1+Somma(5, 0) = 1+5 = 6
Somma(5, 0) = 5

Ricorsiva

  • Somma(M, N) = M, per N = 0
  • Somma(M, N) = Successivo(Somma(M, Precedente(N))), altrimenti

Esempio

M=5, N=3

Somma(5, 3) = Successivo(Somma(5, Precedente(3)) = Successivo(Somma(5, 2)) = Successivo(7) = 8
Somma(5, 2) = Successivo(Somma(5, Precedente(2)) = Successivo(Somma(5, 1)) = Successivo(6) = 7
Somma(5, 1) = Successivo(Somma(5, Precedente(1)) = Successivo(Somma(5, 0)) = Successivo(5) = 6
Somma(5, 0) = 5

Oppure

  • Somma(M, N) = M, per N = 0
  • Somma(M, N) = Somma(M+1, N-1), altrimenti

Oppure

  • Somma(M, N) = M, per N = 0
  • Somma(M, N) = Somma(Successivo(M), Precedente(N)), altrimenti

Esempio

M=5, N=3

Somma(5, 3) = Somma(Successivo(5), Precedente(3)) = Somma(6, 2) = 8
Somma(6, 2) = Somma(Successivo(6), Precedente(2)) = Somma(7, 1) = 8
Somma(7, 1) = Somma(Successivo(7), Precedente(1)) = Somma(8, 0) = 8
Somma(8, 0) = 8

Algoritmo di Euclide

L’algoritmo di Euclide permette di calcolare il massimo comun divisore, MCD, tra due numeri interi. Vedi Wikipedia: Algoritmo di Euclide.

euclide_0Algoritmo

Dati due numeri naturali a e b

  • se b è zero allora la risposta è a
  • altrimenti si divide a per b e si assegna ad r il resto della divisione
    • se r=0 allora la risposta è b
    • altrimenti ab e br e si ripete nuovamente la divisione.

Esempi

Con a=70, b=15

a b r
70 15 70=4*15 + 10
15 10 15=1*10 + 5
10 5 10=2*5 + 0, STOP

MCD(70, 15)=5.

Con a=15, b=70

a b r
15 70 15=0*70 + 15
70 15

MCD(15, 70)=5.

Con a=71, b=15

a b r
71 15 71=4*15 + 11
15 11 15=1*11 + 4
11 4 11=2*4 + 3
4 3 4=1*3 + 1
3 1 3=3*1 + 0, STOP

MCD(71, 15)=1.

euclide_1L’algoritmo precedente può essere trasformato in un programma di alto livello soltanto utilizzando l’istruzione GOTO.

Con qualche modifica (le due assegnazioni vengono eseguite comunque) può essere adattato alla esigenze della programmazione strutturata.

euclideCon qualche altra modifica si semplifica ulteriormente il codice necessario

Dati due numeri naturali a e b

se b è diverso da 0

  • rresto della divisione intera tra a e b
  • ab
  • br
  • ripeti l’operazione

altrimenti

  • la risposta è a

Esempio

Con a=70, b=15

a b r
70 15 70=4*15 + 10
15 10 15=1*10 + 5
10 5 10=2*5 + 0
5 0 STOP

MCD(70, 15)=5.

Versione ricorsiva

Con a=70, b=15

MCD(70, 15) = MCD(15, 70 Mod 15)
= MCD(15, 10) = MCD(10, 15 Mod 10)
= MCD(10, 5) = MCD(5, 10 Mod 5)
= MCD(5, 0) = 5

oppure…

La torre di Hanoi

Il problema

Nel tempio di Brahma si trova una piattaforma di ottone con tre perni di diamanti.
Sul primo di tali perni sono infilati 64 dischi d’oro, di dimensioni decrescenti, che formano una torre.
Si deve portare la torre sul terzo perno, spostando un solo disco alla volta e in modo che mai un disco di diametro maggiore si trovi sopra un disco di diametro minore.
Per risolvere la questione si può utilizzare il secondo perno come perno di servizio.

Quando i monaci termineranno l’opera il mondo sarà finito!

Analisi

Siano D1, D2, …, Dn le etichette dei dischi di una torre di Hanoi con n dischi.

1 Il problema con un solo disco è banale

  1. il disco è sinistra
  2. sposta il disco D1 dalla 1° alla 3° torre

2 Se i dischi sono 2 le mosse sono 3

  1. i dischi sono a sinistra
  2. sposta il disco D1 dalla 1° alla 2° torre
  3. sposta il disco D2 dalla 1° alla 3° torre
  4. sposta il disco D1 dalla 2° alla 3° torre

3 Se i dischi sono 3 le mosse sono 7

  1. i dischi sono a sinistra
  2. sposta il disco D1 dalla 1° alla 3° torre
  3. sposta il disco D2 dalla 1° alla 2° torre
  4. sposta il disco D1 dalla 3° alla 2° torre
  5. sposta il disco D3 dalla 1° alla 3° torre
  6. sposta il disco D1 dalla 2° alla 1° torre
  7. sposta il disco D2 dalla 2° alla 3° torre
  8. sposta il disco D1 dalla 1° alla 3° torre

Se i dischi sono 4, 5, … si può riconoscere lo schema risolutivo

  1. i dischi sono a sinistra
  2. sposta i dischi D1…Dn-1 dalla 1° alla 2° torre (usando la 3° come appoggio) in modo da liberare Dn
  3. sposta il disco Dn dalla 1° alla 3° torre
  4. sposta i dischi D1…Dn-1 dalla 2° alla 3° torre (usando la 1° come appoggio) sopra Dn

Algoritmo

 Ad ogni passo è sufficiente specificare

  • il numero di dischi coinvolti, perché si parla sempre dei dischi in cima a una torre
  • il nome della torre di origine
  • il nome della torre di appoggio
  • il nome della torre di destinazione

allora l’algoritmo risolutivo per il problema

Hanoi(n, origine, appoggio, destinazione)

diventa

  1. Hanoi(n-1, origine , arrivo  , appoggio    )
  2. Hanoi(  1, origine , appoggio, destinazione)
  3. Hanoi(n-1, appoggio, origine , destinazione)

con l’accortezza che nel caso di torre con un solo disco è sufficiente comunicare di spostare il disco dalla torre origine alla torre destinazione.


Dopo aver analizzato il problema decidiamo che il tempo di esecuzione dell’algoritmo è proporzionale al numero di spostamenti di dischi

T(1) = 1
T(2) = T(1)+T(1)+T(1) = 1+1+1 = 3
T(3) = T(2)+T(1)+T(2) = 3+1+3 = 7
T(4) = T(3)+T(1)+T(3) = 7+1+7 = 15
...
T(n) = T(n-1)+T(1)+T(n-1) = 2*T(n-1)+1

Numericamente si tratta della successione

1, 3, 7, 15, 31, 63, 127, ...

cioè

21-1, 22-1, 23-1, 24-1, 25-1, 26-1, 27-1, ...

quindi

T(n) = 2n-1

I tempi necessari per risolvere il problema sono

n T(n) = 2n-1 1 Hz (uomo) 1 GHz (PC)
1 21-1 = 1 un secondo 10-9 s
2 22-1 = 3 3 secondi 3*10-9 s
10 210-1 = 1023 ~17 minuti ~10-6 s
20 220-1 = 1.048.575 ~12 giorni ~10-3 s
30 230-1 = 1.073.741.823 ~34 anni ~1 s
64 264-1 = 18.446.744.073.709.551.615 ~5*1011 anni ~500 anni

Conclusioni

  • L’algoritmo per il problema della torre di Hanoi ha complessità in tempo asintotica esponenziale, O(2n)
  • Non può esistere un algoritmo con complessità minore
  • Il problema della torre di Hanoi è un problema intrinsecamente esponenziale
  • Il problema della torre di Hanoi è un problema intrattabile!

Problemi con caratteri

Un carattere

  1. Restituire il maiuscolo (minuscolo) corrispondente
  2. È maiuscolo (minuscolo, cifra)?

Due caratteri

  1. Sono la stessa lettera?
    • a=A / a=a / A=a, A=A
  2. Quanto vale la somma dei codici tra i due caratteri?
  3. Determinare i due caratteri che si trovano a una certa distanza, prima e dopo, di un certo carattere

Sequenze di caratteri

  1. Concatenare una stringa N volte
    • s1=”abc”, N=3 -> s2=”abcabcabc”
  2. Quante volte compare un certo carattere?
  3. Eliminare la prima occorrenza di un certo carattere
  4. … ultima …
  5. … tutte …
  6. Contare il numero di lettere maiuscole contenute
  7. … minuscole …
  8. … maiuscole e minuscole …
  9. Calcolare la somma dei codici dei caratteri contenuti
  10. Una stringa è una sottostringa dell’altra?

Parole

  1. Quante volte compare una certa parola?
  2. Quante sono le parole in un testo?
  3. Quante sono le parole di lunghezza 1, 2, 3, …?
  4. Quante volte compare ogni singola parola?

Frasi

  1. Quante sono le frasi in un testo?
  2. Quante sono le frasi con 1, 2, 3, … caratteri?
  3. Quante sono le frasi con 1, 2, 3, … parole?

Contare i caratteri

I problemi con i testi (parole, frasi) sono diversi da quelli con i numeri…

  • Quanti caratteri in un testo?
  • Quante vocali, consonanti?
  • Quante maiuscole, minuscole?
  • Quante A, B, C, …, Z?

Per contare quante volte compare ciascun lettera puoi cominciare così…

Note

  1. Il codice precedente conta le lettere maiuscole
  2. Se la frase in input contiene caratteri diversi ci sarà un errore in esecuzione
  3. Si potrebbero convertire le lettere minuscole in lettere maiuscole, con Upcase(), e poi conteggiarle.
  4. Si potrebbero contare tutti i caratteri della tabella ASCII dal codice #0 al codice #255

Problemi con numeri casuali

Genera numeri casuali

  1. Testa o croce?
  2. Una cifra
  3. Nell’intervallo [0, A[
  4. Nell’intervallo [A, B[
  5. Nell’intervallo [-A, A[

Lanciare i dadi

  1. Un dado
  2. Lancia continuamente un dado e si ferma con l’estrazione del 3
  3. 2 dadi
  4. n dadi

Lettere casuali

  1. Maiuscola
  2. Minuscola
  3. Maiuscola o minuscola
  4. Vocale

Giocare con il computer

  1. Indovino io – Il computer prova a indovinare un numero che l’utente ha pensato…
  2. Indovina tu – Il computer pensa un numero e invita l’utente a indovinarlo…
    Alla fine sarà visualizzato il numero di tentativi.
  3. Dadi – Stabilisci prima le regole…
  4. Roulette – …

Utilizzando un array di appoggio

  1. Lanciare un dado (due dadi) più volte e conteggiare le uscite (le frequenze assolute/relative…)
    lanci=10

    1 2 3 4 5 6
    1 0 3 2 3 1
    10% 0% 30% 20% 30% 10%
  2. Generare tanti numeri casuali nell’intervallo [1, 100] e conteggiare le uscite (le frequenze assolute/relative…)
  3. Generare le uscite della Tombola
  4. Generare un Mazzo di carte
    1. napoletane, 40 carte (bastoni, coppe, ori, spade)
    2. francesi, 52 carte (cuori, quadri, fiori, picche)