PROGRAMMAZIONE: linguaggi
1
Linguaggi ad alto livello : Java, Basic, C++, HTMLLinguaggi a basso livello: assemblyLinguaggio macchina
PROGRAMMAZIONE: traduttori
2
COMPILATORI: da linguaggio evoluto a linguaggio macchina (eventualmente attraverso assembly)INTERPRETI: da linguaggio evoluto a linguaggio macchina, una istruzione alla voltaASSEMBLATORI: da linguaggio assembly a linguaggio macchina
ELEMENTI DEI LINGUAGGI
3
Ogni linguaggio ha un alfabeto costituito da differenti caratteri.
Un insieme di caratteri costituisce una parola.
Istruzione è un elemento del linguaggio di programmazione con cui si richiede l’esecuzione di una operazione.
• Ingresso• Uscita• Assegnazione• Confronto• Operazione logica o matematica• Salto
ELEMENTI DEI LINGUAGGI
4
Funzione: insieme di espressioni il cui risultato dipende dal valore assunto da una o più variabili.
Struttura: insieme razionale e ordinato di varie istruzioni• Sequenza• Selezione• Ripetizione
ALGORITMI
5
Un algoritmo (detto anche procedura, prescrizione, processo, routine, metodo) è un insieme di regole (dette anche direttive o istruzioni) che, eseguite secondo un ordine prestabilito, consentono di trovare il risultato di un problema a partire dai dati in ingresso.
ALGORITMI
6
Le caratteristiche fondamentali degli algoritmi sono:
1.non ambiguità: le operazioni indicate devono essere sufficientemente semplici e ben definite da poter essere comprese da un esecutore non particolarmente esperto (uomo o macchina);
2.eseguibilità: l’esecutore deve essere in grado di eseguire ogni singola regola con le risorse a sua disposizione;
3.finitezza: ogni algoritmo deve terminare dopo un numero finito di passi, cioè in un intervallo finito di tempo.
DIAGRAMMI DI FLUSSO
7
Il diagramma di flusso è una rappresentazione grafica di un algoritmo costituita da un insieme di simboli (figure geometriche standard) collegate da frecce.
DIAGRAMMI DI FLUSSO
8
RAPPRESENTAZIONE A BLOCCHI DI SELEZIONI
9
RAPPRESENTAZIONE A BLOCCHI DI SELEZIONI
10
RAPPRESENTAZIONE A BLOCCHI DI RIPETIZIONI
11
Esempio: Massimo Comun Divisore. Un esempio di algoritmo contenente due selezioni binarie con una sola azione è fornito da quello che calcola il Massimo Comun Divisore (MCD) di due interi positivi secondo il seguente metodo di Euclide
Per calcolare il MCD di due interi positivi:
• si divide il maggiore per il minore
• se il resto è 0 il minore rappresenta il MCD cercato
• altrimenti il minore sostituisce il maggiore, il resto sostituisce il minore e il procedimento ricomincia da capo.
Il relativo diagramma di flusso è indicato in figura.
La corrispondente espressione in pseudo istruzioni è la seguente:
1. leggi x, y;2. if (x < y)
scambiali;3. dividi x per y e
chiama r il resto;4. poni x = y;5. poni y = r;6. if (r == 0) stampa
x ; fine 7. vai a 3);
Come si può osservare, nella forma strutturata sono scomparse le istruzioni di salto e i riferimenti numerici delle singole istruzioni.
Esempio: lati di un triangolo. Come esempio di selezioni binarie in cascata si può considerare il seguente
PROBLEMA: “scrivere un algoritmo che consenta di stabilire se tre numeri, a, b, c possono essere i lati di un triangolo”.
ALGORITMO: come è noto, in un triangolo la somma di due lati qualsiasi è maggiore del terzo.
Perciò dovranno essere contemporaneamente soddisfatte le tre condizioni:
a + b > c a + c > b b + c > a
1) leggi a, b, c;2) se (a + b <= c) vai a 7);3) se (a + c <= b) vai a 7);4) se (b + c <= a) vai a 7);5) stampa “Lati validi”;6) fine;7) stampa “Lati non validi”;8) fine;
Esse si traducono nelle seguenti pseudo istruzioni:
e quindi nel diagramma di flusso indicato a lato:
Per dividere tra loro due numeri naturali:
• si sottrae il divisore dal dividendo;
• si continua a sottrarlo dal risultato dell’ultima sottrazione fino a che tale risultato sia maggiore o uguale al divisore
• il numero di sottrazioni effettuate fornisce il quoziente
• il risultato dell’ultima fornisce il resto della divisione
Esempio: divisione con sottrazioni ripetute. Un esempio di ciclo con guardia all’inizio è costituito dall’algoritmo che esegue la divisione intera fra due numeri naturali con il seguente metodo delle sottrazioni ripetute:
Questo algoritmo si traduce facilmente nel diagramma di flusso seguente, dove la variabile res contiene inizialmente il dividendo, la variabile den il divisore. res contiene poi i risultati delle successive sottrazioni, l’ultimo dei quali fornisce appunto il resto.
Il quoziente è fornito dal contatore quoz, che inizialmente vale 0 e viene incrementato di 1 a ogni sottrazione eseguita.
Esempio: moltiplicazione con addizioni ripetute. Un esempio di ciclo con guardia alla fine è costituito dall’algoritmo che esegue la moltiplicazione di due numeri naturali con il metodo delle addizioni ripetute:
Questo algoritmo si traduce facilmente nel seguente diagramma di flusso dove indichiamo con
•A, B i due numeri da moltiplicare
•prod il prodotto
•K una variabile contatore, posta inizialmente uguale a uno dei due numeri. K viene diminuita di 1 ogni volta che si esegue un’addizione, e quando raggiunge il valore 0 determina la fine del ciclo.
per moltiplicare tra loro due numeri naturali si somma uno di essi a se stesso un numero di volte uguale all’altro.
Top Related