Fondamenti di programmazione in C++ - Algoritmi, strutture...

Fondamenti di programmazione in C++ - Algoritmi, strutture dati e oggetti Luis Joyanes Aguilar

Copyright © 2008 – The McGraw-Hill Companies srl

2.1.

Se si elimina il commento // il programma scrive anche

Ciao mondo

altrimenti non scrive nulla.

Le istruzioni system(“PAUSE”);

return EXIT_SUCCESS;; servono per chi usa gli “Integrated Development Environment” tipo DevC++ per mantenere attiva la console di output fino alla successiva pressione del tasto INVIO (ENTER). Esse potrebbero essere rimpiazzate da: cout << "Premi INVIO per terminare. \n";

cin.get(); comunque nei successivi esercizi ometteremo queste due instruzioni.

2.2. questo è un collaudo Scriviamo di nuovo. esce la stringa. stringa.

2.3 #include <iostream> using namespace std; int main() { cout << "*******\n"; cout << "* *\n"; cout << "* *\n"; cout << "* *\n"; cout << "*******\n"; cout << "* *\n"; cout << "* *\n"; cout << "* *\n"; cout << "*******\n"; return 0; }

2.4. #include <iostream>


Copyright © 2008 – The McGraw-Hill Companies srl using namespace std; int main() { cout << "Benvenuto al C++;\n"; cout << "Cominceremo presto a programmare in C.\n"; return 0; }

2.5. #include <iostream> using namespace std; int main() { char esempio[50];

strcpy(esempio, "è un nuovo esempio in C++\n"; cout << esempio << endl; return 0; }

2.6.

Questo è un esempio di definizione di costante. Salta due righe e anche un n esempio stringhe

2.7. Giovanni il Senza Paura----> anni il Senza Paura Giovanni il Senza Paura il Senza Paura

2.8. #include <iostream> using namespace std; int main( ) { int numero_pezzi; float peso_unitario, prezzo_unitario; cout << "Introduca il numero dei pezzi "; cin >> numero_pezzi; cout << " pezzi: " << numero_pezzi << "\n"; cout << "Introduca peso unitario e prezzo unitario"; cin >> peso_unitario >> prezzo_unitario;



cout << peso_unitario << ", " << prezzo_unitario << endl; }

2.9. #include <iostream> using namespace std; int main( ) { float larghezza, lunghezza; cout << "Introduca la larghezza \n"; cin >> larghezza; cout << "Introduca la lunghezza \n"; cin >> lunghezza; cout << "La lunghezza è “ << lunghezza << endl; cout << "La larghezza è “ << larghezza << endl;

}

2.10.

N OK MioProblema OK Mio Gioco KO (spazio bianco) MioGioco OK write OK m&m KO registro OK * 143Eta KO (non può iniziare per * e spazio bianco) 85 Nome KO (non può iniziare per cifra e spazio bianco) AAAAAAAAAA OK Nome_Cognome OK Saldo_Attuale OK 92 KO (non può iniziare per cifra) Universidad Pontificia

KO (spazio bianco)

Set 15 KO (spazio bianco)

3.1

Nel caso delle divisione fra interi l'operatore / indica la divisione intera mentre l'operatore % il resto della divisione intera. Pertanto i risultati sono:

15 / 12 = 1 15 / 12 = 3

24 / 12 = 2 24 / 12 = 0

123 / 100 = 1 123 / 100 = 23

200 / 100 = 2 200 / 100 = 0

3.2.

a) 10 * 14 – 3 * 2 140 – 3 * 2 140 – 6 134

d) (4 – 40 / 5) % 3 (4 – 8) % 3 -4 % 3 -1

b) 4 + 5 * 2 4 + 10 14

e) 4 * (3 + 5) – 8 * 4 % 2 – 5 4 * 8 – 8 * 4 % 2 – 5 32 – 8 * 4 % 2 – 5 32 – 32 % 2 – 5 32 – 0 – 5 32 – 5 27

c) 13 – (24 + 2 * 5) / 4 % 3 13 – (24 + 10) / 4 % 3 13 – 34 / 4 % 3 13 – 8 % 3 13 – 2 11

f) -3 * 10 + 4 * (8 + 4 * 7 – 10 * 3) / 6 -30 + 4 * (8 + 4 * 7 – 10 * 3) / 6 -30 + 4 * (8 + 28 – 10 * 3) / 6 -30 + 4 * (8 + 28 – 30) / 6 -30 + 4 * (36 – 30) / 6 -30 + 4 * 6 / 6 -30 + 24 / 6 -30 + 4 -26

3.3

In C++ la funzione potenza è pow( ), per esempio l'espressione (x+y)2 si calcola pow(x+y,2)

a) x / y + 1 d) b / (c + d) g) x * y / (1 – 4 * x)

b) (x + y) / (x - y) e) (a + b) * (c / d) h) x * y / (m * n)

c) x + y / z f) pow(pow(x + y, 2),2) i) pow(x + y,2) * (a - b)

3.4.

Fondamenti di programmazione in C++ - Algoritmi, strutture dati e oggetti Luis Joyanes Aguilar Copyright © 2008 – The McGraw-Hill Companies srl

Se ausiliare è una variabile dello stesso tipo di x ed y

ausiliare = x; x = y; y = ausiliare;

3.5.

Un possibile programma è: #include <iostream> using namespace std; int main() { int x, y;

cin >> x >> y; cout << x/y << “ “ << x%y << endl;;

}

3.6.

Un possibile programma è: #include <iostream> using namespace std; int main() { float c, f; cout << “Introduca i gradi “;

cin >> c; f = c * 9 / 5 + 32; cout << “ gradi fahrenheit = “ << f << endl;

}

3.7.

Un possibile programma è: #include <iostream> #include <cmath> // contiene la funzione sqrt using namespace std; int main() { float a, b, h; cout << "Introduca i lati del triangolo rettangolo "; cin >> a >> b;


h = sqrt( a * a + b * b ); cout << " lato 1 = " << a << endl; cout << " lato 2 = " << b << endl; cout << " ipotenusa = " << h << endl; } Una possibile esecuzione potrebbe essere: Introduca i lati del triangolo rettangolo 3 4 lato 1 = 3 lato 2 = 4 ipotenusa = 5

3.8.

Un possibile programma è: #include <iostream> using namespace std; int main() { int x; cout << "Introduca un numero intero "; cin >> x; cout << " il doppio vale " << 2 * x; cout << ", il triplo vale " << 3 * x << endl; } Una possibile esecuzione potrebbe essere: Introduca un numero intero 3 il doppio vale 6, il triplo vale 9

3.9.

Un sistema lineare di due equazioni in due incognite ax�b y= cd x�e y= f � ha un'unica soluzione solo se

a�e − b�d ≠ 0 � e la soluzione è data dalle espressioni x = ce − b fae− bd � y = a f − cd

ae − bd �

#include <iostream> using namespace std; int main() { float a, b, c, d, e, f, denominatore, x, y; cout << "Introduca i coefficienti a, b e c: "; cin >> a >> b >> c;


cout << "Introduca i coefficienti d, e e f: "; cin >> d >> e >> f; denominatore = a * e - b * d; if (denominatore == 0) cout << " nessuna soluzione. \n"; else { x = (c * e - b * f) / denominatore; y = (a * f - c * d) / denominatore; cout << " la soluzione del sistema è:\n "; cout << "x = " << x << " y = " << y << endl; } return 0; } Una possibile esecuzione potrebbe essere: Introduca i coefficienti a, b e c: 2 3 5 Introduca i coefficienti d, e e f: 1 6 7 la soluzione del sistema è: x = 1 y = 1

3.10.

La costante di gravitazione universale vale G=6.673e-8 #include <iostream> using namespace std; int main() { const float G = 6.673e-8; float massa1, massa2, distanza, forza; cout << "Introduca la massa dei due corpi in grammi: "; cin >> massa1 >> massa2; cout << "Introduca la loro distanza in centimetri: "; cin >> distanza; if ((massa1 <= 0) || (massa2 <= 0) || (distanza <= 0)) cout << " nessuna soluzione. \n"; else { forza = G * massa1 * massa2 / (distanza * distanza); cout << " la forza è: " << forza << " centomillesimi di newton." << endl; } return 0; } Una possibile esecuzione potrebbe essere: Introduca la massa dei due corpi in grammi: 4567 5267 Introduca la loro distanza in centimetri: 3 la forza è: 0.17835 centomillesimi di newton.


3.11. #include <iostream> using namespace std; int main() { const float c = 2.997925e+10; float massa, energia; cout << "Introduca la massa: "; cin >> massa; energia = c * c * massa; cout << "l'energia liberata è "<< energia << " ergs." << endl; return 0; }

3.12.

#include <iostream>

using namespace std; int main() { float piedi, pollici, iarde, metri, centimetri; cout << "Introduca la misura in piedi: "; cin >> piedi; pollici = piedi * 12; iarde = piedi / 3; centimetri = pollici * 2,54; metri = centimetri / 100; cout << " la misura in piedi vale "<< piedi << " piedi." << endl; cout << " la misura in pollici vale "<< pollici << " pollici." << endl; cout << " la misura in iarde vale "<< iarde << " iarde." << endl; cout << " la misura in metri vale "<< metri << " metri." << endl; cout << " la misura in centimetri vale "<< centimetri << " centimetri." << endl; return 0; } Una possibile esecuzione potrebbe essere: Introduca la misura in piedi: 34 la misura in piedi vale 34 piedi. la misura in pollici vale 408 pollici. la misura in iarde vale 11.3333 iarde. la misura in metri vale 8.16 metri. la misura in centimetri vale 816 centimetri.


3.13. #include <iostream> using namespace std; int main() { int ettometri, decametri, metri, decimetri; cout << "Introduca la misura in ettometri, decametri e metri:"; cin >> ettometri >> decametri >> metri; decimetri = ((ettometri * 10 + decametri) * 10 + metri) * 10; cout << " la misura in decimetri vale "<< decimetri << endl; return 0; } Una possibile esecuzione potrebbe essere: Introduca la misura in ettometri, decametri e metri:4 35 5 la misura in decimetri vale 7550

3.14. #include <iostream> using namespace std; int main() { int cinquecento, duecento, cento, cinquanta, venti, dieci, cinque; // banconote int due, uno, cinquantac, ventic, diecic, cinquec, duec, unoc; // monete float contanteOriginale; long int contante; cout << "Introduca il contante desiderato in euro:"; cin >> contanteOriginale; contanteOriginale *= 100; // passaggio a centesimi di euro contante = (int) contanteOriginale; // si tronca a centesimi di euro cinquecento = contante / 50000; contante = contante % 50000; duecento = contante / 20000; contante = contante % 20000; cento = contante / 10000; contante = contante % 10000; cinquanta = contante / 5000; contante = contante % 5000; venti = contante / 2000; contante = contante % 2000; dieci = contante / 1000; contante = contante % 1000; cinque = contante / 500; contante = contante % 500; due = contante / 200; contante = contante % 200;


