INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
ESEMPIO
INIZIO
PREPARA-CAFFE
FINE
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
SCOMPOSIZIONE: processo “prepara caffè”
INIZIO PREPARA-CAFFE
PREPARA-MACCHINETTA
METTI-MACCHINETTA-SU-FUOCO
CUCINA-CAFFE
SERVI-CAFFE
FINE PREPARA-CAFFE
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
SCOMPOSIZIONE: processo “prepara macchinetta”
INIZIO PREPARA-MACCHINETTA
1
2
PRENDI-MACCHINETTA-DACREDENZA
PRENDI-CAFFE-DA-DISPENSA
METTI-ACQUA-IN-MACCHINETTA
METTI-CAFFE-IN-MACCHINETTA
FINE PREPARA-MACCHINETTA
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
INIZIO PREPARA-MACCHINETTA
V
F
1
Macchinetta in
credenza
PRENDI-MACCHINETTA-DACREDENZA
2
PRENDI-CAFFE-DA-DISPENSA
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
NODO CONNETTORE
q
q
TEST/VERIFICA/DECISIONE
CONDIZIONE
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
ENTRATA
TEST
F
q
A
V
B
USCITA
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
V
F
Macchinetta in credenza
1
PRENDI-MACCHINETTA
F
2
V
Caffè non in dispensa
COMPRA-CAFFE
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
TESTS IN CASCATA
F
V
p
1
A
B
V
F
q
2
C
D
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
TESTS NIDIFICATI
F
V
p
C
F
B
q
V
A
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
SCOMPOSIZIONE: processo “servi caffè”
INIZIO SERVI-CAFFE
TOGLI-CAFFE-DA-FUOCO
ZUCCHERA-CAFFE
VERSA-CAFFE
PORGI-CAFFE
FINE SERVI-CAFFE
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
SCOMPOSIZIONE: processo “zucchera caffè”
INIZIO ZUCCHERA-CAFFE
V
Caffè amaro
AGGIUNGI-ZUCCHERO
F
ASSAGGIA-CAFFE
FINE ZUCCHERA-CAFFE
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
ITERAZIONE PER VERO
V
p
A
F
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
SIMBOLI
INIZIO/FINE
PROCESSO
PROCESSO
AZIONE
TEST
NODO
CONNETTORE
FLUSSO
INTRODUZIONE ALLA PROGRAMMAZIONE STRUTTURATA
STRUTTURE
SEQUENZA
ITERAZIONE PER VERO
V
p
A
ITERAZIONE PER FALSO
TEST
F
B
p
F
V
A
A
F
p
V
Progetto: Calcolo del resto
Calcolo del resto
La divisione di due numeri positivi, può essere espressa
attraverso la sottrazione:
n:m equivale a sottrarre m da n fino a quando n diventa
inferiore di m. Il numero di volte in cui tale sottrazione ha
luogo, è il risultato della divisione.
Calcolo del resto
inizio
Lettura dividendo
Lettura divisore
resto = divisore
F
resto >= divisore
V
Stampa “resto”
resto = resto - divisore
Calcolo del resto
#include <stdio.h>
int main()
{
int dividendo, divisore, resto;
printf("Inserire dividendo:\n");
scanf("%d", &dividendo);
printf("Inserire divisore:\n");
scanf("%d", &divisore);
//lettura dividendo
//lettura divisore
resto = dividendo;
while (resto >= divisore){
resto = resto - divisore;
}
printf("\nresto della divisione %d/%d e' %d", dividendo, divisore, resto);
return 0;
}
Progetto: Calcolo numero primo
Calcolo del numero primo
Definizione
Un numero n>=2 è un numero PRIMO se è divisibile per 1 e per se stesso.
L’ algoritmo consiste nel dividere il numero n per tutti i numeri
interi minori di n.
Se il numero n risulta divisibile per uno di questi interi (ovvero il
resto della divisione è zero) allora n è un numero non PRIMO; in
caso contrario n è un numero PRIMO
Calcolo del numero primo
Esempio
N=5
int main()
{
int n, divisore, quoz, resto;
int primo;
printf("Insrire Numero:");
scanf("%d", &n);
}
primo = true;
divisore = 2;
while (divisore < n && primo==true){
quoz = n/divisore;
//calcolo del quoziente
resto = n-(quoz*divisore); //calcolo del resto
if (resto == 0){
//se il resto è nullo
primo = false;
//il numero in esame non è primo
} else{
//altrimenti
divisore = divisore + 1; //incremento il divisore
}
}
if (primo==true){
printf ("\n\n%d e` un numero primo",n);
}else{
printf ("\n\n%d non e` un numero primo",n);
}
Calcolo del numero primo
inizio
Lettura n
primo = true
divisore = 2
divisore = divisore +1
F
Divisore < n
AND
primo = true
V
F
resto == 0
V
resto = n –
(quoz*divisore)
quoz = n/divisore
stampa
Primo = false
resto
quoziente
È stato
trovato
un divisore
Progetto: Torri di Hanoi
http://it.wikipedia.org/wiki/Torre_di_Hanoi
http://www.frasi.net/giochionline/torre-di-hanoi/
Torri di Hanoi: regole
• Il rompicapo è costituito da tre pile di dischi
(“torri”) allineate
– all’inizio tutti i dischi si trovano sulla pila di
sinistra
– alla fine tutti i dischi si devono trovare sulla pila
di destra o centrale
• I dischi sono tutti di dimensioni diverse e
quando si trovano su una pila devono
rispettare la seguente regola
– nessun disco può avere sopra di sé dischi più
grandi
Torri di Hanoi: regole
Situazione iniziale
Situazione finale
Torri di Hanoi: regole
• Per risolvere il rompicapo bisogna spostare un
disco alla volta
– un disco può essere rimosso dalla cima della
torre ed inserito in cima ad un’altra torre
• non può essere “parcheggiato” all’esterno…
– in ogni momento deve essere rispettata la
regola vista in precedenza
• nessun disco può avere sopra di sé dischi
più grandi
Algoritmo di soluzione
• Il problema generale consiste nello spostare n dischi da
una torre ad un’altra, usando la terza torre come deposito
temporaneo
• Per spostare n dischi da una torre all’altra si suppone di
saper spostare n-1 dischi da una torre all’altra, come
sempre si fa nella ricorsione
Ricorsione
Una funzione ricorsiva è una funzione che richiama se stessa
La “Torre di Hanoi”
A
B
C
Torre di Hanoi: algoritmo
int mossa = 0;
void hanoi(int, char, char, char);
void muovi(int, char, char);
int main()
{
int DISCHI;
printf("\nInserire il numero di DISCHI:");
scanf("%d",&DISCHI);
printf("\nMosse da eseguire per spostare %d dischi\n", DISCHI);
hanoi(DISCHI, 'A', 'B', 'C');
}
Torre di Hanoi: algoritmo
void hanoi(int n, char piolo_b, char piolo_a, char aus)
{
if(n == 1) {
muovi(n, piolo_b, piolo_a);
}else {
hanoi(n-1, piolo_b, aus, piolo_a);
muovi(n, piolo_b, piolo_a);
hanoi(n-1, aus, piolo_a, piolo_b);
}
}
void muovi(int n, char piolo_b, char piolo_a)
{
char invio;
printf("\nMossa %3d: ", ++mossa);
printf("disco %d da %c a %c\n",n, piolo_b, piolo_a);
scanf("%c", &invio);
}
Torre di Hanoi: output
Torre di Hanoi: sequenza di
trasferimenti
1
2
3
A
B
C
2
3
1
A
B
C
Mossa 1
A
3
1
2
3
A
B
C
A
Mossa 2
3
1
2
1
3
2
1
2
3
B
C
A
B
C
A
B
Mossa 4
Mossa 5
1
2
B
C
Mossa 3
1
2
3
C
Mossa 6
A
B
C
Mossa 7