Sommario - di.unito.itrossano/DIDATTICA/MDAMS-0506/... · Rossini); • Anche per sapere...

1

Informatica di Base Informatica di Base ---- R.GaetaR.Gaeta

Sommario

• Problema computazionale• Sviluppo software• Algoritmi

– Diagrammi di Flusso;– Pseudo Codice

• Istruzioni Sequenziali, Condizionali, Cicliche;• Javascript

2


Il Problema computazionale

• È computazionale un problema che da alcuni dati iniziali porta ad un risultato in uscita tramite almeno una sequenza preordinata di passi;

• Esempi nella vita pratica si trovano facilmente nell’arte culinaria o nella musica.

3


Esempi

Il Risotto alla Zucca:- Abbiamo gli ingredienti (riso, zucca, olio, prezzemolo, cipolla,

sale, etc.) con le giuste quantità;- Seguiamo la ricetta;- Serviamo il piatto a tavola.

4


Altro esempio

L’esecuzione della nona di Beethoven:- Abbiamo l’orchestra, il direttore ed i musicisti;- Seguiamo lo spartito;- La musica riempie la sala.

5


Ma…

• Non è così facile come sembra!• Per scrivere la “sequenza di passi” bisogna essere un

bravo cuoco o un bravo compositore (o entrambi, come Rossini);

• Anche per sapere “eseguire” bisogna imparare l’arte (bisogna avere un ottimo esecutore).

6


Il “cuore” dell’informatica

• definizione di un particolare problema computazionale• scrittura di un algoritmo che lo risolve• scrittura del programma che traduce i passi

dell’algoritmo in termini comprensibili dal computer

7


Il “cuore” dell’informatica

• Ovvero, dato un problema bisogna definire un procedimento (l’algoritmo) che possa essere eseguito automaticamente da un esecutore a partire dai dati in ingresso per risolvere il problema (fornire i risultati in uscita)

esecutore

algoritmo

input output

8


Quindi…

problema risolutore algoritmoesecutore

esecuzione

essere umano

calcolatore

9


Cosa è un Algoritmo

• Un algoritmo (procedimento) è una sequenza finita di passi (azioni) che un esecutore è in grado di eseguire affinchévenga risolto (in un tempo finito) un dato problema computazionale.

• Ogni passo deve essere eseguibile dall’esecutore e in un tempo finito.

• Un algoritmo determina un procedimento sequenziale (un passo dopo l’altro secondo un ordine specificato chiamato flusso di esecuzione)

• La cosa difficile è scrivere una sequenza di passi che risolvano il problema computazionale e NON scrivere un programma per il calcolatore

10


Esecutore di algoritmi

• Un esecutore è caratterizzato da– il linguaggio che è in grado di interpretare– l’insieme di azioni che è in grado di compiere– l’insieme delle regole che ad ogni frase corretta del linguaggio

(costrutto linguistico) associano le relative azioni da compiere

11


Caratteristiche di un algoritmo

• Tutte le azioni specificate dall’algoritmo devono essere eseguibili dall’esecutore– sono azioni elementari

• In caso contrario, si deve scomporre un problema complesso in più sotto-problemi più semplici

• Per ogni problema più semplice deve esistere un’istruzione nel linguaggio adottato per la scrittura degli algoritmi la cui esecuzione lo risolve.

12


Esempio di algoritmo

L’esecutore è un essere umano che è solo in grado di premere tasti ed usare il mouse

• Accendere il calcolatore• Accendere il monitor• Scrivere il nome utente• Scrivere la password• Premere il tasto invio• Se compare il messaggio di “password scaduta” allora

cambiare la password altrimenti accedere al desktop di windows

13


Esempio: scomposizione in sotto-problemi

• Ma l’esecutore sa direttamente eseguire il comando “cambiare la password”?

• NO! Abbiamo definito in maniera precisa ed univoca che cosa l’esecutore è in grado di fare per cui dobbiamo scrivere un algoritmo per la risoluzione del problema “cambiare la password”– scrivere una sequenza di almeno sei caratteri– ri-scrivere, per conferma, la stessa sequenza– premere il tasto invio

• Per esercizio, avendo ormai esperienza di come si accede all’aula 15, completate l’algoritmo!!

14



• Formulazione generale– la soluzione individuata non deve dipendere solo da valori predefiniti dei dati, cosi

che l’algoritmo sia utilizzabile nel maggior numero possibile di casi

• Passi eseguibili univoci e non ambigui– “abbastanza”, “a volontà”, “un pochetto”, non sono adatti ad esecutori come i

calcolatori.

• Determinismo– una volta fatto un passo, in maniera univoca quello successivo può essere

determinato dall’esecutore anche se ci sono alternative

• Finitezza del numero di passi• Terminazione

– prima o poi l’esecuzione dell’algoritmo deve terminare

• La finitezza del numero dei passi implica la terminazione?

15



Ogni passo (azione) deve

• terminare entro un intervallo finito di tempo• produrre un effetto osservabile • produrre lo stesso effetto ogni volta che viene eseguito a

partire dalle stesse condizioni iniziali

16


Elementi degli algoritmi

• Oggetti: le entità su cui opera l’algoritmo– Dati iniziali del problema, informazioni ausiliarie, risultati parziali e

finali– Le informazioni sono dette dati (anche i risultati parziali e finali) e

possono essere variabili o costanti

• Operazioni: Interventi da effettuare sui dati– Calcoli, confronti, ricopiature,acquisizioni, emissioni, ecc.

• Flusso di controllo: l’indicazione delle possibili successioni dei passi dell’algoritmo– La correttezza dei risultati dipende non solo dalla corretta esecuzione

delle singole operazioni, ma anche dalla corretta sequenza con cui sono eseguite

17


Flusso di controllo e di esecuzione

• Flusso di controllo: la descrizione a priori di tutte le possibili sequenze nell’esecuzione dei passi dell’algoritmo, in particolare di operazioni in alternativa e di operazioni da ripetere più volte ciclicamente

• Flusso di esecuzione: la sequenza di operazioni effettivamente seguita durante una particolare esecuzione dell’algoritmo e che dipende dai particolari valori che i dati assumono in quell’esecuzione

18


Cosa è un programma

• Il programma è la “scatola nera” che risolve il problema computazionale;

• Il programma è una sequenza di istruzioni che devono essere eseguite;

• Il programma è la traduzione per il computer dei passi dell’algoritmo

• Deve essere scritto tramite un linguaggio che il computer capisca (linguaggio macchina);

• Il programmatore utilizza un linguaggio di programmazioneche poi viene tradotto (da qualcosa) in linguaggio macchina;

19


Dall’uomo al calcolatore

calcolatoreinput output

uomo

algoritmo

programma

linguaggio macchina

traduttore

pseudo codicediagramma di flusso

linguaggio di programmazionead alto livello

esecuzione del processore

20


Fasi di creazione di un programma

1. Studio Preliminare

2. Analisi del Sistema

3. Progettazione

4. Sviluppo

5. Implementazione

6. Manutenzione e Test

21


Le fasi

• Analisi del problema computazionale (individuare input ed output, etc.)

• Progettazione di una soluzione proponendo una suddivisionedel problema in sottoproblemi più semplici; alla fine di questa fase, per ogni sottoproblema si deve scrivere l’algoritmo utilizzando pseudo-codici e diagrammi di flusso;

• Stesura del programma a partire dall’algoritmo: implementazione vera e propria