uno = contante / 100; contante = contante % 100; cinquantac = contante / 50; contante = contante % 50; ventic = contante / 20; contante = contante % 20; diecic = contante / 10; contante = contante % 10; cinquec = contante / 5; contante = contante % 5; duec = contante / 2; contante = contante % 2; unoc = contante; cout << "Questa somma di " << contanteOriginale << " centesimi di euro "; cout << "verrà erogata in maniera da ottimizzare il numero di pezzi "; cout << "cioè: \n"; cout << cinquecento << " banconote da 500 euro\n"; cout << duecento << " banconote da 200 euro\n"; cout << cento << " banconote da 100 euro\n"; cout << cinquanta << " banconote da 50 euro\n"; cout << venti << " banconote da 20 euro\n"; cout << dieci << " banconote da 10 euro\n"; cout << cinque << " banconote da 5 euro\n"; cout << due << " monete da 2 euro\n"; cout << uno << " monete da 1 euro\n"; cout << cinquantac << " monete da 50 centesimi\n"; cout << ventic << " monete da 20 centesimi\n"; cout << diecic << " monete da 10 centesimi\n"; cout << cinquec << " monete da 5 centesimi\n"; cout << duec << " monete da 2 centesimi\n"; cout << unoc << " monete da 1 centesimo\n"; return 0; } Una possibile esecuzione potrebbe essere: Introduca il contante desiderato in euro: 9988.88 Questa somma di 998888 centesimi di euro verrà erogata in maniera da ottimizzare il numero di pezzi, cioè: 19 banconote da 500 euro 2 banconote da 200 euro 0 banconote da 100 euro 1 banconote da 50 euro 1 banconote da 20 euro 1 banconote da 10 euro 1 banconote da 5 euro 1 monete da 2 euro 1 monete da 1 euro 1 monete da 50 centesimi 1 monete da 20 centesimi 1 monete da 10 centesimi 1 monete da 5 centesimi


1 monete da 2 centesimi 1 monete da 1 centesimo




4.1

Mancano le parentesi del test dell'if ed il punto e virgola prima dell'else. L'espressione corretta è la seguente: if (x > 25.0) y = x; else y = z;

4.2.

Il programma scriverà

cotoletta

Se la variabile prima_opzione avesse avuto il valore 3 avrebbe scritto

bistecca dolce

perchè il case 3 non ha il break

4.3 if (voto > 100) cout << "Alto"; else cout << "Basso";

4.4. int x, y; cin >> x >> y; if (x > y) cout << y; else cout << x;

4.5.

Un possibile programma è: #include <iostream> #include <cmath> using namespace std; int main() { float a, b, c, d, x1, x2; cout << "Introduca i tre coefficienti: ";


Copyright © 2008 – The McGraw-Hill Companies srl cin >> a >> b >> c; if ( a != 0) { d = b * b - 4 * a * c; if ( d > 0 ) { cout << " due soluzioni reali e distinte\n"; x1 = (-b + sqrt(d)) / ( 2 * a); x2 = (-b - sqrt(d)) / ( 2 * a); cout << " x1 = " << x1 << " x2 = " << x2 << "\n"; } else if ( d == 0 ) { cout << " due soluzioni reali ed uguali\n"; x1 = (-b) / ( 2 * a); cout << " x = " << x1 << "\n"; } else { cout << " non ha soluzioni reali ma due complesse\n"; x1 = (-b) / ( 2 * a); x2 = sqrt(-d) / ( 2 * a); cout << " prima soluzione\n"; cout << " parte reale " << x1 << endl; cout << " parte immaginaria " << x2 << endl; cout << " seconda soluzione\n"; cout << " parte reale " << x1 << endl; cout << " parte immaginaria " << -x2 << endl; } } else if ( b != 0 ) cout << " una soluzione semplice = " << -c / b << endl; else if ( c == 0 ) cout << " ha introdotto l'identità 0 = 0\n"; else cout << " senza soluzione\n"; return 0; } Una possibile esecuzione potrebbe essere: Introduca i tre coefficienti: 1 2 3 non ha soluzioni reali ma due complesse prima soluzione parte reale -1 parte immaginaria 1.41421 seconda soluzione parte reale -1 parte immaginaria -1.41421


Copyright © 2008 – The McGraw-Hill Companies srl 4.6.

Un possibile programma è: #include <iostream> using namespace std; int main() { int x, y, z; bool ordinati; cout << "Introduca i tre numeri: "; cin >> x >> y >> z; ordinati = x >= y ? true : false; ordinati = ordinati && (y >= z ? true : false); if ( ordinati) cout << " stanno in ordine decrescente\n"; else cout << " non stanno in ordine decrescente\n"; return 0; }

4.7.

Un possibile programma è: #include <iostream> using namespace std; int main() { int op1, op2; char op; cout << "Introduca due numeri interi: "; cin >> op1 >> op2; cout << "Introduca l'operatore (+, -, *, /): "; cin >> op; switch (op) { case '+': cout << op1 + op2 << '\n'; break; case '-': cout << op1 - op2 << '\n'; break; case '*': cout << op1 * op2 << '\n'; break; case '/': cout << op1 / op2 << '\n'; break; default : cout << "errore! \n"; } }

4.8.


Copyright © 2008 – The McGraw-Hill Companies srl Un possibile programma è: #include <iostream> #include <cmath> #define PI 3.141592 using namespace std; int main() { float a, b, h, angolo; cout << "Introduca la misura dei due cateti: "; cin >> a >> b; if ((a <= 0) || (b <= 0)) cout << "nessuna soluzione \n"; else { h = sqrt(a * a + b * b); angolo = 180 / PI * asin( a / h ); // angolo in gradi cout << " ipotenusa = " << h << endl; cout << " angolo 1 = " << angolo << endl; cout << " angolo 2 = " << 90 - angolo << endl; } } Una possibile esecuzione potrebbe essere: Introduca la misura dei due cateti: 23 45 ipotenusa = 50.5371 angolo 1 = 27.0721 angolo 2 = 62.9279

4.9. 2 4 6 8

4.10.

a) Ciao 10 Ciao 8 Ciao 6 Ciao 4 Ciao 2 b) 2 1.5 1 0.5

4.11.


Copyright © 2008 – The McGraw-Hill Companies srl a) 1 b) 2 c) loop infinito perchè l'if non aggiorna mai l'indice i

4.12.

a) * * * * * * * * * * b) * * * * * * * * * * * * * * *

4.13. 2 3 5 9 3 4 6 10 4 5 7 11 *****

4.14. #include <iostream> using namespace std; int main() { int n, i=1, somma=0; do { cout << "inserisca il valore di n (>0): "; cin >> n; } while (n <= 0); while ( i <= n ) {


Copyright © 2008 – The McGraw-Hill Companies srl somma += i; i++; } cout << " la somma vale " << somma << endl; return 0; } Una possibile esecuzione potrebbe essere: inserisca il valore di n (>0): -2 inserisca il valore di n (>0): -1 inserisca il valore di n (>0): 5 la somma vale 15

4.15. #include <iostream> using namespace std; int main() { for (int i = 1; i < 5; i++) { for (int j = 1; j <= i; j++) if (j != 1) cout << "??" << j; else cout << j; cout << endl; } for (int i = 4; i > 0; i--) { for (int j = 1; j <= i; j++) if (j != 1) cout << "??" << j; else cout << j; cout << endl; } }

4.16. #include <iostream> #define MAX 10 using namespace std; int main() { int pos=0, neg=0, nul=0, dato; for (int i=1; i<=MAX; i++) { cin >> dato; if (dato > 0) pos++; else if (dato < 0) neg++;


Copyright © 2008 – The McGraw-Hill Companies srl else nul++; } cout << "positivi negativi nulli " << endl; cout << " " << pos << " " << neg << " " << nul << endl; return 0; } Una possibile esecuzione potrebbe essere: 3 -4 -6 7 8 1 0 0 -8 -6 positivi negativi nulli 4 4 2

4.17. #include <iostream> using namespace std; int main() { int i, j, n; do { cout << "inserisca il valore di n (>0): "; cin >> n; } while (n <= 0); for (i=n; i>=1; i--) { cout << "1"; for (j=2; j<=i; j++) cout << "?" << j; cout << endl; } return 0; }

4.18. SUGGERIMENTO Il problema si risolve con tre cicli. Il primo è un ciclo do-while che convalida l'immissione di un


Copyright © 2008 – The McGraw-Hill Companies srl limite_massimo positivo. Il secondo è un ciclo do-while che convalida l'immissione di una base_intera positiva. Il terzo ciclo for è controllato dalla variabile potenza e stampa i valori richiesti. Esso inizializza potenza ad 1 e ad ogni iterazione ne moltiplica il valore per base_intera. La condizione di terminazione è potenza > limite_massimo.

4.19. #include <iostream> #define M 30 using namespace std; int main() { int i, somma=0; for (i=1; i<=M; i++) somma += 2 * i; cout << somma << endl; return 0; }

4.20. #include <iostream> #define PI 3.2141592 using namespace std; int main() { float raggio, superficie, volume; do { cout << "inserisca il valore del raggio (>0): "; cin >> raggio; } while (raggio <= 0); superficie = 4 * PI * raggio * raggio; volume = 4.0 / 3 * PI * raggio * raggio * raggio; cout << "la superficie ed il volume della sfera di raggio " << raggio << " sono:\n "; cout << "superficie: " << superficie << endl; cout << " volume: " << volume << endl; return 0; } Una possibile esecuzione potrebbe essere: inserisca il valore del raggio (>0): 5 la superficie ed il volume della sfera di raggio 5 sono: superficie: 321.416 volume: 535.693



4.21.

si definisce qui una funzione in linea (prossimo capitolo) f(x) #include <iostream> #include <cmath> // per la funzione cos #define M 5 #define f(x) cos(3 * x) - 2 * x using namespace std; int main() { for (double x = 0.0; x <= M; x +=0.5) cout << x << " " << f(x) << endl; return 0; }

4.22. SUGGERIMENTO Si inizializzi a 0 una variabile invertito. Si legga da tastiera in un ciclo do-while il valore di numero fintanto che esso non sia positivo. Si utilizzi un ciclo for per invertire le cifre del numero. Ad ogni iterazione si scriva in numero il quoziente della divisione intera di numero per 10. Se ad esempio il numero letto fosse 234 si avrebbe per le varie iterazioni 234, 23, 2 e 0. Ad ogni iterazione del ciclo si calcoli pure il resto della divisione intera di numero per 10. Per 234 avremmo 4, 3 e 2. Quindi per ottenere invertito basta notare che 432=4*10*10+3*10+2=(((0*10+4)*10+3)*10+2). Basta accumulare in invertito il valore di invertito moltiplicato per 10 e sommargli il resto della divisione intera.

