ESERCIZI di GARA

Pagina 193 La sequenza iniziale, contenente i caratteri A, B e C, si riflette allo specchio, viene ribaltata. Esempi Nastro iniziale Nastro finale 1° AA AA 2° ABC CBA 3° ABBACC CCABBA Affronta il problema per passi successivi Diagramma di stato #1 Ogni lettera A viene cancellata con un asterisco e ricopiata a sinistra.Lo stato … Leggi tutto

Raddoppi Si scriva un programma per macchina di Turing che, ricevuto in ingresso un numero intero, lasci sul nastro il doppio del numero indicato. Nastro iniziale Nastro finale 1° 31 62 2° 1 2 3° 1651 3302 4° 9 18 Diagramma di stato (0, [0..9], 0, [0..9], >) Va destra (0, -, 2, -, <) … Leggi tutto

Pagina 176, 183 Data una sequenza input costituita da lettere A, B e C tradurla in una nuova sequenza dove Esempi Nastro iniziale Nastro finale 1° A B 2° AB BC 3° ABC BCA Diagramma di stato Tabella delle transizioni di stato A B C – 0 0, B, > 0, C, > 0, A, … Leggi tutto

Musica, musica! Tradizionalmente, le sette note della scala musicale vengono denominate in Italia do, re, mi, fa, sol, la, si.Le stesse note nel sistema anglosassone vengono indicate con le prime lettere dell’alfabeto: A, B, … G, con Si scriva un programma che, data una stringa di note nel sistema anglosassone, lasci sul nastro le note … Leggi tutto

Sostituzione di caratteri Programmare una macchina di Turing che, dato un nastro iniziale contenente una sequenza arbitraria di simboli A e B, sostituisca ogni occorrenza di due simboli consecutivi AB con due simboli CD. Nastro iniziale Nastro finale 1° AABABBBAABAAABAABAA ACDCDBBACDAACDACDAA 2° BBBBAAA BBBBAAA 3° AABB ACDB Diagramma di stato Quintuple (0,B,0,B,>) Salta le B … Leggi tutto

Numeri Trini 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. NASTRO INIZIALE NASTRO FINALE 3 TRINO 5 DISTRINO … Leggi tutto

Problema 1 – Musica, musica! Tradizionalmente, le sette note della scala musicale vengono denominate in Italia do, re, mi, fa, sol, la, si. Le stesse note nel sistema anglosassone vengono indicate con le prime lettere dell’alfabeto: A, B, … G, con do C re D … … sol G la A si B Si scriva un … Leggi tutto

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 … Leggi tutto

Addizione unaria 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 … Leggi tutto

Cambio di casacca Nel Mondo dei Programmatori, la vita politica è molto intensa e piena di sorprese.Nuove liste e partiti si formano e dissolvono di continuo, mentre i Programmatori discutono di quale sia il linguaggio migliore da utilizzare. Per esempio, fino a qualche anno fa si contavano vari movimenti: Negli anni, questi raggruppamenti hanno cambiato … Leggi tutto