Edizione VI – Problema 1

  • by

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

  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 #1

(0,0,0,0,>) 
(0,1,0,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,>) 
(0,-,1,-,<) 
(1,0,H,1,<) 
(1,1,H,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,<)
Salta la cifra 0
Salta la cifra 1
---
---
---
---
---
---
---
Salta la cifra 9
Trova la fine, passa all'incremento di 1
La cifra 0 diventa 1
La cifra 1 diventa 2
---
---
---
---
---
---
La cifra 8 diventa 9
La cifra 9 diventa 0, con riporto di 1

Codice #2

(0,[0..9],0,[0..9],>) 
(0,-,1,-,<) 
(1,[0..8],H,[1..9],<) 
(1,9,1,0,<)
Salta tutte le cifre
Comincia con la prima cifra
Le cifre da 0 a 8 diventano 1,...,9
La cifra 9 diventa 0, con riporto di 1

Lascia un commento

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