4.23. SUGGERIMENTO L'algoritmo trasforma una coppi di interi positivi (maggiore,minore) in una coppia (minore, resto) dividendo ripetutamente il maggiore per il minore, rimpiazzando il maggiore con il minore ed il minore con il resto, fino a quando il resto diventa 0. A quel punto il corrispondente minore è il Massimo Comune Divisore cercato. Si legga da tastiera in un ciclo do-while i valori maggiore e minore fintanto che essi non siano entrambi positivi. Dopodiché, mediante un altro ciclo while si effettuino le divisioni e le trasformazioni indicate fintanto che resto è diverso da 0. A quel punto la variabile minore contiene il MCD cercato.

4.24. SUGGERIMENTO Si legga da tastiera in un ciclo do-while il valore di n fintanto che esso non sia positivo. I numeri sono introdotti dall'utente. Il primo introdotto inizializza le variabili maggiore, minore e somma. Si leggano


Copyright © 2008 – The McGraw-Hill Companies srl gli altri mediante un ciclo for aggiornando di volta in volta maggiore, minore e somma. Alla fine si scriveranno maggiore, minore e media, cioè somma/n.

4.25. #include <iostream> using namespace std; int main() { int i, n; float somma, massimo; do { cout << "inserisca il valore massimo (>0): "; cin >> massimo; } while (massimo <= 0); for (somma=0,i=0;somma <=massimo;) { i++; somma = somma + i * i - i - 2; } n = i; cout << "La somma vale " << somma << endl; cout << "numero dei termini " << n << endl; } Una possibile esecuzione potrebbe essere: inserisca il valore massimo (>0): 30 La somma vale 58 numero dei termini 6

4.26. #include <iostream> using namespace std; int main() { int d1, d2, d3, i, x; cout << "lista dei numeri che soddisfano la condizione\n"; for (i=100; i <=999; i++) { x = i; d1 = x % 10;


Copyright © 2008 – The McGraw-Hill Companies srl x = x / 10; d2 = x % 10; x = x / 10; d3 = x; if (d1*d1 + d2*d2 + d3*d3 == i/3) cout << "numero " << i << endl; } } Una possibile esecuzione potrebbe essere: lista dei numeri che soddisfano la condizione numero 116 numero 155 numero 267

4.27

SUGGERIMENTO Il problema si risolve tenendo presente che per calcolare la somma della serie basta venir accumulando in una variabile approssimato i valori di ogni termine, e che ciascuno di essi si ottiene dal precedente moltiplicandolo per x e dividendolo per i, dove i è il contatore che sta contando i termini che vengono sommati. Il termine di indice zero vale 1, il termine di indice 1 vale x, il termine di indice 2 vale x2/2! e così via. Quindi è conveniente inizializzare sia approssimato che termine ad 1. Il ciclo deve andare avanti 15 volte, come richiesto, per poi restituire il valore di approssimato.

4.28

SUGGERIMENTO Si legga da tastiera in un ciclo do-while il valore di massimo fintanto che esso non sia positivo. Per risolvere il problema si possono utilizzare due cicli for annidati. Il ciclo esterno percorre tutti i numeri n minori o uguali a massimo, quello interno decide se il numero n è perfetto. Esso utilizza un contatore i incaricandosi di trovare tutti i possibili divisori di n (quelli per cui il resto della divisione itera di n per i è 0) mettendoli in un accumulatore inizializzato a 0; se alla fine del ciclo interno l'accumulatore vale n allora il numero n è perfetto.

4.29 #include <iostream> using namespace std; int main() {


Copyright © 2008 – The McGraw-Hill Companies srl char c, primo='Z'; for (primo='Z'; primo >='A'; primo--) { for (c=primo; c >= 'A'; c--) cout << c << ' '; cout << endl; } }

4.30

SUGGERIMENTO Si legga da tastiera in un ciclo do-while il valore di n fintanto che esso non sia positivo. Per calcolare la somma della serie basta accumulare in una variabile somma (inizializzata a 0) i termini 1/(i*i*i) partendo da i=1 fino ad arrivare ad i=n.

4.31 #include <iostream> #include <cmath> #define VENTI 20 using namespace std; int main() { float somma=0; for (float i=1; i <= VENTI; i++) somma = i * i / pow(3,i); cout << "Il valore della somma è " << somma << endl; }

4.32

SUGGERIMENTO Un numero diverso da 1 è primo se i suoi unici divisori sono 1 e sé stesso. Un numero naturale contatore è divisore di numero ed è minore della sua radice quadrata, se e solo se esiste un altro numero naturale che è pure divisore di numero ed è maggiore della sua radice quadrata. Quindi per cercare i divisori di numero possiamo limitarci ai naturali minori della sua radice quadrata. Il programma si compone di un solo ciclo in cui si cerca un divisore di numero (maggiore di 1 letto da tastiera). Si inizializza una variabile booleana primo a true e si avvia un for controllato da contatore inizializzato a 2 ed incrementato di 1 fino a raggiungere la radice quadrata di numero. Se contatore



5.1

Utilizzando la funzione di libreria isdigit(c) e sapendo che esa restituisce un valore diverso da 0 se le si passa una cifra e restituisce 0 in qualuque altro caso, una possibile codifica è:

bool enumero(char c) { return isdigit(c); }

5.2. bool divisibile(int m, int n) { return m % n; }

5.3 int fahrenheit(int celsius) { return 9 * celsius / 5 + 32; }

5.4 bool vocale(char c) { if (isalnum(c) && !isdigit(c)) c = toupper(c); return (c=='A' || c=='E' || c=='I' || c=='O' || c=='U'); }

5.5 SUGGERIMENTO Si legga da tastiera in un ciclo do-while due numeri fintanto che non siano entrambi positivi. La funzione resto in primo luogo determina il maggiore ed il minore dei due num1 e num2. Mediante un accumulatore inizializzato a minore e mediante un ciclo while si somma ad accumulatore il valore di minore fino a quando il valore di accumulatore diventa maggiore di maggiore. A questo punto il resto deve essere il valore di maggiore meno il valore di accumulatore più il valore di minore.

5.6 int quoziente (int num1, int num2) { int c=0, acc = num2; while (acc <= num1) {


Copyright © 2008 – The McGraw-Hill Companies srl acc += num2; c++; } return c; }

5.7

SUGGERIMENTO Il programma principale legge il valore di n e chiama funzioney. Essa consiste in un ciclo di for che mette nella variabile x il valore funzioney(n-3), in y il valore funzioney(n-2) ed in z il valore funzioney(n-1). Per calcolare il valore funzioney(n) basta assegnare aus=x+3*y-z e riassegnare i nuovi valori x, y e z per la successiva iterazione.

5.8 bool perfetto (int n) { int i, acc = 0; for (i=1; i<n; i++) if (n % i == 0) acc += i; return (acc == n); }

5.9

SUGGERIMENTO Usare la libreria cmath. Esiste una funzione apposita che legge i gradi e li trasforma in radianti

5.10

bool NumeroPrimo(int n) { int i=2, lim=(int)sqrt(n); bool primo = true; while (primo && (i <= lim)) { primo = !(n % i == 0); i++; } return(p); }


Copyright © 2008 – The McGraw-Hill Companies srl 5.11

SUGGERIMENTO Una funzione menu deve gestire le opzioni 1-4. Il programma principale chiama la funzione menu, legge i dati e chiama le 3 funzioni. Si itera un ciclo for che termina quando menu restituisce l'opzione 4.

La funzione aa calcola l'annualità di capitalizzazione data da: a a= cr�1�r��1 �� r�t− 1

La funzione cc calcola il capitale residuo dato da: cc= a�1�r��1�r�t− 1r �

La funzione tt calcola il numero di anni: t t =log�1� cr

a�1�r��

�

�1�rlog

5.12

SUGGERIMENTO Bisogna utilizzare la funzione fattoriale, che calcola il prodotto dei primi numeri naturali positivi.

Quindi la funzione combinatoria �ni�= n !

� . i !�n − i�!

5.13

SUGGERIMENTO La funzione polari trasforma le coordinate polari r e teta in coordinate cartesiane x ed y mediante le corrispondenti formule. Il programma principale legge i valori dell'angolo teta e del modulo positivo r e li passa alla funzione polari che stampa le corrispondenti coordinate cartesiane x ed y.

5.14

SUGGERIMENTO Una funzione menu deve gestire le opzioni 1-4. Il programma principale chiama la funzione menu, legge i dati e chiama le 3 funzioni.

5.15

SUGGERIMENTO Per il MCD si veda l'esercizio 4.23. Per il mcm si tenga presente che dati due numeri a e b, MCD(a,b)*mcm(a,b)=a*b.



SUGGERIMENTO Le frazioni si appresentano con due numeri naturali, il numeratore ed il denominatore, essendo quest'ultimo diverso da 0. La funzione leggifrazioni legge due frazioni chiamando la funzione leggef. La funzione leggef legge una funzione assicurandosi che il denominatore sia diverso da 0 e che entrambi siano numeri primi; altrimenti chiama la funzione semplificaf che divide numeratore e denominatore per il loro MCD (esercizio precedente). La funzione scrivif riceve i due numeri come parametri e visualizza la funzione.

5.17

SUGGERIMENTO Una funzione menu deve gestire le varie opzioni. Il programma principale chiama la funzione menu, legge i dati e chiama le funzioni definite nei due precedenti esercizi. Le quattro funzioni prendono in input quattro numeri che saranno i due numeratori ed i due denominatori delle due frazioni, ed accetteranno anche altri due parametri riferimento per restituire in output il numeratore ed il denominatore della funzione risultante.

5.18

SUGGERIMENTO La formula che calcola i valori di sen(x) si può anche ottenere sommando un sufficiente numero di termini della seguente serie: sen(x) = t1 + t3 + t5 + t7 + t9 + ...

dove t 1= x � e 2

t i=−x

i�i− 1�t i−2 �

Il ciclo che controlla la sommatoria si potrà fermare dopo 20 iterazioni oppure dopo che il successivo termine da sommare è inferiore ad un dato valore assoluto passato come parametro.

5.19

SUGGERIMENTO La formula che calcola i valori di cos(x) si può anche ottenere sommando un sufficiente numero di termini della seguente serie: cos(x) = t0 + t2 + t4 + t6 + t8 + ...

dove t 0= 1 � e 2

t i=−x

i�i− 1�t i−2 �

Il ciclo è analogo a quello per la funzione sen(x) ma cambiano l'inizializzazione del termine term e dell'accumulatore somma. float coseno(float x, float error) { float term=1.0, somma=1.0, xx=x*x; int i=0;



6.1

L'output dipende ovviamente dall'input. Vengono letti 6 numeri e ne vengono scritti in output solo 3, quelli che occupano le posizioni 6, 4 e 2. Per esempio, se vengono immessi 3 7 4 -1 0 6 verranno stampati 6 -1 7.

6.2

L'output dipende ovviamente dall'input. Col primo ciclo il programma riempie il vettore Primo[] con i valori 3, 4, 5, ..., 11, 12 nelle posizioni 0, 1, 2, ..., 9. Se l'input fosse per esempio 8 3, il programma non stamperà nulla poichè il secondo ciclo partirebbe da 8 che è già superiore a 3, e quindi non partirebbe per nulla. Se i dati immessi fossero invece 3 8, allora il programma scriverebbe il contenuto delle posizioni 3, 4, 5, 6, 7 e 8 di Primo[], cioè i valori 6, 7, 8, 9, 10 e 11. Se il secondo dato immesso invece che 8 fosse maggiore di 9, allora verrebbero scritti in output valori imprevedibili corrispondenti agli elemnti di memoria successivi a quelli allocati all'array Primo[].

6.3

Il primo ciclo riempie il vettore Primo[] dalla posizione 0 alla posizione 10 con i primi undici numeri pari: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22. Il secondo ciclo riempie il vettore Secondo[] dalla posizione 0 alla posizione 5 con i numeri: 2, 7, 12, 17, 22, 27. Il terzo ciclo stampa in output i valori delle posizioni 4, 5 e 6 del vettore Primo[], e 2, 3 e 4 del vettore Secondo[], alternati ed andando dopo ogni coppia a capo, cioè: 10 12 12 17 14 22

6.4 #include <iostream> #define MAX 10 using namespace std; int main() { int i, vettore[MAX]; for (i=0; i<MAX; ) vettore[i++] = 2*i + 1; for (i=0; i<MAX; i+=2) cout << vettore[i] << ' '; cout << endl; }


Copyright © 2008 – The McGraw-Hill Companies srl la stampa produce: 1 5 9 13 17

6.5 SUGGERIMENTO Si definisca una costante MAX=10. Dopo aver dichiarato il vettore, con un primo ciclo vi si introducano i dati letti da tastiera, mentre con un secondo ciclo si sommino i dati del vettore in un accumulatore inizializzato a 0 per poi calcolare anche la media dividendo per MAX

6.6 bool vettore_simmetrico (float v[], int n) { bool simmetrico=true; for (int i=0; i<=n/2 && simmetrico; i++) if (v[i] != v[n-1-i]) simmetrico=false; return simmetrico; }

6.7 bool vettore_maggioritario (float v[], int n) { int nvolte, nvoltemassimo=0; for (int i=0; i<=n/2; i++) { nvolte = 1; for (int j=i+1; j<n; j++) if (v[i] == v[j]) nvolte++; if nvolte > nvoltemassimo) nvoltemassimo=nvolte; } return (nvoltemassimo > n/2); }

6.8

SUGGERIMENTO Per la funzione che calcola il prodotto scalare si utilizzi un ciclo for controllato da un contatore i inizializzato a 0 che termini quando i=n-1. Ad ogni iterazione si accumuli su acc (pure inizializzato a 0) il valore di a[i]*b[i]. Alla fine essa restituisca acc. La funzione norma di a[] non è altro che la radice quadrata del prodotto scalare a[]*a[]. Il coseno è il quoziente fra il prodotto scalare dei due vettori ed il prodotto della norma di a[] per la norma di b[].

6.9

SUGGERIMENTO Si usi la soluzione del problema 5.10 all'interno di un ciclo while che inizi dal contatore i inizializzato a


Copyright © 2008 – The McGraw-Hill Companies srl 2 ed incrementato ad ogni ciclo di 1. Ogni volta che si trova un numero primo si incrementi di 1 il contatore primi e lo si scriva in output. Si esca dal ciclo while quando primi=100.

6.10

SUGGERIMENTO Si definisca nel main un vettore di MAX elementi, con MAX costante definita. Si definisca una funzione aleatorio per riempire in maniera casuale i MAX elementi del vettore. Dopo aver calcolato la media, la deviazione media accumula in acc i valori fabs(a[i]-media); il valore finale di acc si divide poi per MAX. La funzione per il calcolo della deviazione tipica è simile, con la differenza che si accumula il valore (a[i]-media)*(a[i]-media), dividendo poi per MAX e calcolando la radice quadrata.

6.11 #define MAX 11 void trasposta (float a[][max], int n) { float aux; for (int i=0; i<n; i++) for (int j=0; j<i; j++) { aux = a[i][j]; a[i][j] = a[j][i]; a[j][i] = aux; } }

6.12

SUGGERIMENTO Si suppone che la matrice non abbia elementi ripetuti. La funzione riceve come paramentro la matrice di reali a[MAX][MAX]. Un primo ciclo scandisce le colonne della matrice, mentre un ciclo interno scandisce la colonna alla ricerca del suo elemento maggiore riportandone l'indice di riga. Successivamente si controlla se tale elemento sia anche il minore della sua riga, caso in cui avremo trovato una sella e se ne visualizzeranno le coordinate.

6.13

SUGGERIMENTO Il problema si risolve con queste funzioni:

successivo(int i, int n) dove 0 <= i <= n-1. La funzione restituisce il valore i+1, a meno che esso non sia uguale ad n, caso in cui la funzione restituisce 0.

precedente(int i, int n) dove 0 <= i <= n-1. La funzione restituisce il valore i-



1, a meno che esso non sia uguale a -1, caso in cui la funzione restituisce n-1. quadrato calcola il quadrato magico secondo il successivo algoritmo:

Si azzera tutta la matrice. Si inizializzano gli indici di riga i=0 e colonna j=n/2. Mediante un ciclo che parte da 1 si collocano i valori in ordine crescente fino a n*n in

questo modo: se l'elemento i,j vale 0 si ricalcola la riga con la funzione precedente e la

colonna con la funzione successivo se l'elemento i,j non vale 0 si ricalcola la riga con la funzione successivo e

la colonna con la funzione precedente, si colloca l'elemento nella nuova posizione e si ricalcolano gli indici di riga e colonna rispettivamente con le funzioni precedente e successivo

6.14

SUGGERIMENTO Si deve realizare una funzione che prende come parametri la matrice quadrata a[][] e la dimensione n e calcoli il maggiore ed il minore. Si inizializzano sia il maggiore che il minore all'elemento a[0][0] così come i rispettivi indici. Due cicli annidati scorrono tutta la matrice comparando ,elemento corrente con il maggiore ed il minore correnti, rimpiazzandoli se l'elemento corrente è rispettivamente maggiore o minore di essi. Alla fine si presentano le coordinate del maggiore e del minore con i rispettivi valori.

6.15 bool matrice_simmetrica (float a[][MAX], int n) { bool simmetrica = true; for (int i=0; i<n && simmetrica; i++) for (int j=0; j<i && simmetrica; j++) if (a[i][j] != a[j][i]) simmetrica = false; return simmetrica; }

6.16

SUGGERIMENTO Visualizzeremo il triangolo di Pascal in questa forma: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 Dichiariamo sia il vettore che la matrice di lunghezza massima MAX=11.



la funzione principale main() dichiara la matrice ed il vettore, legge l'ordine in ciclo do-while validandolo e chiama le funzioni

la funzione Triangolo2Dimensioni ha come parametri la matrice[][] e l'intero ordine e calcola il triangolo di Pascal di quell'ordine passato come parametro. Il triangolo di Pascal va sopra la diagonale della matrice mediante due cicli annidati. Il ciclo esterno controllato da i itera da 0 ad n-1, quello interno controllato da j itera da 0 ad i. matrice[i][j] prende il valore 1 se j==0 oppure i==j, negli altri casi matrice[i][j] = matrice[i-1][j-1] + matrice[i-1][j]

la funzione StampaTriangolo2Dimensioni prende come parametri la matrice[][] ed il parametro ordine e stampa il triangolo di Pascal contenuto nella matrice[][]

la funzione Triangolo1Dimensione ha come parametri il vettore[] e l'intero ordine e calcola e stampa il triangolo di Pascal contenuto nel vettore[].

6.17

SUGGERIMENTO Si dichiara un vettore vocali di cinque interi inizializzati a 0 che serve per contare le vocali all'interno di un ciclo controllato dal contatore i. I contatori nparole ed nlinee vengono utilizzati all'interno di due cicli innestati; l'esterno termina alla fine del flusso di input (Ctrl-Z), mentre l'interno aggiorna nlinee ogni volta che incontra un /n.

6.18 #include <iostream> using namespace std; bool palindroma(string); int main() { string s; cout << "Immetti una stringa: "; while (getline(cin,s)) { cout << "La stringa \"" << s; if (palindroma(s)) cout << "\" è palindroma!\n"; else cout << "\" non è palindroma.\n"; cout << "Immetti un'altra stringa: "; } } bool palindroma(string s) { string ss=s; int k=0; for (int i=0; i<s.length(); i++) // estrae k caratteri if (isalpha(s[i])) ss[k++]=toupper(s[i]); s = ss.substr(0,k); // adopera solo i primi k caratteri for (int i=0; i<k/2; i++) if (ss[i] != ss[k-1-i]) return false; return true; }



6.19

SUGGERIMENTO Per risolvere il problema si usa la base 10 come base intermedia e si suppone che il numero ricevuto come parametro stia in un long int. Per trasformare il numero espresso in base1 letto in una stringa di caratteri dall'input nello stesso numero in altra base2 scritto in un'altra stringa in output basta chiamare le funzioni: numero=valoreBase10(input,base1) che trasforma input al numero espresso in base 10 e, successivamente, chiamare la funzione cambiobase(numero,base2,output) che trasforma il numero in base 10 alla stringa di caratteri rappresentante lo stesso numero in base2.

6.20

SUGGERIMENTO Definire una variabile c di tipo char ed vettore di contatori inizializzato tutto a 0. In un ciclo while(cin >>c) aumentare di 1 il contatore di indice c-'A' se la lettera in c è maiuscola.

6.21

SUGGERIMENTO Definire due stringhe, s ed aux, la prima per leggere la frase in input, la seconda per collocarci ogni parola estratta da s. Il ciclo while termina quando finiscono le lettere in s. Questo ciclo è controllato dal contatore c inizializzato a 0 che indica la posizione del carattere in s che si sta trattando. Dentro questo ciclo ce n'è un altro che deve estrarre da s la parola, metterla in aux ed elaborarla.



7.1

enum stagioni {primavera=1, estate=2, autunno=3, inverno=4};

7.2 enum stagioni {primavera=1, estate=2, autunno=3, inverno=4}; stagioni LeggeStagione() { int stag; cout << "Introduca il numero della stagione dell'anno: \n"; cout << "1-primavera \n"; cout << "2-estate \n"; cout << "3-autunno \n"; cout << "4-inverno \n"; cin >> stag; switch (stag) { case 1: return primavera; case 2: return estate; case 3: return autunno; case 4: return inverno; default: cout << "Immissione errata!\n"; } }

