Esercizi linguaggio C in PP

Esercitazioni su:
- Algoritmi
- Diagrammi di flusso
- Notazione lineare strutturata
(pseudo-codice)
- Codifica in C (di problemi semplici)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
1
Esercizio 1: Dati due numeri interi non negativi,
calcolarne il prodotto (supponendo che l’esecutore non
abbia a disposizione l’operatore di moltiplicazione)
Dati di Input: M, N con M, N >= 0
Dati di Output: P (il prodotto tra M ed N)
• Note: bisogna effettuare delle somme successive,
cioè sommare M a se stesso per N volte.
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
2
START
Esempio 1
leggi M, N
P=0
V
N=0?
F
P=P+M
scriv i P
N =N -1
END
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
3
Esempio 1: pseudocodice
leggi M, N
P=0
WHILE (N <> 0) {
P=P+M
N=N–1
}
scrivi P
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
4
Esempio 1: codifica in C
#include <stdio.h>
main () {
int M, N, P;
printf(“Inserisci due valori interi positivi:
scanf(“%d%d”, &M,&N);
”);
P = 0;
while (N != 0) {
P = P + M;
N = N – 1;
}
printf(“\n Il prodotto vale %d\n”,P);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
5
Esercizio 2: Trovare quoziente e resto di una divisione
intera per differenze successive (supponendo cioè di
non disporre dell’operatore di divisione)
Dati di Input: D, D1 (supponiamo D1>0)
Dati di Output: Q, R (quoziente e resto)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
6
START
Esempio 2
leggi D, D1
R=D
Q=0
V
R >= D1
F
R = R - D1
scriv i Q, R
Q=Q+1
END
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
7
Esempio 2: pseudocodice
leggi D, D1
R=D
Q=0
WHILE (R >= D1) {
R = R – D1
Q=Q+1
}
scrivi Q, R
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
8
Esempio 2: codifica in C
#include <stdio.h>
main () {
int D, D1, R, Q;
printf(“Inserisci due valori interi positivi: ”);
scanf(“%d%d”, &D, &D1);
R = D;
Q = 0;
while (R >= D1) {
R = R – D1;
Q = Q + 1;
}
printf(“Quoziente = %d, Resto = %d \n”, Q, R);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
9
Esercizio 3: Sommare i primi N numeri interi positivi e
scrivere il risultato
Dati di Input: N
Dati di Output: S
Ing.Tomarchio,Ing.Testa
(con N >= 0)
(somma dei primi N numeri)
Fondamenti di Informatica
10
START
leggi N
Esempio 3
I=0
S=0
S=S+I
I= I+ 1
V
I <= N
F
scrivi S
END
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
11
Esempio 3: pseudocodice
leggi N
I=0
S=0
DO {
S=S+I
I=I+1
} WHILE (I <= N)
scrivi S
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
12
Esempio 3: codifica in C
#include <stdio.h>
main () {
int N, S, i;
printf(“Somma dei primi N interi positivi\n\n”);
printf(“Inserisci N: “);
scanf(“%d”, &N);
i = 0;
S = 0;
do {
S = S + i;
i++;
} while (i <= N)
printf(“La somma dei primi %d numeri e’ %d\n”, N, S);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
13
Esempio 3: codifica in C (uso di for)
#include <stdio.h>
main () {
int N, S, i;
printf(“Somma dei primi N interi positivi\n\n”);
printf(“Inserisci N: “);
scanf(“%d”, &N);
for(i = 1, S = 0; i <= N; i++)
S = S + i;
printf(“La somma dei primi %d numeri e’ %d\n”, N, S);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
14
Esercizio 4: Leggere N numeri e scrivere la loro somma
Dati di Input: N, ed N numeri
Dati di Output: S (somma di questi N numeri)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
15
START
Esempio 4
leggi N
I=1
S=0
I <= N
F
V
scriv i S
leggi NUM
S = S + NUM
END
I =I+ 1
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
16
Esempio 4: pseudocodice
leggi N
I=1
S=0
WHILE (I <= N) {
leggi NUM
S = S + NUM
I=I+1
}
scrivi S
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
17
Esempio 4: codifica in C
(uso del while)
#include <stdio.h>
main () {
int N, S, i, num;
printf(“Somma di N numeri interi\n\n”);
printf(“Inserisci N: “);
scanf(“%d”, &N);
i = 1;
S = 0;
while (i <= N) {
printf(“Inserisci il numero %d : “,i);
scanf(“%d”, &num);
S = S + num;
i++;
}
printf(“La somma vale: %d”, S);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
18
Esempio 4: codifica in C
(uso del for)
#include <stdio.h>
main () {
int N, S, i, num;
printf(“Somma di N numeri interi\n\n”);
printf(“Inserisci N: “);
scanf(“%d”, &N);
for(i=1, S=0; i <= N; i++) {
printf(“Inserisci il numero %d : “,i);
scanf(“%d”, &num);
S = S + num;
}
printf(“La somma vale: %d”, S);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
19
Esercizio 5: Scrivere il valore massimo di una sequenza
illimitata di interi positivi chiusa da uno zero
Dati di Input: N1, N2, N3, ….., 0
Dati di Output: MAX (valore massimo dei
precedenti numeri letti da input)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
20
START
MAX = 0
Esempio 5
leggi N
V
N > MAX ?
F
F
MAX = N
N <> 0 ?
V
F
scrivi MAX
END
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
21
Esempio 5: pseudocodice
MAX = 0
DO {
leggi N
IF (N > MAX) MAX = N
} WHILE (N <> 0)
scrivi MAX
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
22
Esempio 5: codifica in C
#include <stdio.h>
main () {
int N, MAX;
MAX = 0;
do {
printf(“Inserisci un valore intero positivo
(0 per finire)\n”);
scanf(“%d”, &N);
if (N > MAX) MAX = N;
} while (N != 0);
printf(“Il massimo dei valori inseriti e’: %d \n”,MAX);
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
23
Esercizio 6: Dato un intero N>1, scrivere una sola volta
tutti i suoi fattori primi (supponendo di avere a
disposizione l’operatore di divisione intera)
Dati di Input: N
Dati di Output: elenco dei fattori primi di N
• Note: l’espressione Q = (Q / D) * D se verificata mi
indica che D è un divisore di Q
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
24
START
leggi N
Esempio 6
Q =N
GIA_SCRITTO = 0
D=2
F
Q <> 1
V
F
Q <>(Q/D)*D
V
F
GIA_SCRITTO <>1
V
D=D+1
scrivi D
GIA_SCRITTO = 0
GIA_SCRITTO = 1
Q = Q/D
END
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
25
Esempio 6: pseudocodice
leggi N
Q=N
GIA_SCRITTO = 0
D=2
WHILE (Q <> 1) {
WHILE (Q <> (Q/D) * D ) {
D=D+1
GIA_SCRITTO = 0
}
IF (GIA_SCRITTO <> 1) {
scrivi D
GIA_SCRITTO = 1
}
Q = Q/D
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
26
Esempio 6: codifica in C
#include <stdio.h>
main () {
int N, Q, D, GIA_SCRITTO;
printf(“Inserisci un numero intero positivo \n”);
do
scanf(“%d”, &N);
while (N<=0);
Q = N;
GIA_SCRITTO = 0;
D = 2;
while (Q > 1) {
while (Q != (Q/D) * D ) {
D = D + 1;
GIA_SCRITTO = 0;
}
if (GIA_SCRITTO == 0) {
printf(“divisore trovato %d \n”, D);
GIA_SCRITTO = 1;
}
Q = Q/D;
}
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
27
Esercizio 7: Gioco dei fiammiferi: Da un insieme di N
fiammiferi, ciascun giocatore ne toglie a turno un
numero qualunque che vada da 1 a K; perde chi toglie
l’ultimo fiammifero
Spieghiamo la strategia e risolviamo il problema per
N=21 e K=5.
Ipotesi di base:
– vi sono due giocatori, A e B;
– il giocatore che effettua la prima mossa è sempre il calcolatore (A).
Strategia:
– Isolo 1 fiammifero, e divido i rimanenti in gruppi da 6;
– Prima mossa: tolgo i 2 fiammiferi rimasti;
– Mosse successive:tolgo un numero di fiammiferi pari al
complemento a 6 di quelli tolti dall’avversario (sempre
possibile per le ipotesi fatte)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
28
STA RT
Esempio 7
scrivi le regole del gioco
DFD di alto livello
scrivi "Comincio io!"
A toglie 2 f iammiferi
Ci sono ancora
fiammiferi?
F
V
scrivi "Quanti fiammiferi
vuoi togliere?"
scrivi "Ho vinto.
Vuoi giovare ancora
leggi NB
F
leggi RISP
B toglie NB fiammiferi
RISP = "sì" ?
V
A toglie (6 - NB) f iammiferi
F
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica END
29
Esempio 7: pseudocodice
(di alto livello)
scrivi le regole del gioco
DO {
scrivi “Comincio io!”
A toglie due fiammiferi
WHILE (ci sono ancora fiammiferi?) {
scrivi “Quanti fiammiferi vuoi togliere?”
leggi NB;
B toglie NB fiammiferi
A toglie (6-NB) fiammiferi
}
scrivi “Ho vinto! Vuoi giocare ancora?”
leggi RISP
} WHILE (RISP = “sì”)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica
30