Vai al contenuto

Edizione VI – Problema 1

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 INIZIALENASTRO FINALE
35783579
1019910200
999000

Algoritmo

  1. Si posiziona sull’ultima cifra a destra
  2. Se la cifra è compresa fra 0 e 8, viene incrementata e l’esecuzione termina.
  3. Se la cifra è 9 viene scritto 0 e si passa a incrementare la cifra a sinistra (riporto).
Codice #1Commenti
(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 #2Commenti
(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”

  1. Avete anche la soluzione dell’esercizio che deve riconoscere se un numero è una potenza del 2? Stessa edizione di questo

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *