Edizione IX

Problema 1 – Stringhe Trine

Una stringa si dice trina se è della forma aaa, ovvero se è composta da tre parti uguali.

Si scriva un programma che, ricevuta in ingresso una stringa sull’alfabeto {a, b, c}, lasci sul nastro al termine della computazione la stringa trina ottenuta triplicando la stringa di ingresso.

NASTRO INIZIALE	NASTRO FINALE
a	aaa
abc	abcabcabc
babba	babbababbababba
ccc	ccccccccc

Problema 2 – Numeri Trini

Un numero intero si dice trino se è divisibile per 3. Se n è trino, n+1 si dicestrino e n+2 distrino.

Si scriva un programma che, dato in input un numero decimale, lasci sul nastro una delle tre stringhe TRINO, STRINO o DISTRINO a seconda dei casi.

NASTRO INIZIALE	NASTRO FINALE
3	TRINO
5	DISTRINO
82	STRINO
0	TRINO

Problema 3 – Strinatura di numeri

Si scriva un programma che, dato in ingresso un numero decimale, lasci sul nastro il numero strino più vicino.

NASTRO INIZIALE	NASTRO FINALE
24	25
2	1
0	1
91	91

Problema 4 – Inserimento ordinato

Sia data sul nastro una singola cifra decimale, seguita da una X e quindi da una sequenza di cifre decimali di lunghezza qualunque (anche 0).

Si scriva il programma di una macchina di Turing che inserisca il numero dato nella sequenza in modo ordinato, lasciando sul nastro la sequenza risultante.

NASTRO INIZIALE	NASTRO FINALE
5X127	1257
1X0000111117777999	00001111117777999
3X	3
4X134	1344
1X133334	1133334

Problema 5 – Intersomma progressiva

L’intersomma di un numero decimale è la somma aritmetica delle cifre che lo compongono.

• Per esempio, l’intersomma di 186 è 1+8+6 ovvero 15.
• Ovviamente, è possibile calcolare l’intersomma del risultato, in questo caso 1+5 ovvero 6.

Si scriva un programma che, ricevuto in ingresso un numero decimale, restituisca l’intera sequenza ottenuta applicando ripetutamente l’operazione di intersomma al numero di ingresso, fino a che il risultato non è costituito da una sola cifra.
I valori nella sequenza devono essere separati da spazi.

NASTRO INIZIALE	NASTRO FINALE
186	186 15 6
2500	2500 7
594326	594326 29 11 2
1	1
100000	100000 1
0	0

Problema 6 – Contafoglie

Un grafo è una struttura dati formata da un certo numero di nodi connessi da archi.
Un tipo particolarmente importante di grafo è l’albero, caratterizzato dal fatto che ogni nodo può essere connesso a 0 o più figli.
I nodi senza figli sono detti foglie.
Tutti i nodi hanno esattamente un padre, ad eccezione del nodo alla base, detto radice, che è l’unico a non avere padre.
Gli alberi in Informatica crescono al contrario che in Natura, e sono normalmente rappresentati con la radice in alto e le foglie in basso, come negli esempi illustrati più sotto.
Per rappresentare un albero come una stringa è possibile usare le parentesi per indicare la relazione padre-figlio, e singole cifre decimali per indicare le foglie.
Per esempio, (2 3) rappresenta un albero con una radice e due foglie contenenti i valori 2 e 3.
L’albero ((1 2) 3) invece ha un nodo a sinistra che ha come figli due foglie (1 e 2) e un altro figlio foglia (valore 3).

ALBERO	RAPPRESENTAZIONE
	(2 3)
	((1 2) 3)
	((1 2) ((3)))

Più in generale nei nostri alberi le parentesi introducono un nodo intermedio nell’albero i cui figli possono essere:

• Un nuovo nodo intermedio
• Una foglia (una cifra compresa tra 0 e 9).

Si scriva il programma di una macchina di Turing che, dato un albero sul nastro (codificato come descritto e senza spazi intermedi), scriva il numero di foglie in esso presenti.

NASTRO INIZIALE	NASTRO FINALE
2	1
(12)	2
((((1)2)(23))(111))	7
(1)	1
((1))	1
((2)(4)(6)(123456789))	12

Problema 7 – Profondità di un albero

Come visibile negli esempi dell’esercizio precedente, un albero è tipicamente organizzato per livelli, dati dal numero di nodi che si incontrano partendo dalla radice per arrivare a un nodo dato.

Per esempio, i livelli dell’albero ((12)((3)) sono descritti nella figura seguente:

Si scriva il programma di una macchina di Turing che, data sul nastro la definizione di un albero, ne calcoli la profondità, ovvero il numero di livelli massimo dell’albero.

NASTRO INIZIALE	NASTRO FINALE
9	1
(12)	2
((12)3)	3
((12)((3)))	4
((43563)(2(1)))	4

Problema 8 – Diametro di un albero

Si definisce C(l) la cardinalità del livello l di un albero il numero di nodi di quel livello.
Si scriva il programma di una macchina di Turing che, dato un albero sul nastro, scriva la cardinalità massima dell’albero, ovvero il più grande valore di C(l) al variare di l (tale valore è detto diametro dell’albero).

Per esempio, nel caso riportato in figura il diametro sarà 3:

NASTRO INIZIALE	NASTRO FINALE
1	B
(12)	B
(123)	N
(1(23))	B
((12)(1(23)3))	N

Problema 9 – Albero binario

Un albero è binario se e solo se ogni nodo ha al più due figli.

Si scriva il programma di una macchina di Turing che scriva B sul nastro se un albero è binario, N altrimenti.

NASTRO INIZIALE	NASTRO FINALE
1	B
(12)	B
(123)	N
(1(23))	B
((12)(1(23)3))	N

Problema 10 – Algebra Booleana

L’algebra booleana opera su due soli valori, detti vero e falso, spesso codificati con 1 (per vero) e 0 (per falso).
Su questi valori booleani sono definiti un certo numero di operatori, fra cui l’operatore unario not (negazione) e gli operatori binariand (congiunzione), or (disgiunzione), imp (implicazione) e eqv (equivalenza).

Il valore calcolato da questi operatori è definito dalle seguenti tabelle di verità: ???

Una espressione booleana è costituita da una sequenza di valori booleani e relativi operatori, con l’aggiunta di parentesi per indicare l’ordine di valutazione (le espressioni più interne vanno valutate per prime).

Si scriva un programma che, ricevuta in ingresso una espressione booleana, lasci sul nastro il risultato della sua valutazione (che sarà, ovviamente, uno dei due valori possibili: 0 o 1).

Si assuma che

• l’operatore not sia codificato con il simbolo “!”
• l’and con “*”
• l’or con “+”
• l’imp con “-”
• l’eqv con “=”.

NASTRO INIZIALE	NASTRO FINALE
0=0	1
1+(0=0)	1
1*(1-0)	0
1	1
(0+(0-(1=0)))+(!0)	0