Algoritmi Politecnico di Milano C Primi programmi Politecnico di Milano.
-
Upload
ginevra-milano -
Category
Documents
-
view
228 -
download
1
Transcript of Algoritmi Politecnico di Milano C Primi programmi Politecnico di Milano.
Algoritmi Politecnico di Milano
C
Primi programmi Politecnico di Milano
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: numeroOUTPUT: messaggio PRIMO o NON PRIMODIALOGO27NON PRIMO
PROGETTARE
Acquisisco numeroControllo se è primoIf (è primo) printf(“PRIMO”);else printf(“NON PRIMO”);
PROGETTARE: controllo se è 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
Acquisisco il numeroControllo se è primoIf (è primo) printf(“PRIMO”);else printf(“NON PRIMO”);
PROGETTARE: (è primo)
Acquisisco numeroControllo se è primoIf (è 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
Ci sarà un ciclo nel quale divido numeroper 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
Acquisisco il numeroControllo se è primoIf (è primo) printf(“PRIMO”);else printf(“NON PRIMO”);
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”)}
Istruzioni eseguite numero divisore nVolteDivisibile
? ? ?
scanf(“%d”, &numero) 7 ? ? divisore = 2; 7 2 ? nVolteDivisibile = 0; 7 2 0 while (divisore < numero) 7 2 0 if (numero%divisore == 0) 7 2 0 divisore = divisore + 1; 7 3 0 while (divisore < numero) 7 3 0 if (numero%divisore == 0) 7 3 0 divisore = divisore + 1; 7 4 0while (divisore < numero) 7 4 0 if (numero%divisore == 0) 7 4 0 divisore = divisore + 1; 7 5 0while (divisore < numero) 7 5 0 if (numero%divisore == 0) 7 5 0 divisore = divisore + 1; 7 6 0while (divisore < numero) 7 6 0 if (numero%divisore == 0) 7 6 0 divisore = divisore + 1; 7 7 0while (divisore < numero) 7 7 0 if (nVolteDivisibile == 0) 7 7 0 printf(“PRIMO”); 7 7 0
Verificare
PROGETTARE: controllo se è 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
Acquisisco il numeroControllo se è primoIf (è primo) printf(“PRIMO”);else printf(“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”)}
isStato = 1While (condizione uscita){
If (evento) isStato = 0
Preparazione ciclo successivo}If (isStato == 1) ……..
Pattern 4
contaEventi = 0
While (condizione uscita)
{
If (evento)
contaEventi = contaEventi + 1
Preparazione ciclo successivo
}
If (contaEventi ………)
……..
Pattern 5
ESERCIZIO
2. Modificare il programma precedente stampando le coordinate del punto di distanza massima
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
3. Modificare il programma precedente stampando la distanza media
Formalizzazione problema
INPUT: numero punti, sequenza coordinate x e yOUTPUT: distanza massima
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: xi e yi coordinate punto distanza massima
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza media
1
2
3
PROGETTARE
Acquisisco n (numero punti)Leggi punti e calcola distanza massimaStampa distanza massima
PROGETTARE: Leggi punti e calcola 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( )
Acquisisco n (numero punti)Leggi punti e calcola distanza massimaStampa distanza massima
PROGETTARE: Leggi punti e calcola 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
Acquisisco n (numero punti)Leggi punti e calcola distanza massimaStampa distanza massima
#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);}
Stendere l’algoritmo
Pattern del ciclo a conteggio
matematica
massimo
Formalizzazione problema
INPUT: numero punti, sequenza coordinate x e yOUTPUT: distanza massima
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: xi e yi coordinate punto distanza massima
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza media
1
2
3
PROGETTARE
Acquisisco n (numero punti)Leggi punti e calcola distanza massimaStampa le coordinate del punto di distanza massima
PROGETTARE
Acquisisco n (numero punti)Leggi punti e calcola distanza massimaStampa 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
#include <stdio.h>#include <math.h>main(){ /* dichiarazioni */ int n, contatore; float distanza, distanzaMax, x, y, xMax, yMax; /* 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; xMax = x; yMax = y; } contatore = contatore + 1; }/* stampa distanza massima */printf(“punto di distanza massima x = %f y = %f”,xMax, yMax);}
Stendere l’algoritmo
Modifica codice aggiungendo il
salvataggio delle coordinate del punto di
distanza massima
Aggiungo dichiarazione due variabili per salvare le
coordinate del punto di distanza massima
Stampa coordinate punto di distanza
massima
Formalizzazione problema
INPUT: numero punti, sequenza coordinate x e yOUTPUT: distanza massima
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: xi e yi coordinate punto distanza massima
INPUT: numero punti, sequenza coordinate x e y
OUTPUT: distanza media
1
2
3
PROGETTARE
Acquisisco n (numero punti)Leggi punti e calcola distanza mediaStampa la distanza media
PROGETTARE
Acquisisco n (numero punti)Leggi punti e calcola distanza mediaStampa 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 distanzeStampa la distanza media
Per calcolare la somma:1. Uso una variabile somma2. Nel ciclo incremento somma della distanza appena calcolata somma = somma + distanza1. inizializzo somma a 0
La variabile somma si chiama ACCUMULATORE
#include <stdio.h>#include <math.h>main(){ /* dichiarazioni */ int n, contatore; float distanza, somma,; /* Acquisisco n */ scanf (“%d”, &n);
/* leggi i punti e calcola la somma delle distanze*/ contatore = 0; somma = 0; while (contatore < n){ scanf(“%f”, &x); scanf( “%f”, &y); distanza = sqrt (x*x + y*y); somma = somma + distanza; contatore = contatore + 1; }/* stampa media*/printf(“la distanza media è %f ”,somma / n);}
Stendere l’algoritmo
Dichiaro somma
Inizializzo somma
Modifica codice con incremento
somma
esercizio
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
E se il problema fosse?
Per esercizio fare la formalizzazione del problema e la progettazione
Formalizzazione problema
INPUT: sequenza di punti che termina con 0 0 OUTPUT: distanza minima
1
PROGETTARE
Acquisisco le coordinate dei punti e calcolo la distanza minimaStampa la distanza minima
PROGETTARE: Acquisisco le coordinate dei punti e calcolo la distanza minima
Acquisisco le coordinate dei punti e calcolo la distanza minimaStampa la distanza minima
Uso il pattern della sequenza di valori che finisce con 0Leggi il primo valoreInizializzaWhile (il valore non è l’ultimo) { Esegui l’operazione Leggi il prossimo valore }
PROGETTARE: esegui l’operazioneUso il pattern della sequenza di valori che finisce con 0
Leggi il primo valoreInizializzaWhile (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 minima2. Calcolo la distanza3. La confronto con distanza minima e sostituisco se è
più piccola
Date le informazioni mese e anno visualizzare il numero di giorni del mese
ESERCIZIO
• 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 annoCalcolo il numero di giorni del meseStampo i giorni
PROGETTARE: Calcolo il numero di giorni del mese
Acquisisco mese e annoCalcolo il numero di giorni del meseStampo i giorni
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
Mi concentro sulle operazioni in alternativa:If (mesi con 30 giorni) giorni = 30else if (febbraio) gestisco febbraioelse giorni = 31
PROGETTARE: febbraio gestisco
è bisestile: se l’anno è divisibile per 4 e non per 100 o è divisibile per 400
If (è bisestile) giorni = 29else giorni = 28
If ( ((anno % 4 == 0) && (anno % 100 != 0) ) || (anno % 400 == 0))
#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);}
Stendere l’algoritmo
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 vocaliStampo il numero delle occorrenze di ogni vocale
PROGETTARE:stampo il numero di occorrenze di ogni vocale
La parte PRECEDENTE del codice ha come obbiettivo la valorizzazione di questi contatori
Parto dal basso:1. Per ogni vocale devo avere un contatore che vale il numero di volte
che l’ho trovata nella frase2. nA nE nI nU nO sono i contatori3. All’inizio del programma inizializzo i contatori a 0
Acquisisco la frase e conto le vocaliStampo il numero delle occorrenze di ogni vocale
PROGETTARE: Acquisisco la frase e conto le vocali
All’interno del ciclo controllo il carattere se è una vocale incremento il contatore corrispondente
So leggere un carattere alla volta quindi per leggerli tutti ci vuole un ciclo
Acquisisco la frase e conto le vocaliStampo il numero delle occorrenze di ogni vocale
Una frase è una sequenza di caratteri che finisce con a capo = ‘\n’ quindi USO il pattern sequenza di interi che finisce con 0
#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);
Stendere l’algoritmo: prima parte
Inizializzo i contatori
Leggo il primo carattere
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); }/* Stampo il numero delle occorrenze di ogni vocale */printf(“a = %d e = %d i = %d u = %d o = %d”, nA, nE, nI, nU, nO);}
Stendere l’algoritmo: continua
Eseguo l’azione: controllo il carattere appena letto
Non è il carattere di A CAPO
Leggo il prossimo carattere
Sinonimo di nU = nU + 1
Istruzioni eseguite c nA nE nI nU nO
? ? ? ? ? ?nA = 0; ? 0 ? ? ? ?nE = 0; ? 0 0 ? ? ?nI = 0; ? 0 0 0 ? ?nU = 0; ? 0 0 0 0 ?nO = 0; ? 0 0 0 0 0scanf(“%c”, &c); f 0 0 0 0 0while (c != ‘\n’) f 0 0 0 0 0if (c == ‘a’) f 0 0 0 0 0else if (c == ‘e’) f 0 0 0 0 0else if (c == ‘i’) f 0 0 0 0 0else if (c == ‘u’) f 0 0 0 0 0else if (c == ‘o’) f 0 0 0 0 0scanf(“%c”, &c); i 0 0 0 0 0while (c != ‘\n’) i 0 0 0 0 0if (c == ‘a’) i 0 0 0 0 0else if (c == ‘e’) i 0 0 0 0 0else if (c == ‘i’) i 0 0 0 0 0nI++; i 0 0 1 0 0
Verificare
Istruzioni eseguite c nA nE nI nU nO
scanf(“%c”, &c); n 0 0 1 0 0while (c != ‘\n’) n 0 0 1 0 0if (c == ‘a’) n 0 0 1 0 0else if (c == ‘e’) n 0 0 1 0 0else if (c == ‘i’) n 0 0 1 0 0else if (c == ‘u’) n 0 0 1 0 0else if (c == ‘o’) n 0 0 1 0 0scanf(“%c”, &c); e 0 0 1 0 0while (c != ‘\n’) e 0 0 1 0 0if (c == ‘a’) e 0 0 1 0 0else if (c == ‘e’) e 0 0 1 0 0nE++; e 0 1 1 0 0scanf(“%c”, &c); \n 0 1 1 0 0while (c != ‘\n’) \n 0 1 1 0 0printf(“a = %d e …
Verificare