• Test del programma: alfa testing, beta testing, debugging• Produzione documentazione e distribuzione

22


Un altro esempio di algoritmo

Preparazione del Risotto alla Zucca da parte di un esecutore in grado di aggiungere, tagliare, mescolare, tostare, mantecare,…

1. Preparare il soffritto ed il brodo;2. Aggiungere la zucca a pezzettini al soffritto;3. Mescolare fino a quando la zucca non è un purè;4. Aggiungere il riso al soffritto;5. Fare tostare il riso; poi bagnarlo con il vino;6. Aggiungere brodo fino a quando il riso è cotto;7. Aggiungere prezzemolo, pepe e burro; 8. Se preferisci salato, allora aggiungi sale;

23


Sottoproblemi

• L’algoritmo precedente è un altro esempio di cosa significa scomporre un problema in sottoproblemi;– Come si prepara un soffritto?– Come si prepara un brodo?

• Ogni sottoproblema può essere scomposto in problemi via via più elementari;

• Per ogni problema elementare deve esistere un’istruzione nel linguaggio adottato la cui esecuzione lo risolve.

24


Alto e basso livello

• Man mano che si suddivide il problema in sottoproblemi, si scende di livello;

• Se ci si avvicina al linguaggio umano, si parla di linguaggi di Alto livello;

• Se ci si avvicina al linguaggio macchina, si parla di linguaggi di Basso livello;

25


Linguaggi

Linguaggio Macchina

Linguaggio umano (es. Italiano)

Descrizione di un algoritmo (es. diagrammi di flusso,pseudo codice, etc…)

Linguaggi di Programmazione (es. C, VBasic, Java, Logo, etc…)

Alto livello

Basso livello

26


Linguaggi di programmazione

• Linguaggio macchina– Codifica binaria delle istruzioni– Diverso per ogni architettura– Istruzioni e operazioni elementari coincidono

• Linguaggio Assembler– Sempre a livello macchina, ma codifica simbolica delle istruzioni– Es: ADD R1, R6

STORE R1, RAM[255]

MOV R1, #4

27



