stefano/C-2015-ProgrammazioneAvanzata.docx · Web viewIntroduzione del Corso di “Programmazione...

Corso: “Programmazione Avanzata”Diario delle Lezioni edelle Esercitazioni

Università di TorinoCorso di Laurea in Matematica

A.A. 2014-2015

Docente: Stefano Berardi

2

Introduzione del Corso di“Programmazione Avanzata”

1. L’obbiettivo del corso è imparare a progettare e scrivere alcuni semplici programmi partendo dalla rappresentazione dei dati e dalla definizioni di operazioni su di essi.

2. Il programma del corso occupa 6 lezioni e consiste dei capitoli 11-14 del libro di testo <<How to think like a computer scientist>>, disponibile gratuitamente on-line all'indirizzo:

http://greenteapress.com/thinkcpp/index.html Si suppone che lo studente abbia già letto i capitoli 1-10 nel corso di Basi di Informatica. In ogni lezione alterniamo un’ora di spiegazione e una di esercizi.

3. Le esercitazioni del corso occupano le rimanenti 6 lezioni e sono una parte essenziale del corso: spiegano come mettere in pratica le idee presentate nel libro di testo.

4. Il sito Moodle del corso nel 2014/2015 è: http://math.i-learn.unito.it/course/view.php?id=499

Facciamo riferimento al sito per ogni altra informazione sul corso: modalita’ di esame, come trovare un compilatore C++ (noi usiamo il Dev-C++), eccetera.

Questo diario delle lezioni verra’ scritto durante il corso 2014/2015.

Nota 1. Per poter compilare con il Dev-C++ i programmi del libro di testo inclusi in questo diario dovete copiare nella “Compiler Command Line” la riga:

-fpermissive Nel compilatore Dev-C++ usato a lezione, la “Compiler Command Line” si trova nel menù alla voce:

Tools/Compiler Options/Compiler Command line Nota 2. Per poter compilare i programmi di grafica di questo diario dovete inoltre scaricare la libreria di grafica graphics.h (nell’ultima pagina dell’appendice di grafica si spiega come fare). Dovete quindi copiare nella “Linker Command Line” la riga

-lbgi -lgdi32 -lcomdlg32 -luuid -loleaut32 -lole32 Nel compilatore Dev-C++ usato a lezione, la “Linker Command Line” si trova sotto la “Compiler Command Line”, nel menù alla voce:

Tools/Compiler Options/Linker Command line

http://math.i-learn.unito.it/course/view.php?id=499

3

Indice del Corso di“Programmazione Avanzata”

Lezione 01 (Esercitazione). Un esempio di programma di grafica: il programma Coriandoli (ripasso dei comandi visti nel corso precedente).

Lezione 02 (Lezione). Gli Oggetti (Cap. 11.1-11.6 del libro di testo).

Lezione 03 (Lezione). Gli Oggetti (Cap. 11.7-11.9 del libro di testo).

Lezione 04 (Esercitazione).Il programma Coriandoli rivisto utilizzando le classi.

Lezione 05 (Esercitazione).Un “savescreen”: il programma Tubi (definito riutilizzando la classe definita per Coriandoli).

Lezione 06 (Lezione).Vettori di Oggetti (Cap. 12.1-12.8)

Lezione 07 (Lezione).Classi definite reciprocamente (Cap. 13)

Lezione 08 (Esercitazione).Un programma che gioca a Nim.

Lezione 09 (Lezione).Le parti pubbliche e private di una classe (Cap. 14.1 – 14.7)

Lezione 10 (Lezione).Pre-condizioni, Post-condizioni e Invarianti (Cap. 14.8-14.9)

Lezione 11 (Esercitazione).Il crivello di Eratostene.

Lezione 12 (Esercitazione).Presentazione dell’Esercizio di Esame: il programma Demoni.

4

Le 12 Lezioni del Corso di“Programmazione Avanzata”

5

Lezione 01: Un esempio di programma di grafica: i coriandoli(Ripasso dei comandi visti nel Corso precedente)

Lezione 01. Prima ora: l’uso della finestra di grafica In questa lezione ripassiamo alcuni comandi del corso precedente, Basi di Informatica. Per farlo, scriviamo un programma scelto come esempio. Il programma si chiama “Coriandoli”, e utilizza dei comandi di grafica. Insegnare la grafica digitale non è lo scopo del corso. Per imparare un minimo di comandi leggete il “manuale minimo di grafica” in appendice, solo la parte su sfondo e dischi e comando “delay”.

Iniziamo scrivendo insieme un semplice programma di prova per la grafica che troviamo in appendice: disegnare alcuni cerchi multicolori.

Fatto questo, vi chiediamo di dedicare il resto lezione a scrivere un programma “Coriandoli”. “Coriandoli” disegna alcune migliaia di cerchi, ciascuno con il centro, raggio e colori scelti a caso. Il risultato assomiglia ai coriandoli di carnevale:

Usate un ciclo for il cui corpo disegni un solo cerchio di centro, raggio, colore interno, di sfondo e di bordo tutti scelti “casualmente”. Fate ripetere il ciclo alcune migliaia di volte. Per scrivere il programma “Coriandoli” potete usare lo stile che preferite. Alla fine della lezione includiamo una soluzione che non usa le funzioni. Tra qualche lezione ne vedremo un’altra, che invece usa le funzioni. Vedrete che una soluzione che non usa le funzioni è più rapida da scrivere di una che non le usa. Invece la soluzione che usa le funzioni è più facile da capire e da controllare, e ha il vantaggio che si puo’ riutilizzare per

6

scrivere altri programmi di grafica. Per problemi di grandi dimensioni l’uso delle funzioni diventa indispensabile.

Prima di iniziare, leggete i suggerimenti inclusi.

