Accesso

Cherubino     Gara nazionale di programmazione della
Macchina di Turing
 
 

Esercizi di Gara della X edizione


AVVISI:

  • Se non specificato altrimenti negli esercizi, le sequenze iniziali su nastro si intendono non vuote, ovvero contenenti almeno un simbolo.

  • Per numero decimale si intende un numero positivo o nullo rappresentato con le cifre 0, 1, 2, ..., 9, senza zeri iniziali non significativi; per esempio 0 e 19 sono numeri validi, mentre 0032 deve essere scritto come 32.

  • Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!

  • Ogni volta che si salva la soluzione di un esercizio con il simulatore della macchina di Turing, il “timestamp” dell’esercizio viene aggiornato con il tempo trascorso fino a quel momento.


Esercizio 1: Addizione unaria [Punti 7]. Nei sistemi di numerazione posizionale, il valore denotato da un numero è ottenuto moltiplicando ogni cifra per la corrispondente potenza di una base. Nel caso della notazione decimale, la base è 10; la cifra più a destra è moltiplicata per 100=1, quella successiva per 101=10, la terza da destra per 102=100, e così via. Nella numerazione con base 1 (unaria), ciascuna cifra (si usa il carattere "1" per convenzione) viene moltiplicata per 1n=1, qualunque sia n. Per esempio, 1210 = 1111111111111. Si noti che lo 0 si esprime in unario con l'assenza completa del numero. Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una addizione unaria (composta da due numeri unari separati da "+"), lasci sul nastro il risultato dell'addizione, sempre espresso in unario.


NASTRO INIZIALE

NASTRO FINALE

11+111

11111

1111111+1

11111111

1+1

11

1+

1

+




Esercizio 2: Addizione binaria [Punti 10]. La notazione binaria è un sistema di numerazione posizionale con base 2. In binario le cifre (0 o 1) vengono moltiplicate per 20=1, 21=2, 22=4, e così via, in base alla loro posizione. Per esempio, 1210 = 11002. Si scriva un programma per Macchina di Turing che, ricevuta sul nastro una addizione binaria (composta da due numeri binari separati da "+"), lasci sul nastro il risultato dell'addizione, sempre espresso in binario.


NASTRO INIZIALE

NASTRO FINALE

11+111

1010

1+1

10

0+0

0

10001+1101001

1111010

11011001101+1

11011001110



Esercizio 3: Conversione romana [Punti 28]. La notazione romana è un sistema di numerazione non-posizionale. I romani lo adattarono dal sistema Etrusco, e la sua forma moderna si stabilizzò intorno al XIII secolo. In questo sistema si usano alcune lettere per indicare determinati numeri; quando una lettera di valore minore segue una di valore maggiore, si intende che i due valori vadano sommati; quando invece una lettera di valore minore precede una di valore maggiore, si intende che il valore della prima vada sottratto da quello della seconda. Le lettere usate generalmente sono: I=1, V=5; X=10; L=50; C=100; D=500; M=1000 (per esprimere numeri maggiori venivano posti vari segni moltiplicatori sopra o accanto alle lettere usuali). Si noti che i Romani non avevano un segno per lo 0, e che il sistema è ambiguo: per esempio, 99 si può scrivere sia IC che XCIX (entrambe le forme sono attestate in iscrizioni). Noi adotteremo quest'ultima forma, in cui ogni cifra della rappresentazione decimale è codificata indipendentemente: 99 = 90 + 9 = XC IX. Si scriva un programma per macchina di Turing che, ricevuto sul nastro un numero romano fra 1 e 3000, lasci sul nastro il corrispondente numero decimale.


NASTRO INIZIALE

NASTRO FINALE

I

1

IV

4

IX

9

XIX

19

XCIX

99

DCLXVI

666

MCMXLV

1945

MMVI

2006



Esercizio 4: Addizione romana [Punti 20]. Con riferimento alla notazione romana introdotta nell'esercizio precedente, si scriva un programma per macchina di Turing che, ricevuta sul nastro una addizione romana formata da due numeri romani compresi fra 1 e 10 separati dalla locuzione “ et “ (uno spazio, 'e', 't', uno spazio), lasci sul nastro il risultato della loro addizione, sempre espresso in notazione romana.


NASTRO INIZIALE

NASTRO FINALE

I ET I

II

III ET I

IV

IX ET X

XIX

IV ET IV

VIII

X ET V

XV


