Corso: Programmazione Avanzata Diario delle Lezioni e...

Corso: “Programmazione Avanzata”

Diario delle Lezioni e

delle Esercitazioni

Università di Torino

Corso 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://greenteapress.com/thinkcpp/index.html

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

3

Indice del Corso di


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


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


Il programma Coriandoli rivisto utilizzando le classi.


Un “savescreen”: il programma Tubi (definito riutilizzando la

classe definita per Coriandoli).


Vettori di Oggetti (Cap. 12.1-12.8)


Classi definite reciprocamente (Cap. 13)


Un programma che gioca a Nim.


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


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


Il crivello di Eratostene.


Presentazione dell’Esercizio di Esame: il programma Demoni.

4

Le 12 Lezioni del Corso di


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


alla "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: Oggetti

Oggetti 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 ();

10

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 ();

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:

-fpermissive

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

Tools/Compiler Options/Compiler Command line

*/

#include <math.h>

#include <iostream>

#include <stdlib.h>


struct Time {

int hour, minute; //ore e minuti da un istante iniziale

double second; //la componente in secondi

//Una classe ha delle funzioni oltre che degli individui

void 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 secondi

Time 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 */

11

cout << "tempo corrente" << endl;

currentTime.print ();

system("pause");

}

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>


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

14

minute -= 60;

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 secondi

Time currentTime = { 9, 14, 30.0 };

cout << "tempo corrente" << endl;


//Esempi di uso della funzione increment.

cout << "il tempo corrente passati 500 secondi" << endl;

currentTime.increment (500.0);


//Esempi di uso della funzione after

cout << "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: Oggetti

Costruttori e modificatori di oggetti


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

secs -= hour * 3600.0; //minute al posto di t.minute

minute = int (secs / 60.0); //second al posto di t.second

secs -= 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 */


int main ()

