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.

-- AlessandroMei - 12 May 2007

Edit | Attach | Watch | Print version | History: r7 < r6 < r5 < r4 < r3 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r7 - 2007-05-15 - AlessandroMei






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback