EsercizioDue < Architetture2/PZ

Tags: view all tags

---+++ Esercizio 2

Vi siete messi in testa di scrivere un programma MIPS per verificare se un numero è divisibile per tre senza usare moltiplicazioni o divisioni e facendolo in modo efficiente. Non sapendo come fare, andate dal vecchio zio Gianni, che quando era giovane diceva di essere stato all'università e sa un sacco di cose, e gli spiegate il problema.

Facile! Dice lo zio, basta sommare tutte le cifre del numero e vedere se la somma è divisible per tre. Se la somma è un numero piccolo lo vedi subito, altrimenti ripeti il procedimento sul numero che hai ottenuto. Guarda, proviamo con 745, 7+4+5=16. Se sai che 16 non è divisibile per tre (come dovresti) allora hai finito, altrimenti puoi ripetere il procedimento su 16, 1+6=7. E adesso di sicuro abbiamo finito perchè 7 non è divisibile per 3, e allora non lo è neppure 745!

Zio, ma lo sai che nei computer i numeri sono in base due? Funziona lo stesso se uso lo stesso procedimento con i numeri binari?

Eh no che non lo sapevo! Non funziona, è chiaro! Lo Zio ci pensa un po', scribacchia su un pezzo di carta (una vecchia abitudine che ha preso all'università) e dice. Ho creato un procedimento per i computer! Se il numero è in base due allora bisogna prendere il numero cifra per cifra (sono cifre binarie, zero o uno), sommare la prima, sottrarre la seconda, sommare la terza, sottrarre la quarta, e così via. Se la somma finale è divisibile per tre allora lo è anche il numero originale. Funziona sia se parti da destra che da sinistra! Vuoi sapere perché è così?

No Zio non m'interessa, mica faccio l'università, io! Spero solo che funzioni. Proviamo con 1011101, che sarebbe 93, un numero divisibile per tre.

1-0+1-1+1-0+1 = 3, che infatti è divisibile per tre! Speriamo funzioni per tutti i numeri. Ma di sicuro è così, Zio Gianni sa scrivere delle cose che chiama dimostrazioni e, com'è, come non è, è sempre sicuro di quello che dice.

Grazie Zio! Un giorno magari mi spieghi come hai fatto!

Fantastico. Volate a casa e scrivete il vostro programma. 

---++++ Metodo Zio Gianni  (con ricorsione)

Fate attenzione, il metodo Zio Gianni per computer funziona solo con i numeri positivi.
Potete fare così. Create un programma che, partendo da una somma parziale inizializzata
a zero, considera
i bit del numero uno a uno, una volta sommandolo, una volta sottraendolo
alla somma parziale. Se la somma finale è negativa, allora cambiatele di segno.
Dopo di ciò, se il risultato finale è zero, allora il numero è divisibile per tre, se il
risultato finale è uno oppure due, allora il numero non è divisibile per tre, se il risultato
finale è maggiore di due, allora per determinare la divisibilità per tre potete 
richiamate la procedura ricorsivamente sul risultato finale.
Dovete usare shift e operazioni logiche sui bit!

Per risolvere l'esercizio, dovete usare questo metodo. Questo è importante perché parte
della valutazione riguarda la vostra capacità di gestire bene la ricorsione.

-- Users.AlessandroMei - 12 May 2007