Proposte di Lavoro

Linee di Lavoro

1. Vi propongo di provare a codificare (in c++ o Pascal) gli algoritmi descritti nelle prime 5 pagine della dispensa La Programmazione Dinamica. Vi ricordo che la programmazione dinamica risulta fondamentale per alcuni dei problemi proposti nel corso delle olimpiadi (circa due all'anno).
2. Come i cavalieri della Tavola Rotonda dovete navigare tra i problemi assegnati a precedenti edizioni delle Olimpiadi per riportarmi il Sacro Grahal ossia quel problema che non sapete proprio come risolvere! (O di cui non riusciate ad interpretare la soluzione proposta, ove riportata dai compilatori della raccolta). Ecco qui alcuni di tali problemi.

Sfide

1. Scrivere un codice per risolvere quel solitario (per altro ben commercializzato) in cui ti trovi a maneggiare su un quadrato 4x4 con 15 piastrelline scorrevoli numerate da 1 e 15 ed un buco, e dove il tuo obiettivo sia riporre le piastrelline in ordine. Ma forse il seguente è più semplice per incominciare: 8 piastrelline sono nere e 7 sono bianche, come fare a sistemare le 8 nere nella metà alta? Bada bene: a me interessa il metodo che ti porta sempre a casa, e non il risolvere una singola istanza. Allora, riesci a comporre questo codice? (I have no clue!)
2. Sapresti dirmi quale sia il minimo numero di confronti che mi consenta di ordinare sempre 3 interi? E per ordinarne n=4? Ed n=5,6,7? Pensi di riuscirti a pappare anche il caso di n generico? Il problema si sarebbe potuto porre nella seguente forma equivalente: hai una bilancia a braccia eguali ed un insieme di n pesi; quale è il minor numero di pesate che ti permette sempre di stabilire l'ordine corretto tra i pesi?
3. Scrivere un codice per giocare a master-mind (con il calcolatore che generi a caso il codice segreto e voi che lo volete indovinare).
4. Fornire un algoritmo che ordini n numeri interi compresi tra 1 e 10 ricevuti in input. (Si intende che n è generico). Riesci a riadattare il tuo algoritmo al caso in cui gli interi in input siano compresi tra 1 e 100?
5. Fornire un algoritmo che ordini n numeri interi arbitrari ricevuti in input.
6. Scrivere un codice per risolvere il solitario francese.
7. Supponi di avere a disposizione un insieme di n interi e di dover decidere se ti sia possibile partizionarlo in due parti A e B di modo che la somma degli interi riposti in A eguagli perfettamente la somma degli interi riposti in B. Come puoi fare?
8. Supponi di avere due liste di n interi ciascuna ed ordinate per ordine non-decrescente. Sapresti stabilire quale sia il minor numero possibile di confronti che ti consenta sempre di fondere le due liste in un'unica lista ordinata?
9. I numeri di Fibonacci sono i numeri definiti attraverso la ricorrenza F(n) = F(n-1) + F(n-2) dove le condizioni al contorno sono date da F(0)=0 e F(1)=1. Riesci a scrivere un semplice codice che ti consenta di tabulare i primi 20 numeri di Fibonacci? Fino a poco oltre 30-35 un qualsiasi approccio algoritmico dovrebbe reggere, ma se tu volessi tabulare i primi 50 numeri di Fibonacci riuscirebbe il tuo programma a risponderti entro la fine dell'anno? Proporre un algoritmo che tabuli i primi 60 numeri di Fibonacci entro la fine del secolo. E cosa potresti fare per computarti F(1.000.000) o giù di lì?
10. Tastiera italiana ..., tastiera inglese ..., uffa! - non sarebbe mica un problema se uno avesse sempre a portata di mano la tabella del codice ASCII. Sapresti scriverti in due righe di codice un programmino che venga in tuo soccorso in queste evenienze?

Soluzioni Prodotte

1. Propongo la seguente soluzione per il problema del Master Mind
   Avresti saputo fare di meglio? Allora ti propongo un altro problema: sapresti scrivere un codice per far giocare il calcolatore nel ruolo di chi deve indovinare la chiave? No, no: ti propongo un problema più fondamentale: sapresti darmi un algoritmo per decidere se esista o meno una chiave compatibile con tutte le risposte raccolte fino ad una certa fase del gioco? Metti ad esempio di giocare con un avversario De Furbet Checifaochecie, che a volte toppa nell'assegnarti i piolini bianchi e neri, e di trovarti in una situazione in cui non riesci a trovare una chiave che giustifichi tutte le risposte prodotte dal De Furbet. Saprebbe il tuo algoritmo metterlo di fronte alle sue inconsistenze, o sprofonderebbe invece in uno stato di solenne frustrazione?
2. Il seguente programma Pascal restituisce il codice ASCII del tasto premuto Stampa codice ASCII. Ma manca la versione in C, ed a dire il vero tale codice non risolve il nostro problema quando esso si presenta in pratica, ossia quando non abbiamo il tasto che ci serve sulla nostra tastiera. Sapresti proporre di meglio?
3. La definizione dei numeri di Fibonacci è ricorsiva, e viene pertanto naturale pensare ad una funzione ricorsiva per il loro computo. ricFibonacci.cpp è un codice c++ che implementa appunto una soluzione ricorsiva. Ma risulta piuttosto lentino. (Quanto lentino? E perchè?) Allora abbiamo anche pensato ad una soluzione iterativa, che si avvicina in spirito alla programmazione dinamica. Trovi una codifica in c++ nel file tableFibonacci.cpp. Svantaggio principale: utilizza O(n) celle di memoria. Sapresti eliminare tale svantaggio? Ma l'idea algoritmica espressa in matrixFibonacci.cpp vi consentirebbe di computare numeri di Fibonacci ancora più grandi, purchè corredata da un'opportuna libreria per la gestione dei grandi numeri. Il codice contiene tuttavia un piccolo errore, riscontrabile nel valore ritornato per F(0). Sapresti eliminare tale errore?

created:   4 Dicembre 2002 updated:   17 Dicembre 2002

© Department of Computer Science University of Verona