Si vuole realizzare l’odometro di Erone da Alessandria, ovvero un contatore a cifre decimali a lunghezza fissa che incrementa di uno il numero N. Quando raggiunge il valore massimo 99…9, ritorna a 00…0.
Programmare una macchina di Turing che, dato un nastro iniziale contenente un numero decimale N, termini la sua esecuzione lasciando sul nastro l’incremento di N con l’odometro.
Esempi
NASTRO INIZIALE
NASTRO FINALE
3578
3579
10199
10200
999
000
Algoritmo
Si posiziona sull’ultima cifra a destra
Se la cifra è compresa fra 0 e 8, viene incrementata e l’esecuzione termina.
Se la cifra è 9 viene scritto 0 e si passa a incrementare la cifra a sinistra (riporto).
Codice #1
Commenti
(0,0,0,0,>)
Salta la cifra 0
(0,1,0,1,>)
Salta la cifra 1
(0,2,0,2,>)
…
(0,3,0,3,>)
…
(0,4,0,4,>)
…
(0,5,0,5,>)
…
(0,6,0,6,>)
…
(0,7,0,7,>)
…
(0,8,0,8,>)
…
(0,9,0,9,>)
Salta la cifra 9
(0,-,1,-,<)
Trova la fine, passa all’incremento di 1
(1,0,H,1,<)
La cifra 0 diventa 1
(1,1,H,2,<)
La cifra 1 diventa 2
(1,2,H,3,<)
…
(1,3,H,4,<)
…
(1,4,H,5,<)
…
(1,5,H,6,<)
…
(1,6,H,7,<)
…
(1,7,H,8,<)
…
(1,8,H,9,<)
…
(1,9,1,0,<)
La cifra 9 diventa 0, con riporto di 1
Codice #2
Commenti
(0,[0..9],0,[0..9],>)
Salta tutte le cifre
(0,-,1,-,<)
Comincia con la prima cifra
(1,[0..8],H,[1..9],<)
Le cifre da 0 a 8 diventano 1,…,9
(1,9,1,0,<)
La cifra 9 diventa 0, con riporto di 1
1 commento su “Edizione VI – Problema 1”
Avete anche la soluzione dell’esercizio che deve riconoscere se un numero è una potenza del 2? Stessa edizione di questo
Avete anche la soluzione dell’esercizio che deve riconoscere se un numero è una potenza del 2? Stessa edizione di questo