7.3 void ScriviStagione(stagioni s) { switch (s) { case primavera: cout << "Primavera\n"; case estate: cout << "Estate\n"; case autunno: cout << "Autunno\n"; case inverno: cout << "Inverno\n"; } }

7.4

enum mese {gennaio=1, febbraio=2, marzo=3, aprile=4, maggio=5, giugno=6, luglio=7, agosto=8, settembre=9, orrobre=10, novembre=11, dicembre=12};


Copyright © 2008 – The McGraw-Hill Companies srl 7.5 Non si può inizializzare una variabile struttura se non è globale o statica. Non si può usare lo stesso identificatore per due variabili (un identifictore ed un array di caratteri nel nostro caso). La dimensione del vettore deve essere specificata; VERSIONE CORRETTA #include <iostream> using namespace std; struct data { int g,m,a; char mese[10]; } ff = {1,1,2000,"gennaio"}; void scrive(data f); int main() { scrive(ff); return 1; }

7.6

permette di dare nuovi nomi a tipi di dato già esistenti

7.7

SUGGERIMENTO Si definisce una struttura secondo le specifiche del problema si definisce un array di 100 di queste strutture. Dopodichè si fa partire un ciclo for per leggere i dati dall'input e metterli nelle 100 strutture. .

7.8

SUGGERIMENTO basta fare una funzione che prende in input l'array e lo esamina in un ciclo for alla ricerca dei clienti morosi.

7.9

SUGGERIMENTO Stesso suggerimento dell'esercizio precedente

7.10

SUGGERIMENTO Si tratta di leggere e visualizzare strutture annidate mediante due funzioni. Innanzitutto si dichiara la


Copyright © 2008 – The McGraw-Hill Companies srl struttura data con gli attributi ovvi. Poi si dichiara la struttura persona con i suoi campi ed infine la struttura impiegato. La funzione immetti ha come parametro riferimento i di tipo impiegato e stampa le informazioni in essa contenute.

7.10

SUGGERIMENTO Si tratta di leggere e visualizzare strutture annidate mediante due funzioni. Innanzitutto si dichiara la struttura data con gli attributi ovvi. Poi si dichiara la struttura persona con i suoi campi ed infine la struttura impiegato. La funzione immetti ha come parametro riferimento i di tipo impiegato e stampa le informazioni in essa contenute.

7.11

SUGGERIMENTO Un numero complesso è una coppia di numeri reali, uno dei quali rappresenta la sua parte reale e l'altro la sua parte immaginaria. Normalmente si rappresentano così: reale,immaginaria*i. Viene naturale rappresentarlo come una struttura con appunto due campi: reale e immaginaria. Le funzioni aritmetiche sui numeri complessi sono le seguenti: (a, bi) + (c, di) = (a + c), (b + d)i (a, bi) - (c, di) = (a - c), (b - d)i (a, bi) * (c, di) = (a*c - b*d),(b*c + a*d )i (a, bi) / (c, di) = (a*c + b*d)/(b2+d2) (b*c - a*d )/(b2+d2)i

7.12

SUGGERIMENTO realizzare le funzioni in maniera che prendano i parametri come riferimento (per poterli modificare).

7.13

SUGGERIMENTO Per passare dalla forma binomiale a quella polare si usa la seguente trasformazione: il modulo è dato dalla radice quadrata della somma dei quadrati delle parti reale ed immaginaria, mentre l'angolo è l'arco tangente del rapporto fra la parte reale e quella immaginaria.

7.14

SUGGERIMENTO realizzare le funzioni in maniera che prendano i parametri come riferimento (per poterli modificare).

7.15

SUGGERIMENTO si definisca prima una struttura giocatore con i campi comuni sia a giocatori di basket che di calcio. Poi due strutture cestista e calciatore che annidino la precedente.

7.16

SUGGERIMENTO


Copyright © 2008 – The McGraw-Hill Companies srl La funzione miglior_triplista prende in input l'array della squadra di basket e lo percorre alla ricerca del miglior realizzatore di tripli. La funzione capocannoniere prende in input l'array della squadra di calcio e lo percorre alla ricerca del miglior realizzatore. Come gestire i parimerito?

7.17

SUGGERIMENTO Si definisca una struttura con due campi di tipo numero reale che rappresentano le coordinate cartesiane di un punto. Si scrivano le seguenti funzioni:

legge che non ha parametri, legge semplicemente le coordinate dall'input e restituisce la struttura di tipo punto

distanza prende due punti in input e restituisce il numero reale dato dalla distanza cartesiana (radice della somma dei quadrati delle differenze fra le coordinate)

puntomedio prende due punti in input e restituisce il numero reale dato dalla semisomma delle coordinate

7.18

SUGGERIMENTO La funzione indirizzo_IP prende come parametro il long int d e lo mette in una unione oppure un array di 4 unsigned char (unsigned per non far considerare negativo il carattere con il primo bit settato). Ciascuno Di questi 4 caratteri si può poi stampare come numero naturale intervallandoli con un punto.

7.19

SUGGERIMENTO Si definisca una struttura libro con i campi necessari per catalogare un libro. La biblioteca sarà un array di define MAX 100 libro e la variabile int totale da il numero di libri nella biblioteca. La funzione legge_inventario riceve come parametri per riferimento l'array di libri e totale, inizializza quest'ultima a 0 e l'incrementa ogni volta che legge un libro dall'input.



8.1

int& y; // il riferimento deve essere inizializzato

char* c = 'C'; // 'C' è un carattere, non un vettore di caratteri

VERSIONI CORRETTE

int& y = z;

char* c = "C";

8.2

il puntatore a costante punta una costante (si può modificare il suo valore ma non quello dell'oggetto puntato) il puntatore dichiarato come costante punta un oggetto qualunque che potrà essere modificato mediante il puntatore (ma non si potrà modificare il puntatore)

8.3

Il nome di un vettore è un puntatore al primo elemento del vettore, quindi è un puntatore che punta il tipo degli elementi del vettore. La matrice è un vettore di vettori di un certo tipo di elementi. Il nome di una matrice è un puntatore al primo elemento del vettore di vettori di un certo tipo di elementi, quindi è un puntatore che punta il tipo vettore di quel tipo di elementi.

8.4 for (f=0; f<N; f++) { for (c=0; c<M; c++) cout << *((*(mt + f)) +c) cout << '\n'; }

8.5 double* minore_vettore(double* a, int n) { int i; double minore = a[0]; double* indirizzo_minore = a[0]; for (i=o; i<n; i++) if (a[i] < minore) { indirizzo_minore = &a[i]; minore = a[i]; } return indirizzo_minore;


Copyright © 2008 – The McGraw-Hill Companies srl }

8.6

Dopo l'istruzione return ci deve essere il punto e virgola. Nel ciclo for ci deve essere un errore semantico, poichè il test dell'if non viene mai modificato. La versione coretta dovrebbe essere: double* gorta(double* v, int m, double k) { int j; for (j=0; j<m; j++) if (*v == k) return v; else v++; return 0; }

la prima chiamata è corretta perchè ad un puntatore void si può assegnare qualunque puntatore la seconda è sintatticamente corretta la terza è scorretta perchè ad una variabile double non si può assegnare un puntatore a double

8.7

SUGGERIMENTO Si definisce una struttura persona secondo le specifiche del problema. Le due funzioni richieste devono avere entrambe un parametro di tipo puntatore a persona ai cui membri si accederà mediante ->.

8.8

SUGGERIMENTO Una matrice è simmetrica se ogni suo elemento è uguale al simmetrico rispetto alla diagonale principale. #include <iostream> #include <cstdlib> #include <ctime> using namespace std; float matrice[2][2]; bool MatriceSimmetrica(float mat[][2], int rig, int col) { for (int i=0; i<rig; i++) for (int j=0; j<col; j++) if (*((*(mat + i)) + j) != *((*(mat + j)) + i)) return false; } void RiempiMatrice(float mat[][2], int rig, int col) { int seed = static_cast<int>(time(0));


Copyright © 2008 – The McGraw-Hill Companies srl srand(seed); for (int i=0; i<rig; i++) for (int j=0; j<col; j++) *((*(mat + i)) + j) = rand() % 3; } void StampaMatrice(float mat[][2], int rig, int col) { for (int i=0; i<rig; i++) { for (int j=0; j<col; j++) cout << *((*(mat + i)) + j) << ' '; cout << endl; } } int main() { RiempiMatrice(matrice,2,2); if (MatriceSimmetrica(matrice, 2, 2)) { StampaMatrice(matrice,2,2); cout << "Simmetrica" << endl; } else { StampaMatrice(matrice,2,2); cout << "Asimmetrica" << endl; } return 0; }

8.9 #include <iostream> #include <cstdlib> #include <ctime> using namespace std; float matrice[4][5]; int colonna; float SommaProdottiColonna(float mat[][5], int col) { float acc = 0.0; for (int i=0; i<col; i++) acc += *(*(mat + i)) * *((*(mat + i)) + col -1); return acc; } void RiempiMatrice(float mat[][5], int rig, int col) {


Copyright © 2008 – The McGraw-Hill Companies srl int seed = static_cast<int>(time(0)); srand(seed); for (int i=0; i<rig; i++) for (int j=0; j<col; j++) *((*(mat + i)) + j) = rand() % 3; } void StampaMatrice(float mat[][5], int rig, int col) { for (int i=0; i<rig; i++) { for (int j=0; j<col; j++) cout << *((*(mat + i)) + j) << ' '; cout << endl; } } int main() { RiempiMatrice(matrice,4,5); cout << "Con quale colonna vuole moltiplicare la prima?"; cin >> colonna; cout << "La somma dei prodotti è " << SommaProdottiColonna(matrice,colonna) << endl; StampaMatrice(matrice,4,5); return 0; }

8.10

SUGGERIMENTO LA funzione scambiarighe riceve gli indici delle due righe che deve scambiare e, mediante un ciclo itera su tutte le colonne scambiando in esse gli elementi corrispondenti agli indici di riga ricevuti in input.

8.11

SUGGERIMENTO triviale

8.12

SUGGERIMENTO Per caricare in memoria il testo nominare linea (con typedef) il tipo char*. Così facendo si può dichiarare testo_input come puntatore a linea (cioè a puntatore a char). Si allocherà poi dinamicamente memoria per la matrice che conterrà il testo letto in input così: testo_input = new linea[20]

8.13

SUGGERIMENTO


Copyright © 2008 – The McGraw-Hill Companies srl Definire una struttura tempo per il conteggio dei minuti e dei secondi.

8.14

