Algoritmi - Parte 2

Algoritmi di calcolo

END END ENDsomma prodotto divisione interadi due numeri di due numeri di due numeri13Informatica Generale Maria De MarsicoEsempi stampa 30 volte laSTART parola TREC := 1stampa “TRE”C = 30V FC := C + 1END 14Informatica Generale Maria De MarsicoEsempi stampa NUMERO volte laparola PAROLA (NUMEROe PAROLA sono valori diingresso per ilSTART programma)dati PAROLA e NUMEROC := 1stampa PAROLAC = NUMEROV FC := C + 1END 15Informatica Generale Maria De Marsico 5Esempisomma due numeri STARTavendo a disposizionesolo l’operazione di dati A Bincremento unitario RIS := A; CON := 1RIS := RIS + 1V FCON = Bstampa RIS CON := CON + 1END Nota: B > o 16Informatica Generale Maria De MarsicoEsempimoltiplica due numeri STARTavendo a disposizionesolo l’operazione di dati A Bsomma RIS := 0; CON := 1RIS := RIS + AV FCON = Bstampa RIS CON := CON + 1END Nota: A e B > o 17Informatica Generale Maria De MarsicoAltri esempi• Vediamo i diagrammi di flusso degli algoritmiper il calcolo

1. Trovare il maggiore fra 2 numeri interi x e y
2. Trovare il massimo fra N numeri

Informatica Generale Maria De Marsico

Il maggiore fra 2 numeri interi

Algoritmo max_xy

1. Leggi i valori di x e y dall'esterno
2. Calcola la differenza d fra x e y (d=x-y)
3. Se d è maggiore di 0 vai al passo 5 altrimenti prosegui in sequenza
4. Stampa 'il massimo è ...' seguito dal valore di x e vai a 6
5. Stampa 'il massimo è ...' seguito dal valore di y
6. Termina l'esecuzione

Informatica Generale Maria De Marsico

DF di max_xy

START

1. Leggi x e y
2. d = x - y
3. Se d > 0 ? Scrivi 'max è y'
4. Scrivi 'max è x'

END

Informatica Generale Maria De Marsico

DF di max_xy

START Passo 1

Leggi x e y

Passo 2

d = x - y

Passo 3

1. No
2. Se d > 0 ? Scrivi 'max è y'
3. Scrivi 'max è x'

Passo 5

Passo 4

END

Passo 6

Informatica Generale Maria De Marsico

Il massimo fra N numeri

numeri interi

• Algoritmo max_N1. Leggi il valore di N dall'esterno
• Leggi i primi due numeri
• Trova il maggiore m fra i primi due numeri (conmax_xy)
• Finchè (hai esaminato meno di N numeri)
  • Leggi un nuovo numero x
  • Trova il maggiore fra m e x usando l'algoritmo max_xy
  • Assegna il valore del maggiore a m
• Stampa 'il massimo è...' ed il valore di m e termina

Informatica Generale Maria De Marsico

DF per il problema del START massimo di N numeri

Leggi i primi due numeri x1 e x2 e memorizzali nelle variabili a e b

m = max_xy(a,b)

Si

No

Ancora numeri da esaminare ? Scrivi 'max è m'

Leggi il nuovo numero in a

END

m = max_xy(a,m)

Informatica Generale Maria De Marsico

DF e programmi

Per ottenere una codifica interpretabile direttamente dalla macchina dobbiamo però usare solo operazioni elementari :

trasformare tutte le 'frasi' in variabili e modifiche su di esse, oppure confronti :

'Ancora

numeri da esaminare?’ deve essere tradotto in qualcosa di calcolabile dalla macchina usando solo le operazioni elementari

Informatica Generale Maria De Marsico 8

START

Leggi N

Leggi N e i primi due numeri x1 e x2 e memorizzali nelle variabili a e b

m = max_xy(a,b)

Cont = 2

Si

No

DF per il problema del Cont < N ? massimo di N numeri

Cont = Scrivi ‘max è m’ (seconda versione)

Cont + 1

END

Leggi il nuovo numero in a

N ≥ 2

m = max_xy(a,m)

Informatica Generale Maria De Marsico

DF e programmi

Per ottenere una codifica interpretabile direttamente dalla macchina dobbiamo anche scrivere il tutto con una codifica ‘leggibile’ dalla macchina

Ricordiamo la definizione di programma

specifica di un algoritmo utilizzando un linguaggio non ambiguo e direttamente comprensibile dal computer

… ma possibilmente senza arrivare al linguaggio macchina (codificato con zeri e uni) !!!!

Informatica Generale Maria De Marsico

DF e

programmi• … soluzione….• usare linguaggi di ‘livello’ più alto (linguaggidi programmazione ad alto livello)• usare dei programmi appositi per far tradurre inostri programmi in linguaggio macchina (icompilatori)• importante ….• I tipici linguaggi (C, Java, Fortran, Basic…)permettono di definire strutture del tuttoanaloghe ai diagrammi di flusso che abbiamovisto finora 27Informatica Generale Maria De Marsico 9Dal diagramma alprogrammaSTART begin<azione 1>azione 1 <azione 2>endazione 2END 28Informatica Generale Maria De MarsicoDal diagramma alprogrammaV Fcondizioneazione 1 azione 2se if <condizione>allora then <azione 1>altrimenti else <azione 2> 29Informatica Generale Maria De MarsicoDal diagramma alprogrammaV Fcondizione finchèazione 1 ripetiwhile <condizione>do <azione 1> 30Informatica Generale Maria De Marsico 10