• Linguaggio ad alto livello (HLL - High-Level Languages– Elaboratore virtuale

• Operazioni molto più astratte delle operazioni HW– Es: x = y+2

z = cos(x)

– Linguaggio indipendente dalla piattaforma!– Possibile mediante l’esistenza di traduttori

28



Programmasorgente(HLL)

Programmaeseguibile(bit)

Traduttore

29


Traduttori

TraduttoreTraduttore

“somma due interi”…“stampa un messaggio”...

010101010111010101111111101010101010101010101011

Uomo Macchina

30


Traduttori

• Due schemi– Compilatori– Interpreti

31


Compilatori

• Traduzione avviene in due passi:– Compilazione vera e propria– Collegamento (link)

• Dopo la fase di link, il programma può essere eseguito direttamente

• Ogni fase produce un file corrispondente all’aggiunta di informazioni di vario tipo– Formato oggetto– Formato eseguibile

32


Compilatori

sorgente

oggetto

eseguibile

Libreria

COMPILATORECOMPILATORE

LINKERLINKER

010110100101010011111111...

33


Linker

• Risolve i riferimenti ad indirizzi di memoria– Indirizzi logici => indirizzi fisici

• Aggiunge al codice le librerie:– Funzioni pre-compilate e riutilizzabili (es. funzioni matematiche)

e distribuite con il compilatore– Codice scritto in precedenza– Due schemi:

• Librerie statiche• Librerie dinamiche

34


Interpreti

• Il formato interno viene generato interpretando e traducendo il formato sorgente

• Il programma viene interpretato ed immediatamente eseguito istruzione per istruzione.

• Non viene generato né formato intermedio (oggetto) néeseguibile.

35


Compilatori vs. interpreti

• Linguaggi compilati:– Vantaggi:

• Formato del programma eseguibile più efficiente → esecuzione più veloce• Migliore supporto per istruzioni “complesse” e programmi di grandi

dimensioni– Svantaggi:

• Rallentamento tempo di sviluppo dei programmi• Maggiori requisiti di spazio di memoria (il compilatore è un programma

sofisticato)

• Linguaggi interpretati:– Ideali in ambiente didattico per lo sviluppo rapido di programmi.

36


Portabilità del software

• Possibilità per un programma di poter essere eseguito su piattaforme HW e SW diverse da quelle su cui è stato sviluppato

codice sorgente

compilatore Windows

compilatore Linux

compilatore MacOS

codice eseguibile Windows

codice eseguibile Linux

codice eseguibile MacOS

37



• FORTRAN– FORmula TRANslation (1956)

• calcoli tecnico-scientifici (ambiente fisico/matematico)• svariate librerie • compilato

• COBOL– COmmerce and Business Oriented Language (1960)

• elaborazione di archivi, tabulati• applicazioni contabili

38



• BASIC– Beginner’s All-purpose Symbolic Instruction Code (1962)

• relativamente semplice• capacità grafiche• interpretato• versioni “evolute” (VisualBasic)

• PASCAL– (1972)

• Linguaggio molto “formale” (progetto accademico)• Programmazione strutturata• Utile per la didattica• Compilato

39



• C– Bell Labs (1972)

• Evoluzione più efficiente del PASCAL• Istruzioni per ottimizzazione del codice• efficiente• Molto usato nella programmazione di sistema• compilato

• C++– Bell Labs (‘80)

• Evoluzione del C ad oggetti• Diverso paradigma di programmazione• Include il C• compilato

40



• Java– Sun MicroSystems (‘90)

• Evoluzione del C++• Schema misto compilato+interpretato• Portabilità universale tramite formato intermedio (bytecode)• Vasta gamma di librerie• Supporto alla programmazione web

• Perl– GNU project (‘90)

• interpretato• complesso, ma molto potente• molto utilizzato nella programmazione web• programmi=>script

41


Sviluppo di programmi

• Per la costruzione di un programma conviene:1. condurre un’analisi del problema da risolvere2. elaborare un algoritmo della soluzione rappresentato in un

linguaggio adatto alla comprensione degli esseri umani ma abbastanza vicino ai linguaggi di programmazione

3. produrre un programma scritto nel linguaggio di programmazione scelto

42



• FASE 1: Dare un nome al problema partendo dall’analisi del problema

• FASE 2: Scrivere la specifica funzionale• FASE 3: Scrittura dell’algoritmo

– FASE 3.1: Introduzione dei contenitori di dati (variabili) necessarie e delle relative operazioni elementari

– FASE 3.2: Specifica di un diagramma di flusso ( o di uno pseudocodice) che descrive in modo preciso e non ambiguo la sequenza di operazioni da eseguire

• FASE 4: Traduzione del diagramma di flusso ( o dello pseudo codice) in un programma in un linguaggio di programmazione

43








44


FASE 1: problema e sua analisi

• L’analisi di un problema è la primissima cosa da fare quando si è di fronte alla richiesta di risolverlo

• Bisogna capire bene il problema prima di pensare di risolverlo!

• L’analisi del problema deve fornire come prodotto:– un nome ed una breve descrizione di cosa si vuol fare– un elenco di requisiti, ovvero, di richieste, vincoli che il

programma deve soddisfare

45


Esempio di Analisi del problema: ax2+bx+c

• Problema: CALCOLO RADICI• Descrizione: calcolare le soluzioni reali di una equazione

di secondo grado• Requisiti: l’equazione può avere nessuna soluzione reale,

due soluzioni coincidenti, o due soluzioni distinte. Si devono, in questi casi, evidenziare il messaggio– nessuna radice– radici coincidenti r (dove r è il valore delle radici)– radici distinte r1 ed r2 (dove r1 ed r2 sono il valore delle radici)

46








47


FASE 2: specifica funzionale

• Una specifica funzionale descrive:– quali sono i dati iniziale, ovvero i dati di input (ingresso) da

elaborare– qual è il risultato atteso in funzione dei dati in ingresso (output,

uscita dell’algoritmo)

48


Esempio di specifica funzionale

CALCOLO RADICI: specifica funzionale• INPUT: i numeri reali a,b,c che sono i coefficienti

dell’equazione da risolvere• OUTPUT: i messaggi

– “nessuna radice reale”– “x1=x2=r” se l’equazione ha due radici reali coincidenti pari ad r– “x1=r1, x2=r2” se l’equazione ha due radici reali distinte pari ad

r1 ed r2

49








50


FASE 3: scrittura dell’algoritmo

• Descrizione dell’algoritmo, ovvero, dei passi da eseguire per giungere al risultato di uscita partendo dai dati in input

• La prima stesura non necessariamente deve essere completa di ogni dettaglio. in genere, si procede per raffinamenti successivi

51


Esempio di stesura preliminare di algoritmi

CALCOLO RADICI: stesura preliminare dell’algoritmo• risolvo il problema calcolando il discriminante (delta)

dell’equazione• analizzo i vari casi di delta

– < 0– = 0– > 0

• costruisco per ognuno di questi casi il messaggio da produrre in output

• Successivamente si definiscono le variabili (contenitori di dati) coinvolte e dettaglio la specifica dell’algoritmo usando un diagramma di flusso o lo pseudo codice.

52





– FASE 3.1: Introduzione delle variabili (contenitori di dati) necessarie e delle relative operazioni elementari



53


FASE 3.1: definizione delle variabili

• Ogni algoritmo deve tenere traccia (memorizzare) i valori dei dati in input, dei risultati in output, e dei valori intermedi calcolati durante l’esecuzione dei passi

• A questo fine si usano delle variabili (contenitori di dati). Ogni variabile ha un nome associato al dato (valore)memorizzato.

• Una variabile è una astrazione (semplificazione) della nozione di area di memoria (una o più celle della RAM, un registro generale) contenente i bit rappresentanti i dati

• I dati contenuti in una variabile hanno un tipo (si dice che una variabile è di un certo tipo) che caratterizza un insieme di elementi e le operazioni che sono possibili su di essi

54



• Ogni variabile memorizza il valore di un dato• Ogni dato appartiene ad un tipo di dato• Un tipo di dato è: un insieme di elementi,

rappresentabili in modo finito, dotato di operazioni primitive su di esso

• ESEMPIO: il tipo di dato intero– è l’insieme dei numeri interi, sequenze di cifre, con segno– dotato di operazioni primitive ed effettivamente eseguibili

come somma (+), differenza (-), prodotto (*), divisione intera (/), resto.

55



• Le variabili da usare per memorizzare i valori dei dati intermedi dipendono dall’algoritmo

• All’inizio della stesura di un algoritmo difficilmente si ègià a conoscenza di quante e quali variabili si dovranno usare

• Ad ogni raffinamento dell’algoritmo si possono aggiungere o togliere variabili fino ad arrivare all’uso corretto di ognuna

56


Esempio di definizione di variabili

CALCOLO RADICI: variabili usate• ci vogliono tante variabili quanti sono i dati in input. In

questo caso ci vogliono tre variabili che chiamiamo a,b,c per i coefficienti dell’equazione

• ci vogliono tante variabili quanti sono i dati in uscita. In questo caso, servono due variabili r1,r2 per il valore delle radici dell’equazione

• ci vogliono alcune variabili per tenere conto di dati intermedi da calcolare e modificare per ottenere la soluzione. In questo caso, potremmo usare una variabile per memorizzare il valore del discriminante. La variabile la chiamiamo delta

• Il tipo di tutte queste variabili è float (numeri reali).

57








58


Descrizione di un algoritmo

• Si descrive un algoritmo cercando di sintetizzare il piùpossibile la sua sequenza di passi;

• Non si utilizza un linguaggio di programmazione specifico, ma è meglio utilizzare qualcosa di piùgenerale;

• Pseudo-codici o Diagrammi di Flusso

59



• Un algoritmo descrive due tipi fondamentali di operazioni:– calcoli ottenibili tramite le operazioni primitive su tipi di dato

(valutazione di espressioni)– azioni che consistono nella modifica del valore associato alle

variabili

60





variabili

61


Calcoli: espressioni valutabili

• L’esecutore dell’algoritmo valuta espressioni dove gli elementi possono essere variabili o valori costanti– 3 * X + sin (Y * sqrt(z))– b*b-4*a*c– h / j– k / 2.23– 192

62


Calcoli: espressioni booleane (logiche)

• Ci sono anche particolari tipi di espressioni chiamate booleane o logiche

• Sono espressioni che possono dare origine a due soli possibili valori: VERO o FALSO

• Una proposizione della quale dobbiamo valutare se èvera o falsa

• Per costruire un’espressione logica si possono usare le seguenti relazioni:– = (uguaglianza);– < (minore); <= (minore o uguale);– > (maggiore); >= (maggiore o uguale);– <> (diverso);

63


Esempi di espressioni booleane (logiche)

• A seconda del valore delle variabili l’espressione booleana può essere vera o falsa– b*b-4*a*c = 0– h / j <> 2.4– k / 2.23 > p– 192 <= 12

64


Calcoli: espressioni logiche complesse - NOT

• Possiamo costruire espressioni booleane più complesse grazie ad alcune regole della cosiddetta algebra booleana;

• Se A è un’espressione logica, anche Not A (la negazione logica di A) lo è

VeroFalso

FalsoVero

A Not A

65


Congiunzione (AND)

• Se A e B sono espressioni logiche, anche A and B lo è;

A B A and B

FalsoFalsoFalso

FalsoVeroFalso

FalsoFalsoVero

VeroVeroVero

66


Disgiunzione (OR)

• Se A e B sono espressioni logiche, anche A or B lo è;

A B A or B

FalsoFalsoFalso

VeroVeroFalso

VeroFalsoVero

VeroVeroVero

67





variabili

68


Azioni: modifica valori delle variabili

• L’esecutore di un algoritmo deve poter compiere azioni che hanno un effetto sui dati gestiti

• Le azioni più semplici sono assegnamenti a variabili• Un assegnamento ad una variabile si denota con

VARIABILE:= ESPRESSIONE• con il seguente significato:

1. l’esecutore valuta l’espressione a destra del :=2. e poi modifica il valore della variabile con il risultato della

valutazione dell’espressione

69


Esempi di azioni: assegnamenti a variabili

• L’esecutore valuta espressioni dove gli elementi possono essere variabili o valori costanti e se ne assegna il valore ad una variabile

– pippo := 3 * X + sin (Y * sqrt(z))– delta := b*b-4*a*c– a := h / j– W := k / 2.23– M := 192– T := p– x := x + 1

• Una variabile non può essere “vuota”: ad una variabile deve sempre essere associato un valore

• Il valore contenuto in una variabile è l’ultimo assegnatole e resta inalterato finché una successiva assegnazione non modifica il valore stesso

70


Formalismi per la descrizione di algoritmi

• Per descrivere in passi di un algoritmo bisogna essere precisi e non ambigui

• Il linguaggio naturale degli esseri umani si presta a interpretazioni non univoche

• Si usano due formalismi: – diagrammi di flusso: formalismo grafico– pseudo-codice: linguaggio con istruzioni simili a quelle dei

linguaggi di programmazione

• si possono usare in alternativa

71


Specifica di inizio e di fine

• Ogni algoritmo deve avere un inizio ed una fine

start………………………………

end

start

end

72


Input ed output di dati

• Ogni algoritmo parte da dati in ingresso per produrre dati in uscita (problema computazionale)

……read X……

……write Z……

readX

write Z

73


Specifica delle azioni

• Ogni algoritmo specifica azioni che l’esecutore deve compiere del tipo descritto in precedenza

……

Z := X + 1

……

Z := X + 1

74


Specifica delle condizioni logiche

• Alcuni passi di un algoritmo si devono eseguire se sono verificate condizioni logiche su valori di variabili

• In genere, questi salti dell’algoritmo sono sottoposti ad una condizione logica (risposta vero o falso);

• Si parla di blocchi decisionali

75



………azioniif (condizione logica) then

azioni caso veroelse

azioni caso falsoend ifazioni seguenti comuni………

condizionelogica

azioni seguenti comuni

azioni caso falso

azioni caso vero

vero falso

azioni

76



………azioniif (condizione logica) then

azioni caso veroend ifazioni seguenti comuni………

condizionelogica


azioni caso vero

vero

falso

azioni

77


Condizioni logiche Annidate: esempio………azioniif (condizione logica 1) then

if (condizione logica 2) thenazioni vero 2

elseazioni falso 2

end ifelse

if (condizione logica 3) thenazioni vero 3

end ifend ifazioni seguenti comuni………


vero falso

azioni

vero falso

vero

falso

azioni vero 2 azioni falso 2 azioni vero 3

condizionelogica 1

condizionelogica 2

condizionelogica 3

78


Flusso di esecuzione

• I singoli diagrammi devono essere uniti tramite i connettori (linee e frecce in un flow chart);

• L’esecuzione dei passi deve essere fatta sequenzialmente, ovvero seguendo i connettori, partendo dall’inizio dell’algoritmo fino a raggiungere la sua fine

• Quando si scrive l’algoritmo bisogna fare molta attenzione alla direzione del flusso di esecuzione

79


Strutture di controllo: iterazione

……azioniwhile (condizione logica)

azioni da ripetereend whileazioni seguenti ……

condizionelogica

azioni seguenti

azioni daripetere

vero

falso

azioni

80


Strutture di controllo: iterazioni annidate

……azioniwhile (condizione logica esterna)

while (condizione logica interna) azioni iterazione interna da ripetere

end whileazioni iterazione esterna da ripetere

end whileazioni seguenti……

azioni iterazioneinterna da ripetere

vero

falso

azioni iterazioneesterna da ripetere

azioni seguenti

falso

azioni

condizionelogicainterna

vero condizionelogica

esterna

81








82


Esempio di algoritmo

• Scrivere l’algoritmo che esegue la somma di due numeri

startread Xread YZ := X + Y write Z

end

end

read X

read Y

Z := X + Y

write Z

start

83


Esempio: massimo tra due numeri

Dati due numeri, dire qual è il massimo tra i due.start

read Xread Yif (X > Y) then

max := Xelse

max := Yend ifwrite max

endend

read X

read Y

start

X > Yvero falso

write max

max := X max := Y

84


Esempio di algoritmo: calcolo radicistart

read a,b,cdelta := b*b-4*a*cif (delta < 0) then

write “nessuna radice”else

r1 := (-b+sqrt(delta))/2*ar2 := (-b-sqrt(delta))/2*awrite r1,r2if (delta = 0) then

write “radici coincidenti”else

write “radici distinte”end if

end ifend

end

read a,b,c

start

delta < 0vero falso

delta:=b*b-4*a*c

delta = 0vero falso

r1 := (-b + sqrt(delta))/2*a

r2 := (-b - sqrt(delta))/2*a

write"radici distinte"

writer1,r2

write"nessuna radice"

write"radici coincidenti"

85


Esercizio: massimo di una sequenza

• Si supponga di fornire in input ad un programma un numero indefinito di interi positivi. L’inserimento verràterminato dall’utente quando questi inserirà uno zero (0). Il programma deve restituire il valore massimo tra quelli introdotti. Disegnare il diagramma di flusso di tale programma.

86


Strutture di controllo: iterazione

……azioniwhile (condizione logica)

azioni da ripetereend whileazioni seguenti ……

condizionelogica

azioni seguenti

azioni daripetere

vero

falso

azioni

87


Strutture di controllo: iterazioni annidate

……azioniwhile (condizione logica esterna)

while (condizione logica interna) azioni iterazione interna da ripetere

end whileazioni iterazione esterna da ripetere

end whileazioni seguenti……

azioni iterazioneinterna da ripetere

vero

falso

azioni iterazioneesterna da ripetere

azioni seguenti

falso

azioni

condizionelogicainterna

vero condizionelogica

esterna

88


Esercizio: massimo di una sequenza

startmax := -1read numerowhile (numero > 0)

if (numero > max) thenmax := numero

end ifread numero

end whilewrite max

end

end

read numero

start

vero

falso

max := -1

numero >0 write max

numero > max

max := numero

read numero

vero

falso

89


Esercizio: massimo di una sequenzastart

max := -1read numerowhile (numero <> 0)

if (numero < 0) thenwrite “solo positivi!!”

elseif (numero > max) then

max := numeroend if

end ifread numero

end whilewrite max

end

end

read numero

start

vero

falso

max := -1

numero <> 0 write max

numero > max

max := numero

read numero

vero

falso

write "solo positivi!!"

numero < 0vero

falso

90


Esercizio: cosa fa questo algoritmo?

end

read A,B

start

vero

falso

P := 0

A <> 0 write P

P := P + B

vero

falso

A := A / 2

B := B * 2

A è dispari

startP := 0read A,Bwhile (A <> 0)

if (A è dispari) thenP := P + B

end ifA := A / 2B := B * 2

end whilewrite P

end

91



P 0 3 9 21

A 7 3 1 0

B 3 6 12 24

92



P 0 0 0 12 36

A 12 6 3 1 0

B 3 6 12 24 48

93


Esercizio: dispari-pari

startread Nwhile (N > 1)

N := N – 2end whileif (N = 0) then

write “pari”else

write “dispari”end if

end

Dato un numero, verificare se è pari o dispari e stampare il relativo messaggio

end

start

read N

N > 1N := N - 2

N = 0

write "pari" write "dispari"

vero

falso

vero falso

94


Esercizio: dispari-pari (controllo input)

startread Nif (N < 0) then

N := -Nend ifwhile (N > 1)

N := N – 2end whileif (N = 0) then

write “pari”else

write “dispari”end if

end

Dato un numero stampare se è pari o dispari

end

start

read N

N > 1N := N - 2

N = 0

write "pari" write "dispari"

vero

falso

vero falso

N < 0 N := -Nvero

falso

95


Esercizio: minimo di una sequenza di K numeri

• Si supponga di fornire in input ad un programma un numero K e K interi positivi. Il programma deve restituire il valore minimo tra quelli introdotti.

96


Esercizio: minimo di una sequenza di K numeristart

read Kread numeromin := numeroinseriti := 1while (inseriti < K)

read numeroif (numero < min) then

min := numeroend ifinseriti := inseriti + 1

end whilewrite min

end

end

read numero

start

vero

falsoinseriti < K write min

K

min := numero

inseriti := 1

read numero

numero < min

min := numero

inseriti := inseriti + 1

vero

falso

97


Esercizio: minimo di una sequenza di K numeri (controllo input)

startread Kif ( K <= 0) then

write “K deve essere positivo!”else

read numeromin := numeroinseriti := 1while (inseriti < K)

read numeroif (numero < min) then

min := numeroend ifinseriti := inseriti + 1

end whilewrite min

end ifend

end

read numero

start

vero

falsoinseriti < K write min

K

min := numero

inseriti := 1

read numero

numero < min

min := numero

inseriti := inseriti + 1

vero

falso

K <= 0 write "K deve essere positivo!"

vero

falso

98


Esercizio: elevamento a potenza

Data la base e l’esponente calcolare l’elevamento a potenza

startpotenza := 1read B,Ewhile (E > 0)

potenza := potenza * BE := E - 1

end whilewrite potenza

end

end

read B,E

start

vero

falso

potenza:= 1

E > 0 write potenza

potenza:= potenza * B

E := E -1

99


Esercizio: elevamento a potenza (controllo input)

Data la base e l’esponente calcolare l’elevamento a potenzastart

read B,Eif (E >= 0) then

potenza := 1while (E > 0)

potenza := potenza * BE := E - 1

end whilewrite potenza

elsewrite “esponente negativo!”

end ifend

end

read B,E

start

vero

falsoE > 0 write potenza

potenza:= potenza * B

E := E -1

E >= 0vero

falso write"esponentenegativo!"

potenza := 1

100


Esercizio: fattoriale

Dato un numero calcolare il suo fattoriale

startfattoriale := 1read Nwhile (N > 0)

fattoriale := fattoriale * NN := N - 1

end whilewrite fattoriale

end

end

read N

start

vero

falso

fattoriale:= 1

N > 0 write fattoriale

fattoriale:= fattoriale * N

N:= N -1

101


Esercizio: fattoriale (controllo input)

Dato un numero calcolare il suo fattorialestart

read Nif (N >= 0) then

fattoriale := 1while (N > 0)

fattoriale := fattoriale * NN := N - 1

end whilewrite fattoriale

elsewrite “numero negativo!”

end ifend

end

read N

start

vero

falsoN > 0 write fattoriale

fattoriale:= fattoriale * N

N := N -1

vero

falso

fattoriale:= 1

N >= 0 write"numeronegativo!"

102


Esercizio: numero primo

• Dato un numero N scrivere un algoritmo che verifichi se N è un numero primo e stampi un relativo messaggio

• Il numero N è un numero primo se è divisibile solo per 1 e per N

• Quindi, per verificare se un numero N è primo èsufficiente provare a dividerlo per tutti gli interi minori di esso– Se almeno uno di questi interi è un divisore di n allora n non è

primo– Altrimenti n è primo

103


Esercizio: numero primostart

read Ndivisore := 2primo := verowhile (divisore < N)

if (N divisibile per divisore) thenprimo := falso

end ifdivisore := divisore + 1

end whileif (primo = vero) then

write “numero primo”else

write “numero non primo”end if

endend

start

vero falsodivisore < N

N

divisore := 2

primo := vero

N divisibeper divisore

primo := falso

divisore := divisore + 1

vero

falso

primo = vero

write"numero primo"

write"numero nonprimo"

vero falso

104


Esercizio: numero primo – ottimizzazione Istart

read Ndivisore := 2primo := verowhile (divisore < N and primo = vero)

if (N è divisibile per divisore) thenprimo := falso





endend

start

vero falso

N

divisore := 2

primo := vero


primo := falso


vero

falso

primo = vero

write"numero primo"


vero falso

divisore < Nand

primo = vero

105


Esercizio: numero primo – ottimizzazione IIstart

read Ndivisore := 2primo := verowhile (divisore < N)

if (N è divisibile per divisore) thenprimo := falsodivisore := N





endend

start

vero falsodivisore < N

N

divisore := 2

primo := vero


primo := falso


vero

falso

primo = vero

write"numero primo"


vero falso

divisore := N

106


Esercizi

• Produrre un algoritmo che controlla la correttezza dell’input

• Produrre un algoritmo più efficiente di quello di base (più efficiente vuol dire che compie meno operazioni)

107


Esercizio: divisibilità

startread DD,DSwhile (DD >= DS)

DD := DD – DSend whileif (DD = 0) then

write “divisibile”else

write “non divisibile”end if

end

Dati un dividendo ed un divisore scrivere un algoritmo che verifichi la divisibilità

end

start

read DD,DS

DD := DD - DS

DD = 0

write "divisibile" write "non divisibile"

vero

falso

vero falso

DD >= DS

108


Esercizi

• Produrre un algoritmo che sia corretto per ogni tipologia di dati in ingresso

• Come risolvereste il problema del pari o dispari adesso?

109


Esercizio: triangoli

• Scrivere un algoritmo che, date le coordinate di tre punti corrispondenti ai vertici di un triangolo, riconosca se si tratta di un triangolo degenere o no, e nel caso di triangolo non degenere calcoli il suo perimetro

B

A

C

110


Esercizio: triangoli – soluzione preliminare

start

end

leggi coordinatedei vertici A,B,C del

triangolo

triangolo degenere

write"triangolo degenere"

calcola la lunghezzadei lati

calcola il perimetro del

triangolo

writeperimetro

vero falso

111


Esercizio: triangoli - raffinamentostart

end


LAB := distanza(A,B)LBC := distanza(B,C)LCA := distanza(C,A)

perimetro:=LAB+LBC+LCA

writeperimetro

vero falso

leggi coordinatedei vertici A,B,C del

triangolo

(A coincide con B) OR(B coincide con C) OR(C coincide con A) OR(A,B,C sono allineati)

112


Esercizio: triangoli – raffinamento ulteriorestart

end



writeperimetro

vero falso

read AX,AY,BX,BY,CX,CY

(AX=BX AND AY=BY) OR(BX=CX AND BY=CY) OR(CX=AX AND CY=AY) OR

(A,B,C sono allineati)

LAB := sqrt((AX-BX)*(AX-BX)+(AY-BY)*(AY-BY))LBC := sqrt((BX-CX)*(BX-CX)+(BY-CY)*(BY-CY))LCA := sqrt((CX-AX)*(CX-AX)+(CY-AY)*(CY-AY))

113


Esercizio: triangoli

• Se i tre vertici sono allineati allora otteniamo due triangoli rettangoli i cui cateti sono nella stessa proporzione

(AY-BY):(AX-BX)=(AY-CY):(AX-CX)

B

A

C

114


Esercizi: triangoli

• In una proporzione il prodotto dei medi è uguale al prodotto degli estremi per cui i tre vertici sono allineati se è vera la condizione logica

(AX-BX)*(AY-CY)=(AY-BY)*(AX-CX)

115


Esercizi: triangoli - soluzionestart

end



writeperimetro

vero falso

read AX,AY,BX,BY,CX,CY

(AX=BX AND AY=BY) OR(BX=CX AND BY=CY) OR(CX=AX AND CY=AY) OR

(AX-BX)*(AY-CY)=(AY-BY)*(AX-CX)

LAB := sqrt((AX-BX)*(AX-BX)+(AY-BY)*(AY-BY))LBC := sqrt((BX-CX)*(BX-CX)+(BY-CY)*(BY-CY))LCA := sqrt((CX-AX)*(CX-AX)+(CY-AY)*(CY-AY))

116


Individuazione di sottoproblemi

• Quando il problema è complesso conviene partire con una individuazione di sottoproblemi

• Scriviamo un algoritmo contenente azioni o condizioni complesse per l’esecutore che dettaglieremo e raffineremo in passaggi successivi per ottenere un algoritmo direttamente eseguibile

• Ognuno dei sottoproblemi potrà essere risolto da un algoritmo a parte che potremo riutilizzare, quando sarànecessario, nella soluzione di ulteriori problemi complessi.

117


Individuazione di sottoproblemi: vantaggi

• I dettagli delle diverse soluzioni sono descritti negli algoritmi dei sottoproblemi

• In generale, uno stesso sottoproblema deve essere risolto più volte nella soluzione di un problema principale

• Dagli algoritmi derivano programmi, quindi si possono raccogliere librerie di software da riutilizzare in nuovi programmi

118


Esercizio: frazioni

• Scrivere un algoritmo che verifichi se una frazione èapparente o propria

• Sapreste risolverlo senza un’analisi del problema?• Vi ricordate la “FASE 1: Dare un nome al problema

partendo dall’analisi del problema” e la “FASE 2: Scrivere la specifica funzionale”?– apparenti: numeratore multiplo di denominatore– proprie: numeratore minore di denominatore

119


Esercizio: MCD

• Scrivere un algoritmo che calcoli il massimo comune divisore di due numeri


partendo dall’analisi del problema” e la “FASE 2: Scrivere la specifica funzionale”?– Il massimo comune divisore di due numeri è il più grande

numero, minore o uguale del più piccolo dei due, che divide entrambi

120


Esercizio: anno bisestile

• Scrivere un algoritmo che verifichi se un anno èbisestile producendo un messaggio


partendo dall’analisi del problema” e la “FASE 2: Scrivere la specifica funzionale”?– Un anno è bisestile (ha 366 giorni) se è divisibile per quattro (come

il 1980) e non è divisibile per 100 (ad es. il 1900 non è bisestile). Fanno eccezione gli anni divisibili per 400, che sono bisestili (ad es. il 2000 è bisestile).

– Questa regola non si applica prima del 1582, anno di introduzione del calendario gregoriano.

121


Esercizio: busta paga

• Scrivete un algoritmo che calcoli l’importo della busta paga settimanale di un lavoratore sapendo il numero di ore che ha lavorato durante una settimana e la retribuzione oraria

• L’algoritmo deve segnalare l’opportunità di far recuperare al lavoratore delle ore di lavoro se non è stato rispettato l’accordo sindacale che prevede un minimo di 35 ore settimanali

• L’algoritmo deve altresì tenere in conto le ore di straordinario che sono, come da contratto, retribuite il doppio di quelle normali

122


Esercizio: poligoni

• Scrivere un algoritmo che, date le coordinate di quattro punti corrispondenti ai vertici di un poligono irregolare, riconosca se si tratta di un quadrato o di un rettangolo e nel caso calcoli la sua area

123


Problema: calcolare il massimo tra K numeri

• Scrivere un algoritmo che fornisca in input ad un programma un numero K e K interi positivi. L’algoritmo deve restituire il valore massimo tra quelli introdotti e stampare in ordine inverso i numeri inseriti.

• Sembra un problema già visto:– Si supponga di fornire in input ad un programma un numero K e K

interi positivi. Il programma deve restituire il valore minimo tra quelli introdotti.

• ma non lo è!! Infatti dobbiamo memorizzare tutti i valori inseriti per stampare il primo inserito per ultimo

• Ma quante variabili usiamo?

124


Gli array

• Nelle situazioni in cui si devono memorizzare un INSIEME di dati allori si può usare la struttura di dati chiamata vettore o array

• Un array (vettore) è costituito da una sequenza di elementi consecutivi nella memoria di un calcolatore

• Un array si può vedere come una generalizzazione del concetto di variabile

125


Gli array

• Ad ogni istante un array individua un insieme di valori• Ogni singolo valore nell’array è individuato dall’identificatore

(nome) dell’array e da un indice che ne individua la posizione nella sequenza degli elementi nell’array stesso

• Un array è caratterizzato da una dimensione che esprime il numero di elementi che contiene

• L’operazione di assegnazione permette di modificare il valore di un determinato elemento della sequenza come per una qualsiasi variabile

• In genere gli elementi di un array sono tutti dello stesso tipo(stringhe, interi, caratteri, ecc.) ma in alcuni linguaggi di programmazione sono permessi array di elementi di tipo diverso, es. JavaScript, ma non è una scelta consigliabile

126


Gli array in Javascript

• Gli array (o vettori) contengono un insieme di dati rappresentati da un singolo nome di variabile

• Un array contiene un insieme di elementi

• Ogni elemento è identificato da un indice (il primo ha indice zero)

0

elemento

127


Gli array in Javascript

• Un array è creato mediante la seguente dichiarazione:

var nome_array = new Array (numero_di_elementi)

• Si fa riferimento ad un elemento, ad esempio, nei seguenti modi:– nome_array[0] = “Pippo”;

– nome_array[y] = 27*sqrt(k/2);

– window.prompt(nome_array[k*3]);

128



• Ipotizziamo di aver già letto i numeri

2 5 4 1 6 8 5 3 7 3

0 1 2 3 4 5 6 7 8 9

ListaNumeri

129



2

5 4 1 6 8 5 3 7 3

MAX

2

ListaNumeri

0 1 2 3 4 5 6 7 8 9

130



2

5

4 1 6 8 5 3 7 3

MAX

5

ListaNumeri

0 1 2 3 4 5 6 7 8 9

131



2

5

4 1 6 8 5 3 7 3

MAX

5

ListaNumeri

0 1 2 3 4 5 6 7 8 9

132



2

5

4 1 6 8 5 3 7 3

MAX

5

ListaNumeri

0 1 2 3 4 5 6 7 8 9

133



2 5 4 1

6

8 5 3 7 3

MAX

6

ListaNumeri

0 1 2 3 4 5 6 7 8 9

134



2 5 4 1 6

8

5 3 7 3

MAX

8

ListaNumeri

0 1 2 3 4 5 6 7 8 9

135



2 5 4 1 6

8

5 3 7 3

MAX

8

ListaNumeri

0 1 2 3 4 5 6 7 8 9

136


Problema: soluzione preliminare e raffinamentistart

end

read K

leggi i K numeri

max := ListaNumeri[0]

calcola max

write max

scrivi in ordine inverso

startleggi i K numeri

i := 0

i < K

i := i + 1

vero

falso endleggi i K numeri

readListaNumeri[i]

137



end

read K

leggi i K numeri


calcola max

write max


startcalcola max

i := 1

i < K

i := i + 1

ListaNumeri[i] > max

max := ListaNumer[i]

vero

falso

vero

falso

endcalcola max

138



end

read K

leggi i K numeri


calcola max

write max


startscrivi in ordine inverso

i := K - 1

i >= 0

i := i - 1

vero

endscrivi in ordine inverso

writeListaNumeri[i]

falso

139


Esercizio

• Tradurre il precedente algoritmo e tutti i successivi in pseudo-codice

• Scrivere il codice Javascript che traduca l’algoritmo

140


Esempio

• Assegnare a tutte le posizioni di un vettore un numero X. Assumere che la dimensione del vettore sia uguale ad N e che la prima posizione del vettore sia uguale a 0

141


Esempiostart

i := 0

i < N

i := i + 1

vero

falsoend

read X,N

vettore[i] := X

142


Codice Javascript<html><head>

<title>Esercizio sugli array</title></head><body><script></script></body></html>

Inserito per mostrareil contenuto dell’array

143


Esempio

• Assegnare alle posizioni di indice pari di un vettore il valore 10 e alle posizioni dispari il valore 20. Assumere che la dimensione del vettore sia uguale ad N e che la prima posizione del vettore sia uguale a 0

144


Esempiostart

i := 0

i < N

i := i + 1

vero

falsoend

read N

vettore[i] := 10

i è dispari

vettore[i] := 20

falso vero

145


Codice Javascript<html><head><title>Esercizio sugli array</title>

</head><body><script></script></body></html>

Inserito per mostrareil contenuto dell’array

146


Problema: ricerca di un elemento

• Ricerca di un numero all'interno di un vettore. Assumere che la dimensione del vettore sia uguale ad N e che la prima posizione del vettore sia uguale a 0.

• Esempio: Se N=4 e il contenuto del vettore è– vettore[0]=7– vettore[1]=10– vettore[2]=555– vettore[3]=14

• se proviamo a cercare il numero 555 il risultato deve essere il seguente: “il numero 555 è alla posizione 2 del vettore”

• se proviamo a cercare il numero 90 il risultato deve essere il seguente: “il numero 90 non è presente nel vettore”

147


Problema: ricerca di un elementostart

i := 0

i < N

i := i + 1

vero

falso

end

read N,X

vettore[i]=Xvero

write"X è in posizione i"

presente := false

presente := true

falso

presente=false

write"X non presente"

vero

falso

148


Codice Javascript: prima parte<html><head><title>Esercizio sugli array</title>

</head><body><script><!-- Inizio script JavaScriptvar N,X,i,presente;

N = window.prompt("Inserisci la lunghezza dell'array");N = N * 1;var vettore = new Array(N);i = 0;while (i < N){vettore[i] = window.prompt("Inserisci vettore[" + i + "]");vettore[i] *= 1; //è la stessa cosa di: vettore[i]=vettore[i]*1;i = i + 1;}X = window.prompt("Inserisci il numero da ricercare");X = X * 1;………………………

Non presente nell’algoritmoma necessario

149


Codice Javascript: seconda parte………………………i = 0;presente = false;while (i < N){if(vettore[i]==X){window.alert("Il numero " + X + " è presente in posizione " + i);presente = true;

} i = i + 1;

}if(presente==false){window.alert("Il numero " + X + " non è presente");

}// Fine script --></script> </body></html>

150


Problema: conteggio occorrenze

• Conteggio delle occorrenze di un numero all'interno di un vettore. Assumere che la dimensione del vettore sia uguale ad N e che la prima posizione del vettore sia uguale a 0.

• Esempio: Se N=4 e il contenuto del vettore è– vettore[0]=555– vettore[1]=10– vettore[2]=555– vettore[3]=14

• se proviamo a contare quante volte il numero 555 compare nel vettore allora il risultato deve essere il seguente: “il numero 555 compare 2 volte”

• se proviamo a cercare il numero 90 il risultato deve essere il seguente: “il numero 90 compare 0 volte”

151


Problema: conteggio occorrenzestart

i := 0

i < N

i := i + 1

vero

falso

end

read N,X

vettore[i]=Xvero

occorrenze := 0

occorrenze := occorrenze + 1falso

writeoccorrenze

152


Codice Javascript: prima parte<html><head>

<title>conteggio occorrenze in array</title></head><body><script><!-- Inizio script JavaScriptvar N;var X;var i;var occorrenze;

N = window.prompt("Inserisci la lunghezza dell'array");N = N * 1;var vettore = new Array(N);i = 0;while (i < N){vettore[i] = window.prompt("Inserisci vettore[" + i + "]");vettore[i] *= 1;i = i + 1;

}X = window.prompt("Inserisci il numero da ricercare");X = X * 1;………………

Non presente nell’algoritmoma necessario

153


Codice Javascript: seconda parte

………………i = 0;occorrenze = 0;while (i < N){if(vettore[i]==X){occorrenze = occorrenze + 1;

} i = i + 1;

}window.alert("Il numero " + X + " compare " + occorrenze + " volte nell'array");

// Fine script -->

</script></body></html>

154


Problema: verifica ordinamento

• Scrivere un algoritmo ed un relativo programma in Javscriptche calcoli il valore di una variabile booleana che deve essere true se l’array è ordinato in maniera crescente e falsealtrimenti e stampi il relativo messaggio. Assumere che la dimensione del vettore sia uguale ad N e che la prima posizione del vettore sia uguale a 0.

• Esempio: Se N=4 e il contenuto del vettore è– vettore[0]=555, vettore[1]=10, vettore[2]=555, vettore[3]=14

allora la variabile deve valere false• Esempio: Se N=4 e il contenuto del vettore è

– vettore[0]=12, vettore[1]=17, vettore[2]=555, vettore[3]=1312

allora la variabile deve valere true

155


Problema: verifica ordinamentostart

i := 0

i < N -1

i := i + 1

vero

falso

end

read N

vero

ordinato:= true

ordinato := false

ordinato=true

write"array ordinato"

vero

falsovettore[i]>vettore[i+1]

write"array ordinato"falso

156


Codice Javascript: prima parte<html><head>

<title>verifica ordinamento array</title></head><body><script>

<!-- Inizio script JavaScriptvar N;var i;var ordinato;

N = window.prompt("Inserisci la lunghezza dell'array");N = N * 1;

var vettore = new Array(N);

i = 0;while (i < N){vettore[i] = window.prompt("Inserisci vettore[" + i + "]");vettore[i] *= 1;i = i + 1;

}………………

157


Codice Javascript: prima parte………………i = 0;ordinato = true;while (i < N){if(vettore[i]>vettore[i+1]){ordinato = false;

} i = i + 1;

}if(ordinato==true){ window.alert("array ordinato");

}else{ window.alert("array non ordinato");

}

// Fine script -->


158


Individuazione di sottoproblemi

• Quando il problema è complesso conviene partire con una individuazione di sottoproblemi

• Scriviamo un algoritmo contenente azioni o condizioni complesse per l’esecutore che dettaglieremo e raffineremo in passaggi successivi per ottenere un algoritmo direttamente eseguibile

• Ognuno dei sottoproblemi potrà essere risolto da un algoritmo a parte che potremo riutilizzare, quando sarànecessario, nella soluzione di ulteriori problemi complessi.

159



• I dettagli delle diverse soluzioni sono descritti negli algoritmi dei sottoproblemi

• In generale, uno stesso sottoproblema deve essere risolto più volte nella soluzione di un problema principale o in problemi diversi

• Dagli algoritmi derivano programmi, quindi si possono raccogliere librerie di software da riutilizzare in nuovi programmi

160


Esempio: ripetizione di codice

• Se in un algoritmo fosse prevista la lettura di due numeri positivi in ingresso, allora la parte di codice Javascript che traduce questa parte dell’algoritmo potrebbe essere

161


Esempio: ripetizione di codice<SCRIPT> </SCRIPT>

162



• Desideriamo controllare che l’input inserito sia effettivamente un numero intero positivo

• Se non è un intero positivo il numero inserito si segnala l’errore e si richiede una nuova immissione

• Si noti parseInt(.), isNaN(.) e alert(.)

163



• Il precedente esempio contiene due blocchi di istruzioni simili per la richiesta e il controllo dell’input, una per ogni valore richiesto all’utente

• I due blocchi di istruzioni differiscono per:– la variabile su cui è memorizzato il valore in input (a0 e b0)– il messaggio che viene visualizzato nella finestra “prompt” (“Inserisci il

primo/secondo numero”)• Se l’algoritmo prevedesse l’inserimento di 12 numeri da

memorizzare in altrettante variabili avremmo scritto per 12 volte lo stesso codice!!!

• Ci piacerebbe poter disporre di una nuova istruzione del tipo• promptNumero(messaggio)

• La nuova istruzione dovrebbe essere come prompt ma con il controllo che il valore immesso sia un intero positivo

164


Esempio: ripetizione del codice

• Se dovessimo scrivere un algoritmo che presi tredici numeri determini se sono tutti e tredici dispari o meno allora questo stralcio di codice dovrebbe essere scritto 13 volte per 13 variabili diverse (con un arrayrisparmieremmo un po’)

var N1, N1_dispari;

N1 = window.prompt("Inserisci il numero");

N1 = N1 * 1;

while (N1 > 1) {

N1 = N1 - 2;

}

if (N1==0)

{ N1_dispari = true; }

else

{ N1_dispari = true; }

165


Esempio: ripetizione del codice

• Ci piacerebbe poter disporre di una nuova istruzione del tipo

• NumeroDispari(numero)• La nuova istruzione dovrebbe dire true se il numero è

dispari e false altrimenti così potremmo scrivere

var N1, N1_dispari;

N1 = window.prompt("Inserisci il numero");

N1 = N1 * 1;

N1_dispari = NumeroDispari(N1);

166



• Per risolvere il problema del calcolo del MCD bisogna risolvere il sottoproblema della divisibilità

• Per risolvere il problema del pari o dispari bisogna risolvere il sottoproblema della divisibilità

• Per risolvere il problema del numero primo bisogna risolvere il sottoproblema della divisibilità

• La suddivisione in sottoproblemi serve a risolvere un sottoproblema con un algoritmo, codificarlo in un linguaggio di programmazione, riusare il codice scritto per la risoluzione di altri problemi (pensate al problema di calcolare la radice quadrata di un numero)

167


Le funzioni: definizione

• In altre parole: si vorrebbe definire una funzione , cioèuna parte di codice utilizzabile in più parti di uno stesso programma

• In JavaScript questo è possibile farlo utilizzando la parola chiave function :

function nome_della_funzione ( arg1, arg2, …, argn) {“definizione della funzione”

}

parametri “formali”della funzione, usatinella definizione della funzione

nome dellafunzione

parentesi graffe!

168


Le funzioni: richiamo

• La definizione di una funzione è una sequenza di istruzioni, un blocco di istruzioni

• Le istruzioni contenute in una funzione non vengono eseguite quando definite ma solo al momento del richiamo della funzione:

• nome_della_funzione(val1, val2, …, valn)

• Quando l’interprete incontra un richiamo di una funzione passa ad eseguire il codice contenuto nella definizione della funzione, dopo aver sostituito i parametri formali con quelli attuali

parametri attuali della funzione

169


Ambito di validità delle variabili

• Variabili locali: i parametri formali e le dichiarazioni di variabili interne ad una funzione

• Variabili globali: le dichiarazioni di variabili esterne alle funzioni, a livello più alto

• La variabili locali sono visibili solo all'interno della funzione in cui sono dichiarate ma mai all'interno di altre funzioni o a livello principale

• Le dichiarazioni locali nascondono quelle principali con lo stesso identificatore

170


Le funzioni: restituire un risultato

• All’interno di una funzione si può usare l’istruzione return per restituire dei valori, di solito il risultato prodotto dalla funzione stessa– return <espressione>; : restituirà il valore computato

dall’espressione– return ; : restituirà undefined

• In entrambi i casi si esce dalla funzione e l’interprete JavaScript passa ad eseguire l’istruzione che segue il richiamo della funzione

171


Esempio<SCRIPT> </SCRIPT> -->

172


Esempio

• La funzione promptNumero(.) richiede un numero intero in input, verifica che il valore immesso lo sia

• Il valore restituito è il numero intero positivo inserito dall’utente, dopo averlo convertito in numero(!)

• Il parametro attuale è il messaggio da visualizzare nella richiesta

173


Individuazione di sottoproblemi: esempio

• Scrivere un algoritmo che determina se un numero èperfetto.

• Un numero si dice perfetto quando è uguale alla somma di tutti i suoi divisori escluso se stesso.

• Ad esempio, il numero 28, divisibile per 1, 2, 4, 7, 14 èun numero perfetto (28 = 1 + 2 + 4 + 7 + 14).

• Per scrivere questo algoritmo dovremmo scrivere un algoritmo per la divisibilità ed il relativo codice Javascript

174


Esempio: numero perfetto

end

start

vero

falso

divisore < N

N

divisore := 1



vero falso

write"numero perfetto"

write"numero non perfetto"

vero falso

somma := 0

somma = N

somma := somma+divisore

175


Codice Javascript<html><head>

<title>Esercizio sui numeri perfetti</title></head>

<body><script><!-- Inizio script JavaScript

function isDividable(dividendo,divisore){if(dividendo%divisore==0)return true;

elsereturn false;

}

function promptNumero(messaggio) {var numero = window.prompt(messaggio);while (isNaN(numero) || numero <= 0 ||

numero == null ||((numero - parseInt(numero)) != 0)) {

window.alert("Il valore " + numero + " non va bene,\n" +"inserire un numero intero positivo.");

numero = window.prompt(messaggio);}return numero * 1;

}

176


Codice Javascript

var N;var divisore;var somma;

N = promptNumero("Inserisci il numero");divisore = 1;somma = 0;while (divisore < N){if(isDividable(N,divisore)==true)somma = somma + divisore;

divisore = divisore + 1;}

if(somma==N)window.alert("Il numero " + N + " è perfetto");

elsewindow.alert("Il numero " + N + " non è perfetto");

// Fine script -->


177


Cosa è un programma per il processore?

<html><head>

<title>Esempio</title></head><body><script></script></body></html>

A: indirizzo in RAM 1000B: indirizzo in RAM 1002X: indirizzo in RAM 1004

4726 …….4730 MOV R1,10004734 MOV R2,10024738 MOV R3,10044342 JNE R1,R2,43544346 MOV R3,#14350 JMP 43584354 MOV R3,#24358 ……..

Sommario - di.unito.itrossano/DIDATTICA/MDAMS-0506/... · Rossini); • Anche per sapere...

Documents

Transcript of Sommario - di.unito.itrossano/DIDATTICA/MDAMS-0506/... · Rossini); • Anche per sapere...