Suggerimenti per il programma “Coriandoli”. Dovete definire dei cerchi dato il centro, il raggio, il colore interno, del bordo, eccetera. Per sapere come, leggete il manuale minimo di grafica all’inizio di questo testo fino alla voce “ellissi”.Per generare interi casuali usate la funzione rand(), inclusa nella libreria cmath. rand() produce ad ogni chiamata un intero “casuale” tra 0 e 215-1 = 32 767. Se b è un intero positivo molto più piccolo di 215-1, per generare un intero casuale < b è sufficiente scrivere rand()%b (il resto della divisione di rand() per b). Se 0<=a<a+b, la formula (a+rand()%(b-a)) sceglie un intero a caso nell’intervallo [a,b[. Quindi:

per generare un valore casuale tra 0 e 255 è sufficiente scrivere rand()%256: a partire da tre interi casuali tra 0 e 255 possiamo poi costruire un colore casuale con il comando COLOR.

Se la finestra grafica ha dimensioni NxM, possiamo ottenere un punto casuale sulla finestra usando come coordinate rand()%N, rand()%M.

Possiamo ottenere un raggio casuale tra 1 e R scrivendo (1+rand()%R).

Il comando setfillstyle(S,E); richiede come primo argomento uno “stile” S, ovvero un “modo” di colorare i prossimi cerchi che disegniamo. Per esempio se scegliamo S = SOLID_FILL (“tinta unita”) i prossimi cerchi che disegniamo vengono riempiti completamente, con il colore E.

Uno stile di rimpimento diverso da S=SOLID_FILL riempe un cerchio con due colori: in parte con il colore E scelto per l’interno, in parte con il colore scelto per lo sfondo.

Quindi se volete variare a caso i colori di un cerchio dovete variare a caso ogni volta: sia il colore scelto per l’interno, sia il colore scelto per lo sfondo (senza dimenticare di scegliere il colore per il bordo).

Uno “stile” è rappresentato da un intero tra 0 e 11. Scrivendo rand()%12 scegliamo uno “stile” di riempimento a caso.

Nota sulla funzione rand(). La funzione rand del C++ ha un difetto: chiamata 100 volte di seguito, restituisce si’ 100 valori che sembrano casuali, ma sono sempre gli stessi 100 ad ogni esecuzione del programma. Dunque anche le nostre schermate di coriandoli vengono tutte uguali. Per eliminare questo difetto, occorre scrivere l’istruzione: srand(time(NULL)); che sceglie il primo valore della successione “casuale” usando il valore time(NULL) dell’orologio del computer. I valori successivi vengono scelti di conseguenza e cambiano anch’essi. Basta scrivere questa istruzione un’unica volta, all’inizio del main . Per usare time(NULL)) dovete includere la libreria <time.h>.

7

Confrontate il vostro eseguibile con quello disponibile all’indirizzo:

http://www.di.unito.it/~stefano/C-Coriandoli-2015.exe

/* LEZIONE 01 - SOLUZIONI - IL PROGRAMMA "CORIANDOLI" (SENZA USO DI FUNZIONI) Questo programma disegna un grande numero di dischi con posizione, raggio, colore, colore del bordo e dello sfondo, stile di riempimento tutti scelti a caso. Questa soluzione non usa funzioni, e' rapida da scrivere, ma faticosa da leggere, da correggere e da riutilizzare all’interno di altri programmi. Per problemi di maggiori dimensioni e' necessario usare uno stile di programmazione diverso, scomponendo il problema in problemi piu’ piccoli, ciascuno risolto da una funzione.

Per compilare questo programma dovete scaricare la libreria graphics.h (nell'ultima pagina dell'appendice di grafica si spiega come fare) e aggiungere

-lbgi -lgdi32 -lcomdlg32 -luuid -loleaut32 -lole32alla "Linker Command Line", che si trova nel menu del Dev-C++ alla voce: Tools/Compiler Options/Linker Command line */

#include <graphics.h>#include <iostream>#include <cmath>#include <time.h>using namespace std;

/* A. PARAMETRI GRAFICA *//* 1. base e altezza della finestra grafica. */int basefinestragrafica=1000, altezzafinestragrafica=768;/* 2. Colore neutro per lo sfondo */int GREY = COLOR(128,128,128);

/* B. PARAMETRI DEL PROGRAMMA "CORIANDOLI"/*1. Raggio di un disco */int R=30; /*2. Numero dei dischi da disegnare */int NDischi=50000;

/* Programma "Coriandoli" */

int main() //Il primo passo e' inizializzare la grafica:{srand(time(NULL)); //initializzo rand() //1. Apro una finestra grafica NxM initwindow(basefinestragrafica, altezzafinestragrafica); //2. Scelgo il colore dello sfondo setbkcolor(GREY);

http://www.di.unito.it/~stefano/C-Coriandoli-2015.exe

8

//3. Disegno il colore dello sfondo cleardevice(); //4. Scelgo il colore del bordo disco setcolor(COLOR(rand()%256,rand()%256,rand()%256)); //Dichiaro il parametri di un disco D int centrox, centroy, raggio;

/* disegno un numero Ndischi di dischi, con posizioni e con raggi diversi, scelti a caso */

for(int i = 0; i < NDischi;++i) {// sposto e cambio raggio del disco D a caso centrox = rand()%basefinestragrafica; centroy = rand()%altezzafinestragrafica; raggio = rand()%R;// cambio a caso colori e stile del disco D //1. scelgo il colore dello sfondo a caso setbkcolor(COLOR(rand()%256,rand()%256,rand()%256)); // 2, scelgo lo stile e il colore del disco D a caso setfillstyle(rand()%12,COLOR(rand()%256,rand()%256,rand()%256)); // 3. scelgo il colore del bordo del disco D a caso setcolor(COLOR(rand()%256,rand()%256,rand()%256));//disegno il disco D nella sua posizione corrente fillellipse(centrox, centroy, raggio, raggio); } //salvo l'ultima immagine dello schermo su un file writeimagefile("C-Coriandoli.bmp");//fermo l'esecuzione e guardo il risultato system("pause");}

9

Lezione 02: OggettiOggetti e funzioni: qualche esempio (Cap. 11.1-11.6 libro di testo)

Lezione 02. Prima ora. Cap. 11.1-11.3.In questa lezione introduciamo uno stile di programmazione chiamato:

Object Oriented Programming. <<Un programma Object Oriented si definisce partendo da strutture che rappresentano il mondo reale e i suoi oggetti, e da funzioni che corrispondono al modo con cui operariamo sugli oggetti reali. >>

Alcuni esempi di strutture che rappresentano il mondo reale. Le strutture Time, Point e Rect viste nel corso precedente, per esempio:

struct Time {int hour, minute; double second;};Gli elementi di queste strutture corrispondono al modo con cui nel mondo reale si rappresentano date, punti del piano e rettangoli del piano. A queste strutture nella programmazione Object Oriented si aggiungono le:

Member functions: funzioni dichiarate insieme a una struttura e definite sugli elementi della struttura. Nella programmazione Object Oriented , una struttura con aggiunte delle funzioni viene chiamata classe. Gli elementi di una classe vengono detti oggetti: come esempio, gli oggetti della classe Time sono le date.

Esempi di member functions per la classe Time. Quando una funzione è membro di una classe, il suo primo argomento è sempre un elemento della classe, che non viene elencato tra gli argomenti, non ha un nome proprio, e viene indicato con la notazione *this. Vediamo come esempio una member function che stampa una data. Usiamo la classe Time, che rappresenta le ore, minuti e secondi trascorsi da un istante scelto come iniziale: le ore (hour) sono un intero relativo qualunque, mentre i minuti (minutes) sono un intero da 0 a 59, e i secondi (seconds) un numero reale da 0 compreso a 60 escluso.

Nota sulla versione di C++ usata. Ci sono due modi per dichiarare una member function che stampa una data: void Time::print (); e void print (); Nel primo caso ricordiamo che il primo argomento di print() è void, nel secondo no. Noi, seguendo il libro, useremo il secondo modo, più enfatico, e scriveremo void Time::print ();

10

In qualche compilatore, questo modo di scrivere richiede il comando “-fpermissive”, da aggiungersi nel menu alla voce: Tools/Compiler Options/Compiler Command line.

Passiamo ora a leggere gli esempi proposti dal libro di testo.

/* Primo programma che utilizza le classi. Perche’ funzioni, ricordatevi di aggiungere la riga:

-fpermissivenel menu del compilatore Dev-C++ alla voce:

Tools/Compiler Options/Compiler Command line */

#include <math.h>#include <iostream>#include <stdlib.h>using namespace std;

struct Time {int hour, minute; //ore e minuti da un istante inizialedouble second; //la componente in secondi

//Una classe ha delle funzioni oltre che degli individuivoid Time::print ();//La funzione viene promessa e definita in seguito};

/* print() ha come primo argomento una data (un oggetto della classe Time). Questo primo argomento non ha nome proprio e non compare nell’elenco degli argomenti di print.*/

void Time::print () {Time time = *this; //ora time è il nome proprio del primo argomento di Time::print()cout << time.hour << ":" << time.minute << ":" << time.second << endl;}/* print() non ha argomenti oltre a currentTime: ecco perche’ dopo print compare la lista vuota () */

main(){//ore 9, quattordici minuti e 30 secondiTime currentTime = { 9, 14, 30.0 };/* una member function si applica a un oggetto della classe scrivendo l’oggetto seguito da un punto e dalla funzione con eventuali altri argomenti */cout << "tempo corrente" << endl;currentTime.print ();system("pause");

11

}

Nota. C’e’ una notazione alternativa per indicare il primo argomento di una member function, al posto di usare *this. All’interno di una definizione di una member function, possiamo usare hour, minute, second per indicare la componente ora, minuti e secondi del primo argomento di una funzione. Ecco come si presenta la definizione alternativa di print().

void Time::print (){cout << hour << ":" << minute << ":" << second << endl;}

12

Lezione 02. Seconda ora. Cap. 11.4-11.6.Come esercizio, vi chiediamo di arricchire la classe Time con nuove funzioni, come segue:

struct Time {int hour, minute;double second;//Inseriamo altre funzioni oltre a print()void Time::print () ;double Time::convertToSeconds () ;void Time::increment (double secs) ;bool Time::after ( Time& time2) ;};

Time makeTime (double secs);

La funzione makeTime(double secs) non fa parte della classe Time (non ha argomenti di tipo Time). Converte da una data espressa in secondi al formato usato nella classe Time.

La funzione convertToSeconds() converte una data in secondi. La funzione increment(double secs) aggiunge a una data un

numero sec di secondi. La funzione after(Time &time2) prende due date e restituisce

true se la prima data segue la seconda, e false altrimenti.

13

//Lezione 02. Seconda ora.//Soluzione dell’esercizio: estendere la classe Time. #include <math.h>#include <iostream>#include <stdlib.h>using namespace std;

struct Time {int hour, minute;double second;//Inseriamo altre funzioni oltre a print()void Time::print () ;void Time::increment (double secs) ;double Time::convertToSeconds () ;bool Time::after ( Time& time2) ;};

/* Inseriamo una funzione che converte un numero di secondi in una data */Time makeTime (double secs) { /* se vogliamo usare l’operazione % (modulo) dobbiamo prima convertire i secondi in interi */Time t;t.hour = ((int) secs) / 3600;t.minute = ((int) secs / 60) % 60;t.second = ((int) secs) % 60;return t;};

/* è possibile riscrivere la definizione di print() in modo più conciso, facendo riferimento ai nomi hour, minute e second della struttura */

void Time::print (){cout << hour << ":" << minute << ":" << second << endl;}

/* La funzione increment aggiunge un numero secs di secondi a una data, correggendo il risultato se il numero dei secondi supera 60 oppure il numero dei minuti supera 60 */

void Time::increment (double secs) {second += secs;while (second >= 60.0) {second -= 60.0;minute += 1;}while (minute >= 60) {minute -= 60;

14

hour += 1;}} //Definiamo la conversione di una data in secondi:double Time::convertToSeconds () {int minutes = hour * 60 + minute;double seconds = minutes * 60 + second;return seconds;}

/* Se la funzione ha due argomenti che appartengono alla classe, il secondo argomento viene trattato normalmente */bool Time::after ( Time& time2) {if (hour > time2.hour) return true;if (hour < time2.hour) return false;if (minute > time2.minute) return true;if (minute < time2.minute) return false;if (second > time2.second) return true;return false;}

main(){//ore 9, quattordici minuti e 30 secondiTime currentTime = { 9, 14, 30.0 };cout << "tempo corrente" << endl;currentTime.print ();

//Esempi di uso della funzione increment.cout << "il tempo corrente passati 500 secondi" << endl; currentTime.increment (500.0);currentTime.print ();

//Esempi di uso della funzione aftercout << "tempo di fine cottura o <<done time>>" << endl; Time doneTime = { 9, 30, 00.0 };doneTime.print ();cout << "Se il tempo di fine cottura viene dopo il tempo corrente stampiamo:" << endl;if (doneTime.after (currentTime)) {cout << "The bread will be done after it starts." << endl;}system("pause");}

15

Lezione 03: OggettiCostruttori e modificatori di oggetti

(Cap. 11.7-11.9 libro di testo)

Lezione 03. Prima ora.In questa lezione terminiamo la nostra introduzione delle classi in C++ introducendo la nozione di costruttore. Un costruttore è una funzione che prende dei parametri e costruisce un oggetto di una classe. Per esempio, consideriamo ancora la classe Time delle date espresse in ore, minuti e secondi a partire da un istante iniziale. La funzione makeTime vista nella lezione precedente è un costruttore per la classe Time:

Time makeTime (double secs) { Time t; t.hour = ((int) secs) / 3600; t.minute = ((int) secs / 60) % 60; t.second = ((int) secs) % 60; return t;};

Esiste una speciale sintassi per i costruttori, che consente di omettere le informazioni non essenziali:

i costruttori non hanno un nome proprio, come il primo argomento di una funzione di una classe, e prendono il nome della classe a cui sono associati.

in un costruttore, la dichiarazione di una nuova variabile t per contenere il valore di ritorno e il comando return t; si omettono,

se t contiene il valore di ritorno, al posto di t.hour, t.minute, t.second si scrive hour, minute, second, come facciamo quando definiamo una funzione member.

La funzione makeTime, di conseguenza, si puo’ anche scrivere come:

Time::Time (double secs) {//omettiamo la dichiarazione Time t; hour = int (secs / 3600.0); //hour al posto di t.hoursecs -= hour * 3600.0; //minute al posto di t.minuteminute = int (secs / 60.0); //second al posto di t.secondsecs -= minute * 60.0;second = secs;//omettiamo il comando return t;

}

16

Fatto questo, anziche’ dichiarare una nuova variabile come Time t = makeTime(secs);possiamo scrivere in forma abbreviata, omettendo il nome del

costruttore: Time t(secs);

Quando si usa questa sintassi abbreviata non si puo’ più usare la sintassi con le parentesi graffe: non si puo’ più scrivere Time t = {19, 45, 0}. Possiamo dichiarare più costruttori, purche’ abbiano un diverso numero di argomenti oppure almeno un argomento diverso. Per esempio possiamo aggiungere un costruttore che usa ore, minuti e secondi per fornire una data:

Time::Time (int h, int m, double s){hour = h; minute = m; second = s;}

I costruttori si possono usare per definire nuove member functions. Per esempio, l’addizione tra due date, usando i costruttori appena visti, si puo’ scrivere come:

Time Time::add (const Time& t2) {double seconds = convertToSeconds () + t2.convertToSeconds ();Time time (seconds);return time;}

Infine, tutta la parte relativa alla classe time si puo’ includere dentro due files, uno di nome Time.h che contiene la dichiarazione della classe Time, con tutte le dichiarazioni di funzione, e un file Time.cpp, che contiene invece tutte le dichiarazioni di member functions e di costruttori della classe. Questi file definiscono una libreria C++, e per poter usare le definizioni che essi contengono dobbiamo usare il comando #include "Time.h" all’inizio del file. La libreria stessa deve trovarsi nella stessa cartella che contiene il programma, come abbiamo visto nel corso precedente per la libreria "Matrix.cpp".

Ecco un esempio di un programma che usa la libreria Time.h:

//Lezione 03. Prima ora.//Soluzione dell’esercizio: estendere la classe Time. #include <math.h>#include <iostream>#include <stdlib.h>

17

#include "Time.h" /* questo programma funzionera’ solo dopo aver definito la libreria Time.h, Time.cpp */using namespace std;

int main (){Time currentTime (9, 14, 30.0);currentTime.increment (500.0);currentTime.print ();Time breadTime (3, 35, 0.0);Time doneTime = currentTime.add (breadTime);doneTime.print ();if (doneTime.after (currentTime)) {cout << "The bread will be done after it starts." << endl;}system("pause");}

Lezione 03. Seconda ora. Come esercizio, provate a scrivere un file Time.h e Time.cpp che contenga tutte le definizioni viste sulla classe Time, e che renda funzionante il programma precedente.

18

Lezione 04: Un esempio di programma:

“Coriandoli” usando le classi

Lezione 04. Prima ora: il programma “Coriandoli”. In questo corso vedremo alcuni esempi di progettazione di programmi, partendo dalla rappresentazione dei dati e dalla definizioni di operazioni su di essi. In questa lezione rivediamo il programma “Coriandoli” della prima lezione. Rileggete un attimo di cosa si tratta. Questa volta, scriveremo “Coriandoli” usando una classe i cui elementi sono proprio i coriandoli. La chiameremo la classe dei Dischi. Nella prossima riutilizzeremo la classe dei Dischi utilizzata per scrivere il programma Coriandoli per scrivere un nuovo programma, “Tubi”.

Definizione di una classe di Dischi. Iniziamo quindi a chiederci: come si rappresenta un “coriandolo”, ovvero un disco nello schermo? Un disco deve avere le coordinate del centro e il valore del raggio, quindi richiede 3 numeri, che per semplicita’ supponiamo interi. Definiamo quindi una struttura o una classe di nome Dischi, i cui elementi hanno 3 campi. Scelta la rappresentazione dei dati, dobbiamo chiederci quale genere di operazioni dobbiamo essere in grado di eseguire su un disco per poter scrivere il programma “Coriandoli”. Le operazioni vengono rappresentate in C++ da funzioni. In questo caso la scelta delle operazioni è semplice.

1. Un funzione che costruisce una rappresentazione di un disco, a partire dai suoi parametri. Il disco costruito resta invisibile, dentro la memoria.

2. Una funzione che disegna un disco (qui bisogna consultare il manuale di grafica in appendice).

3. Una funzione che sposta a caso centro e raggio del disco, sorteggiando dei nuovi valori.

La funzione 1 è il costruttore della classe. Le funzioni 2, 3, 6 non restituiscono un valore ma disegnano un disco o ne modificano i parametri. Dunque hanno valore di ritorno void.

I parametri del programma “Coriandoli”. Oltre a scrivere tutte queste funzioni dobbiamo stabilire i parametri del disegno, ovvero i valori che restano fissi per tutta la durata del programma “Coriandoli”. Scegliamo come parametri del programma:

19

1. Il raggio massimo di un disco.2. Il numero di dischi da disegnare.

Tutti questi valori diventano variabili globali del programma. Inizializzazione della grafica. Infine, prima di iniziare il programma dovremo inizializzare la finestra di grafica e i parametri del programma. Possiamo inizializzare usando funzioni di appoggio. Scegliamo di definire:

1. Una funzione che calcoli un colore a caso, che usiamo per scegliere i valori dei colori. Tranne per lo sfondo, che è meglio sia di colore neutro, e che disegnamo grigio.

2. Una funzione che inizializzi i parametri della finestra grafica. Nel manuale di grafica è spiegato come.

Realizzeremo il programma nell’ordine opposto a quello con cui ne abbiamo parlato.

A. Iniziamo definendo le funzioni di appoggio per inizializzare la grafica.

B. Continuiamo definendo i parametri del programma “Coriandoli”. C. Definiamo la classe Dischi dei dischi e le sue funzioni. D. Infine scriviamo il nostro programma “Coriandoli” usando tutte

le funzioni precedenti.

Lezione 04. Ultime avvertenze. Ecco alcuni errori comuni, di programma o di metodo, che potreste fare nel programma Coriandoli.

1. Non dimenticatevi di assegnare un colore a caso sia all’interno del disco che allo sfondo. Il colore dello sfondo è spesso visibile nei varchi lasciati dal colore dell’interno, quindi per avere una maggiore varieta’ di dischi bisogna prima di ogni disegno cambiare entrambi, oltre a cambiare il colore del bordo.

2. Una buona scelta è introdurre una funzione che sorteggia questi tre colori e richiamarla ogni volta.

20

/* SOLUZIONI - IL PROGRAMMA "CORIANDOLI".Questo programma disegna un grande numero di dischi con posizione, raggio, colore, colore del bordo e dello sfondo, stile di riempimento scelti a caso. Per compilare questo programma dovete scaricare la libreria graphics.h (nell’ultima pagina dell’appendice di grafica si spiega come fare) e aggiungere

-lbgi -lgdi32 -lcomdlg32 -luuid -loleaut32 -lole32alla “Linker Command Line”, che si trova nel menu del Dev-C++ alla voce: Tools/Compiler Options/Linker Command line */

#include <graphics.h>#include <iostream>#include <cmath>#include <time.h>using namespace std;

/* A. PARAMETRI GRAFICA *//*1. base e altezza della finestra grafica. */int basefinestragrafica=1000, altezzafinestragrafica=768;

/*2. Funzione che restituisce un colore a caso */int coloreacaso(){return COLOR(rand()%256,rand()%256,rand()%256);}

/*3. Colore neutro per lo sfondo */ int GREY = COLOR(128,128,128);

/* 4 funzione che sceglie i colori a caso per sfondo, interno e bordo. */void sceglicoloriacaso(){ //4.1. sceglie colore sfondo a caso setbkcolor(coloreacaso()); //4.2 sceglie stile e colore disco a caso setfillstyle(rand()%12,coloreacaso()); //4.3. sceglie colore bordo disco setcolor(coloreacaso()); } /*5. funzione che inizializza tutti i parametri della grafica */ void inizializzagrafica(){srand(time(NULL)); //initializza rand() //5.1. apre una finestra grafica NxM initwindow(basefinestragrafica, altezzafinestragrafica); //5.2. sceglie colore sfondo setbkcolor(GREY); //5.3. disegna colore sfondo cleardevice(); //5.4 sceglie stile e colore disco setfillstyle(SOLID_FILL,coloreacaso()); //5.5. sceglie colore bordo disco

21

setcolor(coloreacaso()); }

/* B. PARAMETRI DEL PROGRAMMA "CORIANDOLI”/*1. Raggio di un disco */int R=30; /*2. Numero dei dischi da disegnare */int NDischi=50000;

/* C. LA CLASSE DISCO CHE RAPPRESENTA I DISCHI */struct Dischi {int centrox, centroy, raggio; //parametri disco Dischi::Dischi(int Cx, int Cy, int R); //costruttore di un disco

void Dischi::disegna(); //disegna un disco void Dischi::spostacambiaraggioacaso(); /* sposta e cambia il raggio di un disco a caso */}; /* FUNZIONI E COSTRUTTORI CLASSE DISCO */Dischi::Dischi(int cx, int cy, int r){centrox = cx; centroy = cy; raggio = r;}

void Dischi::disegna(){fillellipse(centrox, centroy, raggio, raggio);} void Dischi::spostacambiaraggioacaso(){centrox = rand()%basefinestragrafica; centroy = rand()%altezzafinestragrafica; raggio = rand()%R;}

/* D. Ora definiamo il programma "Coriandoli" a partireda tutte le funzioni precedenti. */

main() //Il primo passo e':{inizializzagrafica(); //Costruisco un disco D di centro (0,0) e raggio R Dischi D(0, 0, R); //disegno D in molte posizioni distinte e con raggi diversi for(int i = 0; i < NDischi;++i) { D.spostacambiaraggioacaso(); // sposto e cambio raggio a caso sceglicoloriacaso(); //cambio a caso colori e stile di D D.disegna(); //disegno D nella sua posizione corrente }//salvo l'ultima immagine dello schermo su un file writeimagefile("C-Coriandoli.bmp");//fermo l'esecuzione e guardo il risultato system("pause");}

22

Lezione 05: un esempio di programma:il salvaschermo “Tubi”

Progettiamo ora una animazione grafica, che chiameremo "Tubi", e che un tempo veniva utilizzata come salvaschermo (da molti anni ne è disponibile una versione 3D, cercate 3D Pipes Screensaver per saperne di più). Tocca a voi finire voi il programma.

Vi chiediamo di scrivere il programma “Tubi” usando le classi, modificando il programma “Coriandoli” e la classe “Dischi” visti nella lezione precedente.

Il programma “Tubi” muove un disco colorato nello schermo a velocità costante, facendolo rimbalzare contro i bordi, e senza mai cancellare le posizioni precedenti del disco. L’effetto è disegnare una linea che va a zig-zag, tutta composta di dischi sovrapposti, e che ricorda un groviglio di tubi. Ecco un esempio:

Per introdurre maggiore varieta’ nel disegno, in istanti scelti a caso, e purche’ il disco non stia gia’ rimbalzando, si modifica casualmente direzione e velocità del disco. Nell’esempio incluso sopra, inoltre, il colore del disco cambia gradualmente. Noi pero’ scriveremo una versione del programma più semplice, cambiando a caso (e quindi bruscamente) il colore ogni volta che cambiamo la velocità. Di questo programma ci interessa non tanto l’effetto grafico quanto il modo con cui viene progettato. Pur essendo un problema semplice, risulta vantaggioso progettare il programma a partire dalla rappresentazione dei dati, e riutilizzando il programma “Coriandoli” già scritto. L’argomento di questo corso è appunto

23

come progettare un programma dalla rappresentazione dei dati, e come riutilizzare programmi e librerie già scritte.

Estensione della classe di Dischi. Iniziamo quindi a chiederci: come si rappresenta un disco mobile nello schermo? Un disco deve avere le coordinate del centro e il valore del raggio; un disco mobile deve anche avere una velocità lungo l’asse delle x e una velocità lungo l’asse delle y. Quindi un disco mobile richiede 5 numeri, che per semplicita’ supponiamo interi. Modifichiamo quindi la struttura Dischi, portando i suoi elementi da 3 a 5 campi. Scelta la rappresentazione dei dati, dobbiamo chiederci quale genere di operazioni dobbiamo essere in grado di eseguire su un disco per poter scrivere il programma “Tubi”. Sta a noi scegliere queste operazioni, e non devono essere troppe, ma perche’ la scelta sia utile devono essere facili da realizzare e da controllare. Se una operazione risulta complessa da realizzare la definiamo a partire da altre, e iniziamo a realizzare quelle più semplici. Alla fine dobbiamo essere in grado di scrivere il programma combinando insieme tutte le operazioni che abbiamo definito. Le operazioni vengono rappresentate in C++ da funzioni. In questo caso scegliamo di definire le seguenti funzioni su dischi. Alcune fanno già parte della classe Dischi, altre si possono ottenere modificando delle funzioni esistenti, altre sono completamente nuove. Eccole qui:

1. Un funzione che costruisce una rappresentazione di un disco, a partire dai suoi parametri. Il disco costruito resta invisibile, dentro la memoria.

2. Una funzione che disegna un disco (qui bisogna consultare il manuale di grafica in appendice).

3. Una funzione che sposta la posizione (x,y) del disco dopo un istante di tempo, in base alla sua velocità vx lungo l’asse x e vy lungo l’asse y.

4. Una funzione che controlla se il disco sta per avere un impatto contro il bordo nella direzione x. Un’altra funzione con lo stesso compito per l’asse y.

5. Una funzione che in caso di rimbalzo in direzione x cambia segno alla velocità lungo l’asse x, e in caso di rimbalzo in direzione y cambia segno alla velocità lungo l’asse y,

6. Una funzione che cambia casualmente la velocità di un disco lungo l’asse x e lungo l’asse y, e il colore del suo interno.

La funzione 1 restituisce un disco e le funzioni 4, 5 un valore di verita’, la risposta alla domanda: è avvenuto un impatto lungo

24

l’asse x, lungo l’asse y? Le funzioni 2, 3, 6 dell’elenco qui sopra non restituiscono un valore ma disegnano un disco o ne modificano i parametri. Dunque hanno valore di ritorno void.

I parametri del programma “Tubi”. Oltre a scrivere tutte queste funzioni dobbiamo stabilire i parametri del disegno, ovvero i valori che restano fissi per tutta la durata del programma “Tubi”. Scegliamo come parametri del programma:

1. Il raggio di un disco.2. La minima velocità e la massima, lungo l’asse x e y.3. Il numero di dischi da disegnare.4. Il ritardo tra il disegno di un disco e il successivo. 5. La probabilita’ che il disco cambi casualmente velocità.

Tutti questi valori diventano variabili globali del programma. Il ritardo tra un disegno e il successivo viene inserito per evitare disegni troppo veloci, fastidiosi a vedersi e che comunque dopo un po’ producono un “crash” del programma. Il comando per realizzare un ritardo tra disegni è “delay” (vedi il manuale di grafica in appendice).

Inizializzazione della grafica. Infine, prima di iniziare il programma dovremo inizializzare la finestra di grafica e i parametri del programma. Possiamo inizializzare usando funzioni di appoggio. Scegliamo di definire:

1. Una funzione che calcoli un colore a caso, che usiamo per scegliere i valori dei colori. Tranne per lo sfondo, che è meglio sia di colore neutro, e che disegnamo grigio.

2. Una funzione che inizializzi i parametri della finestra grafica. Nel manuale di grafica è spiegato come.

Realizzeremo il programma nell’ordine opposto a quello con cui ne abbiamo parlato.

A. Iniziamo definendo le funzioni di appoggio per inizializzare la grafica.

B. Continuiamo definendo i parametri del programma “Tubi”. C. Definiamo la classe Dischi dei dischi e le sue funzioni. D. Infine scriviamo il nostro programma “Tubi” usando tutte le

funzioni precedenti.

Spieghiamo ancora con che criterio decidere se avviene un rimbalzo oppure no.

25

Un criterio geometrico per il rimbalzo. Supponiamo di avere un cerchio di centro (Cx, Cy) e raggio R, posto entro entro una cornice di base N e altezza M (vedi disegno sotto).

Il cerchio rimbalza orizzontalmente se Cx ha distanza da 0 oppure da N minore del raggio R.

Il cerchio rimbalza verticalmente se Cy ha distanza da 0 oppure da M minore del raggio R.

Nell’esempio qui sotto abbiamo: 1. Ax-R<0 e il cerchio A urta contro il bordo sinistro.2. Bx+R>N e il cerchio B urta contro il bordo destro.3. Cy-R<0 e il cerchio C urta contro il bordo inferiore.4. Dx+R>M e il cerchio D urta contro il bordo superiore.

Quando avviene un rimbalzo orizzontale la componente x della velocità cambia segno.

Quando avviene un rimbalzo verticale la componente y della velocità cambia segno.

Un cerchio puo’ rimbalzare contemporaneamente rispetto alla x e alla y (quando urta contro un angolo: in questo caso inverte la velocità).

Adesso tocca a voi scrivere il programma “Tubi”, modificando il programma “Coriandoli” visto in precedenza. Confrontate il vostro eseguibile con quello disponibile all’indirizzo:

http://www.di.unito.it/~stefano/C-Tubi-2015.exe

ss

0N

M

(Ax,Ay)

(Dx,Dy)

(Cx,Cy)

(Bx,By)

http://www.di.unito.it/~stefano/C-Tubi-2015.exe

26

Lezione 05. Ultime avvertenze. Ecco alcuni errori comuni, di programma o di metodo, che potreste fare nel programma “Tubi”.

1. Una osservazione di metodo: quando modificate una vecchia funzione e ne create una nuova, usate un nome nuovo per la nuova funzione e non cancellate la vecchia. La vecchia funzione puo’ ancora servire, e il nuovo nome sottolinea che il compito della funzione è cambiato. Per esempio: se avete una funzione “spostacambiaraggioacaso” che sorteggia centro e raggio del cerchio, e la modificate per ottenure funzione che muove di moto rettilineo uniforme un disco, usate un nuovo nome per la nuova funzione, per esempio “sposta”.

2. In generale: non modificate i parametri di un programma all’interno del programma stesso, trattateli come se fossero costanti (alcuni programmatori li definiscono appunto come costanti). Se seguite questa regola, per cambiare un valore per tutta la durata del programma vi basta cambiare un parametro.

Vi lasciamo ora scrivere il programma “Tubi”.

27

/* Lezione 05: Soluzioni. IL PROGRAMMA "TUBI". Questo programma un tempo era utilizzato come "salvaschermo". Disegna un disco che cambia colore, si muove e rimbalza contro i bordi dello schermo, lasciando una striscia di immagini. */#include <graphics.h>#include <iostream>#include <cmath>#include <time.h> /* per il comando srand(time(NULL)); che inizializza la funzione rand(), vedi lezione precedente. */using namespace std;

/* A. PARAMETRI GRAFICA *//*1. base e altezza della finestra grafica. */int basefinestragrafica=1000, altezzafinestragrafica=768;

/*2. Funzione che restituisce un colore a caso */int coloreacaso(){return COLOR(rand()%256,rand()%256,rand()%256);}

/*3. Colore neutro per lo sfondo */ int GREY = COLOR(128,128,128);

/*4. funzione che inizializza tutti i parametri della grafica */ void inizializzagrafica(){srand(time(NULL)); //initializza rand() //4.1. apre una finestra grafica NxM initwindow(basefinestragrafica, altezzafinestragrafica); //4.2. sceglie colore sfondo setbkcolor(GREY); //4.3. disegna colore sfondo cleardevice(); //4.4 sceglie stile e colore disco setfillstyle(SOLID_FILL,coloreacaso()); //4.5. sceglie colore bordo disco setcolor(coloreacaso()); }

/* B. PARAMETRI DEL PROGRAMMA "TUBI" *//*1. Raggio di un disco */int R=30;

/*2. Numero dei dischi da disegnare */int NDischi=10000;

/*3. massima e minima velocità di un disco

28

nelle componenti x,y */int minvx = 5, maxvx = 10, minvy = 5, maxvy = 10;

/*4. Millisecondi tra due disegni di dischi*/int DELAY = 3; /* Scegliere almeno 3, altrimenti lo schermo non fa a tempo a disegnare tutti i dischi e il programma salta */

/*5. probabilita' in ogni instante che un disco cambi direzione: una su probabilitatotali */int probabilitatotali = 200;

/* C. LA CLASSE DISCO CHE RAPPRESENTA I DISCHI.Questa classe si puo’ ottenere estendendo la classe Dischi introdotta nella lezione precedente per il programma “Coriandoli”. Avvertenza. Se modificate una vecchia funzione, per esempio “spostacambiaraggioacaso”, date alla nuova funzione un nuovo nome, per evitare di confonderla con la vecchia. */

struct Dischi {int centrox, centroy, raggio, velocitax, velocitay;//parametri disco

Dischi(int Cx, int Cy, int R, int vx, int vy); //costruttore di un disco void Dischi::disegna(); //disegna un disco void Dischi::sposta(); /*muove un disco di un vettore (velocitax, velocitay) */ bool Dischi::impattox();/*verifica se c'e' un impatto orizzontale contro il bordo */ bool Dischi::impattoy();/*verifica se c'e' un impatto verticale contro il bordo */ void Dischi::rimbalzo(); /* controlla se il disco rimbalza contro un bordo e cambia la velocità se è cosi' */ void Dischi::cambiavelocitacolore();/*sceglie a caso nuova velocità e colore per il disco */};

29

/* DEFINIZIONE FUNZIONI E COSTRUTTORI CLASSE DISCO */Dischi::Dischi(int cx, int cy, int r, int vx, int vy){centrox = cx; centroy = cy; raggio = r; velocitax = vx; velocitay = vy;}

void Dischi::disegna(){fillellipse(centrox, centroy, raggio, raggio);}

void Dischi::sposta(){centrox = centrox + velocitax; centroy = centroy + velocitay;}

bool Dischi::impattox() {//centrox - raggio è il lato sinistro //centrox + raggio è il lato destro return ((centrox - raggio < 0) || (centrox + raggio > basefinestragrafica));}

bool Dischi::impattoy() {//centroy - raggio è il lato superiore //centroy + raggio è il lato inferiore return ((centroy - raggio < 0) || (centroy + raggio > altezzafinestragrafica));}

void Dischi::rimbalzo() {if (impattox()) {velocitax = -velocitax;} if (impattoy()) {velocitay = -velocitay;} }; void Dischi:: cambiavelocitacolore () {velocitax = minvx + rand()%(maxvx-minvx); velocitay = minvy + rand()%(maxvy-minvy); setfillstyle(SOLID_FILL,coloreacaso());};

/* D. Ora definiamo il programma “Tubi” a partire da tutte le funzioni precedenti. */

main() //Il primo passo e':{inizializzagrafica(); //D disco a centro schermo, raggio R, immobile Dischi D(basefinestragrafica/2, altezzafinestragrafica/2, R,0,0); //scelgo a caso velocità e colore per D D. cambiavelocitacolore (); //disegno D in molte posizioni consecutive

30

for(int i = 0; i < NDischi;++i) {D.disegna(); //disegno D nella sua posizione corrente D.rimbalzo(); //se necessario, cambio la direzione di D per rimbalzo D.sposta(); //sposto D in base alla velocità/* se il disco non è in fase di rimbalzo, e se sorteggiando tra 0 e probabilitatotali-1 ottengo 0, allora cambio a caso la velocità e il colore */ if ((D.impattox()==false) && (D.impattoy()==false) && (rand()%probabilitatotali == 0)) {D. cambiavelocitacolore();}/* fermo l'esecuzione del programma di un tempo DELAY per dare tempo allo schermo di aggiornarsi */ delay(DELAY);}//salvo l'ultima immagine dello schermo writeimagefile("C-Tubi.bmp"); system("pause");}

31

Lezione 06: Vettori di Oggetti La classe delle carte da gioco

(Cap. 12.1-12.8 libro di testo)

Lezione 06. In questa lezione vediamo come rappresentare le carte da gioco come oggetti di una classe, e i mazzi di carte come vettori di carte, dunque come vettori di oggetti.

Nota sul C++ usato. Rispetto al libro di testo, sostituiamo le classi apvector e apstring con le classi vector e string di cui abbiamo gia’ parlato nel corso di Basi di Informatica. Ricordiamo che se n è una costante o variabile intera, un vettore per esempio di n interi si dichiara con vector<int> V(n,0). V.size() calcola la lunghezza di V. Gli elementi di V sono numerati da 0 a n-1 e V[i] è l’elemento di posto i di V.

La classe Card delle carte da gioco. Rappresentiamo i “suit” o semi delle carte con interi da 0 a 3: “Clubs” o Fiori = 0, “Diamonds” o Quadri = 1, “Hearts” o Cuori = 2, “Spades” o Picche = 3. Rappresentiamo il “rank” o valore dall’asso al dieci con i numeri da 1 a 10, e poniamo: “Jack” o Fante = 11, “Queen” o Regina = 12, “King” o Re = 13. Definiamo una carta con la coppia del suo seme e del suo valore. Per fare una classe aggiungiamo un costruttore che definisce una carta “bianca”, con un valore 0, e un altro che prende seme e valore e restituisce la carta corrispondente, più alcune funzioni member.

#include <iostream>#include <math.h>#include <vector>#include <stdlib.h>using namespace std;

struct Card{ int suit, rank; Card (); //costruttore di una carta “bianca” Card (int s, int r); //costruttore di una carta normale void Card::print (); //stampa di una carta bool Card::isGreater (Card& c2); /* controlla se una carta è maggiore di un’altra nell’ordine tra le carte */};

/* Costruttori. Hanno nome Card::Card e assegnano i campi della classe per costruire un nuovo oggetto della classe. Non richiedono un return alla fine, è implicito. */

32

Card::Card () {suit = 0; rank = 0;} /*carta “bianca”*/Card::Card (int s, int r) {suit = s; rank = r;} /*carta di seme e valore dato */

D’ora in poi, se scriviamo Card C; usiamo il costruttore senza argomenti per definire C come carta “bianca”. Per costruire una variabile che contenga il 3 di cuori scriviamo invece:

Card threeOfClubs (0, 3);

Le funzioni della classe Card. Possiamo immagazzinare in due vettore di “stringhe” (messaggi) i nomi dei semi e dei valori delle carte, per tradurre un numero con il seme che rappresenta e con il valore che rappresenta. Usando questi vettori, possiamo scrivere la funzione member che data una carta ne stampa la descrizione.

/* Il primo argomento di un costruttore o di una funzione member è sempre indicato con (*this). Davanti al nome di funzione si scrivere Card:: per indicare questo argomento. Al posto di (*this).suit, (*this).rank si puo’scrivere solo suit, rank. */void Card::print () { vector<string> suits (4);suits[0] = "Clubs"; //nome del seme 0suits[1] = "Diamonds"; //nome del seme 1suits[2] = "Hearts"; //nome del seme 2suits[3] = "Spades"; //nome del seme 3

vector<string> ranks (14);ranks[0] = "NON-VALID";ranks[1] = "Ace";ranks[2] = "2";ranks[3] = "3";ranks[4] = "4";ranks[5] = "5";ranks[6] = "6";ranks[7] = "7";ranks[8] = "8";ranks[9] = "9";ranks[10] = "10";ranks[11] = "Jack";ranks[12] = "Queen";ranks[13] = "King";cout << ranks[rank] << " of " << suits[suit] << endl;}

Se a questo punto scriviamo Card card (1, 11); e quindi card.print (); otteniamo la stampa: “Jack of Diamonds”, Fante di Quadri. Il test (.==.) di eguaglianza del C++ non funziona con i tipi che definiamo noi. Tuttavia, possiamo definire un test di eguaglianza controllando che seme e valore siano gli stessi:

33

bool equals (Card& c1, Card& c2) {return (c1.rank == c2.rank && c1.suit == c2.suit);}

Possiamo ordinare le carte mettendo in quest’ordine Fiori, Quadri, Cuori e Picche, e per ogni seme le carte dall’asso al re. Il test (.>.) di eguaglianza del C++ non funziona con i tipi che definiamo noi. Tuttavia, possiamo definire la funzione member che controlla se una carta è maggiore di un’altra nell’ordine che abbiamo scelto.

bool Card::isGreater (Card& c2) {// confrontiamo prima i semi di c1 e c2.if (suit > c2.suit) return true;if (suit < c2.suit) return false;// se i semi sono uguali, confrontiamo i valori di c1 e c2.if (rank > c2.rank) return true;if (rank < c2.rank) return false;// se anche i valori sono uguali, allora c1=c2 e restituiamo falsoreturn false;}

Come abbiamo anticipato, possiamo combinare le carte a formare un mazzo, usando un vettore di carte. Ecco la costruzione di un mazzo di 52 assi di picche:

Card aceOfSpades (3, 1);vector<Card> deck (52, aceOfSpades);

Dato deck e un i tra 0 e 51 la carta numero i del mazzo è deck[i], ha seme deck[i].suit e valore deck[i].rank. Ecco la costruzione del tradizionale mazzo di 52 carte, ordinato dalla carta più piccola a quella più grande.

//Costruzione di un mazzo con tutte e 52 le carte int i = 0; for (int s = 0; s <= 3; s++) {for (int r = 1; r <= 13; r++) {deck[i].suit = s;deck[i].rank = r;i++;}}

Dato un mazzo di carte sotto forma di un vettore di carte, possiamo stamparne il contenuto nell’ordine con cui compare nel vettore:

void printDeck (vector<Card>& deck) {for (int i = 0; i < deck.size(); i++) {deck[i].print ();}}

34

Lezione 06. Seconda ora. Svolgete i seguenti esercizi sulla classe delle carte da gioco. L’esercizio 5.3 viene svolto dal libro di testo nel capitolo 12.9, con la differenza che il libro usa il tipo apvector<Card>, noi usiamo il tipo vector<Card>.

Esercizio 5.1. Ricopiate la classe Card vista a lezione insieme a tutte le sue funzioni in un file. Aggiungete un main in cui costruite e stampate alcuni mazzi di carte, uno solo con l’asso di fiori, uno con tutte le 52 carte, e cosi’ via.

Esercizio 5.2. Definite una funzione int find(Card C, vector<Card> M){…};

che data una carta C e un mazzo M, restituisce il primo i tale che C è la carta numero i del mazzo M, e restituisce invece -1 se C non compare affatto in M. Usate find per controllare se certe carte si trovano oppure no nei mazzi che avete creato. Suggerimento. Confrontate a una a una le carte del mazzo con la carta da cercare, usando un ciclo for. Se trovate la carta uscite subito restituendo la sua posizione, se finite il for senza trovarla, restituite -1. Ricordate che i vettori in C++ sono numerati a partire da 0. Ricordate che il test == non esiste per le carte, usate al suo posto il test equals che abbiamo definito a lezione.

Esercizio 5.3. (Impegnativo). In questo esercizio non usate un ciclo for ma una definizione ricorsiva. Supponiamo di un mazzo ordinato M. Definire una funzione ricorsiva F(C, M, a, b) che trova una carta C in un mazzo ordinato M tra la posizione a e la posizione b comprese, restituendo -1 se la carta non compare tra a e b. Il fatto che il mazzo sia ordinato consente di usare la seguente definizione induttiva per la funzione F. Sia m=(a+b)/2 il punto medio di [a,b] (arrotondato per difetto), allora poniamo:

F(C, M, a, b) =

se (a>b) (dunque [a,b] vuoto): -1 altrimenti se (C = M[m]): m altrimenti se (C > M[m]): F(C, M, m+1, b) altrimenti (dunque C < M[m]): F(C, M, a, m-1)

Nota. Per induzione sul numero di elementi in [a,b] si puo’ dimostrare che se i=F(C,M,a,b) allora C = M[i] se C compare in M tra la posizione a e b, e i=-1 se C non compare tra a e b. Suggerimento. Per decidere se (C = M[m]) e se (C > M[m]), usate le funzioni viste in questa lezione che controllano l’eguaglianza e l’ordine tra carte. Ricordate: non esistono in C++ funzioni gia’ definite con questo compito per i tipi che definiamo noi.

35

/* Soluzioni Lezione 06: come trovare una carta in un mazzo di carte */#include <iostream>#include <math.h>#include <vector>#include <stdlib.h>using namespace std;

struct Card{ int suit, rank; Card(); /*costruttore di una carta “bianca”, si usa in mancanza di altro */ Card (int s, int r);//costruttore di una carta dato seme e valore void Card::print ();//stampa di una carta bool Card::isGreater (Card& c2); /* controlla se una carta è maggiore di un'altra nell'ordine tra le carte */};

Card::Card () {suit = 0; rank = 0;}Card::Card (int s, int r) {suit = s; rank = r;}

void Card::print () {vector<string> suits(4);suits[0] = "Clubs"; //nome del seme 0suits[1] = "Diamonds"; //nome del seme 1suits[2] = "Hearts"; //nome del seme 2suits[3] = "Spades"; //nome del seme 3

vector<string> ranks(14);ranks[0] = "NON-VALID value";ranks[1] = "Ace";ranks[2] = "2";ranks[3] = "3";ranks[4] = "4";ranks[5] = "5";ranks[6] = "6";ranks[7] = "7";ranks[8] = "8";ranks[9] = "9";ranks[10] = "10";ranks[11] = "Jack";ranks[12] = "Queen";ranks[13] = "King";cout << ranks[rank] << " of " << suits[suit] << endl;}

36

bool equals (Card& c1, Card& c2) {return ((c1.rank == c2.rank) && (c1.suit == c2.suit));}

bool Card::isGreater (Card& c2) {// confrontiamo prima i semi di c1 e c2.if (suit > c2.suit) return true;if (suit < c2.suit) return false;// se i semi sono uguali, confrontiamo i valori di c1 e c2.if (rank > c2.rank) return true;if (rank < c2.rank) return false;// se anche i valori sono uguali, allora c1=c2 e restituiamo falsoreturn false;}

void printDeck (vector<Card>& deck) {for (int i = 0; i < deck.size(); i++) {deck[i].print ();}}

int find(Card C, vector<Card> M){int L = M.size(); for(int i=0;i<L;++i) {if (equals(C,M[i])==true) return i;} //se esco dal for allora finisco il mazzo e non trovo la carta return -1;}

int F(Card C, vector<Card> M, int a, int b){int m = (a+b)/2; if (a>b) return -1; else if (equals(C,M[m])==true) return m; else if (C.isGreater (M[m]) == true) return F(C, M, m + 1, b); else return F(C, M, a, m - 1);}

main(){Card card0 (0,0); Card card1 (1, 11); Card card2 (0, 1); cout << "\n 1. STAMPA DELLE CARTE: (0,0), (1,11), (0,1)" << endl;

37

card0.print (); card1.print ();card2.print (); cout << "\n 2. STAMPA DI TUTTE LE 52 CARTE DEL MAZZO CLASSICO" << endl; Card aceOfSpades (3, 1); Card kingOfSpades (3, 13); vector<Card> deck (52, card0); //Costruzione di un mazzo con tutte e 52 le carte int i = 0; for (int s = 0; s <= 3; s++) {for (int r = 1; r <= 13; r++) {deck[i].suit = s;deck[i].rank = r;i++;}} //Stampa di un mazzo con tutte e 52 le carte printDeck(deck); cout << "\n 3. RICERCA DELL'ASSO E DEL RE DI PICCHE" << endl; cout << "Controllo che si trovino nelle posizioni 39 e 51 del mazzo" << endl; cout << endl; cout << "deck[39] = "; deck[39].print(); cout << "deck[51] = "; deck[51].print(); cout << endl; cout << "find(aceOfSpades,deck) = " << find(aceOfSpades,deck) << endl; cout << "find(kingOfSpades,deck) = " << find(kingOfSpades,deck) << endl; cout << endl; cout << "F(aceOfSpades,deck,0,51) = " << F(aceOfSpades,deck,0,51) << endl; cout << "F(kingOfSpades,deck,0,51) = " << F(kingOfSpades,deck,0,51) << endl; cout << endl; system("pause");}

38

Lezione 07: Classi definite l’una dall’altra(Cap. 13 libro di testo)

In questa lezione svolgeremo l’esercizio proposto nel capitolo 13 del libro di testo: scrivere delle classi che descrivano una carta e un mazzo di carte, e che contengano una funzione che mescola il mazzo di carte e che ordina un mazzo di carte.

Le funzioni che manipolano le carte fanno riferimento alla nozione del mazzo di carte e viceversa, quindi le due strutture Card (carte) e Deck (mazzi di carte) sono definite una rispetto all’altra. è possibile scrivere queste definizioni incrociate, purche’ siano logicamente corrette (definiscano in modo univoco cosa è una carta e un mazzo di carte), e purche’ dichiariamo subito all’inizio del programma che Card, Deck sono strutture.

Voi dovete copiare il programma qui sotto e completarlo, aggiungendo le funzioni parte della definizione di ogni classe. Non è banale realizzare la funzione che mescola il mazzo di carte e quella che lo riordina. Il libro propone degli ``algoritmi’’ (dei metodi meccanici di calcolo) che riassumiamo qui. Un algoritmo viene descritto a parole e non dipende da un particolare linguaggio di programmazione ma puo’ venire realizzato in ogni linguaggio.

Mescolare un mazzo di carte. Più in generale, spieghiamo come mescolare a caso un vettore. Per farlo dovete scambiare il primo elemento con un elemento scelto a caso del vettore (che potrebbe essere lui stesso, anche se l’operazione ci sembra insensata). Poi scambiamo il secondo con un elemento scelto a caso dal secondo il poi, il terzo con un elemento scelto a caso dal terzo in poi, eccetera. Un esempio: cominciamo con

1 2 3 4

Scambiamo 1 con 3 (scelta casuale): otteniamo

3 2 1 4

D’ora in avanti non sposteremo più il primo elemento, ma mescoleremo i rimanenti tre. Scambiamo 2 con 1 (scelta casuale): otteniamo

3 1 2 4

39

D’ora in avanti non sposteremo più i primi due elementi, ma mescoleremo i rimanenti due. Scambiamo 2 con se stesso (scelta casuale): otteniamo otteniamo

3 1 2 4

D’ora in avanti non sposteremo più i primi tre elementi. Il quarto elemento puo’ essere solo più scambiato con se stesso, quindi alla fine otteniamo

3 1 2 4

Ordinamento di un mazzo di carte. Più in generale, spieghiamo come ordinare un vettore data una relazione di ordine sui suoi elementi. è più laborioso che non mescolare. Proviamo a ordinare il vettore non ordinato che abbiamo appena ottenuto:

3 1 2 4

Confrontiamo il primo elemento con i successivi, ogni volta che troviamo un elemento più piccolo del primo scambiamo i due elementi trovati, e continuiamo cosi’ fino alla fine del vettore. Il risultato è porre l’elemento più piccolo all’inizio del vettore. Per esempio, nel caso scelto confrontiamo 3 con 1 e li scambiamo:

1 3 2 4

Poi confrontiamo 1 con 2 e non facciamo scambi. Confrontiamo 1 con 4 e non facciamo scambi. Ora non sposteremo più il primo elemento, che è il più piccolo e si trova gia’ al posto giusto.

1 3 2 4

Ripetiamo le stesse operazioni con il secondo, terzo, … elemento del vettore, fino a passarli in rassegna tutti. Il più piccolo tra gli elementi dal secondo in poi finira’ al secondo posto, il più piccolo tra gli elementi dal terzo in poi finira’ al terzo posto, eccetera. Alla fine il vettore sara’ ordinato.

Vediamo cosa succede nel nostro esempio. Se seguiamo alla lettera il metodo descritto non facciamo più scambi. Infatti confrontiamo 2 con 3, 2 con 4 e non eseguiamo scambi.

1 2 3 4

Il 2 è quindi l’elemento più piccolo tra quelli dal secondo posto in poi.

1 2 3 4

40

Confrontiamo 3 con 4 e non eseguiamo scambi: dunque il 3 è l’elemento più piccolo dal terzo posto in poi.

1 2 3 4

Il 4 non puo’ essere scambiato con nessun elemento successivo: dunque ora il vettore è ordinato.

1 2 3 4

Qui sotto trovare il programma con le classi Card e Deck da completare.

/* Lezione 07. Completare le classi Card (carte) e Deck (mazzi di carte) che trovate qui sotto definendo tutte le funzioni della classe, in modo che il main funzioni correttamente. */

#include <iostream>#include <math.h>#include <vector>#include <stdlib.h>#include <time.h>using namespace std;

/* Questo comando definisce Suit come l’insieme di interi che contiene le costanti CLUBS=0, DIAMONDS=1, HEARTS=2, SPADES=3. */enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES };

/* Questo comando definisce Rank come l’insieme di interi che contiene le costanti ACE=1, TWO=2, …, KING=13. */enum Rank { ACE=1, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING };

/* Dichiariamo Card, Deck strutture, ma senza definirle */struct Card; struct Deck;/* Possiamo ora definire Card a partire da Deck e viceversa, purche' le definizioni scelte individuino univocamente Card, Deck. */

/* DEFINIZIONE DI CARD a partire da Deck */struct Card {int suit, rank; //seme e valore di una carta

41

/* COSTRUTTORI DI CARD */Card (); /*costruttore di default: definisce una carta "bianca" e si usa in mancanza di altro */Card (Suit s, Rank r); //costruisce una carta dato seme e valore

/* FUNZIONI MEMBER: non indichiamo mai il primo argomento, che è sempre una carta */void print (); //stampa una cartabool isGreater (Card& c2); //confronta una carta con una carta c2int find (Deck& deck); /* trova la posizione di una carta in un mazzo, restituisce -1 se la carta non c'e' */};

// DEFINIZIONE DI DECK a partire da Card struct Deck { vector<Card> cards; /* un mazzo di carte è un vettore di carte */

/* COSTRUTTORI: abbiamo tutti i costruttori di vector, più dei costruttori nuovi per i mazzi di carte: */ Deck (); //costruttore di default: si usa in mancanza di altro Deck (int n); /* costruttore di una mazzo di n carte tutte “bianche” (con valore di default per il seme e il valore) */

/* FUNZIONI MEMBER: non indichiamo mai il primo argomento, che è sempre un mazzo di carte */ void print (); //stampa delle carte di un mazzo Deck subdeck (int a, int b); /* costruisce un nuovo mazzo di carte prendendo le carte dalla posizione a fino a b */ void shuffle (); //mescola a caso le carte di un mazzo void sort (); //ordina le carte di un mazzo};

/*----------------------------------------------------------------Da qui in poi ci sono le funzioni di Card e Deck da completare in modo che il main incluso alla fine funzioni correttamente ----------------------------------------------------------------*/

/* Costruttore di default di carta: costruisce una carta "bianca", di valore 0, e si usa solo in mancanza d'altro */Card::Card () { }

42

/* Costruttore di una carta dato seme e valore */Card::Card(Suit s, Rank r) {}

/* Traduzione del seme e del valore di una carta in parole */string namesuit(Suit s){ switch (s) { case CLUBS: return "Clubs"; case DIAMONDS: return "Diamonds"; case HEARTS: return "Hearts"; case SPADES: return "Spades"; default: return "Not a valid suit"; }}

string namerank(Rank r){ switch (r) { case ACE: return "Ace"; case TWO: return "Two"; case THREE: return "Three"; case FOUR: return "Four"; case FIVE: return "Five"; case SIX: return "Six"; case SEVEN: return "Seven"; case EIGHT: return "Eight"; case NINE: return "Nine"; case TEN: return "Ten"; case JACK: return "Jack"; case QUEEN: return "Queen"; case KING: return "King"; default: return "Not a valid rank"; }}

void Card::print(){}

void Deck::print(){}

bool equals (Card& c1, Card& c2) {}

43

bool Card::isGreater (Card& c2) {}

int Card::find (Deck& deck){}

Deck::Deck(){}

Deck::Deck(int n){}

/* Funzione che costruisce un nuovo mazzo di (b-a+1) carte prendendo le carte dalla posizione a fino alla posizione b */

Deck Deck::subdeck (int a, int b){Deck result(b-a+1); for(int i=0, j=a;j<b;++i, ++j) result.cards[i] = cards[j]; return result; };

//Funzione che mescola a caso le carte di un mazzovoid Deck::shuffle (){}

void Deck::sort () //ordina le carte di un mazzo{}

main(){/*assegnamo la data segnata dall'orologio del computer come "seme" della successione casuale generata da rand() */ srand(time(NULL)); /* Definiamo una carta "bianca" (di valore 0) con il costruttore di default */ Card Bianca; Card C(HEARTS, ACE); cout << "carta Bianca" << endl; Bianca.print(); cout << "carta C" << endl; C.print();

44

/* Sperimentiamo le diverse funzioni che abbiamo definito: costruiamo un mazzo di carte classico, lo mescoliamo e alla fine lo ordiniamo di nuovo. */ Deck classic_deck; cout << "MAZZO DI 52 CARTE CLASSICO" << endl; classic_deck.print(); cout << "MAZZO DI 52 CARTE PERMUTATO" << endl; classic_deck.shuffle(); classic_deck.print(); cout << "MAZZO DI 52 CARTE RIORDINATO" << endl; classic_deck.sort(); classic_deck.print(); system("pause"); }

45

//Soluzioni Lezione 07: come mescolare un mazzo di carte#include <iostream>#include <math.h>#include <vector>#include <stdlib.h>#include <time.h>using namespace std;

enum Suit { CLUBS, DIAMONDS, HEARTS, SPADES };

enum Rank { ACE=1, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING };

/* Dichiariamo che Card, Deck sono strutture, ma senza definirle */struct Card; struct Deck;/* Possiamo ora definire Card a partire da Deck e viceversa, purche' le definizioni scelte individuino univocamente Card, Deck. */

/* DEFINIZIONE DI CARD a partire da Deck */struct Card {int suit, rank; //seme e valore di una carta

/* COSTRUTTORI DI CARD */Card (); /*costruttore di default: definisce una carta "bianca" e si usa in mancanza di altro */Card (Suit s, Rank r); //costruisce una carta dato seme e valore

/* FUNZIONI MEMBER: non indichiamo mai il primo argomento, che è sempre una carta */void print (); //stampa una cartabool isGreater (Card& c2); //confronta una carta con una carta c2int find (Deck& deck); /* trova la posizione di una carta in un mazzo, restituisce -1 se la carta non c'e' */};

// DEFINIZIONE DI DECK a partire da Card struct Deck { vector<Card> cards; /* un mazzo di carte è un vettore di carte */

/* COSTRUTTORI: abbiamo tutti i costruttori di vector,

46

più dei costruttori nuovi per i mazzi di carte: */ Deck (); //costruttore di default: si usa in mancanza di altro Deck (int n); /* costruttore di una mazzo di n carte tutte con valore di default */

/* FUNZIONI MEMBER: non indichiamo mai il primo argomento, che è sempre un mazzo di carte */ void print (); //stampa delle carte di un mazzo Deck subdeck (int a, int b); /* costruisce un nuovo mazzo di carte prendendo le carte dalla posizione a fino a b */ void shuffle (); //mescola a caso le carte di un mazzo void sort (); //ordina le carte di un mazzo};

/* Costruttore di default di carta: costruisce una carta "bianca", di valore 0, e si usa solo in mancanza d'altro */Card::Card () {suit = 0; rank = 0;}

/* Costruttore di una carta dato seme e valore */Card::Card(Suit s, Rank r) {suit = s; rank = r;}

/* Traduzione del seme e del valore di una carta in parole */string namesuit(Suit s){ switch (s) { case CLUBS: return "Clubs"; case DIAMONDS: return "Diamonds"; case HEARTS: return "Hearts"; case SPADES: return "Spades"; default: return "Not a valid suit"; }}

string namerank(Rank r){ switch (r) { case ACE: return "Ace"; case TWO: return "Two"; case THREE: return "Three"; case FOUR: return "Four"; case FIVE: return "Five"; case SIX: return "Six";

47

case SEVEN: return "Seven"; case EIGHT: return "Eight"; case NINE: return "Nine"; case TEN: return "Ten"; case JACK: return "Jack"; case QUEEN: return "Queen"; case KING: return "King"; default: return "Not a valid rank"; }}

void Card::print(){ cout << namerank(rank) << " of " << namesuit(suit) << endl; }

void Deck::print(){int L = cards.size(); for(int i=0; i< L; ++i) cards[i].print();}

bool equals (Card& c1, Card& c2) {return ((c1.rank == c2.rank) && (c1.suit == c2.suit));}

bool Card::isGreater (Card& c2) {// first check the suitsif (suit > c2.suit) return true;if (suit < c2.suit) return false;// if the suits are equal, check the ranksif (rank > c2.rank) return true;if (rank < c2.rank) return false;// if the ranks are also equal, return falsereturn false;}

int Card::find (Deck& deck){int L = (deck.cards).size(); for(int i=0;i<L;++i) {if (equals(*this,(deck.cards)[i])==true) return i;} //se esco dal for allora finisco il mazzo e non trovo la carta return -1;}

Deck::Deck()

48

{ vector<Card> temp(52); cards = temp; int index = 0; for (Suit s = CLUBS; s <= SPADES; s = s+1) {for (Rank r = ACE; r <= KING; r = r+1) { cards[index].suit = s; cards[index].rank = r; index++; } } }

Deck::Deck(int n){Card C; vector<Card> temp(n); cards = temp; for(int i=0;i<n;++i) cards[i] = C;}

/* Funzione che costruisce un nuovo mazzo di (b-a+1) carte prendendo le carte dalla posizione a fino alla posizione b */

Deck Deck::subdeck (int a, int b){Deck result(b-a+1); for(int i=0, j=a;j<b;++i, ++j) result.cards[i] = cards[j]; return result; };

//Funzione che mescola a caso le carte di un mazzovoid Deck::shuffle (){Card temp; int n = cards.size(); for(int i=0;i<n;++i) {int j = i+rand()%(n-i); temp = cards[i]; cards[i] = cards[j]; cards[j] = temp;}}

void Deck::sort () //ordina le carte di un mazzo{Card temp; int n = cards.size();

49

for(int i=0;i<n-1;++i) for(int j=i+1;j<n;++j) {if (cards[i].isGreater(cards[j]) == true) {temp = cards[i]; cards[i] = cards[j]; cards[j] = temp;}; }}

main(){/*assegnamo la data segnata dall'orologio del computer come "seme" della successione casuale generata da rand() */ srand(time(NULL)); /* Definiamo una carta "bianca" (di valore 0) con il costruttore di default */ Card Bianca; Card C(HEARTS, ACE); cout << "carta Bianca" << endl; Bianca.print(); cout << "carta C" << endl; C.print(); /* Sperimentiamo le diverse funzioni che abbiamo definito: costruiamo un mazzo di carte classico, lo mescoliamo e alla fine lo ordiniamo di nuovo. */ Deck classic_deck; cout << "MAZZO DI 52 CARTE CLASSICO" << endl; classic_deck.print(); cout << "MAZZO DI 52 CARTE PERMUTATO" << endl; classic_deck.shuffle(); classic_deck.print(); cout << "MAZZO DI 52 CARTE RIORDINATO" << endl; classic_deck.sort(); classic_deck.print(); system("pause"); }

50

Lezione 08: Un esempio di programma:

il programma che gioca a “Nim”

La posizione iniziale del gioco del Nim consiste in un vettore v di n interi positivi o nulli. A turno ogni giocatore sceglie un intero positivo e lo rimpiazza con un intero positivo o nullo. Vince chi riduce a zero l’ultimo positivo, cioe’ perde chi per il primo si trova a dover muovere da una posizione fatta solo di zeri. Aiuta rappresentare ogni numero v[i] in v con una riga fatta di v[i] aste, per esempio la posizione v={1,3,5,7} diventa:

IIII

IIIIIIIIIIII

Vediamo una partita.

Un esempio di partita. Sia v={2,2} la posizione iniziale:IIII

1. Il primo giocatore riduce v[0] da 2 a 1, ottenendo v’={1,2}.2. Il secondo riduce v[1] da 2 a 1, ottenendo v”={1,1}. 3. Il primo giocatore rimpiazza v[0] con 0, ottenendo v”’={0,1}.4. Il secondo ottiene v””={0,0} e vince.

Nell’esempio v={2,2}, il secondo giocatore puo’ giocare in modo da vincere sempre. Non è sempre cosi’. Provate a iniziare dalla posizione v={2,2,2}:

IIIIII

Il primo giocatore ha una mossa vincente (scoprite quale).

Il Nim è uno dei pochi giochi effettivamente in uso per cui sia nota la strategia migliore possibile per il giocatore di turno, e per cui questa strategia abbia una descrizione semplice, che utilizza l’operazione (a^b) chiamata “bitwise xor”. Il bitwise xor è una operazione binaria su due interi positivi o nulli a, b. La definizione del bitwise xor e’: la cifra binaria numero i di (a^b) è 0 se le cifre binarie numeri i di a, b sono uguali, è 1 se sono diverse. L’esatta definizione di (a^b) è irrilevante nella descrizione della mossa vincente, e d’ora in poi non la citeremo più. Si dimostra che una posizione pos={pos[0],…,pos[n-1]} è vincente per il giocatore di turno se e solo se prod = (pos[0]^…^pos[n-1]) > 0. Sia prod l’intero positivo o nullo definito qui sopra. La mossa vincente per per il giocatore di turno consiste nello scegliere un i in [0,n-1] tale che valga la misteriosa condizione (pos[i]^prod) < pos[i]: si prova che se prod>0 allora esiste almeno un i per cui ((pos[i]^prod) < pos[i]) vale. Quindi si riduce pos[i] al valore (pos[i]^prod), mossa corretta proprio

51

perche’ abbiamo supposto ((pos[i]^prod) < pos[i]). Invece se prod=0 la strategia ottima sceglie una mossa per perdere tempo, perche’ nel caso sia prod=0 è impossibile vincere contro un avversario bravo.

Incidentalmente: se scegliamo a caso una posizione pos fatta di interi da 0 a 2n-1, allora la probabilita’ che il primo giocatore abbia una strategia vincente è 2n-1 contro 1. Se il primo giocatore non ha una strategia vincente allora ce l’ha il secondo. Dunque giocare per primi da’, in media, un vantaggio enorme, ma solo per chi è capace di trovare la mossa vincente. Per una descrizione più dettagliata del Gioco del Nim, della sua strategia vincente e della misteriosa operazione “bitwise xor” facciamo riferimento a Wikipedia.

Scriveremo un programma “Nim” che fa giocare il computer come secondo giocatore contro un giocatore umano, usando la strategia ottima descritta sopra. Per semplicita’ stampiamo una posizione v={n1,n2,…} come una lista di interi. Come al solito, il nostro vero scopo è imparare a progettare un programma partendo dai dati e dalle operazioni su di essi.

Definizione della classe delle posizioni del Nim. Una posizione del Nim con n interi si rappresenta con un vettore di n interi non negativi. Abbiamo gia’ visto nel corso di Basi di Informatica che un vettore di interi si rappresenta con il tipo vector<int>. La classe delle posizioni del Nim avra’ quindi un unico campo, “pos”, che sara’ un vettore di interi.

Le funzioni della classe Nim. Avremo bisogno di:

1. Un costruttore Nim::Nim(); senza argomenti che sorteggi una posizione iniziale del gioco.

2. Una operazione void Nim::stampa(); che stampi a video una posizione del gioco come una lista di interi.

3. Un test bool Nim::nonzero(); che decida se il gioco continua, e restituisca vero quando è cosi’, falso altrimenti. Il gioco continua quando una posizione contiene almeno un non zero.

4. Di una funzione int Nim::xor_prod(); che prenda una posizione e restituisca l’intero prod = (pos[0]^…^pos[n-1]).

5. Di una funzione void Nim::mossa_giocatore();che prenda una posizione, chieda al giocatore che mossa vuole fare, e se è corretta la esegua modificando la posizione data, altrimenti la chieda di nuovo.

6. Di una funzione void Nim::mossa_computer(); che prenda una posizione, faccia muovere il computer usando la strategia ottima, e modifichi la posizione data di conseguenza.

52

7. Di una funzione void Nim::partita(); che prenda una posizione e giochi una intera partita, chiedendo alternativamente al giocatore e al computer una mossa. Il computer muove per secondo.

I parametri del programma “Nim”. Come parametri del programma “Nim” possiamo scegliere il numero degli interi di cui è composta la posizione e il massimo valore di ciascun intero. Li rappresentiamo come variabili globali e non li modifichiamo durante il programma. Per avere posizioni con più o meno interi e con interi più o meno grandi ci bastera’ cambiare un parametro.

Funzioni di appoggio. Aggiungiamo una funzione void spiegazione(int Nrighe) che dato il numero delle righe del gioco (il numero di interi del vettore poszione) stampa le spiegazioni del gioco all’inizio di ogni partita.

Per facilitarvi il lavoro, di seguito inseriamo un programma gia’ parzialmente completato. Potete confrontare il vostro eseguibile con il seguente:

http://www.di.unito.it/~stefano/C++-GiocoDelNim-2012.exe

Un’avvertenza: scrivete SEMPRE (x^y) e non x^y. Il motivo è che l’operazione “xor” ha una priorita’ algebrica bassa, e senza parentesi rischiate che quello che scrivete non venga capito. Per esempio per stampare (2^3) non scrivete cout << 2^3 << endl; perche’, dato che il << prevale sul ^, viene capito: cout << 2^(3 << endl);espressione che non ha senso. Scrivete invece: cout << (2^3) << endl;cosi’ non ci sono dubbi sul fatto che chiedete di stampare proprio (2^3), e non l’espressione senza senso 2^(3 << endl).

/* Soluzione parziale del gioco del Nim, da completare: non funziona cosi’ come è */#include <iostream> /* per il cout */#include <stdlib.h> /* per il system(“pause”) */#include <vector> /* per i vettori */#include <cmath> /* per il bitwise xor */#include <time.h> /* per il comando srand(time(NULL)); che inizializza la funzione rand(), vedi lezione precedente. */using namespace std; /* per abbreviare il cout */

http://www.di.unito.it/~stefano/C++-GiocoDelNim-2012.exe

53

/* PARAMETRI DEL PROGRAMMA NIM. Numero degli elementi di v e limite superiore per ogni elemento di v */int Nrighe=4,Maxriga=8; //Ogni intero della posizione è <Maxriga

/* CLASSE CON LE POSIZIONI DEL GIOCO DEL NIM */struct Nim { vector<int> pos; //costruttore di una posizione a caso (entro i parametri fissati) Nim(); void Nim::stampa(); //stampa bool Nim::nonzero(); /*controllo se una posizione è finale ( fatta di tutti zeri) */ int Nim::xor_prod(); /* calcolo di (pos[0]^…^pos[n-1]) void Nim::mossa_computer(); /* modifica della posizione in base alla mossa del computer */ void Nim::mossa_giocatore(); /* modifica della posizione in base alla mossa del computer */ void Nim::partita(); /* gioca un’intera partita dalla posizione data */ };

Nim::Nim(){} //costruttore di una posizione a caso void Nim::stampa(){}; //stampa bool nonzero(){}; /*controllo se una posizione è finale ( fatta di tutti zeri) */ int Nim::xor_prod(){}; /* calcolo di (pos[0]^…^pos[n-1]) void Nim::mossa_computer(){}; /* modifica della posizione in base alla mossa del computer */ void Nim::mossa_giocatore(){}; /* modifica della posizione in base alla mossa del computer */ void Nim::partita(){}; /* gioca un’intera partita dalla posizione data */ void spiegazione(int Nrighe){cout << "GIOCO DEL NIM" << endl; cout << "-Viene scelta a caso una lista di numeri >=0" << "\nsiano essi n_0, ..., n_" << Nrighe-1 << endl; cout << "-A turno ogni giocatore sceglie un n_r>0" << "\ne lo riduce" << endl; cout << "-Chi riduce a zero l'ultimo numero positivo\n" << "rimasto vince" << endl; cout << "------------------------------" << endl;}

main(){/*modifico ogni volta la scelta dei numeri casuali*/

54

srand(time(NULL));/* scelgo una pos iniziale del Nim a caso */Nim nim;/* Spiego ogni volta le regole del gioco */spiegazione(Nrighe);/* Inizio partita */nim.partita();/* Fine partita */system("pause");}

55

/* Soluzioni. Lezione 08. Il Gioco del Nim */#include <iostream> /* per il cout */#include <stdlib.h> /* per il system(“pause”) */#include <cmath> /* per pow(a,b) */#include <vector> /* per i vettori */#include <time.h> /* per time(NULL) */using namespace std; /* per abbreviare il cout */

/* PARAMETRI DEL PROGRAMMA NIM. Numero degli elementi di v e limite superiore per ogni elemento di v */int Nrighe=4,Maxriga=8;

struct Nim { vector<int> pos; //costruttore di una posizione a caso (entro i parametri fissati) Nim(); void stampa(); //stampa bool nonzero(); /*controllo se una posizione è finale ( fatta di tutti zeri) */ int xor_prod(); /* calcolo di (pos[0]^…^pos[n-1]) void mossa_computer(); /* modifica della posizione in base alla mossa del computer */ void mossa_giocatore(); /* modifica della posizione in base alla mossa del computer */ void partita();/* gioca un’intera partita dalla posizione data */}; //occhio a non dimenticare il punto e virgola!

//costruttore di una posizione a caso (entro i parametri fissati)Nim::Nim(){vector<int> v(Nrighe); for(int i=0;i<Nrighe;++i) v[i]=rand()%Maxriga; pos = v;//nota: un costruttore non richiede il return}

/* Funzioni member della classe Nim */void Nim::stampa(){int n = pos.size(); cout << " "; for(int i=0;i<n;++i) cout << pos[i] << " "; cout << endl;}

bool Nim::nonzero()

56

{int n = pos.size(); for(int i=0;i<n;++i) {if (pos[i]!=0) return true;} return false;}

int Nim::xor_prod(){int n = pos.size(); int prod = pos[0]; for(int i=1; i<n; ++i) prod = (prod^pos[i]); return prod;} void Nim::mossa_computer(){int n = pos.size(); int prod = (*this).xor_prod(), b;

if (prod>0) /* se prod>0, scelgo la mossa vincente prevista dalla teoria e esco subito */ for(int i=0;i<n;++i) {b = (prod^pos[i]); if (b < pos[i]) {pos[i] = b; return; /*termino appena eseguita la mossa vincente*/ } } else /* se prod=0, non c'e' una mossa vincente, allora scelgo una mossa per perdere tempo */ {int a=rand()%Nrighe; //scelgo una riga a caso while (pos[a]==0) //finche' la riga è vuota ripeto la scelta {a=rand()%Nrighe;} pos[a]=pos[a]-1;} //riduco la riga non vuota di 1}

void Nim::mossa_giocatore(){int n=pos.size(), r, s; bool corretta;/* chiedo al giocatore di scegliere un numero r tra 0 e n-1 da ridurre. Finche’ la risposta non è corretta ripeto la domanda */ corretta=false; // per far eseguire il while almeno una volta while (corretta==false) {cout << " quale numero vuoi ridurre (da 0 a " << n-1 << ")?" << endl; cin >> r; corretta = (0<=r) && (r<n); // controllo se r è corretto if (corretta == false) cout << "!mossa non corretta!" << endl;}

57

/* chiedo al giocatore di scegliere un valore s con cui ridurre pos[r]. Finche’ la risposta non è corretta ripeto la domanda */ corretta=false; // per far eseguire il while almeno una volta while (corretta==false) {cout << " quale valore s vuoi sottrarre (da 1 a " << pos[r] << ")?" << endl; cin >> s; corretta = (0<s) && (s<=pos[r]); // controllo se s è corretto if (corretta == false) cout << "!mossa non corretta!" << endl;} /* Alla fine, ottenuta una mossa (r,s) corretta la eseguo */ pos[r]=pos[r]-s; } void Nim::partita(){int n = pos.size(); cout << "Posizione iniziale" << endl; (*this).stampa(); cout << "------(inizio gioco)----------" << endl;

bool continuare = true; int count=1;/* Finche' non ho raggiunto l'ultima posizione, chiedo una mossa al giocatore e una al computer. Raggiunta l'ultima posizione decido il nome del vincitore e lo stampo */ while (continuare==true) {cout << "Turno n. " << count << endl;/* MOSSA GIOCATORE. Controllo se il giocatore perde */ continuare = (*this).nonzero();/* Se il giocatore ha perso il gioco finisce, altrimenti il giocatore muove */ if (continuare==true) {cout << "Mossa giocatore" << endl; (*this).mossa_giocatore(); cout << "Posizione corrente" << endl; (*this).stampa();} else {cout << "***VINCE IL COMPUTER***" << endl;}/* MOSSA COMPUTER. Controllo se il computer perde */ if (continuare==true) {continuare = (*this).nonzero();/* Se il computer ha perso il gioco finisce, altrimenti il computer muove */ if (continuare==true) {cout << "Risposta computer" << endl; (*this).mossa_computer();

58

stampa();} else {cout << "***VINCE IL GIOCATORE***" << endl;} } /* aggiorno il contatore dei turni e segno la fine di un turno */ ++count; cout << "------(fine turno)------------" << endl; } cout << "FINE" << endl; }

void spiegazione(int Nrighe){cout << "GIOCO DEL NIM" << endl; cout << "-Viene scelta a caso una lista di numeri >=0" << "\nsiano essi n_0, ..., n_" << Nrighe-1 << endl; cout << "-A turno ogni giocatore sceglie un n_r>0" << "\ne lo riduce" << endl; cout << "-Chi riduce a zero l'ultimo numero positivo\n" << "rimasto vince" << endl; cout << "------------------------------" << endl;}

main(){/*modifico ogni volta la scelta dei numeri casuali*/srand(time(NULL));/* scelgo una posizione iniziale del Nim a caso */Nim nim;/* Spiego ogni volta le regole del gioco */spiegazione(Nrighe);/* Inizio partita */nim.partita();/* Fine partita */system("pause");}

59

Lezione 09: parti pubbliche e private di una classe (Cap. 14.1-14.7 del libro di testo)

Il libro di testo dedica il capitolo 14 alla nozione di “data encapsulation”. Si tratta possibilità di nascondere, a chi scrive il programma, il modo con cui i dati sono rappresentati, per rendere i dettagli del programma e i dettagli dei dati indipendenti tra loro, per quanto possibile. È qualcosa che implicitamente abbiamo già fatto, ma rendere questa scelta esplicita ha almeno due vantaggi.

1. Quando scrivo un programma posso usare solo le operazioni disponibili sui dati e la loro descrizione, sono quindi costretto a trascurare ogni informazione sulla rappresentazione dei dati che servirebbe solo a confondermi.

2. Inoltre, quando ho finito di scrivere un programma posso cambiare il modo con cui le operazioni sui dati vengono realizzate, purché non ne cambi la descrizione.

D’ora in poi usiamo la parola “classe” per indicare una struttura con una parte nascosta: facciamo questo solo per capirci, in realtà “struttura” e “classe” sono sinonimi. Possiamo trasformare la struttura Card delle carte in una classe nascondendo il modo con cui Card viene realizzata, come segue:

class Card /* Card è una struttura con una parte nascosta */{

private: /* “private” significa: gli interi suit, rank non sono accessibili a chi usa la struttura, ma solo alle funzioni della struttura. */ int suit, rank;

public: /* “public” significa: queste funzioni sono accessibili a chi usa la struttura. */ Card (); // Carta “bianca” Card (int s, int r); // Carta dato seme e valore int getRank (){ return rank; } // Valore di una carta int getSuit (){ return suit; } // Seme di una carta int setRank (int r) { rank = r; } // Modifico il valore int setSuit (int s) { suit = s; } // Modifico il seme

}; //non dimenticate il punto e virgola

Quando usiamo la parola “Class”, la parola “private” si può omettere (cap. 14.2), ma la definizione è più chiara se la lasciamo. Nel caso di Card non c’è nessun vantaggio a nascondere il modo con cui Card viene rappresentata: la rappresentazione

60

ottimale di una carta da gioco è la coppia (seme, valore), e questa rappresentazione è immediatamente visibile guardando le funzioni della classe Card. C’è vantaggio a nascondere il modo con cui una struttura viene realizzata quando la rappresentazione dei dati è complessa, oppure cambia a seconda dell’uso che vogliamo fare dei dati. Abbiamo quindi bisogno di un altro esempio.

La struttura dei numeri complessi (capitoli 14.3-14.7). L’esempio scelto dal libro è la struttura Complex dei numeri complessi: posso rappresentare un numero complesso con coordinate cartesiane, polari oppure entrambe. Quando scrivo un programma non desidero sapere come un numero complesso viene rappresentato, quindi ne nascondo la rappresentazione. L’esempio è scelto in base alla sua semplicità, non in base alla sua verosimiglianza, e convince fino a un certo punto. Passare dalla rappresentazione cartesiana a quella polare è una attività poco costosa, per cui si potrebbero rappresentare i numeri complessi in coordinate cartesiane e convertire a rappresentazione polare quando serve. Tuttavia l’esempio ci fa capire che più la rappresentazione di un dato è ricca di dettagli, più conviene trattare questa rappresentazione a parte, nella parte “privata” della definizione di una classe, lasciando il programma che scriviamo indipendente dai dettagli della scelta fatta.

Vediamo ora la classe Complex dei numeri complessi. Un numero complesso può avere rappresentazione cartesiana, oppure polare, oppure tutte e due, purché le due rappresentazioni siano rappresentazioni dello stesso numero.

/* Lezione 09. La classe Complex */#include <iostream> /* per il cout */#include <stdlib.h> /* per il system(“pause”) */#include <cmath> /* per sin, cos */using namespace std; /* per abbreviare il cout */

class Complex{ //rappresentazione di un numero complesso c

private: double real, imag; // rappresentazione cartesiana (quando usata) double mag, theta; // rappresentazione polare (quando usata) bool cartesian; // se cartesian = vero allora c=(real,imag) bool polar; // se polar = vero allora c=(mag, theta) void Complex::calculateCartesian(); // aggiorna co. cartesiane void Complex::calculatePolar(); // aggiorna co. polari

61

public: Complex::Complex (); // costruisce un complesso banale, lo zero Complex (double re, double im); // costruisce complesso (re+im*i) void Complex::setPolar(double m, double t);// assegna co. polari double Complex::getReal (); // parte reale double Complex::getImag (); // parte immaginaria double Complex::getMag (); // norma double Complex::getTheta (); // angolo void Complex::printCartesian (); // stampa co. cartesiane void Complex::printPolar (); // stampa co. polari

}; //non dimenticate il punto e virgola

Complex::Complex() /* costruisce un numero complesso banale, lo zero */{ cartesian = true; real = 0; imag = 0; polar = false; } Complex::Complex (double r, double i) /* costruisce un numero complesso in rappresentazione cartesiana, data parte reale e immaginaria, e privo di coordinate polari */ { real = r; imag = i; //devo annotare che ho solo le coordinate cartesiane cartesian = true; polar = false; }

double Complex::getReal ()/* Calcola la parte reale */{ //se la parte reale manca prima la calcola if (cartesian == false) calculateCartesian (); return real;}

double Complex::getImag ()/* Calcola la parte immaginaria */{ //se la parte immaginaria manca prima la calcola if (cartesian == false) calculateCartesian (); return imag;}

double Complex::getMag ()/* Calcola la norma */{//se la norma manca prima la calcola if (polar == false) calculatePolar (); return mag;}

double Complex::getTheta ()/* Calcola l’angolo */

62

{ //se l’angolo manca prima lo calcola if (polar == false) calculatePolar (); return theta;}

/* Calcola le coordinate cartesiane a partire dalle polari */void Complex::calculateCartesian (){ real = mag * cos (theta); imag = mag * sin (theta); cartesian = true;}

/* Calcola le coordinate polari a partire dalle cartesiani */void Complex::calculatePolar (){double pi=3.14159265; mag = sqrt(real*real + imag*imag); if (mag==0) theta = 0; else if (imag>0) theta = acos(real/mag); else //imag<=0 theta = 2*pi-acos(real/mag); polar = true;}

void Complex::printCartesian (){//se mancano le coordinate cartesiane prima le calcola if (cartesian == false) calculateCartesian (); cout << getReal() << " + " << getImag() << "i" << endl;}

void Complex::printPolar (){//se mancano le coordinate polari prima le calcola if (polar == false) calculatePolar (); cout << getMag() << " e^ " << getTheta() << "i" << endl;}

void Complex::setPolar (double m, double t){ mag = m; theta = t; cartesian = false; polar = true;}

/* Definizione di addizione e moltiplicazione.

63

Siamo liberi di usare la rappresentazione dei complessi che preferiamo, senza preoccuparci di come viene ottenuta. */

Complex add (Complex& a, Complex& b){ double real = a.getReal() + b.getReal(); double imag = a.getImag() + b.getImag(); Complex sum (real, imag); return sum;}

Complex mult (Complex& a, Complex& b){ double mag = a.getMag() * b.getMag(); double theta = a.getTheta() + b.getTheta(); Complex product; product.setPolar (mag, theta); return product;}

/* Sperimentazione della classe Complex. */int main(){cout << "----------------------------" << endl;

cout << "Capitolo 14.5. Prova funzioni di stampa" << endl;cout << "stampa di Complex c0 (17.0, -6.0)" << endl;Complex c0 (17.0, -6.0);c0.printCartesian();cout << "versione in coordinate polari" << endl;c0.printPolar();cout << "stampa di Complex c1 (2.0, 3.0)" << endl;Complex c1 (2.0, 3.0);c1.printCartesian();cout << "versione in coordinate polari" << endl;c1.printPolar();cout << "----------------------------" << endl;

cout << "Capitolo 14.6. Prova funzione di somma" << endl;cout << "somma di Complex c1 (2.0, 3.0) e Complex c2(3.0, 4.0)" << endl;Complex c2 (3.0, 4.0);Complex sum = add (c1, c2);sum.printCartesian();cout << "versione in coordinate polari" << endl;sum.printPolar();cout << "----------------------------" << endl;

64

cout << "Capitolo 14.7. Prova funzione di prodotto" << endl;cout << "prodotto di Complex c1 (2.0, 3.0) e Complex c2(3.0, 4.0)" << endl;Complex product = mult (c1, c2);product.printCartesian();cout << "versione in coordinate polari" << endl;product.printPolar();cout << "----------------------------" << endl;system("pause");}

65

Lezione 09. Seconda ora. Utilizzate la classe Complex vista a lezione per:

Esercizio 1. Scrivere una funzione Complex root(Complex c, int n)

che dato un numero complesso e un intero n>0 calcola la radice n-esima canonica di c. Suggerimento. La norma (magnitudo) della radice n-esima di c è la radice reale n-esima della magnitudo. L’angolo della radice n-esima di c è /n, dove è l’angolo di c.

Esercizio 2. Scrivere una funzione void stampa_radici_unita(int n);

che dato un intero n>0 stampa le n radici dell’unità. Suggerimento. Sia i = 0, …, n-1. La radice i-esima dell’unità ha norma 1 e angolo (2/n)*i.

66

/* Soluzioni esercizi Lezione 09. Dovete aggiungere queste funzioni prima del main nel programma visto a lezione perche’ si possano compilare. */

Complex root(Complex c, int n) //n>0{ double mag = pow(c.getMag(),1./n); double theta = c.getTheta()/n; Complex result; result.setPolar (mag, theta); return result;}

void stampa_radici_unita(int n) //n>0{double pi= 3.14156592; for(int i=0;i<n;++i) { double mag = 1; double theta = 2*pi*i/n; Complex unita; unita.setPolar (mag, theta); cout << "radice n." << i << "\t"; unita.printCartesian(); }}

/* Controllo esercizi Lezione 09. Dovete aggiungere queste righe all’interno del main del programma visto a lezione per sperimentare le funzioni appena definite. */

cout << "Prova funzione root" << endl;cout << "radice quadrata di c (0., 1.)" << endl;Complex c(0., 1.);Complex result = root (c,2);result.printCartesian();cout << "versione in coordinate polari" << endl;result.printPolar();cout << "----------------------------" << endl;

int n=8;cout << "Stampa radici " << n << "-esime unita: " << endl;stampa_radici_unita(n);system("pause");

67

Lezione 10: Invarianti, Precondizioni e Postcondizioni (Cap. 14.8, 14.9 del libro di testo: conclusione)

Riprendiamo la descrizione della classe Complex vista nella Lezione 09. La descrizione dei numeri complessi consente allo stesso numero di venire rappresentato in due modi diversi, con coordinate cartesiane e con coordinate polari. Perché la rappresentazione sia sensata, occorre essere sicuri di quanto segue: “ogni numero costruibile con le operazioni della classe ha almeno una rappresentazione, e quando un numero ha due rappresentazioni, allora le due rappresentazioni siano dello stesso numero”.

In questo caso non è difficile controllare che le cose stanno davvero così, purchè i costruttori della classe Complex costruiscono solo numeri con almeno una rappresentazione. Tutte le funzioni pubbliche della classe Complex trasformano un numero con una rappresentazione oppure due rappresentazioni consistenti, in un altro numero con la stessa proprietà. Dunque se utilizzo un numero qualunque di volte le funzioni della classe Complex ottengo o numeri con una rappresentazione oppure due consistenti tra loro. Un programma può agire su un numero complesso solo usando le funzioni pubbliche della classe, quindi può solo produrre numeri con rappresentazioni consistenti.

Queste proprietà dei dati che si mantengono vere in una qualsiasi esecuzione del programma vengono dette invarianti. Gli invarianti vengono utilizzati quando appare necessario provare in modo preciso che un programma non produrrà mai un errore di un certo tipo. Altri due enunciati utilizzati per lo stesso scopo sono le precondizioni e le post-condizioni. La precondizione è una richiesta sui dati in ingresso a una funzione. Per esempio la funzione

double pot(double x, int n) //PRECONDIZIONE: n>=0 {int i; double ris; for(i=0, ris=1;i<n;++i) {ris = ris*x;} return ris;} //POST-CONDIZIONE: pow(x,n) = xn

ha come precondizione (n>=0). Infatti pot(x,n) calcola xn, ma solo quando n>=0: pot(10,-1), invece, restituisce 1, un risultato errato. La post-condizione descrive il risultato di una funzione quando i dati in ingresso soddisfano la precondizione. In questo

68

caso la post-condizione ci dice che pot(x,n) = xn. Questa condizione vale se n>=0. Il ciclo for che esegue il calcolo di pot(x,n), invece, ha il seguente invariante: all’inizio di ogni esecuzione del corpo {ris = ris*x;} del ciclo, ris contiene xi. Questa proprietà può esser usata per descrivere il comportamento del ciclo e provare che alla fine di esso, quando i=n, ris contiene xn.

Invarianti, precondizioni e post-condizioni prendono il nome collettivo di asserzioni. Idealmente le asserzioni sono pensate per essere controllate con un ragionamento, ma quasi sempre questa attività risulta essere troppo lunga e faticosa, a causa dell’enorme numero di dettagli presenti anche nei programmi più semplici. Tuttavia è possibile fare controlli empirici, inserendo all’inizio di una funzione un comando assert(precond); dove precond traduce la precondizione della funzione nel linguaggio C++. È anche possibile aggiungere, alla fine della definizione di una funzione, assert(postcond); dove postcond traduce la postcondizione della funzione nel linguaggio C++. Eseguendo un numero finito di volte la funzione possiamo scoprire alcuni errori: quando la precondizione o la post-condizione risulta falsa il programma si ferma e otteniamo un messaggio di errore. Questo approccio empirico, e molti altri approcci che esistono equivalenti ad esso, non garantiscono di trovare tutti gli errori, ma rappresentano un buon controllo. Non utilizzeremo sistematicamente questo metodo, che è comunque complesso, ma accenniamo alla sua esistenza.

Per esempio, possiamo scrivere il seguente programma per controllare precondizione, post-condizione e invariante della potenza:

/* Lezione 10. Prima ora. Invariante, pre-condizione e post-condizione della funzione xn */#include <iostream> /* per il cout */#include <stdlib.h> /* per il system("pause") */#include <cmath> /* per sin, cos */#include <assert.h> /* per il comando assert */using namespace std; /* per abbreviare il cout */

69

double pot(double x, int n) //PRECONDIZIONE: n>=0 {int i; double ris; assert(n>=0); cout << "INIZIO CICLO FOR" << endl; for(i=0, ris=1;i<n;++i) /* Stampiamo a ogni passo I valori di i, ris perverificare l’invariante (ris = xi) */ {cout << "i = " << i << " ris = " << ris << endl; ris = ris*x;} cout << "FINE CICLO FOR" << endl; cout << "i = " << i << " ris = " << ris << endl; return ris;} //POST-CONDIZIONE: pow(x,n) = xn

int main(){cout << "Stampiamo il calcolo di pot(10,3) per verificare l’invariante del ciclo for" << endl; cout << "pot(10,3) = " << pot(10,3) << endl; cout << "Se facciamo eseguire pot(10,-1), l’asserzione n>=0 fallisce e blocca il programma" << endl; // cout << "pot(10,3) = " << pot(10,3) << endl; system("pause");}

Lezione 10. Seconda ora. Esercizio 1. Riprendete la classe Complex. Provate ad aggiungere: assert(polar == true) all’inizio di CalculateCartesian() e assert(cartesian == true) all’inizio di CalculatePolar(). Si tratta di precondizioni per le due funzioni. Infatti per calcolare le coordinate cartesiane a partire da quelle polari occurre che le coordinate polari esistano, e dunque che (polar == true). Per calcolare le coordinate polari a partire da quelle cartesiani occurre che le coordinate cartesiane esistano, e dunque che (cartesian == true). Provate a eseguire diversi esempi e verificate che il programma non segnala mai che l’asserzione viene violata: infatti le funzioni pubbliche della classe Complex utilizzano CalculateCartesian() solo quando non ci sono coordinate cartesiane, e quindi ci sono coordinate polari, e utilizzano CalculatePolar() solo quando non ci sono coordinate polari, e quindi ci sono coordinate cartesiane.

70

Esercizio 2. Provate poi ad aggiungere deliberatamente una funzione errata alla classe:

void printCartesianPolar() //stampa delle due rappresentazioni { calculateCartesian(); calculatePolar(); cout << getReal() << " + " << getImag() << "i" << endl; cout << getMag() << " e^ " << getTheta() << "i" << endl; }

Trovate un caso in cui un programma si blocca e segnala che l’asserzione che fa da precondizione non è stata rispettata.

Esercizio 3. Controllate empiricamente la verità dell’invariante: “ogni numero complesso viene rappresentato in coordinate cartesiane o polari o entrambe”. Questa asserzione si scrive in C++ come segue: ((cartesian == true) || (polar == true)). Controllate che questo invariante può diventare falso in qualche programma se si usa un costruttore:

Complex::Complex() /* costruisce un numero complesso banale */{ cartesian = false; polar = false; }

Se invece si usa:

Complex::Complex() /* costruisce lo zero */{ cartesian = true; real = 0; imag = 0; polar = false; }

allora l’invariante resta sempre vero. Per controllare l’invariante, aggiungete dentro ogni definizione di funzione, alla fine, il controllo assert(invariante); e provate a eseguire diversi programmi.

71

Lezione 10. Soluzioni. Inseriamo le asserzioni per le pre-condizioni, post-condizioni e invarianti richiesti nella classe Complex della lezione 09. Verifichiamo che se utilizziamo solo costruttori che producono complessi ben definiti, e se correggiamo opportunamente la funzione che stampa sia la rappresentazione cartesiana che quella polare, allora le asserzioni non segnalano errori.

/* Lezione 10. L'uso di asserzioni */#include <iostream> /* per il cout */#include <stdlib.h> /* per il system("pause") */#include <cmath> /* per sin, cos */#include <assert.h> /* per il comando assert */using namespace std; /* per abbreviare il cout */

class Complex{ //rappresentazione di un numero complesso c

private: double real, imag; // rappresentazione cartesiana (quando usata) double mag, theta; // rappresentazione polare (quando usata) bool cartesian; // se cartesian = vero allora c=(real,imag) bool polar; // se polar = vero allora c=(mag, theta) void Complex::calculateCartesian(); // aggiorna co. cartesiane void Complex::calculatePolar(); // aggiorna co. cartesiane public: Complex::Complex (); // costruisce un complesso "indefinito" Complex (double re, double im); // costruisce complesso (re+im*i) void Complex::setPolar(double m, double t);// assegna co. polari double Complex::getReal (); // parte reale double Complex::getImag (); // parte immaginaria double Complex::getMag (); // norma double Complex::getTheta (); // angolo void Complex::printCartesian (); // stampa co. cartesiane void Complex::printPolar (); // stampa co. polari void Complex::printCartesianPolar(); //stampa delle due rappresentazioni }; //non dimenticate il punto e virgola

//Complex::Complex() /* costruisce un numero complesso privo di rappresentazione e quindi privo di valore *///{ cartesian = false; polar = false; }

72

Complex::Complex() /* costruisce un numero complesso banale, lo zero */ { cartesian = true; polar = false; real = 0; imag = 0; assert((cartesian == true) || (polar == true)); }

Complex::Complex (double r, double i) /* costruisce un numero complesso in rappresentazione cartesiana, data parte reale e immaginaria, e privo di coordinate polari */ { real = r; imag = i; cartesian = true; polar = false; assert((cartesian == true) || (polar == true));}

double Complex::getReal ()/* Calcola la parte reale */{ //se la parte reale manca prima la calcola if (cartesian == false) calculateCartesian (); assert((cartesian == true) || (polar == true)); return real;}

double Complex::getImag ()/* Calcola la parte immaginaria */{ //se la parte immaginaria manca prima la calcola if (cartesian == false) calculateCartesian (); assert((cartesian == true) || (polar == true)); return imag;}

double Complex::getMag ()/* Calcola la norma */{ //se la norma manca prima la calcola if (polar == false) calculatePolar (); assert((cartesian == true) || (polar == true)); return mag;}

double Complex::getTheta ()/* Calcola l'angolo */{ //se l'angolo manca prima lo calcola if (polar == false) calculatePolar (); assert((cartesian == true) || (polar == true)); return theta;

73

}

void Complex::calculateCartesian (){assert(polar==true); real = mag * cos (theta); imag = mag * sin (theta); cartesian = true; assert((cartesian == true) || (polar == true));}

void Complex::calculatePolar (){assert(cartesian==true); double pi=3.14159265; mag = sqrt(real*real + imag*imag); if (mag==0) theta = 0; else if (imag>0) theta = acos(real/mag); else //imag<=0 theta = 2*pi-acos(real/mag); polar = true; assert((cartesian == true) || (polar == true));}

void Complex::printCartesian (){ if (cartesian == false) calculateCartesian (); cout << getReal() << " + " << getImag() << "i" << endl; assert((cartesian == true) || (polar == true));}

void Complex::printPolar (){ if (polar == false) calculatePolar (); cout << getMag() << " e^ " << getTheta() << "i" << endl; assert((cartesian == true) || (polar == true));}

void Complex::setPolar (double m, double t){ mag = m; theta = t; cartesian = false; polar = true; assert((cartesian == true) || (polar == true));}

74

Complex add (Complex& a, Complex& b){ double real = a.getReal() + b.getReal(); double imag = a.getImag() + b.getImag(); Complex sum (real, imag); return sum;}

Complex mult (Complex& a, Complex& b){ double mag = a.getMag() * b.getMag(); double theta = a.getTheta() + b.getTheta(); Complex product; product.setPolar (mag, theta); return product;}

Complex root(Complex c, int n) //n>0{ double mag = pow(c.getMag(),1./n); double theta = c.getTheta()/n; Complex result; result.setPolar (mag, theta); return result;}

void stampa_radici_unita(int n) //n>0{double pi= 3.14156592; for(int i=0;i<n;++i) { double mag = 1; double theta = 2*pi*i/n; Complex unita; unita.setPolar (mag, theta); cout << "radice n." << i << "\t"; unita.printCartesian(); }}

/* VERSIONE ERRATA void Complex::printCartesianPolar() //stampa delle due rappresentazioni { calculateCartesian(); calculatePolar(); cout << getReal() << " + " << getImag() << "i" << endl;

75

cout << getMag() << " e^ " << getTheta() << "i" << endl; assert((cartesian == true) || (polar == true)); } */

void Complex::printCartesianPolar() //stampa delle due rappresentazioni { if (cartesian==false) calculateCartesian(); if (polar==false) calculatePolar(); cout << getReal() << " + " << getImag() << "i" << endl; cout << getMag() << " e^ " << getTheta() << "i" << endl; assert((cartesian == true) || (polar == true)); }

int main(){cout << "----------------------------" << endl;cout << "Capitolo 14.5. Prova funzioni di stampa" << endl;cout << "stampa di Complex c0 (17.0, -6.0)" << endl;Complex c0 (17.0, -6.0);c0.printCartesian();cout << "versione in coordinate polari" << endl;c0.printPolar();cout << "stampa di Complex c1 (2.0, 3.0)" << endl;Complex c1 (2.0, 3.0);c1.printCartesian();cout << "versione in coordinate polari" << endl;c1.printPolar();cout << "----------------------------" << endl;

cout << "Capitolo 14.6. Prova funzione di somma" << endl;cout << "somma di Complex c1 (2.0, 3.0) e Complex c2(3.0, 4.0)" << endl;Complex c2 (3.0, 4.0);Complex sum = add (c1, c2);sum.printCartesian();cout << "versione in coordinate polari" << endl;sum.printPolar();cout << "----------------------------" << endl;

cout << "Capitolo 14.7. Prova funzione di prodotto" << endl;cout << "prodotto di Complex c1 (2.0, 3.0) e Complex c2(3.0, 4.0)" << endl;

76

Complex product = mult (c1, c2);product.printCartesian();cout << "versione in coordinate polari" << endl;product.printPolar();cout << "----------------------------" << endl;

cout << "Prova funzione root" << endl;cout << "radice quadrata di c (0., 1.)" << endl;Complex c(0., 1.);Complex result = root (c,2);result.printCartesian();cout << "versione in coordinate polari" << endl;result.printPolar();cout << "----------------------------" << endl;

int n=8;cout << "Stampa radici " << n << "-esime unita: " << endl;stampa_radici_unita(n);system("pause");

//Stampare un complesso non assegnato viola l'asserzione//per calculateCartesian, se il complesso non assegnato e' "indefinito"cout << "----------------------------" << endl;Complex C;cout << "C.printCartesian ();" << endl;C.printCartesian ();

//Stampare un complesso non assegnato viola l'asserzione//per calculateCartesian, se il complesso non assegnato e' "indefinito"cout << "----------------------------" << endl;Complex Zero(0.,0.);cout << "Zero.printCartesianPolar ();" << endl;Zero.printCartesianPolar ();system("pause");

}

77

Lezione 11: Esercizio: il Crivello di Eratostene

Il “Crivello di Eratostene” è un metodo per la generazione della successione dei numeri primi. Si trova facilmente su Internet e pertanto non lo descriviamo qui. In questa lezione vediamo una sua possibile implementazione. Più che ai numeri primi, siamo interessati alla rappresentazione di un crivello di Eratostene attraverso una struttura del C++.

Per ogni n2, chiamiamo “crivello di eratostene fino a n” la lista dei primi di valore n, disposti in ordine crescente. Possiamo rappresentare il crivello di eratostene fino a n con quattro dati:

un intero FineCrivello, che contiene n. il numero numero_primi dei primi n. un vettore Primi che contiene nelle posizioni da 0 al

numero_primi-1 tutti i numeri primi n, in ordine crescente. la lunghezza MaxCrivello del vettore Primi.

Il valore MaxCrivello esprime il massimo numero di primi che possiamo inserire nella nostra rappresentazione del crivello. Per ogni valore di MaxCrivello, i minimi valori degli altri parameri del crivello sono: FineCrivello = n = 2, e numero_primi = 1. In questo caso il crivello contiene tutti i primi 2, dunque un unico primo, proprio il 2: abbiamo Primi[0]=2. I posti da 1 fino a MaxCrivello-1 non sono (ancora) occupati. È facile dimostrare il seguente Criterio di Primalità: “se n è divisibile per qualche numero primo compreso tra 2 e n allora n è primo, altrimenti n è composto”. Questo consente di estendere il crivello di eratostene per n a quello per n+1 come segue: dividiamo n+1 per tutti i numeri primi (n+1) (stanno nel crivello). Se non troviamo divisori aggiungiamo n+1 al crivello, altrimenti no. In entrambi i casi rimpiazziamo n con n+1.

Stabilito un procedimento per estendere un crivello di un elemento, ripetendo il procedimento possiamo estendere il crivello a piacere, finché c’è spazio nel vettore Primi. Useremo il crivello di eratostene per calcolare: il numero (x) primi in [1,x], e il numero x/(x) degli interi per ogni primo in [1,x].

Suggerimenti. Definite una classe dei crivelli:

struct Crivello { //DATI O “CAMPI” DI UN CRIVELLO int MaxCrivello; //Il massimo di primi per quel crivello int FineCrivello; //Limitazione superiore ai primi gia’ inseriti int numero_primi; //Il numero dei primi già inserito vector<int> Primi; //Il vettore dei primi

78

//FUNZIONI DELLA CLASSE CRIVELLO Crivello::Crivello(int max);//Costruisce un crivello che contiene un solo numero primo il 2, e che ne puo’ contenere fino a max void Crivello::stampa(); //stampa tutti i dati: non usare per crivelli grandi! void Crivello::aggiungi_uno(); //estende FineCrivello di 1 void Crivello::riempi_fino_a(int x); //inserisce tutti i primi <=x, se c’e’ abbastanza spazio nel crivello};

Per aggiungere l’elemento n+1 a un crivello, controllate se n+1 ha divisori primi (n+1) usando un ciclo. Uscite dal ciclo non appena trovate un divisore primo di n+1, per risparmiare tempo. Questo effetto si può ottenere con un comando break; oppure usando una variabile booleana. Esempi di calcolo. Il numero dei numeri primi x si indica con (x). Usate un crivello per controllare che per x = 10, 100, 1000, 10 mila, …, 100 milioni il numero dei numeri primi tra 1 e x vale, rispettivamente: (x) = 4, 25, 168, 1.229, 9.592, 78.498, 664.579, 5.761.455.

Attenzione ai tempi di calcolo: il metodo proposto è lento, e richiede un tempo (quasi) proporzionale a x3/2, dunque un tempo che cresce di un fattore 103/2 (circa di 30 volte) ogni volta che moltiplichiamo x per 10. Con i computer attuali, e per programmi scritti bene, il caso x=10 milioni richiede circa 2-3 secondi di calcolo, e il caso x=100 milioni richiede circa 1 minuto di calcolo.

Verifica empirica del Teorema dei numeri primi. x/(x) è il numero degli interi per ogni primo nell’intervallo [1,x]. Il Teorema dei Numeri Primi afferma che il rapporto tra x/(x) e loge(x) tende a 1, per x che tende a infinito: ci sono circa loge(x) interi per ogni primo tra 1 e x. Calcolate x/(x) per x = 10, 100, 1000, …, 100 milioni e verificate empiricamente il Teorema.

79

/* Lezione 11: Soluzione "NUMERO DEGLI INTERI PER OGNI PRIMO" . */

#include <iostream> /* per il cout */#include <stdlib.h> /* per il system("pause") */#include <cmath> /* per sqrt eccetera */#include <vector> /* per i vettori */using namespace std; /* per abbreviare il cout */

struct Crivello { int MaxCrivello; //Il massimo di primi per quel crivello int FineCrivello; //Limitazione superiore ai primi gia’ inseriti int numero_primi; //Il numero dei primi già inserito vector<int> Primi; //Il vettore dei primi Crivello::Crivello(int max); //Costruisce un crivello che contiene un solo numero primo, il 2, e che ne puo’ contenere fino a max void Crivello::stampa(); //stampa tutti i dati: non usare per crivelli grandi! void Crivello::aggiungi_uno(); //estende FineCrivello di 1 void Crivello::riempi_fino_a(int x); //inserisce tutti i primi <=x se c’e’ abbastanza spazio nel crivello};

Crivello::Crivello(int max){ MaxCrivello = max; FineCrivello = 2; numero_primi = 1; vector<int> temp(MaxCrivello,0); Primi = temp; Primi[0] = 2; }

void Crivello::stampa()//stampa Primi[0],…,Primi[x] e commenta{cout << "FineCrivello = " << FineCrivello << endl; cout << "MaxCrivello = " << MaxCrivello << endl; cout << "numero_primi = " << numero_primi << endl; int i; for(i=0; i<numero_primi; i++) {cout << "Primi[" << i << "]=\t" << Primi[i] << endl;}}

80

void Crivello::aggiungi_uno(){++FineCrivello; int p = FineCrivello; int i; int sqrtp = floor(sqrt(p)); for(i=0; Primi[i]<=sqrtp ;++i) {if (p%Primi[i] == 0) {break;}} if (Primi[i] > sqrtp) //non ci sono divisori primi <=sqrtp {Primi[numero_primi]=p; ++numero_primi;}}

void Crivello::riempi_fino_a(int x){while ((numero_primi < MaxCrivello) && (FineCrivello < x)) aggiungi_uno();}

int main(){int i, x; //Crivello con 1 primo cout << "Stampa valore iniziale di crivello"<<endl<<endl; Crivello crivello(100); crivello.stampa(); system("pause"); system("CLS");

//Crivello con 2 primi cout << "Stampa crivello con un secondo elemento" <<endl<<endl; crivello.aggiungi_uno(); crivello.stampa(); system("pause"); system("CLS");

//Crivello dei primi <= 100 cout << "Stampa crivello dei primi <=100" <<endl<<endl; crivello.riempi_fino_a(100); crivello.stampa(); system("pause"); system("CLS");

//Confronto di pi(x) e x/pi(x) con i valori previsti dalla teoria cout << "Calcolo di pi(x), x/pi(x) e di log_e(x)"<<endl<<endl; int numerozeri=8, MaxPrimi = 10000000; Crivello crivello2(MaxPrimi); vector<double> xp(numerozeri+1);/* stampo pi(x) e x/pi(x) per x = 10, 100, 1000, …, 100 milioni. Uso il comando “showpoint” per stampare le cifre decimali anche se uguali a zero */ for( i=1,x=10; i<=numerozeri; i=i+1,x=x*10) {crivello2.riempi_fino_a(x);

81

int p = crivello2.numero_primi; xp[i] = ((double) x)/p; cout << " x=" << x << " e pi(x)=" << p << " e x/pi(x) = " << showpoint << xp[i] << " e log(x) = " << log(x) << endl;}

cout << endl << "Incremento di x/pi(x) previsto se moltiplico x per 10:" << " log_e(10) = " << log(10) <<endl<<endl; for( i=1, x=10; i<=numerozeri-1; i=i+1, x=x*10) {cout << " tra " << x << " e " << x*10 << " = " << xp[i+1]-xp[i] << endl;} system("pause"); system("CLS");}

82

Lezione 12: Esercizio di EsameIl programma “Demoni”di David Griffeath

Dovete preparare questo esercizio per l’esame, ed essere pronti a spiegare le scelte fatte e a confrontarle con le idee introdotte durante il corso. Questo esercizio utilizza le matrici. Per risolverlo occorre prima istallare la libreria graphics.h e aggiungere una riga alla “Linker Command Line” (vedi la spiegazione all’ultima pagina del diario). Per imparare a usare graphics.h leggete tutto il “Manuale minimo di grafica” in append (sono due pagine). Le spiegazioni sugli automi cellulari ciclici fanno riferimento alla voce di Wikipedia:

http://en.wikipedia.org/wiki/Cyclic_cellular_automaton

Descrizione del programma. Gli automi di Von Neumann sono rappresentazioni (molto semplificate, ma interessanti in linea di principio) della capacita’ di auto-organizzazione della materia e della vita. Vogliamo scrivere un programma che simuli l’evoluzione di un tipo di automi di Von Neumann, chiamati “ciclici” dagli specialisti, fino a uno stadio in cui gli automi ciclici si auto-organizzano in forme auto-replicanti dette comunemente “demoni”. Si intende qui “demone” nel senso informatico di “sottoprogramma privo di padrone, autonomo” e non nel senso di “spirito del male”.

Gli automi “ciclici” sono stato definiti dal matematico David Griffeath, e quindi resi popolari dall’informatico Alexander Dewdney sulla rivista “Scientific American” nell’Agosto 1989. Iniziamo con una scacchiera con NxM celle, dette “automi”, ognuna contenente un numero intero c=0, …, NCOL-1, detto “stato dell’automa”. Ogni numero viene detto “colore” e viene rappresentato da un diverso colore. Ecco un esempio di matrice 2x2 con NCOL=4. I numeri 0,1,2,3 rappresentano quattro colori:

|0|1||3|2|

Ad ogni passo, prendiamo la cella di coordinate (i,j), contenente il numero c1, quindi guardiamo le 4 celle adiacenti, a distanza 1 in orizzontale oppure a distanza 1 in verticale. Definiamo la “distanza 1” ciclicamente: la prima e l’ultima riga e la prima e l’ultima colonna sono considerate contigue. Se una almeno di queste 4 celle contigue contiene un numero c2 = c1+1 contiguo a c1 (di nuovo ciclicamente: dopo NCOL-1 viene 0), allora la cella (i,j) riceve il numero c2 nel passo successivo. Altrimenti (i,j) mantiene il numero c1 nel passo successivo. Definiamo in questo modo una successione infinita di matrici di colori. Vediamo come

http://en.wikipedia.org/wiki/Cyclic_cellular_automaton

83

esempio una matrice 2x2, con NCOL=4, che contiene inizialmente i numeri 0,1,2,3:

|0|1| -> |1|2| -> |2|3| -> |3|0| -> |0|1| -> …|3|2| |0|3| |1|0| |2|1| |3|2| …

Ogni numero è adiacente a un numero consecutivo, quindi a ogni passo ogni numero è incrementato di 1 (ciclicamente: 3 diventa 0). Notiamo che la trasformazione è ciclica: alla fine riotteniamo la matrice di partenza. L’aspetto più importante della definizione di questi automi è che le NxM celle modificano (o non modificano) il numero in esse contenuto simultaneamente: ad ogni passo definiamo quindi ogni numero della nuova matrice NxM a partire dai numeri contenuti nella precedente matrice NxM. Le diverse fasi dell’evoluzione degli automi ciclici. L’auto-organizzazione degli automi passa, con probabilita’ quasi uguale a 1, attraverso 3 o 4 stadi diversi.

1. (Veste di arlecchino) All’inizio, i colori sono distribuiti in un modo puramente casuale, a veste di arlecchino.

2. (Macchie di colori uniformi) Man mano che il programma va avanti, alcune celle ricevono il colore delle celle vicine, e si formano in questo modo macchie di colore uniforme, la maggior parte molto piccole, ma alcune molto grandi.

3. (Macchie di colori ad arcobaleno) Alcune macchie crescono di dimensione fino a incontrare un colore più forte. A questo punto il colore più forte genera un’onda di colore uniforme che copre la macchia con il nuovo colore. A volte una seconda onda con un colore ancora più forte si genera prima che si sia esaurita la prima. Questo capita più e più volte, finche’ le macchie più grandi sono stabilmente percorse da onde di colori “ad arcobaleno”, che contengono i vari colori presi nell’ordine ciclico:

|3|3|3|3||2|2|2|2||1|1|1|1||0|0|0|0|

4. (Spirali cicliche o “demoni”) L’ultimo stadio nell’evoluzione degli automi si ha quando l’urto tra onde di colori crea un insieme di celle vicine, in cui ogni cella è adiacente a una cella dal colore più forte dello stesso insieme. Per esempio, con 4 colori potremmo avere un quadrato di 4 celle con i 4 colori disposti consecutivamente, l’ultimo seguito dal primo.

| | | | || |0|1| || |3|2| || | | | |

84

In base alle regole scelte, a ogni passo ogni colore del quadrato viene sostituito dal colore successivo, per sempre. L’effetto è vedere i quattro colori ruotare senza fine. Questo quadrato (quasi invisibile nell’intrico del disegno) rappresenta il nocciolo di un “demone”. Ruotando, questi quattro colori emettono onde di colori che contemporaneamente si estendono e ruotano su se stesse. La somma di questi due movimenti ci fa’ si che queste onde di colori ci appaiono come spirali multicolori in crescita, cosi’:

|0|1|2|3|2|1| |1|2|3|0|3|2| |2|3|0|1|0|3||1|2|3|2|1|0||0|1|2|1|0|3||3|0|1|0|3|2|

Alla fine le spirali si estendono a tutto lo schermo, dividendosi il territorio. Da questo momento in poi non capita più nulla di nuovo: le spirali continuano a ruotare per sempre, ciascuna nel suo territorio.

Ognuna di queste spirale o “demone” ha qualcosa in comune con una colonia di esseri viventi: è in grado di crescere senza fine inglobando (quasi) tutto il materiale circostante. Ecco un’immagine dell’evoluzione degli automi, dove ogni colore della matrice è rappresentato da un quadratino colorato dello schermo. In questa particolare matrice compaiono simultaneamente tutti gli stadi dell’evoluzione, dai gruppi di colori casuali alle spirali o “demoni”, passando per le macchie di colori percorse da onde ad arcobaleno:

L’evoluzione dai colori casuali ai “demoni” è molto probabile ma non certa. Quando gli automi sono pochi, a volte capita che una

Spirale auto-accrescente o “demone” (nel senso informatico di “sottoprogramma privo di padroni”)

Grandi macchie di colore percorse da onde “ad arcobaleno”

Piccole macchie a “vestito di arlecchino”

http://upload.wikimedia.org/wikipedia/commons/a/a

85

macchia uniforme colonizzi tutto lo schermo. A questo punto l’evoluzione si blocca e non nascono mai i demoni. Quando gli automi sono pochissimi, l’evoluzione si puo’ bloccare ancora prima, nello stadio dei colori casuali divisi in piccole macchie sparse, e lo stadio delle grandi macchie uniformi non arriva mai.

Dettagli sul programma: la rappresentazione degli automi. Per scomporre meglio il programma in parti indipendenti, mantenete ben distinta la matrice degli automi, che contiene interi da 0 a NCOL-1 (“numeri” e non “colori” e neppure “quadrati”), dal suo disegno sullo schermo. La matrice degli automi è fatta di NxM “celle” di numeri, di dimensione 1x1. Il suo disegno è fatto di NxM quadrati di diverso colore, ciascuno di dimensione LxL (con un lato L>0 a piacere). Utilizziamo una finestra grafica di base N*L e altezza M*L.

origine O base N*L *--------------> asse X

| | | | | | | | altezza M*L | | | | | | | | (Disegno delle celle colorate) | | | | | | | |

V asse Y

Come si è detto, ogni numero 0, …, NCOL-1 viene rappresentato da un colore distinto. Se manteniamo ben distinta la matrice di interi dal suo disegno, allora la scelta del lato L>0 di ogni quadrato, e la scelta dei colori associati ai numeri 0,…,NCOL-1 influenzano il disegno, ma non influenzano in alcun modo il resto del programma, che dipende solo dalla matrice NxM di di interi da 0 a NCOL-1.

Esempio: due trasformazioni, da una matrice di NxM interi, ad un’altra matrice sempre di NxM interi. Consideriamo 2x2 celle (da (0,0) a (1,1)) e 4 interi (da 0 a 3); 3x3 celle (da (0,0) a (2,2)) e 9 interi (da 0 a 8):

|0|1| -> |1|2| 4 interi:0,1,2,3, ognuno adiacente |3|2| |0|3| al successivo in senso orario: la cella (0,0) è adiacente alla cella (1,0) che è adiacente alla cella (1,1) … |0|8|1| -> |1|0|2| 9 interi:0,…,9, ognuno adiacente |4|6|5| |5|7|6| al successivo, ma solo se si tiene conto che |3|7|2| |4|8|3| la prima e l’ultima riga e la prima e ultima colonna sono adiacenti: solo tenendo conto di questo, abbiamo che la cella (0,0) è adiacente a (2,0) che è adiacente a (2,2) … Il comando swapbuffers(). Tutto cio’ che disegnamo dopo un comando swapbuffers(); non viene copiato sullo schermo fino al comando swapbuffers(); successivo. Per ragioni di efficienza, dobbiamo utilizzare un comando swapbuffers(); una volta all’inizio del programma, e poi ogni volta dopo aver terminato il disegno

86

della matrice dei colori degli NxM automi. Questo ci fa risparmiare NxM aggiornamenti dello schermo: per disegnare una matrice di NxM colori, infatti, dobbiamo disegnare NxM quadratini, uno per cella, aggiornando ogni volta lo schermo. Usando swapbuffers(), invece, facciamo un solo aggiornamento dello schermo ogni NxM cambiamenti di colore di celle.

Le due matrici dei colori degli NxM automi: la “matrice visibile” e la “matrice attiva”. Presa alla lettera, la definizione degli automi ciclici prevede di usare tante matrici quanti sono gli aggiornamenti delle celle: nel passo t=0 abbiamo una matrice NxM indefinita, nel passo t=1 una matrice NxM con colori casuali, nel passo t=2 una matrice con colori calcolati in base alle regole di Griffeath, eccetera. Per risparmiare spazio di memoria, invece, noi useremo due sole matrici NxM di colori: A[0] e A[1], rappresentate da una sola matrice A di dimensioni 2xNxM. Nel passo numero t, lo stato numero t degli automi si trova sullo schermo e in A[0]. Lo stato t+1 si trova in A[1], e non è visibile. Nel passo numero 0, A[0] non è assegnata: disegnata produce uno schermo nero (o una qualunque altra cosa). A[1], detta “matrice attiva”, è la prossima matrice che intendiamo disegnare: viene assegnata a caso, e contiene lo stato 1 degli automi, come segue.

Matrice A[0] (visibile) Matrice A[1] (attiva) ---------------- ---------------stato 0 | ************** | | |0|1| | stato 1 schermo | ************** | | |3|2| | colori a casonero ---------------- --------------- Le matrici A[0] e A[1] si scambiano continuamente di ruolo.

Tra il passo 0 e il passo 1. Disegnamo sullo schermo lo stato 1 che si trova in A[1], quindi assegnamo lo stato numero 2 a ognuno degli NxM automi alla matrice A[0], a partire dagli stati numero 1 dei colori contenuti in A[1] e usando le regole di Griffeath. A questo punto le due matrici si scambiano i ruoli: A[1] è visible, A[0] è attiva, come segue.

Matrice A[0] (attiva) Matrice A[1] (visibile) ---------------- ---------------stato 2 | |1|2| | | |0|1| | stato 1 | |0|3| | | |3|2| | ---------------- ---------------

Tra il passo 1 e il passo 2: disegnamo A[0], quindi a partire da A[0] definiamo gli stati numero 3 per A[1], usando le regole di Griffeath. Scambiamo matrice attiva e visibile.

L’invariante del ciclo for che aggiorna gli automi è quindi la seguente proprietà: nel passo numero t,

87

“ (Inv) A[matr_vis] è visibile sullo schermo, e contiene lo stato numero t degli automi. A[matr_act] contiene lo stato numero t+1”.

Una lista di costanti e variabili globali necessarie a implementare i “Demoni”. Per ora limitatevi a copiarle: l’uso di ogni nome sara’ chiarito in seguito. Per ridurre lo spazio di memoria necessario, le matrici saranno di tipo short degli interi da 0 a 255. Il tipo short occupa un solo byte di memoria, mentre il tipo int che siamo abituati a usare ne occupa quattro.

//i valori iniziali dei parametri possono essere cambiati const int N = 100; // number of automata in the baseconst int M = 100; // number of automata in the heightconst int NCOL= 12; // Number of colors of the automataconst int MAX = 1000;//Maximum number of updating of the automataconst int L = 10; //base and height of an automata in the screen

//Class for the cellar automata in matr_vis and in matr_actstruct Cells{short A[2][N][M]; int matr_vis, matr_act;/* One matrix 2xNxM of type “short”, representing 2 matrices NxM: A[0], A[1] Two integers:

matr_vis=0 and matr_act=1, or matr_vis=1 and matr_act=2. A[matr_vis] is the visible matrix. A[matr_act] is the active matrix. A[matr_vis][i][j] is the current number visible in the cell (i,j) A[matr_act][i][j] is the next number visible in the cell (i,j) */ vector<int> colors;//a vector of colors representing each number 0, 1, …, NCOL-1};

Funzioni da aggiungere alla classe Cells. Scomponiamo l’esercizio in esercizi più semplici, ciascuno risolto da una funzione: la funzione random, 7 funzioni da aggiungere alla classe Cells, più il main. Includiamo nelle precondizioni di ogni funzione che A[matr_vis] sia la matrice visibile e A[matr_act] la matrice attiva. A ogni passo, lo stato del programma consiste in:

1. due matrici A={A[0],A[1]} ciascuna contenente dei colori per NxM automi per la matrice 0 e la matrice 1.

2. due indici matr_vis, matr_act con il numero della “matrice visibile” e della “matrice attiva”. Uno di questi numeri è 0 e l’altro è 1, e si scambiano in continuazione di ruolo.

3. Lo stato della finestra grafica.

Ricordate cosa dice l’invariante (Inv): “A[matr_vis] contiene i colori dello stato t degli NxM automi, visibili sullo schermo, mentre A[matr_act] contiene i colori dello stato t+1”. Una singola funzione può rendere falso l’invariante, ma l’invariante deve essere valido all’inizio e alla fine di ogni esecuzione del corpo del ciclo che disegna gli automi.

88

Funzione 0. La funzione int randomcolor(), che restituisce un colore a caso. Usa la funzion COLOR della libreria grafica, e la funzione rand() inclusa nella libreria cmath, che produce ad ogni chiamata un intero “casuale” tra 0 e 215-1 = 32767. Scrivete rand()%k per avere un numero casuale tra 0 e k-1. Sperimentate questa funzione disegnando diversi rettangoli di colore casuale, usando il comando della libreria grafica void bar(int left, int top, int right, int bottom);

Funzione 1 (inizializza il vettore colors). Definire una funzione void Cells::InitializeColor(); che inizializza il vettore colors dei colori con valori scelti a caso usando la funzione precedente, e lo assegna al campo colors della classe Cells.

Funzione 2 (inizializza la matrice A[matr_act]). Definire una funzione void Cells::InitializeData(); che assegna alle NxM celle della matrice A[matr_act] dei valori casuali tra 0 e NCOL-1, rappresentanti i colori di ogni cella. Per sperimentarla, fare stampare i numeri contenuti nelle NxM celle di A[matr_act]. La useremo nel passo 0 del calcolo.

Funzione 3 (inizializza i booleani matr_vis, matr_act). Definite un costruttore Cells::Cells(); della classe Cells che assegna ai campi matr_vis, matr_act i valori iniziali 0,1. Usatelo per costruire un oggetto di tipo Cells (dunque un rettangolo di dimensioni NxM di automi, tutti “non assegnati”).

Funzione 4 (disegna gli automi di A[matr_act]). Definite una funzione void Cells::Draw(); che disegna NxM quadrati di lato L. Ogni quadrato (i,j) ha il colore associato al numero A[matr_act][i][j]. Il colore associato a un numero si trova consultando il vettore colors della classe Cells. Usate le funzioni precedenti e la funzione di libreria void bar(int xl, int yl, int xr, int yr); che disegna un rettangolo di vertice superiore sinistro (xl,yl) e inferiore destro (xr,yr). Il colore del rettangolo si decide eseguendo prima setfillstyle(SOLID_FILL, col).

***Funzione 5. Definire una funzione void Cells::UpdateCell(int i, int j); che prenda la cella (i,j) della matrice A[matr_act], e scriva nella cella (i,j) della matrice A[matr_vis] il nuovo colore della cella, ottenuto applicando le regole di Griffeath: se una delle 4 celle adiacenti ha un colore di una unita’ maggiore di quello della cella (i,j), allora la cella (i,j) prende quel colore in A[matr_vis], altrimenti mantiene il proprio. Provate questa funzione sui cambiamenti di stato dati come esempio. La funzione 5 è il nocciolo del programma. Attenzione: una cella “adiacente” si intende a distanza 1 modulo N (per la coordinata x) oppure modulo M (per la coordinata y). Un colore è successivo a un altro se è maggiore di 1 modulo NCOL, dunque 0 è maggiore di NCOL-1. “a modulo b” si scrive a%b, ma solo quando a>=0. Evitate quindi

89

di scrivere (a-1)%b, perche’, quando a=0, l’espressione (-1)%b non è uguale a (-1 modulo b).

Funzione 6. Definire una funzione void Cells::UpdateMatrix(); che prenda lo stato degli automi descritto dalla matrice A[matr_act], e scriva il nuovo stato degli automi nella matrice A[matr_vis], usando la funzione UpdateCell.

Funzione 7. Definire una funzione void Cells::UpdateState(); che modifica lo stato corrente degli automi, grafica inclusa, nello stato successivo. Come precondizione della funzione, assumiamo l’invariante per il passo t: “la variabile globale matr_vis indica la matrice visibile, matr_act la matrice attiva, A[matr_vis] contiene i colori dello stato t ed è visibile sullo schermo, A[matr_act] contiene i colori dello stato t+1”. Come postcondizione della funzione richiediamo l’invariante per t+1.

Definite il main del programma “Demoni” usando tutte le funzioni precedenti. Ricordatevi di eseguire swapbuffers(); all’inizio del programma, e ogni volta che disegnate la scacchiera NxM degli automi. Ricorda che l’invariante deve essere vero all’inizio e alla fine del corpo del ciclo che disegna gli automi. Usate srand(time(NULL)); per inizializzare a caso le successioni pseudo-casuali di numeri colori costruite dalle funzioni rand() e randomcolor().

Confrontate il vostro eseguibile con:

http://www.di.unito.it/~stefano/C-CellarAutomata-2015.exe

http://www.di.unito.it/~stefano/C-CellarAutomata-2015.exe

90

/* Il programma "Demoni". Soluzioni */

#include <graphics.h>#include <iostream>#include <cmath>#include <iomanip>#include <time.h>#include <vector>using namespace std;

/*

THE PROGRAM "DEMONS" FOR CYCLIC CELLAR AUTOMATA BY DEWDNEY http://en.wikipedia.org/wiki/Cyclic_cellular_automaton We draw NxM square cells of base L with random colors 0, ..., NCOL-1. At each step, we take any cell (i,j) of color c1, then we look to the 4 cells up, left,right, down (cyclically: the first and last row are contiguous, the first and last column are contiguous). If any of these 4 cells has color c2 = c1+1 (again cyclically: after color NCOL-1 there is color 0), then cell (i,j) takes color c2 in the next step. Otherwise cell(i,j) keeps color c1 in the next step. All these transformations take place simultaneously. For instance:

|0|1| -> |1|2| 4 colors(0-3), each adiacent to the next one |3|2| |0|3| clockwise |0|8|1| -> |1|0|2| 9 colors (0-8), each adiacent to the next one |4|6|5| |5|7|6| provided we take first and last row adiacent,|3|7|2| |4|8|3| and first and last column adiacent

If we repeat these rules long enough, then, if N,M is large enough, the automata pass through 3 "evolutionary stages".

(1) Stage 1. A random color assignment, with no adiacent cells having consecutive colors.

(2) Large patches having a single color, or having "waves" of consecutive colors

(3) Ever-growing spirals including ciclically all colors.

91

If N, M are small then the automata never pass over stage 1. For medium values of N, M, the automata stop in stage 2, and eventually (almost) the entire board takes a single color. For large N, M, eventually all board is full of rotating spirals, repeating the same configurations with a cycle a length NCOL. If NCOL increases, it takes a larger number of automata to pass from stage 1 to stage 2, and an even larger number to pass from stage 2 to stage 3.

*/

/* WE USE ONE VISIBLE matrix AND ONE ACTIVE matrix:

matrix 0 (visible) matrix 1 (active) --------------- ---------------| | | next state || current state | | | --------------- --------------- swapbuffers(); //swap active and visible matrix / \ / \ / \ |_ _| matrix 0 (active) matrix 1 (visible) --------------- ---------------| automata | | automata || state 1 | | state 0 | --------------- ---------------

swapbuffers();

.................

*/

///////////////BEGIN PARAMETERS ////////// const int N = 1000; // number of automata in the base const int M = 500; // number of automata in the height const int NCOL = 15; // Number of colors of the automata const int MAX = 10000; // Maximum number of updating of the automata

92

const int L = 2; // L base and height of each automata in the drawing///////////////END PARAMETERS //////////

struct Cells {short A[2][N][M]; int matr_vis, matr_act;/* One matrix 2xNxM, which we imagine as a vector {A[0], A[1]} of 2 matrices NxM. If pag_vis is the visible matrix and matrix_act the active matrix, then A[0][i][j] is the current number of the cell (i,j) A[1][i][j] is the next number of the cell (i,j), or conversely *///the red, green, blue components for the color A=0 and B=NCOL-1 vector<int> colors; Cells::Cells(); // we start with matr_vis=0 is visible and matr_act=1 is active.

void Cells::InitializeColor();//Assigns random colors to the vector of colors.

void Cells::InitializeData();//Assigns a random color to all cellar automata in A[matr_act]

void Cells::Draw1();//Draws A[matr_act] in the case all automata have base 1

void Cells::Draw2();//Draws A[matr_act] in the case all automata have base >= 2

void Cells::Draw();// We draw A[matr_act],// no matter whether the automata have base 1 or have base > 1

void Cells::UpdateCell(int i,int j);// Takes cell (i,j) of matr_act, then look to the 4 cells up, left,right, down.// If any of these 4 cells has a color nextc one position higher than color c// of cell (i,j), then cell (i,j) takes color nextc in matr_vis, otherwise// cell(i,j) keeps color c in matr_vis

void Cells::UpdateMatrix();

93

//Calculates all cells in A[matr_vis] from all cells of A[matr_act]

void Cells::UpdateState();//PREC.: matr_vis "visible" and matr_act "active" /*POSTCOND.: we calculates all cells in A[matr_vis] from all cells of A[matr_act]. We draw all cells A[matr_act], then we swap matr_vis, matr_act with (1-matr_vis), (1-matr_act). */}; /////////////// FINE DEFINIZIONE CLASSE DEMON ///////

/* From now on, we write matr_vis, matr_act for the indexes of the visible and active matrix. The program state is: {A[0], A[1], matr_vis, matr_act, graphic window}. */

int randomcolor();//returns a random color

int main() {///////////////BEGIN INITIALIZATION //////////srand(time(NULL));initwindow(N*L,M*L); //opens a graphics window, in which we will draw NxM squares of size LxL. //The initial value of the graphics window is: matrix 0Cells cells;/* we start with matr_vis=0 is visible and matr_act=1 is active. */

cells.InitializeColor();/* We randomly select the colors for our automata */

cells.InitializeData();/* We randomly select one state for each automa *////////////////END INITIALIZATION//////////

swapbuffers();// This function hides everything we draw until the next swapbuffers();

for(int Nstep=0;(Nstep<MAX);++Nstep)

94

{//we start with matr_vis "visible" and matr_act "active" cells.UpdateState(); // For the new values: matr_vis is visible and matr_act is active cout << "step = " << setw(10) << Nstep << endl; swapbuffers(); // This function hides everything we draw until the next swapbuffers();}

writeimagefile("CellarAutomata.bmp");system("pause");} ///////////////BEGIN FUNCTION DEFINITION //////////

int randomcolor()/* returns a random color */{return COLOR(rand()%256, rand()%256, rand()%256);}

Cells::Cells(){matr_vis=0; matr_act=1;}; // matr_vis=0 is visible and matr_act=1 is active.

void Cells::InitializeColor()//Assigns random colors to the vector of colors.{vector<int> temp(NCOL); for(int i=0;i<NCOL;++i) temp[i] = randomcolor(); colors = temp;}

void Cells::InitializeData()//Assigns a random color to all cellar automata in A[matr_act]{for (int i=0;i<N;++i) for (int j=0;j<M;++j) A[matr_act][i][j]=rand()%NCOL;}

void Cells::Draw1()//Draws the automata in the active matrix in the case all automata have base 1{int color; short index;

for (int i=0;i<N;++i)

95

for (int j=0;j<M;++j) { index = A[matr_act][i][j]; color = colors[index]; putpixel(i,j,color); }}

void Cells::Draw2()//Draws the automata in the active matrix in the case all automata have base > 1{int color; short index;

for (int i=0;i<N;++i) for (int j=0;j<M;++j) { index = A[matr_act][i][j]; color = colors[index]; setfillstyle(SOLID_FILL,color); // we set the inside color of automata bar(i*L, j*L, i*L+L, j*L+L);// we draw automa (i,j). //bar(x0,y0,x1,y1) draws a filled rectangle with left upper corner (x0,y0) //and right bottom corner (x1,y1), with the bottom row and the rightmost //column skipped }}

void Cells::Draw()//We draw the current matrix,// no matter whether the automata have base 1 or have base > 1{if (L==1) Draw1(); else /* L>=2 */ Draw2();}

void Cells::UpdateCell(int i,int j)// Takes cell (i,j) of matr_vis, then look to the 4 cells up, left,right, down.// If any of these 4 cells has a color nextc one position higher than color c// of cell (i,j), then cell (i,j) takes color nextc in matr_act, otherwise// cell(i,j) keeps color c in matr_act{short c = A[matr_act][i][j]; //color cell (i,j) short nextc = (c+1)%NCOL;

96

short c1 = A[matr_act][(i+1)%N ][ j ]; //color of the left cell short c2 = A[matr_act][ i ][(j+1)%M ]; //color of the cell below short c3 = A[matr_act][(i-1+N)%N ][ j ]; //color of the right cell short c4 = A[matr_act][ i ][(j-1+M)%M]; //color of the cell above if ((c1 == nextc) || (c2 == nextc) || (c3 == nextc) || (c4 == nextc)) A[matr_vis][i][j] = nextc; else A[matr_vis][i][j] = c;} void Cells::UpdateMatrix()//Calculates A[matr_act] by updating all cells from A[matr_vis]{for (int i=0;i<N;++i) for (int j=0;j<M;++j) UpdateCell(i,j);}

void Cells::UpdateState()//PREC.: matr_vis "visible" and matr_act "active" /*POSTCOND.: we calculates all cells in A[matr_act] from all cells of A[matr_vis]. We draw all cells A[matr_vis], eventually we swap "visible" and "active" matrix, and matr_vis, matr_act with (1-matr_vis), (1-matr_act). */{UpdateMatrix(); //we update the data from A[matr_vis] to A[matr_act] Draw(); //we draw the data A on matr_vis (invisible active) matr_vis=1-matr_vis; // we update matr_vis matr_act=1-matr_act; // we update matr_act }

97

Fine del Corso: Programmazione Avanzata 2014/2015 Corso di Laurea in Matematica

Università di Torino

99

Appendice 1: Input/Output da file(Cap. 15.1-15.4 del libro di testo)

Questa lezione non fa parte del programma di esame, e viene svolta soltanto come esercizio.

Nella prima ora di questa lezione vediamo come leggere un input da file e come inserirlo in un tipo del C++. La lettura e scrittura da file si effettua con comandi cin, cout come per la lettura e scrittura da tastiera, ma contiene una difficoltà supplementare: dobbiamo capire il significato di un dato in base alla sua posizione nel file. In questa lezione, i dati letti riguardano la distanza tra coppie di città. Sono contenuti in un file fatto di righe della forma:“city1” “city2” distance Scriviamo una funzione

DistanceData processLine (string& line)che individua, data una riga, la parte della riga che contiene il nome della prima città, la parte che contiene il nome della seconda città, e la parte che contiene la distanza delle due città. I tre dati vengono assegnati ai tre campi di un dato composto definito come segue:

struct DistanceData {string city1, city2, distString; };

Vediamo ora i dettagli. Per utilizzare il programma seguente, ricopiate i dati seguenti su un file prova.txt posto nella stessa cartella del vostro programma.

"Atlanta" "Chicago" 700"Atlanta" "Boston" 1,100"Atlanta" "Chicago" 700"Atlanta" "Dallas" 800"Atlanta" "Denver" 1,450"Atlanta" "Detroit" 750"Atlanta" "Orlando" 400

/* Lezione su Input/Output da file */#include <iostream> /* per il cout */#include <stdlib.h> /* per il system("pause") */#include <cmath> /* per le funzioni matematiche */

100

#include <vector> /* per i vettori */#include <fstream> /* per il tipo dei files */using namespace std; /* per abbreviare il cout */

struct DistanceData {string city1, city2, distString; };

/* La funzione processLine(…) prende una riga della forma “city1” “city2” distance La funzione scompone nelle tre parti cit1, cti2, distance che la compongono, quindi assegna ognuna di essa a un campo di un dato D di tipo DistanceData. */

DistanceData processLine (string& line){// the character we are looking for is a quotation markchar quote = '\"';// store the indices of the quotation marks in a vectorvector<int> quoteIndex (4);// find the first quotation mark using the built-in findquoteIndex[0] = line.find (quote);// find the other quotation marks using the find from Chapter 7for (int i=1; i<4; i++) { quoteIndex[i] = line.find(quote, quoteIndex[i-1]+1); }// break the line up into substringsint len1 = quoteIndex[1] - quoteIndex[0] - 1;string city1 = line.substr (quoteIndex[0]+1, len1);int len2 = quoteIndex[3] - quoteIndex[2] - 1;string city2 = line.substr (quoteIndex[2]+1, len2);int len3 = line.length() - quoteIndex[2] - 1;string distString = line.substr (quoteIndex[3]+1, len3);// insert the extracted information in D and returns itDistanceData D;D.city1 = city1; D.city2 = city2; D.distString = distString;return D;}

int main() //"ifstream" e' il tipo dei files{ /* Cap. 15.2. Definiamo una variabile "infile" di tipo file e nome "file-name" */ cout << "Cap. 15.2: lettura da file" << endl; ifstream infile ("file-name");

101

/* leggiamo dal file "file-name" prima un valore numerico che chiamiamo "x", poi una riga di caratteri che chiamiamo "line" */ int x; string line; infile >> x; // al posto di cout >> x: scrive un intero da infile in x getline (infile, line); // scrive una riga da infile a line cout << "x = " << x << endl; cout << "line = " << line << endl; system("pause"); system("CLS");

/* Cap. 15.2. Ripetiamo le stesse operazione da un file di nome "prova.txt". */ string fileName = "prova.txt";/* La dichiarazione di una variabile ifstream richiede una stringa C, non C++. Quindi convertiamo la stringa fileName a una stringa C++ prima di dichiarare una variabile ifstream */ ifstream infile2 (fileName.c_str()); /* Usando l’operazione inline2.good() controlliamo se l’apertura di infile2 e’ andata a buon fine. Se non e’ cosi’ arrestiamo il programma */ if (infile2.good() == false) { cout << "Unable to open the file named " << fileName; system("pause"); exit (1); }/* Usando un ciclo leggo (con getline e stampo (con cout) una riga per volta. Uso inline2.eof() per controllare se il file e’ finito */while (infile2.eof() == false) {getline (infile2, line); cout << line << endl;}system("pause");

/* Cap. 15.3. Apro un file in input, un file in output, e usando un cout scrivo ogni riga del file in input sul file in output */cout << "Cap. 15.3: copia da un file a un altro" << endl;ifstream infile3 ("prova.txt");ofstream outfile ("out.txt");if (infile3.good() == false || outfile.good() == false) { cout << "Unable to open one of the files." << endl;

102

system("pause"); exit (1);}

while (infile3.eof() == false) { getline (infile3, line); outfile << line << endl;} system("pause"); /* 15.4 “Parsing” o acquisizione di un dato da file. Leggiamo una riga del file prova.txt, che contiene dati in righe della forma:“city1” “city2” distance La funzione processLine(…) scompone una riga nelle tre parti che la compongono, e assegna ogni parte a un campo di un dato D. */ cout << "15.4 Parsing input" << endl; ifstream infile4 ("prova.txt"); getline (infile4, line); DistanceData D = processLine(line); cout << "Citta 1 = " << D.city1 << endl; cout << "Citta 2 = " << D.city2 << endl; cout << "Distanza = " << D.distString << endl; system("pause");}

/* Fine prima ora */

Nella seconda ora di questa lezione vi chiediamo di:

scrivere un programma che legga tutti i dati di questo tipo contenuti in un file e li inserisca in un vettore vector<DistanceData>.

scrivere una funzione che prenda un vettore Vdi tipo vector<DistanceData>, due città, e restituisca la stringa che contiene la loro distanza, un messaggio di errore se le due città non appartengono all’elenco.

C’è la difficoltà che la lunghezza del vettore V dei dati è uguale al numero di righe del file contenente i dati, e dunque non è nota a priori. Noi invece dobbiamo definire un vettore V con un numero di elementi preciso. Una soluzione è definire V come un vettore di 0 elementi, e poi aggiungere ogni nuovo dato D con una istruzione V.push_back(D); che estende il vettore V con una posizione in più al fondo, e inserisce D nella nuova posizione creata.

103

Appendice 2: Manuale minimo di grafica

Contiene la spiegazione di tutti i comandi di grafica usati almeno una volta nel corso di Informatica a partire dal 2009/2010. La grafica non fa parte del corso, è usata a scopo dimostrativo. Spieghiamo come scaricare, istallare e usare la libreria di grafica nel sito del corso di Programmazione Avanzata 2014/2015:

http://math.i-learn.unito.it/mod/page/view.php?id=26870 Alternativamente: queste spiegazioni sono ripetute all’ultima pagina di questo diario, alla voce “Come istallare una libreria di grafica”. Trovate un manuale della libreria grafica all’indirizzo:

http://www.cs.colorado.edu/~main/cs1300/doc/bgi/Trovate dei semplici esercizi alla voce: “Primi esempi di grafica” al fondo del Laboratorio 03 sulle variabili. La grafica è usata solo come esempio. Non dovete imparare i nomi dei comandi, ve li ripeteremo noi ogni volta che serve.

Il comando#include <graphics.h>

include la libreria di grafica. Il comandoinitwindow(N,M);

apre una finestra di grafica di dimensioni NxM, con un sistema di riferimento con la y diretta verso il basso: Origine x=N *----------------* | | | | y=M| | *----------------* Consigliamo le dimensioni N=1000, M=768. Avete a disposizione i seguenti colori: BLACK, BLUE, GREEN, CYAN, RED, MAGENTA, BROWN, LIGHTGRAY, DARKGRAY, LIGHTBLUE, LIGHTGREEN, LIGHTCYAN, LIGHTRED, LIGHTMAGENTA, YELLOW, WHITE, rappresentati da un intero a 4 bits (dunque tra 0 e 15). Potete creare nuovi colori con la dichiarazione:

int C = COLOR(red,green,blue);dove red, green, blue sono numeri da 0 a 255 che rappresentano le quantita’ di rosso, verde e blu nel colore C, rappresentato da un numero naturale a 32 bits (quindi inferiore a 232). Se le quantita’ di rosso, verde e blu sono uguali si ottengono le sfumature di grigio: (0,0,0) è il nero, (127,127,127) è un grigio, (255,255,255) è il bianco. Dato un colore c, le proporzioni di rosso, verde e blu in c (in scala 0-255) si calcolano con RED_VALUE(c), GREEN_VALUE(c), BLUE_VALUE(c). Non mescolate questi colori a 32 bits con quelli a 4 bits (rappresentati da un intero tra 0 e 15), si creano ambiguita’. Con

setbkcolor(C)

http://www.cs.colorado.edu/~main/cs1300/doc/bgi/

http://math.i-learn.unito.it/mod/page/view.php?id=26870

104

preparate la finestra per ricevere il colore di sfondo C, ma per il momento la finestra mantiene il colore precedente. Se dopo scrivete:

cleardevice();riempite la finestra del colore C, cancellando tutto il contenuto precedente (sia il colore di sfondo che le figure). Con

setcolor(D);decidete il colore D di ogni linea e del bordo di gni figura che disegnate da ora in poi, ma non cambiate il colore di quelli esistenti. Con

setfillstyle(S,E);decidete lo stile S con cui riempite le figure che disegnate da ora in poi, e il loro colore E, ma non cambiate le figure esistenti. Tra gli stili ricordiamo SOLID_FILL che riempe una figura completamente di colore, senza lasciare spazi vuoti. Gli altri stili riempono parzialmente la figura del colore E, lasciando righe e puntini vuoti qua e la’, che vengono riempiti con il colore C di sfondo della finestra. Il bordo della figura riceve l’ultimo colore D assegnato da setcolor(.). Quindi una figura dipende da tre colori, bordo, sfondo e interno. A titolo di curiosita’, gli stili sono EMPTY_FILL, SOLID_FILL, LINE_FILL, LTSLASH_FILL, SLASH_FILL, BKSLASH_FILL, LTBKSLASH_FILL, HATCH_FILL, XHATCH_FILL, INTERLEAVE_FILL, WIDE_DOT_FILL, CLOSE_DOT_FILL, USER_FILL. Si possono indicare in quest’ordine con numeri da 0 a 11.

Tracciare delle ellissi. Con il comandofillellipse(x,y,Rx,Ry);

disegnate una ellisse piena di centro (x,y) e raggi Rx, Ry. Se Rx = Ry = R disegnate un cerchio di raggio R. Il bordo dell’ellisse ha il colore D deciso dall’ultimo comando setcolor(D) che avete eseguito. L’interno dell’ellisse ha lo stile S e il colore E deciso dall’ultimo comando setfillstyle(S,E) che avete eseguito, nei vuoti lasciati dallo stile S viene inserito il colore C di sfondo. Tutto cio’ che si trovava dove inserite la nuova figura viene cancellato.

Tracciare delle linee rette. Usate il comando moveto(a,b); per spostare il cursore che disegna le rette nel punto (a,b): spostare il cursore non disegna punti. Usate lineto(a’,b’) per disegnare una linea retta da (a,b) fino a (a’,b’). La retta ha il colore D deciso dall’ultimo comando setcolor(D) che avete eseguito. Come effetto secondario, il cursore che disegna le rette viene spostato in (a’,b’): la prossima retta parte da (a’,b’).

Tracciare dei Rettangoli vuoti. Il comando void rectangle (int left, int top, int right, int bottom); disegna un rettangolo vuoto con margine superiore sinistro (left,top) e inferiore destro (right,bottom). Il bordo ha il colore D deciso dall’ultimo comando setcolor(D) che avete eseguito.

105

Tracciare dei Rettangoli pieni senza bordo. Il comando void bar (int left, int top, int right, int bottom); disegna un rettangolo privo di bordo con margine superiore sinistro (left,top) e inferiore destro (right,bottom). L’interno ha lo stile S e il colore E deciso dall’ultimo comando setfillstyle(S,E) che avete eseguito, nei vuoti lasciati dallo stile S viene inserito il colore C di sfondo.

Tracciare dei poligoni pieni. Dovete conoscere i vettori in C++ per usare questo comando. Scrivete void fillpoly(int n, int v[]); dove v={x_1,y_1,…,x_n,y_n} è un vettore di 2*n punti, che rappresentano le coordinate x e y degli n punti di un poligono. Il bordo ha il colore D deciso dall’ultimo comando setcolor(D) che avete eseguito. L’interno ha lo stile S e il colore E deciso dall’ultimo comando setfillstyle(S,E) che avete eseguito, nei vuoti lasciati dallo stile S viene inserito il colore C di sfondo.

Salvataggio immagini. Potete salvare una copia del disegno fatto. L’unico formato disponibile è “.bmp” (bitmap, o rappresentazione “punto per punto” del disegno). Il comando è:

writeimagefile("NomeFile.bmp");se invece non scrivete il nome del file nel comando:

writeimagefile(); allora il nome del file vi viene chiesto durante l'esecuzione del programma: l’esecuzione viene sospesa finche’ non ne scegliete uno.

Come nascondere i disegni incompleti: il comando swapbuffers(). Per disegni complessi conviene includere il comando swapbuffers(); una volta all’inizio del programma, e poi ogni volta dopo aver terminato un disegno. Tutto cio’ che disegnamo dopo un comando swapbuffers(); non viene copiato sullo schermo fino al comando swapbuffers(); successivo. Questo comando ci fa risparmiare molti aggiornamenti dello schermo, e aggiornare lo schermo è un comando costoso in termini di tempo. Per disegni complessi swapbuffers(); rende il programma molto più rapido, e anche più gradevole a vedersi. Infatti se aggiorniamo lo schermo troppo volte in troppo poco tempo l’immagine ci appare tremolante, perche’ i pixels che rappresentavano l’immagine precedente non fanno in tempo a cambiare luminosita’ intanto che disegnamo la nuova immagine.

Come rallentare l’animazione. Una animazione troppo veloce ci fa venire il mal di testa e puo’ produrre un crash di sistema. In questi casi possiamo rallentarla usando il comando delay(n); che ritarda l’esecuzione di n millisecondi.

Primi esempi di grafica. Come esempio, vi chiediamo di scrivere un programma che apra una finestra del colore che preferite e disegni alcuni cerchi, con bordo e interno disegnati del colore che preferite. Per sapere come, leggete il manuale minimo di grafica in appendice a questo testo fino alla voce “ellissi”.

106

/* Primi esempi di grafica: soluzioni */#include <graphics.h>#include <stdlib.h>#include <iostream>#include <cmath>using namespace std;

main(){int N=1000, M=768; /* base and height of the window. The y component is downward-directed: Origin x=N *----------------* | | | |y=M| | *----------------* */

///////////////BEGIN INITIALIZATION ////////// initwindow(N,M); //open a NxM graphics window. ///////////////END INITIALIZATION//////////

/* Colors:BLACK, BLUE, GREEN, CYAN, RED, MAGENTA, BROWN, LIGHTGRAY, DARKGRAY, LIGHTBLUE, LIGHTGREEN, LIGHTCYAN, LIGHTRED, LIGHTMAGENTA, YELLOW, WHITE */

setbkcolor(MAGENTA);//setbckcolor(C) sets the background //color for page 0 (but does not draw it!)cleardevice();//fills the window of the "background" color //erasing everything else

/* How to define more colors: defineint C = Color(red,green,blue);

where red, green, blue are integers from 0 to 255, expressing the quantity of red, green, blue in thecolor C */

int GRAY = COLOR(127,127,127);//when the quantities of red, green, blue are the//same we obtain some degree of gray:

107

//(0,0,0) is black and (255,255,255) is white.

// Ball Number 0 setcolor(GRAY); // setcolor(C) sets the color of the border line// of any figure to the given color C setfillstyle(SOLID_FILL,RED);/* setfillstyle(PATTERN,C); set the color filling inside a figure to a given color C and a given "pattern". A “pattern” is the way a color is painted: by dots, lines …. The pattern SOLID_FILL fills a figure completely with color, all other patterns insert the background color There are 12 patterns, represented by a number from 0 to 11, or by the constants: EMPTY_FILL, SOLID_FILL, LINE_FILL, LTSLASH_FILL, SLASH_FILL, BKSLASH_FILL, LTBKSLASH_FILL, HATCH_FILL, XHATCH_FILL, INTERLEAVE_FILL, WIDE_DOT_FILL, CLOSE_DOT_FILL, USER_FILL */ fillellipse(500,350,200,200); //fillellipse(x,y,Radiusx,Radiusy)//draw an ellipse (or a ball) with the colors we selected//for the border and for the inside, and with//the "pattern" we choose.

/*Remark the two radius of the ellipse must be equal if we want a ball */

// Ball Number 1setcolor(BLACK); //set the line color to the given color //we fill with a pattern setfillstyle(XHATCH_FILL,BLUE);//set the fill color to the given pattern and color fillellipse(300,200,200,200); //fillellipse(x,y,Radiusx,Radiusy)

system(“pause”);}

108

Come istallare una libreria di grafica Ci sono molte librerie di grafica per il C++. Noi utilizzeremo la libreria graphics.h, con file di appoggio libbgi.a. Questa libreria funziona principalmente per il sistema operativo Windows. Per aggiungere la libreria graphics.h procedete come segue

Primo. Cercate in quale cartella si trova il wxDev-C++. Come esempio, immaginiamo che si trovi nella cartella C:\Dev-Cpp. Ora scaricate graphics.h e libbgi.a dai seguenti indirizzi:

1. http://www.di.unito.it/~stefano/graphics.hcopiatelo nella cartella C:\Dev-Cpp\include\common

2. http://www.di.unito.it/~stefano/libbgi.acopiatelo nella cartella C:\Dev-Cpp\lib

(Nota. Non spaventatevi se aprendo la pagina libbgi.a vi compaiono solo dei "geroglifici"! Questo secondo file è scritto nel linguaggio "assembler" del sistema operativo Windows, non è scritto in C++, dunque non potete leggerlo, ma potete salvarlo come un file di tipo ".a". )

Secondo. Aprite il Dev-C++ alla voce "Tools" del Menu, quindi alla voce "Compiler Options". Quando si apre la finestra, controllate di avere come compiler set "Default GCC compiler", come compiler type "Mingw". Infine copiate nello spazio sottostante relativo alla "linker command line" la seguente riga:

-lbgi -lgdi32 -lcomdlg32 -luuid -loleaut32 -lole32

Salvate i cambi della finestra "Compiler Options" (altrimenti quello che avete fatto è tutto inutile) e chiudete la finestra. L'effetto è informare il wxDev-C++ dell'aggiunta delle nuove librerie e del loro contenuto. D'ora in avanti potete utilizzare la libreria grafica nei vostri programmi, aggiungendo all'inizio del file il comando

#include <graphics.h>

(Gia’ che ci siete, aggiungete la riga “-fpermissive” nel menu alla voce: Tools/Compiler Options/Compiler Command line. Rende il compilatore più tollerante a piccole variazioni della sintassi delle classi.)

stefano/C-2015-ProgrammazioneAvanzata.docx · Web viewIntroduzione del Corso di “Programmazione...

Documents

Transcript of stefano/C-2015-ProgrammazioneAvanzata.docx · Web viewIntroduzione del Corso di “Programmazione...