SUGGERIMENTO Definire un array areafigura[] di puntatori a funzione contenente i nomi di ogni funzione.

8.15


8.16

SUGGERIMENTO Definire una funzione DaStringaANumero che prende in input la stringa di caratteri e restituisce il numero reale che essa rappresenta. Bisogna che essa salti gli spazi, riconosca il segno e la parte decimale. Basta leggere gli ASCII cifra dopo cifra e ricostruire il numero complessivo trasformandoli in numeri.

8.17

SUGGERIMENTO Si definisca un array di puntatori a funzione con un puntatore per ogni operazione aritmetica.



9.1

SUGGERIMENTO

p1=new int assegna l'indirizzo del nuovo int a p1. *p1=45 mette il valore 45 dentro il nuovo int. p2=p1 assegna a p2 l'indirizzo di p1. A questo punto *p2=54 cambia il valore del nuovo int da 45 a 54.

9.2

SUGGERIMENTO

*p1=*p2 assegna al nuovo int puntato da p1 il valore del nuovo int puntato da p2

9.3 #include <iostream> using namespace std; int main() { int* entrata; for (int i=0; ; i++) // ciclo infinito { entrata = new int[5012]; if (entrata == NULL) { cout << " memoria esaurita \n"; break; } cout << " assegnati " << i*10 << " KBytes \n"; } return 0; }

9.4 #include <iostream> using namespace std; int main() { int* entrata; entrata = new int[10]; for (int i=0; i<10 ; i++) cin >> entrata[i]; return 0; }

9.5


Copyright © 2008 – The McGraw-Hill Companies srl bottone* b; b = new bottone;

9.6 bottone* b; b = new bottone; cin >> b->codice; b->cartellino = new char[21]; // per esempio, stringa di 20 caratteri cin.getline(b->cartellino, 20);

9.7 #include <iostream> using namespace std; int main() { struct punto3D { char* nome; float x, y, z; }; punto3D* vettore3D; int n; cout << "Introduca n \n"; cin >> n; if ((vettore3D = new punto3D[n]) == NULL) { cout << "Errore assegnamento memoria dinamica \n"; exit(1); } }

9.8

SUGGERIMENTO La funzione LeggePunto3D restituisce come parametro riferimento le tre coordinate del punto ed il suo nome. Al nome (puntatore a char) si assegna dinamicamente memoria in base alla lunghezza del nome inserito dall'utente (per risparmiare memoria). La funzione LeggeVettorePunti3D restituisce nel vettore di n punti che riceve come parametro i dati richiesti effettuando n chiamate alla funzione che legge la struttura LeggePunto3D.



SUGGERIMENTO simile al problema precedente

9.10

SUGGERIMENTO La funzione distanza restituisce sqrt(x*x+y*y+z*z).

9.11


9.12


9.13

SUGGERIMENTO Qui abbiamo come struttura dati un vettore di puntatori a carattere. Serve per ottimizzare la memoria perché ogni linea letta in input viene allocata con la sola memoria che le serve.

9.14

SUGGERIMENTO triviale.

9.15


9.16

SUGGERIMENTO La funzione CopiaArray riceve sia il vettore v che il vettore copia come puntatori a double.

9.17

SUGGERIMENTO La funzione legge riceve un puntatore a float v come parametro riferimento perché possa assegnare dinamicamente memoria al vettore v.

9.18




SUGGERIMENTO Realizzare la funzione con l’aritmetica dei puntatori. Se p è un vettore di puntatori a real, allora *(p+i) è un puntatore a real, per cui *(*(p+i)) è il numero da sommare.

9.20 #include <iostream> using namespace std; typedef float* col; // col è sinonimo di puntatore a float void generamatrice(float** &m, int n) { m = new col[n]; for (int i=0; i<n; i++) m[i] = new float[n]; } int main() { int n; float** m; generamatrice(m, n); return 0; }

9.21

SUGGERIMENTO La funzione riceve come parametro la matrice m ed assegna aleatoriamente lo stesso valore a m[i][j] e m[j][i].

9.22

SUGGERIMENTO Semplice.

9.23

SUGGERIMENTO Semplice.



10.1

sono equivalenti nell'inizializzare una stringa di caratteri, meno la seconda che inizializza semplicemente un array di caratteri (non mette il byte nullo alla fine)

10.2

niente

10.3

la variabile c1 è un puntatore a puntatore di carattere; la c2 è un vettore di 10 puntatori a carattere; la c3 una matrice di 210 puntatori a carattere

10.4 #include <iostream> using namespace std; int main() { char s1[81], s2[81]; cout << "Introduca una stringa: "; cin.getline(s1,80); cout << "Introduca un'altra stringa: "; cin.getline(s2,80); cout << "Prima della concatenazione: \n"; cout << "s1 = \"" << s1 << "\", lunghezza = " << strlen(s1) << "\n"; cout << "s2 = \"" << s2 << "\", lunghezza = " << strlen(s2) << "\n"; strcat(s1, s2); cout << "Dopo la concatenazione: \n"; cout << "s1 = \"" << s1 << "\", lunghezza = " << strlen(s1) << "\n"; return 0; }

Una possibile esecuzione potrebbe essere: Introduca una stringa: sarebbe anche una bella giornata Introduca un'altra stringa: se non mi facesse male il dente!! Prima della concatenazione: s1 = "sarebbe anche una bella giornata", lunghezza = 32 s2 = "se non mi facesse male il dente!!", lunghezza = 33 Dopo la concatenazione: s1 = "sarebbe anche una bella giornatase non mi facesse male il dente!!", lunghezza = 65


Copyright © 2008 – The McGraw-Hill Companies srl 10.5 #include <iostream> #include <cstring> using namespace std; int main() { char s1[81]; cout << "Introduca una stringa: "; cin.getline(s1,80); strupr(s1); cout << "Stringa invertita: \n" << s1 << "\n"; return 0; };

10.6

Per trasformare una stringa di cifre che rappresenta un numero in esadecimale nel corrispondente long int si utilizzi il metodo di Horner di valutazione di un polinomio scritto in una certa base: “2345”16= (((0*16+2)*16+3)*16+4)*16+5

10.7

triviale

10.8

SUGGERIMENTO Utilizzare la funzione atoi() che trasforma una stringa formata da cifre decimali nel corrispondente int.

10.9

SUGGERIMENTO La funzione deve restituire tre valori che possono quindi essere appoggiati su tre parametri passati per riferimento. Si utilizzino le unzioni di libreria isupper, tolower e isdigit.

10.10

SUGGERIMENTO Utilizzare la funzione tolower().

10.11

SUGGERIMENTO Utilizzare la funzione cin.getline.

10.12

SUGGERIMENTO


Copyright © 2008 – The McGraw-Hill Companies srl Utilizzare la funzione strstr().

10.13

SUGGERIMENTO Utilizzare un vettore per contenere la lunghezza di ogni linea e la posizione iniziale che possiede nel testo (per poterle ordinare in output senza spostarle nel testo).

10.14

SUGGERIMENTO Dichiarare testo come vettore di stringhe di caratteri di lunghezza variabile. Dichiarare un puntatore a stringa di caratteri ptr da usare nella funzione strstr() per stabilire se la chiave letta è presente nella stringa.

10.15

SUGGERIMENTO Si calcoli la lunghezza della stringa letta, se ne determini la lunghezza e si allochi spazio opportuno per la sua inversa. Mediante un for che assegni inversa[lunghezza – i – 1]=stringa[i].

10.16


10.17

SUGGERIMENTO Per risolvere il problema si segua il seguente schema:

invertire le stringhe di caratteri e convertirle in stringhe di uguale lunghezza per poterle sommare da sinistra verso destra 487954558 invertito 855459784 235869 invertito 000968532

sommare le stringhe convertendo come passo intermedio i caratteri in numeri e convertendo di nuovo il risultato in stringa 487954558 855459784 235869 000968532 ____________________________________ 488190427 724091884

Prima di cominciare la somma si riserva spazio in memoria per il risultato della somma.

10.18

SUGGERIMENTO seguire il suggerimento precedente.

10.19


Copyright © 2008 – The McGraw-Hill Companies srl SUGGERIMENTO Usare le funzioni definite nei due problemi precedenti.

10.20

Si legge il testo linea dopo linea mettendo nella variabile maggiore la lunghezza della più lunga. Una volta terminata la lettura si riempiono di bianchi le linee per convertirle in stringhe di caratteri della stessa lunghezza.



11.1

L'ordinamento di una lista o un vettore è il processo per cui la disposione interna dati viene posta in sequenza secondo un criterio di ordinamento. La ricerca scorre la lista o il vettore alla ricerca di un particolare elemento ed ha lo scopo duplice di stabilire semplicemente se l'elemento cercato è presente de, eventualmente, in quale posizione all'interno della struttura dati.

11.2

prima iterazione 3, 8, 13, 25, 45, 23, 98, 58 seconda iterazione 3, 8, 13, 25, 45, 23, 98, 58 terza iterazione 3, 8, 13, 25, 45, 23, 98, 58 quarta iterazione 3, 8, 13, 23 ,25, 45, 98, 58

11.3

L'ordinamento per selezione cerca l'elemento più piccolo (o più grande) e lo mette nella posizione che gli compete. Quindi comincia col cercarlo in tutto il vettore per metterlo in posizione 0, poi cerca nel resto del vettore e lo mette nella posizione 1 e così via. L'ordinamento per inserzione parte da un vettore parzialmente ordinato fino alla posizione i-1 e decide dove mettere l'elemento che attualmente occupa la posizione i per aumentare la porzione di vettore ordinata.

11.4

Dopo la prima passata il metodo di ordinamento a bolle produrrebbe un vetore ordinato, pe cui non è lui. Ordinameno per selezione prima iterazione 3, 47, 21, 32, 56, 92 seconda iterazione 3, 21, 47, 32, 56, 92 Ordinameno per inserzione prima iterazione 3, 47, 21, 32, 56, 92 seconda iterazione 3, 21, 47, 32, 56, 92 quindi può essere uno di questi due.

11.5 Ricerca della chiave 88 prima iterazione, chiave centrale 26 26 < 88 ricerca in 44, 56, 88, 97 seconda iterazione, chiave centrale 56 56 < 88 ricerca in 88, 97 terza iterazione, chiave centrale 88 88=88 ricerca conclusa Ricerca della chiave 20 prima iterazione, chiave centrale 26


Copyright © 2008 – The McGraw-Hill Companies srl 26 > 20 ricerca in 8, 13, 17 seconda iterazione, chiave centrale 13 13 < 20 ricerca in 17 terza iterazione, chiave centrale 17 17<20 ricerca in ____ ricerca conclusa: elemento non trovato

11.6

Per ordinare in senso decrescente il vettore basta cambiare la condizione di confronto A[j]> A[indicemax].

11.7

