programmazione_f_c

PROGRAMMAZIONE: linguaggi
Linguaggi ad alto livello : Java, Basic, C++, HTML
Linguaggi a basso livello: assembly
Linguaggio macchina
1
PROGRAMMAZIONE: traduttori
COMPILATORI: da linguaggio evoluto a linguaggio
macchina (eventualmente attraverso assembly)
INTERPRETI: da linguaggio evoluto a linguaggio
macchina, una istruzione alla volta
ASSEMBLATORI: da linguaggio assembly a
linguaggio macchina
2
ELEMENTI DEI LINGUAGGI
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
3
ELEMENTI DEI LINGUAGGI
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
4
ALGORITMI
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.
5
ALGORITMI
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.
6
DIAGRAMMI DI FLUSSO
Il diagramma di flusso è una rappresentazione grafica di un
algoritmo costituita da un insieme di simboli (figure
geometriche standard) collegate da frecce.
7
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.
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);
Il relativo diagramma di
flusso è indicato in figura.
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
Esse si traducono nelle seguenti
pseudo istruzioni:
1)
2)
3)
4)
5)
6)
7)
8)
leggi a, b, c;
se (a + b <= c) vai a 7);
se (a + c <= b) vai a 7);
se (b + c <= a) vai a 7);
stampa “Lati validi”;
fine;
stampa “Lati non validi”;
fine;
e quindi nel diagramma di flusso
indicato a lato:
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:
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
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:
per moltiplicare tra loro due numeri naturali si somma uno
di essi a se stesso un numero di volte uguale all’altro.
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.