Ing.Tomarchio,Ing.TestaFondamenti di Informatica1 Esercitazioni su: -Algoritmi -Diagrammi di flusso...
of 30
/30
-
Upload
leopoldo-motta -
Category
Documents
-
view
214 -
download
0
Embed Size (px)
Transcript of Ing.Tomarchio,Ing.TestaFondamenti di Informatica1 Esercitazioni su: -Algoritmi -Diagrammi di flusso...
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 1
Esercitazioni su:
- Algoritmi- Diagrammi di flusso- Notazione lineare strutturata
(pseudo-codice)- Codifica in C (di problemi semplici)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 2
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 >= 0Dati 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 3
Esempio 1
START
leggi M, N
P = 0
N = 0 ?
P = P + M
N =N -1
scriv i P
END
V
F
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 4
Esempio 1: pseudocodice
leggi M, NP = 0WHILE (N <> 0) {
P = P + MN = N – 1
}scrivi P
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 5
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 6
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 7
Esempio 2
START
leggi D, D1
R = D
R = R - D1
Q = Q + 1
scriv i Q, R
END
V
F
Q = 0
R >= D1
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 8
Esempio 2: pseudocodice
leggi D, D1R = DQ = 0WHILE (R >= D1) {
R = R – D1Q = Q + 1
}scrivi Q, R
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 9
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 10
Esercizio 3: Sommare i primi N numeri interi positivi e scrivere il risultato
Dati di Input: N (con N >= 0)
Dati di Output: S (somma dei primi N numeri)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 11
Esempio 3
START
leggi N
I = 0
S = S + I
I = I + 1
scrivi S
END
V
F
S = 0
I <= N
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 12
Esempio 3: pseudocodice
leggi NI = 0S = 0DO {
S = S + II = I + 1
} WHILE (I <= N)scrivi S
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 13
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 14
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 15
Esercizio 4: Leggere N numeri e scrivere la loro somma
Dati di Input: N, ed N numeriDati di Output: S (somma di questi N
numeri)
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 16
Esempio 4
START
leggi N
I = 1
leggi NUM
I = I + 1
scriv i S
END
V
F
S = 0
I <= N
S = S + NUM
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 17
Esempio 4: pseudocodice
leggi NI = 1S = 0WHILE (I <= N) {
leggi NUMS = S + NUMI = I + 1
}scrivi S
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 18
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 19
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 20
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 21
Esempio 5
START
MAX = 0
MAX = N
scrivi MAX
END
VFN > MAX ?
N <> 0 ?
leggi N
V
F
F
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 22
Esempio 5: pseudocodice
MAX = 0DO {
leggi NIF (N > MAX) MAX = N
} WHILE (N <> 0) scrivi MAX
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 23
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 24
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: NDati 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 25
Esempio 6
START
leggi N
Q =N
D = D + 1
GIA_SCRITTO = 0
scrivi D
V
F
D = 2
GIA_SCRITTO = 0
Q <> 1 F
GIA_SCRITTO <>1
GIA_SCRITTO = 1
Q = Q/D
Q <>(Q/D)*D
END
V
VF
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 26
Esempio 6: pseudocodiceleggi NQ = N GIA_SCRITTO = 0D = 2WHILE (Q <> 1) {
WHILE (Q <> (Q/D) * D ) {D = D + 1GIA_SCRITTO = 0
}IF (GIA_SCRITTO <> 1) {
scrivi DGIA_SCRITTO = 1
}Q = Q/D
}
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 27
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 28
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 fiammiferoSpieghiamo 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 29
Esempio 7
DFD di alto livello
START
scrivi le regole del gioco
leggi RISP
END
V
FCi sono ancora f iammiferi?
scrivi "Comincio io!"
V
F
F
A toglie 2 f iammiferi
RISP = "sì" ?
scrivi "Quanti fiammiferivuoi togliere?"
leggi NB
B toglie NB fiammiferi
A toglie (6 - NB) f iammiferi
scrivi "Ho vinto. Vuoi giovare ancora
Ing.Tomarchio,Ing.Testa
Fondamenti di Informatica 30
Esempio 7: pseudocodice (di alto livello)
scrivi le regole del giocoDO {
scrivi “Comincio io!”A toglie due fiammiferiWHILE (ci sono ancora fiammiferi?) {
scrivi “Quanti fiammiferi vuoi togliere?”leggi NB;B toglie NB fiammiferiA toglie (6-NB) fiammiferi
}scrivi “Ho vinto! Vuoi giocare ancora?”leggi RISP
} WHILE (RISP = “sì”)