Ad ogni iterazione si prende la posizione dell'elemento maggiore e lo si colloca nella posizione di indice n-1. Poi si cerca il maggiore fra i non collocati e lo si mette in posizione n-2 e così via.

11.8

SUGGERIMENTO Utilizzare l'ordinamento bubble-sort per ordinare ilo vettore e le funzioni di libreria seed e random per generare aleatoriamente i numeri positivi minori di 100.

11.9

SUGGERIMENTO In primo luogo si dichiara con typedef un sinonimo stringa di puntatore a char, e poi le variabili testo e testoaus come puntatori a stringa per mettervi dentro il testo letto e la copia da ordinare. Si alloca dinamicamente spazio in memoria per ciascuna delle due variabili da riempire con le funzioni incaricate di leggere e trasformare il testo. La funzione legge_testo assegna dinamicamente la lunghezza di ogni linea letta dall'input (per ottimizzare l'uso della memoria). La funzione trasforma_testo_in_testoordinato copia linea a linea testo in testoaus, così come il vettore lunghezze, che contiene le lunghezze di ogni linea. Per ordinare il vettore utilizzare l'inserimento diretto.



12.1

SUGGERIMENTO

Ispirarsi alla soluzione del problema 7.11, facendo però attenzione al sovraccaricamento dell'operatore di moltiplicazione, usato sia per la moltiplicazione fra due numeri complessi che per la moltiplicazione di un numero complesso per un numero reale.

12.2

Si rappresenti l'insieme con attributi numero_elementi, int che contiene la cardinalità dell'insieme, e un vettore di int L con al massimo 512 elementi. I numeri vengano collocati nel vettore in ordine crescente. Per facilitare l'inserimento e l'eliminazione dei numeri nell'insieme si scriva una funzione membro non pubblica cercare che cerchi un elemento passatole come parametro nell'insieme corrente per poterlo cassare se esiste già, o per poterlo inserire nella posizione che gli spetta se non è già presente nell'insieme. La funzione segua la ricerca binaria classica. Le altre funzioni si programmino come funzioni membro con costruttore e distruttore.



13.1

La classe base ha due funzioni; una virtuale, f, che è ridefinita nelle due classi derivate, ed un'altra non virtuale g che viene pure ridefinita nelle due classi derivate. Con le tre prime istruzioni del main si chiamano le funzioni della classe base. Con le successive tre istruzioni si chiama la funzione virtuale f ridefinita nella classe derivata1 e la funzione g della classe base. Con le successive tre istruzioni si chiama la funzione virtuale f ridefinita nella classe derivata2 e la funzione g della classe base.

Per eseguire la funzione g delle classi derivata1 oppure derivata2 bisogna scrivere d1.g() oppure d2.g() perché con le assegnazioni p=&d1 e p=&d2, essendo p un puntatore alla classe base, l'espressione p->g() accede alla funzione non virtuale della classe base.

13.2

SUGGERIMENTO La gerarchia di classi è praticamente ovvia. La classe Punto1D possiede un solo attributo che è la coordinata x del punto unidimensionale. La classe Punto2D eredita la coordinata x e le funzioni membro dalla classe Punto1D, ma aggiunge l'attributo y e le funzioni membro corrispondenti. La classe Punto3D a sua volta eredita gli attributi x ed y e le unzioni membro della classe Punto2D e aggiunge l'attributo z.

13.3

SUGGERIMENTO La classe astratta figura ha solo il costruttore e la dichiarazione delle funzioni virtuali perimetro ed area. Le classi derivate cerchio, quadrato e rettangolo aggiungono attributi raggio, lato, larghezza. Le funzioni virtuali perimetro ed area gestiranno gli attributi di ciascuna classe derivata.

13.4

SUGGERIMENTO La classe base sport deriva le altre come calcio, pallacanestro e pallavolo. La classe sport dichiara la funzione virtuale giocare, così come ciascuna classe derivata. Scrivendo sport* s[4] si dichiara un vettore di puntatori a sport. Successivamente si inizializza s[] ai vari sports. La chiamata s[i]->giocare(“Messi”) produce un link dinamico perché il compilatore non può sapere quale implementazione specifica della funzione giocare dovrà mandare in esecuzione all'atto della chiamata.



15.1

SUGGERIMENTO Si tratta di operazioni base per aprire un file in lettura o in scrittura. Controllare l'avvenuta apertura del file.

15.2


15.3

SUGGERIMENTO Si definisca un oggetto flusso della classe fstream che possa essere letto sia in scrittura che in lettura in modo binario. Si legga il testo dalla tastiera carattere a carattere (fino alla fine del lusso CTRL-Z) e lo si carichi nel file binario. Dopodiché si riapra il file binario in lettura per stamparlo in output carattere dopo carattere.



16.1

Supponiamo di aver definito le seguenti classi Nodo e ListaS: #include <iostream> using namespace std; typedef int Telemento; class Nodo { protected: Telemento e; Nodo* suc; public: Nodo(){} // costruttore vuoto Nodo(Telemento x); // costruttore Nodo(Telemento x, Nodo* s); // costruttore ~Nodo(){} // distruttore per default Telemento OE(); // Ottenere elemento void SE(Telemento e); // Stabilire elemento Nodo* Osuc(); // Ottenere successivo void Ssuc(Nodo *p); // Stabilire successivo }; Nodo::Nodo(Telemento x) { // costruttore che inizializza e ad x e suc a NULL e = x; suc = NULL; } Nodo(Telemento x, Nodo* s) { // costruttore che inizializza e ad x e suc ad s e = x; suc = s; } Telemento Nodo::OE() { // ottiene una copia dell’attributo e return e; } void Nodo::SE(Telemento x) { // stabilisce l’attributo e ad x e = x; }