{

Time currentTime (9, 14, 30.0);

currentTime.increment (500.0);


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

19

la durata del programma “Coriandoli”. Scegliamo come parametri del

programma:

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


alla “Linker Command Line”, che si trova nel menu del Dev-C++ alla

voce: Tools/Compiler Options/Linker Command line */


#include <iostream>

#include <cmath>

#include <time.h>



/*1. base e altezza della finestra grafica. */


/*2. Funzione che restituisce un colore a caso */

int coloreacaso()

{return

COLOR(rand()%256,rand()%256,rand()%256);}

/*3. Colore neutro per lo sfondo */


/* 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


//5.2. sceglie colore sfondo

setbkcolor(GREY);

//5.3. disegna colore sfondo

cleardevice();

//5.4 sceglie stile e colore disco

21

setfillstyle(SOLID_FILL,coloreacaso());



/* B. PARAMETRI DEL PROGRAMMA "CORIANDOLI”


int R=30;


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 partire

da 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


{

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

0 N

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 <iostream>

#include <cmath>

#include <time.h> /* per il comando srand(time(NULL)); che

inizializza la funzione rand(), vedi lezione precedente. */



/*1. base e altezza della finestra grafica. */


/*2. Funzione che restituisce un colore a caso */

int coloreacaso()

{return COLOR(rand()%256,rand()%256,rand()%256);}

/*3. Colore neutro per lo sfondo */


/*4. funzione che inizializza tutti i parametri della grafica */

void inizializzagrafica()

{srand(time(NULL)); //initializza rand()

//4.1. apre una finestra grafica NxM


//4.2. sceglie colore sfondo

setbkcolor(GREY);

//4.3. disegna colore sfondo

cleardevice();

//4.4 sceglie stile e colore disco

setfillstyle(SOLID_FILL,coloreacaso());



/* B. PARAMETRI DEL PROGRAMMA "TUBI" */


int R=30;


int NDischi=10000;

28

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

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 ();

30

//disegno D in molte posizioni consecutive


{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


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>


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 */

};

32

/* 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. */

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 0

suits[1] = "Diamonds"; //nome del seme 1

suits[2] = "Hearts"; //nome del seme 2

suits[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

33

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:

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 falso

return 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

35

e l’ordine tra carte. Ricordate: non esistono in C++ funzioni gia’

definite con questo compito per i tipi che definiamo noi.

/* Soluzioni Lezione 06: come trovare una carta in un mazzo di

carte */

#include <iostream>

#include <math.h>

#include <vector>

#include <stdlib.h>


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 0

suits[1] = "Diamonds"; //nome del seme 1

suits[2] = "Hearts"; //nome del seme 2

suits[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";

36

ranks[13] = "King";

cout << ranks[rank] << " of " << suits[suit] << endl;}


{return ((c1.rank == c2.rank) && (c1.suit == c2.suit));}


{

// confrontiamo prima i semi di c1 e c2.



// se i semi sono uguali, confrontiamo i valori di c1 e c2.



// se anche i valori sono uguali, allora c1=c2 e restituiamo falso

return 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);

37

cout << "\n 1. STAMPA DELLE CARTE: (0,0), (1,11), (0,1)"

<< endl;

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>


/* 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 carta

bool isGreater (Card& c2); //confronta una carta con una carta c2

int 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()

{}


{}

43


{}

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 mazzo

void 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();


cout << "MAZZO DI 52 CARTE RIORDINATO" << endl;

classic_deck.sort();


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>


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 carta

bool isGreater (Card& c2); //confronta una carta con una carta c2

int 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 */

46

/* 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 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";

47

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

{ cout << namerank(rank) << " of " << namesuit(suit) << endl; }

void Deck::print()

{int L = cards.size();

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

cards[i].print();}


{return ((c1.rank == c2.rank) && (c1.suit == c2.suit));}


{

// first check the suits



// if the suits are equal, check the ranks



// if the ranks are also equal, return false

return 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;

}

48

Deck::Deck()

{

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 mazzo

void Deck::shuffle ()

{Card temp; int n = cards.size();


{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;

49

int n = cards.size();

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;


cout << "MAZZO DI 52 CARTE PERMUTATO" << endl;

classic_deck.shuffle();


cout << "MAZZO DI 52 CARTE RIORDINATO" << endl;

classic_deck.sort();


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:

I

III

IIIII

IIIIIII

Vediamo una partita.

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

II

II

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}:

II

II

II

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

51

riduce pos[i] al valore (pos[i]^prod), mossa corretta proprio

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


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


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 <cmath> /* per pow(a,b) */


#include <time.h> /* per time(NULL) */


/* 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;


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!


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 << " ";


cout << pos[i] << " ";

cout << endl;}

56

bool Nim::nonzero()



{if (pos[i]!=0) return true;}

return false;

}

int Nim::xor_prod()


int prod = pos[0];

for(int i=1; i<n; ++i)

prod = (prod^pos[i]);

return prod;}

void Nim::mossa_computer()


int prod = (*this).xor_prod(), b;

if (prod>0) /* se prod>0, scelgo la mossa

vincente prevista dalla teoria e esco subito */


{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()


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 */


{continuare = (*this).nonzero();

/* Se il computer ha perso il gioco finisce, altrimenti il

computer muove */


{cout << "Risposta computer" << endl;

58

(*this).mossa_computer();

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

60

lasciamo. Nel caso di Card non c’è nessun vantaggio a nascondere

il modo con cui Card viene rappresentata: la rappresentazione

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 <cmath> /* per sin, cos */


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)

61

void Complex::calculateCartesian(); // aggiorna co. cartesiane

void Complex::calculatePolar(); // aggiorna co. polari

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


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



return imag;

}

double Complex::getMag ()/* Calcola la norma */

{//se la norma manca prima la calcola

if (polar == false)

calculatePolar ();

return mag;

62

}

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

{ //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



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;

}

63

/* Definizione di addizione e moltiplicazione.

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


64

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;

Complex product = mult (c1, c2);

product.printCartesian();


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;


{

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();


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

68

errato. La post-condizione descrive il risultato di una funzione

quando i dati in ingresso soddisfano la precondizione. In questo

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 <stdlib.h> /* per il system("pause") */


#include <assert.h> /* per il comando assert */


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

70

CalculatePolar() solo quando non ci sono coordinate polari, e

quindi ci sono coordinate cartesiane.

Esercizio 2. Provate poi ad aggiungere deliberatamente una

funzione errata alla classe:

void printCartesianPolar() //stampa delle due rappresentazioni

{ calculateCartesian();

calculatePolar();



}

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 <assert.h> /* per il comando assert */


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


//Complex::Complex() /* costruisce un numero complesso privo di

rappresentazione e quindi privo di valore */

72

//{ cartesian = false; polar = false; }

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;


}

double Complex::getReal ()/* Calcola la parte reale */

{ //se la parte reale manca prima la calcola




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 */

{ //se l'angolo manca prima lo calcola


73


return theta;

}

void Complex::calculateCartesian ()

{assert(polar==true);

real = mag * cos (theta);

imag = mag * sin (theta);

cartesian = 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;


}

void Complex::printCartesian ()

{

if (cartesian == false) calculateCartesian ();



}

void Complex::printPolar ()

{




}

void Complex::setPolar (double m, double t)

{

mag = m; theta = t;

cartesian = false; 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;


{

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();

75

calculatePolar();




}

*/

void Complex::printCartesianPolar() //stampa delle due

rappresentazioni

{

if (cartesian==false)

calculateCartesian();

if (polar==false)

calculatePolar();




}

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.printPolar();

cout << "stampa di Complex c1 (2.0, 3.0)" << endl;

Complex c1 (2.0, 3.0);



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();


sum.printPolar();

cout << "----------------------------" << endl;

cout << "Capitolo 14.7. Prova funzione di prodotto" << endl;

76

cout << "prodotto di Complex c1 (2.0, 3.0) e Complex c2(3.0, 4.0)"

<< endl;

Complex product = mult (c1, c2);

product.printCartesian();


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();


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

78

vector<int> Primi; //Il vettore dei primi

//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 <cmath> /* per sqrt eccetera */



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();


//Crivello dei primi <= 100

cout << "Stampa crivello dei primi <=100" <<endl<<endl;

crivello.riempi_fino_a(100);

crivello.stampa();


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

81

{crivello2.riempi_fino_a(x);

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;}


}

82

Lezione 12: Esercizio di Esame

Il 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


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 caso

nero ---------------- ---------------

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 base

const int M = 100; // number of automata in the height

const int NCOL= 12; // Number of colors of the automata

const int MAX = 1000;//Maximum number of updating of the automata

const int L = 10; //base and height of an automata in the screen

//Class for the cellar automata in matr_vis and in matr_act

struct 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 <iostream>

#include <cmath>

#include <iomanip>

#include <time.h>

#include <vector>


/*

THE PROGRAM "DEMONS" FOR CYCLIC CELLAR AUTOMATA BY DEWDNEY


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 0

Cells 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


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


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


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 */


100


#include <cmath> /* per le funzioni matematiche */


#include <fstream> /* per il tipo dei files */


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

/* La funzione processLine(…) prende una riga della forma


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 mark

char quote = '\"';

// store the indices of the quotation marks in a vector

vector<int> quoteIndex (4);

// find the first quotation mark using the built-in find

quoteIndex[0] = line.find (quote);

// find the other quotation marks using the find from Chapter 7

for (int i=1; i<4; i++)

{

quoteIndex[i] = line.find(quote, quoteIndex[i-1]+1);

}

// break the line up into substrings

int 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 it

DistanceData 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" */

101

cout << "Cap. 15.2: lettura da file" << endl;

ifstream infile ("file-name");

/* 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;


/* 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)

102

{

cout << "Unable to open one of the files." << endl;

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:


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

103

posizione in più al fondo, e inserisce D nella nuova posizione

creata.

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 la libreria di grafica. Il comando

initwindow(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

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

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

104

setbkcolor(C)

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 comando

fillellipse(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 <stdlib.h>

#include <iostream>

#include <cmath>


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: define

int C = Color(red,green,blue);

where red, green, blue are integers from 0 to 255,

expressing the quantity of red, green, blue in the

color 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 1

setcolor(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.h

copiatelo nella cartella C:\Dev-Cpp\include\common

2. http://www.di.unito.it/~stefano/libbgi.a

copiatelo 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:


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


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

http://www.di.unito.it/~stefano/graphics.h

http://www.di.unito.it/~stefano/libbgi.a

Corso: Programmazione Avanzata Diario delle Lezioni e...

Documents

Transcript of Corso: Programmazione Avanzata Diario delle Lezioni e...