Primi
programmi
Algoritmi
Politecnico di Milano
Politecnico di Milano
C
ESERCIZIO
Dato un numero n stampare PRIMO se n è primo,
NON PRIMO altrimenti
FORMALIZZAZIONE PROBLEMA
Dato un numero n stampare PRIMO se n è primo,
NON PRIMO altrimenti
INPUT: numero
OUTPUT: messaggio PRIMO o NON PRIMO
DIALOGO
27
NON PRIMO
PROGETTARE
Acquisisco numero
Controllo se è primo
If (è primo)
printf(“PRIMO”);
else
printf(“NON PRIMO”);
PROGETTARE: controllo se è primo
Acquisisco il numero
Controllo se è primo
If (è primo)
printf(“PRIMO”);
else
printf(“NON PRIMO”);
Penso a quello che conosco:
• un numero è primo se è divisibile solo per sé stesso e per 1
•Divisibile: il resto della divisione intera è 0
•In C la divisione intera si indica con / il resto con %
Come farei “a mano”?
Continuo a dividere il numero per tutti i numeri
da 2 al numero – 1
Se il resto della divisione è SEMPRE 0 allora è primo
PROGETTARE: (è primo)
Acquisisco numero
Controllo se è primo
If (è primo)
printf(“PRIMO”);
else
printf(“NON PRIMO”);
“è primo” è una condizione: deve tradursi nel valore
di una variabile che l’esecutore può controllare
Uso un contatore che conta le volte che numero è divisibile:
nVolteDivisibile = 0
è primo
nVolteDivisibile > 0 non è primo
PROGETTARE: controllo se è primo
Acquisisco il numero
Controllo se è primo
If (è primo)
printf(“PRIMO”);
else
printf(“NON PRIMO”);
Ci sarà un ciclo nel quale divido numero
per un divisore, che la prima volta varrà 2 e poi
Poi 3 poi 4 … : in ogni ciclo aumenterà di 1
L’obbiettivo del ciclo è contare quante volte il numero
è divisibile quindi calcolare nVolteDivisibile
Uso 3 variabili intere: numero, divisore, nVolteDivisibile
Stendere l’algoritmo
#include <stdio.h>
main()
{ /* dichiarazioni */
int numero, divisore, nVolteDivisibile;
/* Acquisisco Il numero */
scanf (“%d”, &numero);
/* Controllo se è primo */
divisore = 2;
nVolteDivisibile = 0;
while (divisore < numero)
{
if (numero%divisore == 0)
nVolteDivisibile = nVolteDivisibile + 1;
divisore = divisore + 1;
}
if (nVolteDivisibile == 0)
printf(“PRIMO”);
else
printf(“NON PRIMO”)
}
Verificare
Istruzioni eseguite
scanf(“%d”, &numero)
divisore = 2;
nVolteDivisibile = 0;
while (divisore < numero)
if (numero%divisore == 0)
divisore = divisore + 1;
while (divisore < numero)
if (numero%divisore == 0)
divisore = divisore + 1;
while (divisore < numero)
if (numero%divisore == 0)
divisore = divisore + 1;
while (divisore < numero)
if (numero%divisore == 0)
divisore = divisore + 1;
while (divisore < numero)
if (numero%divisore == 0)
divisore = divisore + 1;
while (divisore < numero)
if (nVolteDivisibile == 0)
printf(“PRIMO”);
numero
divisore nVolteDivisibile
?
?
?
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
7
?
2
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
7
?
?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
PROGETTARE: controllo se è primo
Acquisisco il numero
Controllo se è primo
If (è primo)
printf(“PRIMO”);
else
printf(“NON PRIMO”);
Mi accorgo di fare troppi controlli inutili: posso pensare di
diminuirne il numero fermandomi quando il
Divisore = numero / 2
Posso diminuire il numero dei controlli anche fermandomi
appena numero risulta divisibile:
uso una variabile a 2 stati:
isPrimo = 1 il numero è primo
isPrimo = 0 il numero non è primo
Stendere l’algoritmo: seconda versione
#include <stdio.h>
main()
{ /* dichiarazioni */
int numero, divisore, isPrimo;
/* Acquisisco Il numero */
scanf (“%d”, &numero);
/* Controllo se è primo */
divisore = 2;
isPrimo= 1;
while ((isPrimo == 1) && (divisore <= numero/2))
{
if (numero%divisore == 0)
isPrimo = 0;
divisore = divisore + 1;
}
if (isPrimo == 1)
printf(“PRIMO”);
else
printf(“NON PRIMO”)
}
Pattern 4
isStato = 1
While (condizione uscita)
{
If (evento)
isStato = 0
Preparazione ciclo successivo
}
If (isStato == 1)
……..
Pattern 5
contaEventi = 0
While (condizione uscita)
{
If (evento)
contaEventi = contaEventi + 1
Preparazione ciclo successivo
}
If (contaEventi ………)
……..
ESERCIZIO
1. data una sequenza di n > 0 punti nel piano con n scelto
dall’utente, stampare la distanza massima dall’origine degli assi
dei punti introdotti
2. Modificare il programma precedente stampando le coordinate del
punto di distanza massima
3. Modificare il programma precedente stampando la distanza
media
Formalizzazione problema
1
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza massima
2
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: xi e yi coordinate punto distanza
massima
3
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza media
PROGETTARE
Acquisisco n (numero punti)
Leggi punti e calcola distanza massima
Stampa distanza massima
PROGETTARE: Leggi punti e calcola distanza massima
Acquisisco n (numero punti)
Leggi punti e calcola distanza
massima
Stampa distanza massima
Devo leggere n punti: pattern del ciclo a conteggio
contenente la lettura della coordinata x e della coordinata y di
un punto
Calcola la distanza :
dati x e y so calcolare la distanza dall’origine
Distanza = sqrt (x*x + y*y)
Mi devo ricordare: #include <math.h> per usare sqrt( )
PROGETTARE: Leggi punti e calcola distanza massima
Acquisisco n (numero punti)
Leggi punti e calcola distanza
massima
Stampa distanza massima
Calcola la distanza MASSIMA:
Mi ricordo che per trovare il massimo di una serie di numeri:
1. Usavo 2 variabili: distanza
distanzaMax
2. Usavo un if posto nel ciclo:
If (distanza > distanzaMax) distanzaMax = distanza
3. Inizializzavo distanzaMax
Stendere l’algoritmo
#include <stdio.h>
main()
{ /* dichiarazioni */
int n, contatore;
float distanza, distanzaMax, x, y;
/* Acquisisco n */
scanf (“%d”, &n);
/* leggi i punti e calcola la distanza massima */
contatore = 0;
distanzaMax = 0;
while (contatore < n)
{ scanf(“%f”, &x);
scanf( “%f”, &y);
distanza = sqrt (x*x + y*y);
if (distanza > distanzaMax) distanzaMax = distanza;
contatore = contatore + 1;
}
/* stampa distanza massima */
printf(“%f”, distanzaMax);
}
Pattern del ciclo a
conteggio
matematica
massimo
Formalizzazione problema
1
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza massima
2
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: xi e yi coordinate punto distanza
massima
3
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza media
PROGETTARE
Acquisisco n (numero punti)
Leggi punti e calcola distanza massima
Stampa le coordinate del punto di distanza
massima
PROGETTARE
Acquisisco n (numero punti)
Leggi punti e calcola distanza massima
Stampa le coordinate del punto di distanza massima
Parto da fondo: dal risultato che devo ottenere:
Le coordinate del punto di distanza massima:
Se alla fine le devo stampare allora prima le devo salvare
Quando devo salvare le coordinate del punto di distanza massima?
Provo a risolvere il problema “a mano”:
Le salvo quando salvo la “nuova” distanza massima
Stendere l’algoritmo
#include <stdio.h>
#include <math.h>
main()
{ /* dichiarazioni */
int n, contatore;
float distanza, distanzaMax, x, y, xMax, yMax;
/* Acquisisco n */
scanf (“%d”, &n);
Aggiungo dichiarazione due
variabili per salvare le
coordinate del punto di distanza
massima
Modifica codice
aggiungendo il
salvataggio delle
coordinate del punto di
distanza massima
/* leggi i punti e calcola la distanza massima */
contatore = 0;
distanzaMax = 0;
while (contatore < n)
{ scanf(“%f”, &x);
scanf( “%f”, &y);
distanza = sqrt (x*x + y*y);
if (distanza > distanzaMax) { distanzaMax = distanza; xMax = x; yMax = y; }
contatore = contatore + 1;
}
/* stampa distanza massima */
printf(“punto di distanza massima x = %f y = %f”,xMax, yMax);
}
Stampa coordinate
punto di distanza
massima
Formalizzazione problema
1
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza massima
2
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: xi e yi coordinate punto distanza
massima
3
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza media
PROGETTARE
Acquisisco n (numero punti)
Leggi punti e calcola distanza media
Stampa la distanza media
PROGETTARE
Acquisisco n (numero punti)
Leggi punti e calcola distanza media
Stampa la distanza media
Cosa conosco del problema?
La media = Σ distanzai / n
Quindi devo calcolare la somma delle distanze e stamperò:
media = sommaDistanze / n
PROGETTARE
Acquisisco n (numero punti)
Leggi punti e calcola la somma delle distanze
Stampa la distanza media
Per calcolare la somma:
1. Uso una variabile somma
2. Nel ciclo incremento somma della distanza appena calcolata
somma = somma + distanza
1. inizializzo somma a 0
La variabile somma si chiama ACCUMULATORE
Stendere l’algoritmo
#include <stdio.h>
#include <math.h>
main()
{ /* dichiarazioni */
int n, contatore;
float distanza, somma,;
Dichiaro
somma
/* Acquisisco n */
scanf (“%d”, &n);
/* leggi i punti e calcola la somma delle distanze*/
contatore = 0;
somma = 0;
while (contatore < n)
Modifica codice
{ scanf(“%f”, &x);
con incremento
scanf( “%f”, &y);
somma
distanza = sqrt (x*x + y*y);
somma = somma + distanza;
contatore = contatore + 1;
}
/* stampa media*/
printf(“la distanza media è %f ”,somma / n);
}
Inizializzo somma
esercizio
E se il problema fosse?
data una sequenza di n punti nel piano che termina con l’inserimento delle
coordinate dell’origine stampare la distanza minima dall’origine degli
assi dei punti introdotti
Per esercizio fare la formalizzazione del problema
e la progettazione
Formalizzazione problema
1
INPUT: sequenza di punti che termina con 0 0
OUTPUT: distanza minima
PROGETTARE
Acquisisco le coordinate dei punti e calcolo la
distanza minima
Stampa la distanza minima
PROGETTARE: Acquisisco le coordinate dei punti e calcolo la
distanza minima
Acquisisco le coordinate dei punti e calcolo
la distanza minima
Stampa la distanza minima
Uso il pattern della sequenza di valori che finisce con 0
Leggi il primo valore
Inizializza
While (il valore non è l’ultimo)
{
Esegui l’operazione
Leggi il prossimo valore
}
PROGETTARE: esegui l’operazione
Uso il pattern della sequenza di valori che finisce con 0
Leggi il primo valore
Inizializza
While (il valore non è l’ultimo)
{
Esegui l’operazione
Leggi il prossimo valore
}
L’operazione da eseguire assomiglia a quella del calcolo
del massimo quindi:
1. Uso due variabili distanza e distanza minima
2. Calcolo la distanza
3. La confronto con distanza minima e sostituisco se è
più piccola
ESERCIZIO
Date le informazioni mese e anno visualizzare il numero
di giorni del mese
• 30 giorni ha novembre con april giugno e settembre di
28 ce n’è uno tutti gli altri ne hanno 31
• Un anno è bisestile se
l’anno è divisibile per 4 e non per 100 o
è divisibile per 400
PROGETTARE
Acquisisco mese e anno
Calcolo il numero di giorni del mese
Stampo i giorni
PROGETTARE: Calcolo il numero di giorni del mese
Acquisisco mese e anno
Calcolo il numero di giorni del mese
Stampo i giorni
Mi concentro sulle operazioni in alternativa:
If (mesi con 30 giorni)
giorni = 30
else if (febbraio)
gestisco febbraio
else
giorni = 31
Conosco che l’esecutore macchina C, se a e b sono interi:
a / b quoziente della divisione intera
a % b resto della divisione intera
Es: 13 / 3 = 4 13 % 3 = 1
PROGETTARE: febbraio gestisco
If (è bisestile)
giorni = 29
else
giorni = 28
è bisestile:
se l’anno è divisibile per 4 e non per 100 o è divisibile per 400
If ( ((anno % 4 == 0) && (anno % 100 != 0) ) ||
(anno % 400 == 0))
Stendere l’algoritmo
#include <stdio.h>
#include <math.h>
main()
{ /* dichiarazioni */
int mese, anno, giorni;
/* Acquisisco mese e anno */
printf(“inserisci mese e anno\n ”);
scanf (“%d%d”, &mese, &anno);
/* Calcolo il numero di giorni del mese */
If ((mese == 4) || (mese == 11) || (mese == 6) || (mese == 9))
giorno = 30;
else if (mese == 2)
if (((anno % 4 == 0) && (anno % 100 != 0)) ||
(anno % 400 == 0))
giorno = 29;
else
giorno = 28;
else
giorno = 31;
/* stampo giorno */
printf(“i giorni del mese %d sono %d”, mese, giorno);
}
ESERCIZIO
Scrivere un programma che data una frase contenente
parole in caratteri minuscoli separate da SPAZI che
termini con UN A CAPO, stampi per ogni vocale il
numero delle volte che è presente nella frase. Se
vengono introdotti caratteri diversi da una lettera
minuscola o un blank o un a capo il programma li
ignora
PROGETTARE
Acquisisco la frase e conto le vocali
Stampo il numero delle occorrenze di ogni vocale
PROGETTARE:stampo il numero di occorrenze di ogni
vocale
Acquisisco la frase e conto le vocali
Stampo il numero delle occorrenze di ogni vocale
Parto dal basso:
1. Per ogni vocale devo avere un contatore che vale il numero di volte
che l’ho trovata nella frase
2. nA nE nI nU nO sono i contatori
3. All’inizio del programma inizializzo i contatori a 0
La parte PRECEDENTE del codice ha come obbiettivo la
valorizzazione di questi contatori
PROGETTARE: Acquisisco la frase e conto le vocali
Acquisisco la frase e conto le vocali
Stampo il numero delle occorrenze di ogni vocale
So leggere un carattere alla volta quindi per leggerli tutti ci vuole un
ciclo
Una frase è una sequenza di caratteri che finisce con a capo = ‘\n’
quindi USO il pattern sequenza di interi che finisce con 0
All’interno del ciclo controllo il carattere se è una vocale incremento
il contatore corrispondente
Stendere l’algoritmo: prima parte
#include <stdio.h>
main()
{ /* dichiarazioni */
char c;
int nA, nE, nI, nU, nO;
/* Acquisisco la frase e conto le vocali */
nA = 0;
nE = 0;
nI = 0;
nU = 0;
nO = 0;
scanf(“%c”, &c);
Inizializzo i contatori
Leggo il primo
carattere
Stendere l’algoritmo: continua
while (c != ‘\n’)
{
if (c == ‘a’)
nA++;
else if (c == ‘e’)
nE++;
else if (c == ‘i’)
nI++;
else if (c == ‘u’)
nU++;
else if (c == ‘o’)
nO++;
scanf(“%c”, &c);
Non è il carattere di A CAPO
Eseguo l’azione: controllo il carattere
appena letto
Sinonimo di nU = nU + 1
Leggo il
prossimo
carattere
}
/* Stampo il numero delle occorrenze di ogni vocale */
printf(“a = %d e = %d i = %d u = %d o = %d”, nA, nE, nI, nU, nO);
}
Verificare
Istruzioni eseguite
nA = 0;
nE = 0;
nI = 0;
nU = 0;
nO = 0;
scanf(“%c”, &c);
while (c != ‘\n’)
if (c == ‘a’)
else if (c == ‘e’)
else if (c == ‘i’)
else if (c == ‘u’)
else if (c == ‘o’)
scanf(“%c”, &c);
while (c != ‘\n’)
if (c == ‘a’)
else if (c == ‘e’)
else if (c == ‘i’)
nI++;
c
nA
nE
nI
nU
nO
?
?
?
?
?
?
?
?
?
?
?
f
f
f
f
f
f
f
i
i
i
i
i
i
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
?
?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
?
?
?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
?
?
?
?
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Verificare
Istruzioni eseguite
c
nA
nE
nI
nU
nO
scanf(“%c”, &c);
while (c != ‘\n’)
if (c == ‘a’)
else if (c == ‘e’)
else if (c == ‘i’)
else if (c == ‘u’)
else if (c == ‘o’)
scanf(“%c”, &c);
while (c != ‘\n’)
if (c == ‘a’)
else if (c == ‘e’)
nE++;
scanf(“%c”, &c);
while (c != ‘\n’)
printf(“a = %d e …
n
n
n
n
n
n
n
e
e
e
e
e
\n
\n
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0