Copyright © 2008 – The McGraw-Hill Companies srl Nodo* Nodo::Osuc() { // ottiene una copia dell’attributo suc return suc; } void Nodo:: Ssuc(Nodo *p) { // Stabilisce l’attributo suc a p suc = p; } class ListaS //classe lista semplicemente concatenata { protected: Nodo* p; public: ListaS(); // costruttore ~ListaS(); // distruttore Nodo* Op(); // Ottenere il puntatore void Sp(Nodo *p1); // Stabilire il puntatore // altre funzioni membro //...... }; ListaS::ListaS() { p = NULL; } ListaS::~ListaS(){}; Nodo* ListaS:: Op() { return p; } void ListaS:: Sp( Nodo *p1) { p = p1; } int main() { ListaS l1; return 0; } in questo caso le due funzioni membro richieste sono:


Copyright © 2008 – The McGraw-Hill Companies srl bool ListaS::E_LVuota() { return !p; } void ListaS::LVuota() { p = NULL; }

16.2

SUGGERIMENTO Per restituire il numero di nodi di una lista basta scorrerla e contarne i nodi dal primo all'ultimo. int ListaS::LunghezzaL() { Nodo* aus = p; int c = 0; while (aus) { c++; aus = aus->Osuc(); } return c; }

16.3

SUGGERIMENTO Per questa funzione membro bisogna puntare il primo nodo della lista per eliminarlo. void ListaS::EliminaTestaL() { Nodo* aus; if (p); // se contiene elementi eliminare il primo { paus = p; // nodo da eliminare p = p->Osuc(); // puntare il nodo da eliminare paus->Psuc(NULL); // porre il successivo a NULL delete paus; } else; // la lista e' vuota e non c'e' nulla da fare }



SUGGERIMENTO Si deve scorrere la lista con un puntatore ausiliario inizializzato alla testa della lista. void ListaS::VisualizzaL() { Nodo* aus = p; while (aus) { cout << aus->OE() << endl; // mostra il dato aus=aus->Osuc(); // scorre la lista } }

16.5

SUGGERIMENTO Se il primo elemento non è NULL lo si restituisce, altrimenti non si fa nulla. Telemento ListaS::TestaL() { if (p); return p->OE(); else; // la lista e' vuota e non c'e' nulla da restituire }

16.6

SUGGERIMENTO Supponiamo definite le due seguenti classi: class NodoD { protected: Telemento e; NodoD* suc; NodoD* ant; public: NodoD(Telemento x); // costruttore Telemento OE(); // Ottenere elemento void SE(Telemento e); // Stabilire elemento NodoD* Osuc(); // Ottenere successivo void Ssuc(NodoD* p); // Stabilire successivo NodoD* Oant(); // Ottenere precedente void Sant(NodoD* p); // Stabilire precedente };


Copyright © 2008 – The McGraw-Hill Companies srl NodoD::NodoD(Telemento x) { e = x; suc = NULL; ant = NULL; } Telemento NodoD::OE() { return e; } void NodoD::SE(Telemento x) { e = x; } NodoD* NodoD::Osuc() { return suc; } void NodoD:: Ssuc(NodoD* p) { suc = p; } NodoD* NodoD::Oant() { return ant; } void NodoD:: Sant(NodoD* p) { ant = p; } e la classe: class ListaD //classe lista doppiamente concatenata { protected: NodoD* p; public: ListaD(){p = NULL;} // costruttore ~ListaD(){}; // distruttore NodoD* Op(){return p;} // Ottenere il puntatore


Copyright © 2008 – The McGraw-Hill Companies srl void Sp(NodoD* p1){p = p1;} // Stabilire il puntatore // altre funzioni membro //...... }; Allora si crea un nuovo nodo di tipo NodoD e si pone l'attributo suc a p. Se la lista non è vuota si pone l'attributo ant del nodo putato da p a aus. Il primo nodo della lista è sempre quello aggiunto. void ListaD::AggiungiTestaLD(Telemento e) { NodoD* aus; aus = new NodoD(e); if (p); { aus->Ssuc(p); p->Sant(aus); } p = aus; }

16.7

SUGGERIMENTO Se la lista non è vuota il primo elemento si ottiene chiamando la funzione membro OE della classe NodoD. Telemento ListaD::Testa() { if (p) return p->OE(); else; // lista vuota }

16.8

SUGGERIMENTO Se la lista non è vuota si fa avanzare l'attributo che punta al primo elemento della lista doppia e si cancella quest'ultimo. Se la lista ha più di un elemento bisogna fare in modo che l'attributo ant del nodo putato da p punti a NULL. void ListaD::EliminaTesta() { NodoD* aus; if(p) { aus = p; p = p->Osuc();


Copyright © 2008 – The McGraw-Hill Companies srl if(p) p->Sant(NULL); delete aus; } else; }

16.9

SUGGERIMENTO Una possibile codifica è la seguente: bool ListaD::E_Vuota() { return !p }

16.10

SUGGERIMENTO Il costruttore di copia s'incarica di copiare la lista semplicemente concatenata che riceve come parametro in qualunque funzione che usi un oggetto della classe ListaS.

16.11

SUGGERIMENTO Il distruttore scorre tutti i nodi della lista mediante un puntatore a Nodo eliminandoli tutti.

16.12

SUGGERIMENTO La funzione membro aggiunge riceve come parametro un elemento x e lo inserisce in maniera ordinata. Si deve creare un nuovo nodo e, se sarà il primo lo si inserisce in testa, altrimenti si scorre la lista alla ricerca della posizione giusta e lo si inserisce in maniera opportuna.

16.13

SUGGERIMENTO Ovviamente bisogna scorrere tutta la lista eliminando però solo gli elementi che corrispondono all'elemento letto come parametro per valore.

16.14


16.15


Copyright © 2008 – The McGraw-Hill Companies srl SUGGERIMENTO

La funzione ordinare esegue il compito richiesto utilizzando quattro puntatori.

16.16

SUGGERIMENTO La funzione mezclar riceve come parametri due oggetti l1 e l2 di tipo ListaS ordinati in maniera crescente e li fonde nell'oggetto l3 pure ordinato.

16.17

SUGGERIMENTO La funzione segue da vicino quella proposta per l'esercizio16.10

16.18

SUGGERIMENTO Se la lista è vuota basta assegnare a p il puntatore ausiliario Se si inserisce come primo elemento e non ultimo bisogna porre l'elemento successivo di aus a p, l'antecedente di p ad aus e p ad aus. Se lo si inserisce come ultimo e non primo bisogna porre il successivo di ant ad aus e l'antecedente di aus ad ant. Se lo si inserisce al centro della lista bisogna porre il successivo di aus in suc, l'antecedente di aus in ant, il successore di ant in aus e l'antecedente di suc in aus. 16.19 SUGGERIMENTO Se l'elemento è il primo e l'ultimo della lista porre p a NULL Se l'elemento è il primo e non l'ultimo porre p al successivo di suc e l'antecedente di p a NULL Se l'elemento è l'ultimo e non il primo porre il successivo di ant a NULL Se l'elemento non è né il primo né l'ultimo porre il successivo di ant al successivo di suc e porre l'antecedente del successore di suc ad ant. Dopo aver riallacciato i puntatori si può eliminare l'elemento. 16.20 SUGGERIMENTO Per copiare una lista doppiamente allacciata puntata da ld nella lista doppiamente allacciata puntata da ld1 si usano le funzioni membro della classe ListaD, utilizzate negli esercizi precedenti. 16.21 SUGGERIMENTO La lista circolare utilizza la stessa classe della lista semplice e le sue stesse funzioni membro. La lista circolare si ottiene facendo puntare p all'ultimo elemento della lista e facendo puntare il suo successivo al primo elemento. Quindi Testa() restituisce p->Osuc()->OE();



18.1

SUGGERIMENTO Si può definire ricorsivamente la funzione potenza an così: an=1 se n=0 an=a*an-1 negli altri casi Ovviamente questo vale solo per n positivi.

18.2

SUGGERIMENTO Il quoziente della divisione intera di n per m (essendo entrambi positivi) si calcola ricorsivamente così: se n<m allora quoziente(n, m)= 0 se n>=m allora quoziente(n, m)= 1 + quoziente(n – m, m).

18.3

SUGGERIMENTO Si tenga conto delle seguenti banali osservazioni: pari(n)= dispari(n-1) se n>1 pari(0)= true dispari(n)= pari(n-1) se n>1 dispari(0)= false

18.4

SUGGERIMENTO La somma delle cifre di un numero naturale si può calcolare ricorsivamente mediante l'espressione. SommaRicorsiva(n)= n mod 10 + SommaRicorsiva(n dic 10)se n>0 SommaRicorsiva(0)= 0

18.5

SUGGERIMENTO La funzione ha come parametri il vettore v, il valore b ed un parametro che serve per calcolare la somma dei primi n-1 elementi maggiori di b. SommaMaggioriB(v, b, 1) = 0 se v[0] <= b SommaMaggioriB(v, b, 1) = v[0] se v[0]> b SommaMaggioriB(v, b, n) = SommaMaggioriB(v, b, n-1) se v[n] <= b SommaMaggioriB(v, b, n) = SommaMaggioriB(v, b, n-1) + v[n] se v[n]> b

18.6

SUGGERIMENTO Si riferisca agli esercizi del capitolo dedicato alle liste semplici.



19.1

nel primo albero il nodo B ha tre figli, gli altri due hanno cammini multipli per uno stesso nodo

19.2

l'altezza è 4 l'albero binario è equilibrato perché la differenza di altezza massima fra i due sottoalberi è 1 i nodi foglia sono W, T, X, V INORDINE W S Q T P U X R V PREORDINE P Q S W T R U X V POSTORDINE W S T Q X U V R P

19.3

I INORDINE: E, M, R, T, Y

PREORDINE: M, R, Y, T, R POSTORDINE: E, R, T, Y, M

II INORDINE: E, M, R, T, Y

PREORDINE: R, E, M, Y, T POSTORDINE: M, E, T, Y, R

M T

E Y

R

R

T

E Y

M



III

INORDINE: E, M, T, R, Y PREORDINE: T, M, E, Y, R

POSTORDINE: E, M, R, Y, T

IV INORDINE: A, C, E, F, K, L, N, O, R, S

PREORDINE: C, A, O, N, F, E, L, K, R, S POSTORDINE: A, E, K, L, F, N, S, R, O, L

19.4

a b

C

O

T

Y M

R E

A

N R

F S

E L

K

+

+

/

- +

C B

A

B / D A

D C



c d

- *

/ +

+B

/A

- + A +

E F B - E F C D

C D

e

/

19.5

--

*B A /

D C F

/

--

*B A /

EE F C D



A

PD

QL Z F

19.6

SUGGERIMENTO Si dichiari Telemento come sinonimo del tipo di nodo dell'albero (nel nostro caso un int) . Si defnisca una classe Nodo in modo che la classe Albero dichiari un puntatore alla classe Nodo come protetto. La classe Albero ha come funzioni membro quella necessaria ad accedere alla radice dell'albero ed ai figli destro e sinistro, insieme col costruttore e col distruttore della classe stessa. La classe Nodo contiene come attributi privati il figlio sinistro e quello destro dei nodi dell'albero, insieme all'elemento informativo Telemento, dichiarando la classe Albero come amica per permetterle di accedere ai suoi attributi rendendo così più facile la scrittura del suo codice.

19.7

SUGGERIMENTO Il costruttore di copia si attiva ogni volta che avviene una chiamata ad un oggetto per valore. Esso fa una copia del parametro attuale arb. La programmazione ricorsiva è facile: se l'albero passato è vuoto (arb.a = NULL) l'oggetto attuale è vuoto; altrimenti si crea un nuovo Nodo che viene assegnato al puntatore a. Alla chiamata del costruttore di Nodo esso riceve come parametri i figli destro e sinistro del parametro e si attiva la copia ricorsivamente.

19.8

SUGGERIMENTO Per copiare l'oggetto attuale in un albero passato per riferimento basta creare un Nodo in cui si copi

RG H

WK


Copyright © 2008 – The McGraw-Hill Companies srl l'elemento della radice dell'oggetto, il figlio sinistro e quello destro.

19.9

SUGGERIMENTO basta creare un Nodo in cui si copi l'elemento della radice dell'oggetto, il figlio sinistro e quello destro.

19.10

SUGGERIMENTO Delle 6 possibili visite in profondità, SDR, SRD, DSR, DRS, RDS, RSD, prendiamo le SDR, SRD, RSD:

SRD o visita inordine; se l'albero è vuoto non si fa nulla; si visita ricorsivamente il figlio sinistro, poi si stampa la radice e quindi si visita ricorsivamente il figlio destro

RSD o visita preordine; se l'albero è vuoto non si fa nulla; si stampa la la radice, si visita ricorsivamente il figlio sinistro, e poi si visita ricorsivamente il figlio destro

SDR o visita postordine; se l'albero è vuoto non si fa nulla; si visita ricorsivamente il figlio destro, e poi si visita ricorsivamente il figlio sinistro e si stampa la la radice.

19.11

SUGGERIMENTO Se l'albero è vuoto il numero dei nodi è zero. Altrimenti il numero dei nodi è 1 più il numero dei nodi del figlio sinistro più il numero dei nodi del figlio destro.

19.12

SUGGERIMENTO vedi il suggerimento precedente

19.13

SUGGERIMENTO Se l'albero è vuoto il numero dei nodi è zero. Altrimenti, se il livello del nodo corrente è inferiore ad n, il numero dei nodi è 1 più il numero dei nodi del figlio sinistro che appartengano ad un livello inferiore ad n più il numero dei nodi del figlio destro che appartengano ad un livello inferiore ad n.

19.14

SUGGERIMENTO Basta visitare in una qualunque maniera l'albero e stampare i nodi che corrispondono alla condizione richiesta

19.15

SUGGERIMENTO Si implementino le due funzioni membro:

AggiungiARIC: se l'albero è vuoto si inserisca il nuovo nodo come foglia. Se non è vuoto, se l'inormazione del nuovo nodo coincide con quella della radice del nodo corrente bisogna gestire il caso di chiavi multiple, altrimenti si inserisce nell'albero sinistro o in quello destro a seconda della comparazione della chiave con l'informazione del nodo corrente

AggiungiAITE: si usi un interruttore enc inizializzato a false, un puntatore a Nodo pos



inizializzato alla radice dell'albero, mediante un ciclo finchè enc è false e l'albero non è terminato (pos != NULL) far sì che: se le chiavi coincidono porre enc a true, altrimenti proseguire a sinistra o a destra a seconda del risultato della comparazione.

19.16

SUGGERIMENTO Si implementino le funzioni membro:

CancellareRIC: è un metodo pubblico della classe Albero. Trovato il nodo con una riceca ricorsiva considera i tre casi: se non ha figlio sinistro si punta il puntatore al figlio destro, se non ha figlio destro si punta il puntatore al figlio sinistro , se ha due figli si chiama una funzione cercaP che cerca l'immediato predecessore, copia l'informazione del nodo che si deve cancellare, cambia il nodo da cancellare nel suo immediato predecessore. Al termine si libera la memoria

cercaP: è un metodo privato della classe Albero. Mediante chiamata ricorsiva cerca l'immediato predecessore e fa quanto indicato al punto precedente.

CancellareITE: cerca iterativamente il nodo da cancellare. Trovatolo considera i tre casi come in CancellareRIC con la differenza che nei primi due casi si deve tener conto dell'eventualità che il nodo corrente sia la radice dell'albero (Ant == NULL) ; nel terzo caso la ricerca del predecessore viene fatta da una funzione cercaPITE. Al termine si libera la memoria

cercaPITE: è un metodo privato della classe Albero. Fa la stessa cosa che fa cercaP.

Fondamenti di programmazione in C++ - Algoritmi, strutture...

Documents

Transcript of Fondamenti di programmazione in C++ - Algoritmi, strutture...