Prof. Andrea Borghesan

venus.unive.it/borg

borg@unive.it

Ricevimento

lunedì, prima o dopo lezione? Aula?

1

INFORMATICA DI BASE

Linguaggio C

Analisi e programmazione

2

Tramite un elaboratore si possono risolvere problemi divaria natura: gestione dei c/c di un istituto di credito,prenotazioni ferroviarie…

Il problema deve essere formulato in modo opportuno,perché sia possibile utilizzare un elaboratore per la suasoluzione

Per analisi e programmazione si intende l’insieme delleattività preliminari atte a risolvere problemi utilizzando unelaboratore, dalla formulazione del problema fino allapredisposizione dell’elaboratore

Scopo dell’analisi definire un algoritmo

Scopo della programmazione definire un programma

Analogia uomo-macchina

3

Analogie tra le azioni che devono essere eseguite da unoperatore umano e da un elaboratore in modo automatico

Programma + datiAlgoritmo + dati

ElaboratoreUomo

RisultatiRisultati

Algoritmo, programma e linguaggio di programmazione

4

Algoritmo: elenco finito di istruzioni, che specificano leoperazioni eseguendo le quali si risolve una classe di problemi

Un algoritmo non può essere eseguito direttamentedall’elaboratore

Programma: ricetta che traduce l’algoritmo ed èdirettamente comprensibile, pertanto eseguibile, da partedi un elaboratore

Linguaggio di programmazione: linguaggio rigoroso chepermette la formalizzazione di un algoritmo in unprogramma

Le fasi del procedimento di analisi e programmazione

5

Risultati

Problema

ANALISI

ELABORAZIONE Dati

PROGRAMMAZIONE

Algoritmo

Programma

Relazioni tra problema, analisi,algoritmo, programmazione, programma,dati ed elaborazione

Definizione di algoritmo

6

Algoritmo deriva dal nome del matematico arabo Abu Ja’farMohammed ibn Musa al-Khowarizmi scrisse, circa nell’825, iltrattato “Kitab al jabr w’al-muqabala”. Il termine originario era agorismo, trasformato in algoritmo per analogia

con aritmetica

Un algoritmo è una successione di istruzioni o passi che definiscono leoperazioni da eseguire sui dati per ottenere i risultati; un algoritmofornisce la soluzione ad una classe di problemi

Lo schema di esecuzione di un algoritmo specifica che i passidevono essere eseguiti in sequenza, salvo diversa indicazione

Ogni algoritmo è concepito per interagire con l’ambiente esterno peracquisire dati e comunicare messaggi o risultati; i dati su cui operaun’istruzione sono forniti dall’esterno o sono frutto di istruzionieseguite in precedenza

Ambiente esterno AlgoritmoRisultati o messaggi

Dati

Esempio: Ordinamento di un mazzo di carte

7

Problema:

Sia dato un mazzo da 40 carte da ordinare in modo che lecuori precedano le quadri, che a loro volta precedono fiori epicche; le carte di uno stesso seme sono ordinate dall’asso alre

Algoritmo:

Si suddivida il mazzo in 4 mazzetti, ciascuno costituito datutte le carte dello stesso seme

Si ordinino le carte di ciascun mazzetto dall’asso al re

Si prendano nell’ordine i mazzetti delle cuori, quadri, fiorie picche

Esempio: Ricerca in un mazzo di chiavi

8

Problema:

Si vuole ricercare, all’interno di un mazzo di chiavi, quellache apre un dato lucchetto

Algoritmo:

1) Si seleziona una chiave dal mazzo e la si marca con unpennarello

2) Si tenta di aprire il lucchetto con la chiave appenamarcata; se funziona, si va al passo 4)

3) Altrimenti, si controlla la chiave successiva

i. Se non è marcata, la si marca e si torna al passo 2)

ii. Viceversa, si prende atto che nel mazzo non è presentela chiave che apre il lucchetto

4) Fine della ricerca

Esempio: Radici delle equazioni di 2° grado

9

Problema:

Calcolo delle radici reali di ax2 bx c 0

Algoritmo:

1) Acquisire i coefficienti a,b,c

2) Calcolare b2 4ac

3) Se 0 non esistono radici reali, eseguire l’istruzione 7)

4) Se 0, x1 x2 b/2a, poi eseguire l’istruzione 6)

5) x1 ( b )/2a, x2 ( b )/2a

6) Comunicare i valori x1, x2

7) Fine

Esempio: Calcolo del M.C.D. 1

10

Problema:

Calcolare il M.C.D. di due interi a,b, con a b

Algoritmo:

Formalizzato da Euclide nel 300 a.C., si basa sul fatto cheogni divisore comune di a e b è anche divisore del resto rdella divisione intera di a per b, quando a b e r 0; se r 0, bè il M.C.D.

MCD(a,b) MCD(b,r), se r 0

MCD(a,b) b, se r 0

Nota

L’algoritmo garantisce la determinazione del M.C.D. senza ilcalcolo di tutti i divisori di a e b

Esempio: Calcolo del M.C.D. 2

11

1) Acquisire i valori di a e b

2) Se b a, scambiare i valori di a e b

3) Calcolare il resto r della divisione intera di a per b