Esercizio 5: Conversione babilonese [Punti 35]. Il sistema di numerazione babilonese, stabilizzatosi fra il 1900 e il 1800 a.C., era un sistema posizionale con base 60. La scelta di questa base rendeva semplici le divisioni per 2, 3, 5, 6, 10, 12, 15, 20 e 30 (tutti fattori di 60), nonché quelle per i loro prodotti (4, 6, 8, 18, 24, ecc.). D'altro canto, l'uso di una base 60 obbliga a usare 59 simboli diversi per rappresentare le cifre (più lo spazio, che rappresentava lo 0). Fortunatamente, i Babilonesi usavano il sistema cuneiforme, e il simbolo di ciascuna cifra era ottenuto incidendo sulle tavolette un certo numero di simboli "<" (che indicavano le decine) e "Y" (che indicavano le unità). Per esempio, la cifra 43 era rappresentata dal simbolo 43 nella tabella accanto, e che noi indicheremo con "<<<<YYY". Naturalmente, se tale simbolo compariva nella posizione più a destra di un numero il suo valore era moltiplicato per 600=1; in quella successiva era moltiplicato per 60, poi per 3600, ecc. Noi rappresenteremo le cifre babilonesi separandole con un ".", e usando il simbolo "=" al posto dello spazio per denotare lo 0. Si scriva un programma che, ricevuto sul nastro in ingresso un numero in notazione babilonese, lasci sul nastro in uscita il corrispondente numero in notazione decimale.


NASTRO INIZIALE

NASTRO FINALE

YYYY

4

<

10

<<<YY

32

Y.<<YYY

83

<.=.YY

36002

<<<YYY.<<YYYYYY

2006

<.=

600



Esercizio 6: Sequenza di pari [Punti 10]. Si scriva il programma di una Macchina di Turing che, dato un numero sul nastro, stampi la sequenza dei numeri pari compresi fra 0 e il numero dato, separati da “.”.


NASTRO INIZIALE

NASTRO FINALE

5

0.2.4

0

0

2

0.2

17

0.2.4.6.8.10.12.14.16



Esercizio 7: Densità di una sequenza [Punti 15]. Si scriva il programma di una macchina di Turing che, data una sequenza di numeri sul nastro, separati da '.' e compresi tra 0 e 20, lasci sul nastro S se questa contiene almeno 10 numeri distinti, N altrimenti.


NASTRO INIZIALE

NASTRO FINALE

0.2.5.6.7.8.10.11.19.11.13

S

0.0.1.5.1.0.11.10.20.20.20

N

10

N

0.0.1.2.3.4.5.6.7.8.9

S



Esercizio 8: Verso di una sequenza [Punti 18]. Una sequenza di interi n1...nk (con k2) è detta crescente se ciascuno degli interi successivi al primo è maggiore del precedente (ovvero, ∂i>1, ni>ni-1); decrescente se ciascuno degli interi successivi al primo è minore del precedente (ovvero, ∂i>1, ni<ni-1), incerta in tutti gli altri casi. Si scriva il programma di una macchina di Turing che, data una sequenza di numeri sul nastro, separati da '.', lasci sul nastro C se la sequenza è crescente, D se è decrescente, I se è incerta.


NASTRO INIZIALE

NASTRO FINALE

0.2.4.5

C

10.15.23.20.6

I

10.5

D

25.20.3.3.0

I



Esercizio 9: Numeri perfetti [Punti 22]. Un numero si dice perfetto se la somma dei suoi divisori propri ha come risultato il numero stesso. Sono perfetti 6 (1+2+3=6), 28 (1+2+4+7+14=28), 496, ecc. Si scriva un programma per la macchina di Turing che, dati sul nastro un numero e la lista dei suoi divisori, lasci sul nastro P se il numero è perfetto, N altrimenti. Si assuma che il nastro inizialmente sia della forma N?D+D+D..., dove N è il numero e i D sono i suoi divisori.


NASTRO INIZIALE

NASTRO FINALE

6?1+2+3

P

7?1

N

15?1+3+5

N

28?1+2+4+7+14

P

30?1+2+3+5+6+10+15

N




Esercizio 10: Numeri di Padovan [Punti 30]. I numeri di Padovan sono definiti dalla seguente formula per ricorrenza:

I primi numeri di Padovan sono dunque, nell'ordine, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, ... Si scriva un programma per Macchina di Turing che, ricevuto sul nastro in ingresso un intero n, lasci sul nastro in uscita l'n-esimo numero di Padovan P(n).


NASTRO INIZIALE

NASTRO FINALE

1

1

8

5

14

28

27

1081

44

128801

  I GARA
  II GARA
  III GARA
  IV GARA
  V GARA
  VI GARA
  VII GARA
  VIII GARA
  IX GARA
  GARA ROTARY 2006
  X GARA
  XI GARA
  XII Gara
  XIII Gara
  XIV Gara
  XV Edizione
  XVI Edizione
  XVII Edizione
  XVIII Edizione
  XIX Edizione
(Altri collegamenti...)