Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Esempio di esecuzione di

leggi_N

N=4 Sequenza di numeri da leggere : 8, 1, 9, 7

X =

Inizialmente X è vuoto 0

posizione 2

1 3

Passo 1, leggo il primo numero

Leggo 8 e lo scrivo nella posizione 0, cioè X[0]=8

I=0 8

Passo 2, leggo il secondo numero 8 1

Leggo 1 e lo scrivo nella posizione 1, cioè X[1]=1

I=1

Passo 3, leggo il terzo numero

Leggo 9 e lo scrivo nella posizione 2, cioè X[2]=9 8 1 9

I=2

Passo 4, leggo il quarto numero

Leggo 7 e lo scrivo nella posizione 3, cioè X[3]=7 8 1 9 7

I=3

Termina I=4, quindi I< N non è più verificata 19

Informatica Generale Maria De Marsico

Sottoalgoritmo per la

Inizio trovare il massimo in un

array di N numeri (max_N)

Leggi N e X[N]

Input:

Int X[N],

Int N m = X[0]

k = 1 i = 0

Strutture dati:

Si No Int X[N] // la sequenza

k < N ? Restituisci m Fine

e la sua posizione i

Si

m > X[k] k = k + 1 Output:

? Int m //il valore del massimo

No Int i // l’indice del massimo

Scorro l’array

m = X[k], i = k Equivale all’azione di leggere il prossimo numero

in entrata che era presente nel vecchio algoritmo

20

Informatica Generale Maria De Marsico

Esempio di max_N

Trova il valore m del massimo in X e la sua posizione i . La

lunghezza di X è N=4 e la sequenza da ordinare e’ 8, 1, 9, 7

numeri già esaminati punta all’attuale massimo 8 1 9 7

X = 0 2

indice 1 3

Inizializzazione m=X[0]=8, i=0 8 1 9 7

Passo 1, k=1 esamino X[1]=1

m > X[1] (infatti 8 > 1 ) quindi m e i non cambiano 8 1 9 7

Passo 2, k=2 esamino X[2]=9

m < X[2] (infatti 8 < 9 ) quindi m e i cambiano 8 1 9 7

m = 9 i = 2

Passo 3, k = 3 esamino X[3]=7

m > X[3] (infatti 9 > 7 ) quindi m e i non cambiano 8 1 9 7

k=4, quindi k< N non è più verificata

Termina 21

Informatica Generale Maria De Marsico 7

Ordinare N numeri interi

N=4 Max_Na = 8 in posizione 1

8 7 3 1 Scambio la posizione 1 e 4

N=3

1 7 3 8 Max_Na = 7 in posizione 2

Scambio la posizione 1 e 3

1 3 7 8 N=2 Max_Na = 3 in posizione 2

Nessuno scambio

1 3 7 8 N=1

Termina

1 3 7 8 22

Informatica Generale Maria De Marsico

Ordinare N numeri interi

• Algoritmo ordina_Na

1. Leggi il valore di N dall’esterno

2. Leggi gli N numeri della sequenza nell’array

numeri (con leggi_N)

3. Trova il maggiore (m, i) fra i primi N numeri

dell’array (con

numeri max_N)

4. Scambia fra loro X[i] e X [N]

5. Considera adesso solo i primi N-1 numeri dell’array

(N=N-1)

6. Se N = 1 continua, altrimenti vai al passo 3

7. Stampa X, termina 23

Informatica Generale Maria De Marsico

Osservazioni

• Ogni algoritmo può utilizzare più sotto-

algoritmi

• Input = può essere dall’utente o da un

algoritmo chiamante

• Output = può essere verso l’utente o

verso un algoritmo chiamante 24

Informatica Generale Maria De Marsico 8

Algoritmo per

ordinare N numeri

(N,X[N])=leggi_N()

Inizio (ordina_N)

L’input in realtà

Input : vuoto Lung=N arriva da leggi_N

Si No il cui output viene

N > 1 ? assegnato alla variabile N

e all’array X

(m,i) = max_N(N,X) Stampa(Lung, X[N]) Strutture dati:

Int X[N]

Fine

T = X[N] // la sequenza

Output:

X[N] = X[i] Int Lung //la lunghezza di X

Int X[N] // l’array X ordinato

X[i] = T Scambio dei due valori

Notare l’uso di una variabile di appoggio

N = N-1 25

Informatica Generale Maria De Marsico

Strutture dati

• Tutti i linguaggi ad alto livello per la

programmazione permettono di definire

almeno due tipi di aggregati di variabili (o

strutture dati)

• array : vettori (se a una dimensione tipo lista) o

tabelle (se a due dimensioni), ma possono avere

anche più dimensioni, di valori tutti dello

stesso tipo

• record : gruppi di variabili di tipo diverso per

memorizzare ad esempio diverse caratteristiche

di un oggetto 26

Informatica Generale Maria De Marsico

Record

• Come abbiamo già detto, normalmente è possibile

avere variabili di tipo diverso che rappresentano

informazioni di natura diversa :

• interi, reali …

• caratteri (‘a’,’b’, …)

• sequenze di caratteri (dette stringhe, ”gatto ”, ”oggi

piove !” …)

• I record sono aggregati di variabili di tipo diverso

e permettono di definire nuovi tipi 27

Informatica Generale Maria De Marsico 9

Record

• A cosa possono servire…...

• A rappresentare le schede della biblioteca

stringa

Nome Autore stringa

Cognome Autore Titolo stringa

Scaffale intero

Posizione intero

reale

Costo

… altre informazioni ….. Campi del record 28

Informatica Generale Maria De Marsico

Record

• Il tipo record scheda espresso in C

struct scheda {

char nome //stringa di al più

[100]; //100 caratteri

char cognome

[100];

char titolo

[300];

int scaffale

;

int posizione

;

double costo ;

} ; 29

Informatica Generale Maria De Marsico

Record

//Come dichiaro che voglio

//una variabile di tipo ‘scheda’

struct scheda nuovo_libro;

// come assegno valori ai diversi campi

nuovo_libro.nome =”Jorge" ;

nuovo_libro.cognome =”Amado" ;

nuovo_libro.titolo =”Dona Flor e i

suoi due mariti" ;

nuovo_libro.scaffale =”8" ;

nuovo_libro.posizione =”356" ; 30

Informatica Generale Maria De Marsico 10


PAGINE

11

PESO

845.23 KB

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in scienze e tecnologie della comunicazione (POMEZIA, ROMA)
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher valeria0186 di informazioni apprese con la frequenza delle lezioni di Informatica Generale e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Costa Luciano.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Informatica generale

Algoritmi - Parte 1
Appunto
Algoritmi - Parte 2
Appunto
Sicurezza e Copyright
Appunto
Informatica - Domande
Appunto