4) Se r 0, MCD(a,b) b; comunicare il risultato all’esterno;eseguire l’istruzione 6)

5) Se r 0, sostituire il valore di a con il valore di b ed il valoredi b con il valore di r; tornare al passo 3)

6) Fine

Proprietà degli algoritmi

12

Affinché una “ricetta”, un elenco di istruzioni, possa essereconsiderato un algoritmo, devono essere soddisfatti i seguentirequisiti: Finitezza: ogni algoritmo deve essere finito, cioè ogni singola

istruzione deve poter essere eseguita in tempo finito ed un numerofinito di volte

Generalità: ogni algoritmo deve fornire la soluzione per unaclasse di problemi; deve pertanto essere applicabile a qualsiasiinsieme di dati appartenenti all’insieme di definizione odominio dell’algoritmo e deve produrre risultati cheappartengano all’insieme di arrivo o codominio

Non ambiguità: devono essere definiti in modo univoco i passisuccessivi da eseguire; devono essere evitati paradossi,contraddizioni ed ambiguità; il significato di ogni istruzione deveessere univoco per chiunque esegua l’algoritmo

Algoritmi e appositi linguaggi

13

Un algoritmo deve poter essere eseguito da chiunque, senzache l’esecutore sia stato necessariamente coinvolto nell’analisidel problema o nella descrizione dell’algoritmo

Gli algoritmi devono essere formalizzati per mezzo di appositilinguaggi, dotati di strutture linguistiche che garantiscanoprecisione e sintesi

I linguaggi naturali non soddisfano questi requisiti, infatti...

sono ambigui: la stessa parola può assumere significati diversi incontesti differenti (pesca è un frutto o un’attività sportiva?)

sono ridondanti: lo stesso concetto può essere espresso in moltimodi diversi, ad esempio “somma 2 a 3”, “calcola 2 3”, “eseguil’addizione tra 2 e 3”

Un primo programma in c

14

Scrivere un programma che calcoli l’area del triangolo:

Elaborare un algoritmo per la risoluzione del problema

Scriverlo in linguaggio C

Compilare il programma ed eseguirlo su computer

Calcolo area triangolo: algoritmo

1. Inserire/leggere la base

2. Inserire/leggere l’altezza

3. Calcolare l’area = (base x altezza)/2

4. Scrivere risultato a video

15

Listato in C: prima versione

// calcolo area del triangolo

# include <stdio.h>

main ()

{

int base;

int altezza;

int area;

base = 3;

altezza = 10;

area = base * altezza /2;

printf(“area = %d\n”, area);

} 16

Listato in C: seconda versione// calcolo area del triangolo

# include <stdio.h>

main ()

{

int base;

int altezza;

int area;

printf(“inserisci valore base: “);

scanf(“%d\n”, &base);

printf(“inserisci valore altezza: “);

scanf(“%d\n”, &altezza);

Area = base * altezza/2;

printf(“area = %d\n”, area);

} 17

Esercizi

1. Scrivere un programma che scriva a video:

Questo

è il mio primo programma

by andrea

2. Scrivere un programma che calcoli y=ax+b,

Dove x=5, a=18 e b =7 (a,b,x numeri interi)

3. Modificare programma precedente in modo che il valore di

x venga immesso dall’utente

18

Esercizi1. Determinare il valore delle var a, b e c al termine di tutte le seguenti istruzioni:

a = -2;

b = a+1;

b = b – abs(a);

c = a*b;

b = 3;

1. Indicare gli errori nel listato:

include <stdio.h>

#define Base 3

#define altezza

main () {

area int;

area = base x altezza

printf(“Base: d\n”, Base); printf(“Altezza: %d/n”; area)

printf(“Area: d\n”, area);

}19

Area del triangolo: versione migliorata

Possiamo accettare base e/o altezza = zero?

// calcolo area del triangolo

# include <stdio.h>

main () {

int base, altezza, area;

printf(“inserisci valore base: “);

scanf(“%d\n”, &base);

printf(“inserisci valore altezza: “);

scanf(“%d\n”, &altezza);

SE base ≠ 0 AND altezza ≠ 0 ALLORA

area = base * altezza/2;

scrivi a video area

ALTRIMENTI “Non è possibile calcolare l’area”

} 20

Esercizi

Se a=5, b=35 e c=7 calcolare le espressioni:

Ris = a+b*c

Ris = (a+b) * (a<b)

Ris = (a+b) && (a<b)

Ris = (a*c-b) || (a>b)

Ris = ((a*c) != b) || (a>b)

Ris = (a>b) || (a<c) || (c==b)

!(a>b) && (c>a)

(a!=c) || ((a<b) && (b<c))

PER CASA: scrivere un programma che verifichi le risposte

21

Esercizi

Scrivere un programma che, richiesti i numeri GG, MM,

AAAA di una data, verifichi se questa è valida

Scrivere un programma che letto l’anno nel formato AAAA,

verifichi se tale anno è bisestile. Suggerimento: un anno è

bisestile se è divisibile per 4 ma non per 100

PER CASA: scrivere un programma che letto base e altezza,

esegua:

A scelta dell’utente il calcolo dell’area del triangolo o

rettangolo

La media delle 2 aree

Il rapporto delle 2 aree

22