IX edizione

Stringhe trine15

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.

Numeri trini10

Un numero intero si dice trino se è divisibile per 3. Se n è trino, n+1 si dice strino 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.

Strinatura di numeri15

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

Inserimento ordinato15

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.

Intersomma progressiva25

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.

Contafoglie15

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). 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.

Profondità di un albero30

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.

Albero binario20

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.

Algebra Booleana30

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 binari and (congiunzione), or (disgiunzione), imp (implicazione) e eqv (equivalenza). 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 “-” e l'eqv con “=”.