Total Hack Cheat
Benvenuto/a su Total hack Cheat....
non aspettate altro tempo Registratevi!!

Parte 1 (3) Guida linguaggio C

Vedere l'argomento precedente Vedere l'argomento seguente Andare in basso

Parte 1 (3) Guida linguaggio C

Messaggio Da RaYoZ il Gio Mag 20, 2010 12:44 pm

Modelli informatici.
Lo scopo di questo capitolo e' di introdurre alcuni algoritmi classici fondamentali.



Algoritmo di Euclide.

Consideriamo quello che per molto tempo e' stato considerato un
prototipo di tutti gli algoritmi e cioe' l'algoritmo di Euclide che serve a trovare il massimo comun divisore di due numeri interi positivi.

var r,m,n: interi;
leggi m, n;
inizio;
fino a che r == 0 esegui;
inizio;
r <- m mod n;
m <- n;n <- r;
fine;
scrivi m;
fine;



Algoritmo di fusione.

Dati due vettori a = {a(1), a(2), ... ,a(m)} e b = {b(1), b(2),
trovare un vettore v con n+m componenti in cui compaiano tutti i componenti di a e b ordinati secondo la stessa relazione.
Un algoritmo che risolve questo problema puo' essere costruito nel seguente modo.
Si confrontano a(1) con b(1) e si inserisce in v(1) il maggiore od uno

a caso se questi sono uguali.
Supponendo che sia a(1) l'elemento scelto si confronta a(2) con b(1), si prende il piu' grande e si inserisce in v(2) e cosi' via.



INPUT:(a(x),b(x))
inizio;
var v, i, j, k : interi;
i <- j <- k <- 1;

inizio;
ripeti fino a
i < m;j < n; | se a(i) < b(j)
| allora v(k) <- b(j);
| j++;k++;
| altrimenti
| v(k) <- a(i);
| i++;k++;
fine;
fine;

Il numero di operazioni richieste dall'esecuzione dell'algoritmo
e' proporzionale a n+m.


Un esempio di fusione :

a = (8, 5, 5, 3, 1); b = (10, 6, 3, 3)

v(1) = max {8,10} = 10
v(2) = max {8,6} = 8
v(3) = max {5,6} = 6
v(4) = max {5,3} = 5
v(5) = max {5,3} = 5
v(6) = max {3,3} = 3
v(7) = max {1,3} = 3
v(Cool = max {1,3} = 3
v(9) = max {1}




Algoritmi di ordinamento.

Tra gli algoritmi fondamentali troviamo quelli di ordinamento.
Dato un vettore a = { a(1), a(2), .... , a(n) } ed una relazione di ordine tra gli elementi, trovare la permutazione degli elementi di a che trasforma il vettore di a in un vettore 'a ordinato rispetto alla relazione.
Esistono vari algoritmi di soluzione.
Ne vedremo qualcuno confrontando il risultato finale.Il primo consiste

nello scegliere negli elementi di a il maggiore e porlo ad esempio nel

primo posto di 'a e cosi' via.



inizio;
var a[n],i,b,k: interi;
per i <- 1 a n |inizio;
|b <- 0;k <- 0;
|per j <- 1 a n
|a passi i+1|inizio
| |se a(j)>b
| |b <-a(j);k <-j;
| |fine;
|a(k) <- a(i);a(i) = b;
|fine;
fine;



Questo algoritmo effettua un numero di confronti pari a n(n-1)/2.
L'aspetto negativo e' che effettua lo stesso numero di conti indipendentemente dal vettore iniziale.
Anche se questo fosse gia' ordinato l'algoritmo eseguirebbe lo stesso numero di cicli.
L'algoritmo che vedremo ora non possiede questo difetto.Esso effettua il confronto del primo elemento di a con il secondo e se questo e' maggiore viene scambiato di posto. Viene poi confrontato il secondo con il terzo e cosi via fino all'ultimo elemento.
A questo punto ricomincia da capo fino che non ci sono piu' scambi per un intero esame del vettore.


inizio;
var b,k,t,a[n]: interi;
k <- t <- 1;
ripeti fino
a quando k = 1 |inizio;
|k <- 0;
| per i <- 1
| a n - t |inizio;
| |se a(i)>a(i+1)
| |allora
| | inizio;
| | b <- a(i);
| | a(i) <- a(i+1);
| | a(i+1) <- b;
| | fine;
| |k <- 1;
| |fine;
|t++;
|fine;
fine;


In questo caso l'algoritmo esegue n(n-1)/2 confronti, quanto il
precedente, ma se il vettore e' gia' ordinato effettua una sola
iterazione e quindi n-1 confronti.
Esistono molti altri algoritmi di ordinamento ma per la loro
complessita' non li tratteremo in questo scritto.



Algoritmi di visita grafi.

Gli algoritmi di visita di un grafo sono quelli che partendo da un nodo assegnato del grafo e muovendosi solo attraverso nodi ed archi adiacenti visitano tutti i nodi e gli archi di un grafo.
L'origine degli algoritmi di visita a grafi e' del secolo scorso quando

vennero studiati come metodi sicuri di uscita dai labirinti.
Tutti questi si basano sulla possibilita' di lasciare dei "marcatori" nei nodi per indicare nodi ed archi gia' visitati.
I segnali lasciati non vengono mai rimossi ne modificati. Si presuppone che il grafo sia memorizzato come lista di adiacenze.
Supponiamo che sia G(N,A) il grafo da visitare e a(i) con i î N la lista si adiacenze (a(i) indica l'insieme di nodi adiacenti al nodo i).
La struttura dell'algoritmo partendo da un nodo generico 1 e' :


inizio
T = {1}
ripeti fino a quando T != 0|inizio;
|scegli un elemento i di T;
|scegli un elemento j di a(i);
|se j non segnato |inizio;
| |segna j;
| |aggiungi j a T;
| |fine;
|se i nodi di a(i)
|sono tutti
|segnati |inizio;
| |togli i da T;
| |fine;
|fine;
fine;


L'algoritmo appena visto non e' completamente specificato in quanto viene descritto ad azioni senza precisare ad esempio quale e' il metodo di selezione tra due nodi adiacenti.




Algoritmo di ricerca a ventaglio.

Un altro algoritmo di visita e' quello di ricerca a ventaglio.
Questo ricerca in ampiezza sciegliendo tra i nodi di T quello inserito per primo . Una volta scelto un nodo i in T, sceglie tutti i suoi nodi
adiecenti prima di proseguire.
In questo modo l'albero di visita risulta di profondita' minima.


inizio;
T = {1};
ripeti fino a quando T != 0|inizio;
|prendi primo nodo di T e toglilo da T
|per ogni j î a(i) |inizio;
| |se j non segnato
| | segna j;
| | mettilo
| | fine T;
| |fine;
|fine;
fine;




Algoritmo di ricerca a scandaglio.

Il seguente algoritmo effettua una ricerca in profondita' ed e' basato sul criterio di scelta ad ogni passo di un arco (i, j) tale che i sia l'ultimo nodo scoperto.
Si indica con p(i) il padre del nodo i, e cioe il nodo dal quale i e' stato scoperto.
Dato che la scelta parte dal nodo 1 possiamo porre p(1) = 1.
V indica l'insieme dei nodi visitati.

inizio;
T = {1}; V = {1}; i = 1;
se tutti gli archi adiacenti a i sono stati visitati
inizio;
se i == p(i) STOP
altrimenti
i <- p(i);
fine;
altrimenti ; inizio;
prendi un arco non visitato adiacente a i;
fine;
se j !î V
inizio;
i <- j;
fine;
fine;


Ai fini dei modelli strutturali ha molta importanza l'ottimizzazione di questi.
Difatti i precedenti algoritmi vogliono esclusivamente dimostrare a grandi linee il funzionamento di questi.
Esistono molti altri algoritmi per la ricerca di cammini ottimali su grafi tra cui l'algoritmo di Dijkstra, quello di Floid Warshall ecc. ma sempre per la loro complessita' verranno qui omessi.
A coloro interessati all'argomento posso consigliare il terzo volume di Knuth della serie "The Art of Computer Programming".
La trattazione sviluppata non e' di quelle piu' semplici ma sicuramente risulta una tra le piu' complete esistenti. E' complicato da trovare.
Nel caso che foste interessati il riferimento internazionale e' il seguente : ISBN: 0-201-03803-x della casa editrice Addison Wesley.
Il suo costo e' di circa 86.000 L. per volume.



Aspetto modulare e sottoprogrammi.

La possibilita' di scomporre e strutturare un programma e'
fondamentale.
La scomposizione perche' sia significativa e' necessario che
venga concepita a livello di analisi.
Per avere un'idea molto semplice di sottoprogramma possiamo dire
che se una certa funzione compare ripetutamente in piu' punti del
programma le si assegna un nome e la si richiama per nome.
Un sottoprogramma si divide in due parti.
Una e' la parte dichiarativa dove figura il nome della stessa
mentre l'altra parte e' il corpo della procedura.

Ad esempio:

scroll() /* Dichiarazione */

{ /*
int righe,i = 1; *
righe=25; * Corpo
while (i++ != righe) * Procedura
printf("\n"); *
} */

Il programma che usa una sottoprocedura viene definito main
program o programma principale.
In genere esiste un programma principale e un numero n di
sottoprocedure : in ogni istante e' attiva una sola di queste.
La struttura delle chiamate puo' essere molto complessa ed
implicare numerosi livelli.
Ad es.:


O Programma Principale
/ \
/ \
/ \
o A o B
/ \ \
/ \ \
o C o D o E
| / \
| / \
o B o B o C


Ogni sottoprocedura possiede una serie di parametri che possono
essere suddivisi in parametri formali e reali.
Come abbiamo visto in esempi precedenti, il programma principale
puo' avere in piu' punti la stessa sequenza di istruzioni.


Ora, la sottoprocedura potrebbe essere completamente indipendente
dal main program.

Un esempio allo scopo di chiarire il concetto :

procedura SALVE;
inizio;
var nota(1:12) :carattere;
nota <- "Salve mondo!"
richiama SCROLL;
scrivi nota;
fine;
subroutine SCROLL;
inizio;
var incremento: intero;
incremento <- 1;
fino a che incremento++ != 23|inizio;
|scrivi '\013';
|fine;
fine;
ritorna;

Difatti come si puo' vedere la subroutine scroll non deve ricevere parametri dal main e quindi puo' essere considerata indipendente.
Nel caso che il sottoprogramma debba elaborare dei valori forniti al momento del richiamo della subroutine allora potremo suddividere i parametri come prima specificato.

Per parametri reali si intendono quelli forniti dal programma chiamante al momento del richiamo della procedura.

Per parametri formali si intendono gli identificatori delle variabili utilizzate che al momento del richiamo della procedura vengono sostituite dai valori reali passati.

Generalmente i valori trasmessi a una sottoprocedura devono essere specificati come dello stesso tipo.
Vedremo questo argomento con il C.



Variabili locali e globali.

Le variabili locali vengono definite nella parte dichiarativa della procedura e hanno validita' solo all'interno di questa.
Parleremo in modo piu' particolareggiato di questo argomento nei capitoli riguardanti il linguaggio C.
Le variabili globali sono invece definite nel programma principale dove possono essere utilizzate.
Queste possono essere utilizzate anche all'interno delle sottoprocedure in qunto vengono trasmesse come argomento al momento della chiamata.



Quando una variabile e' riferita ad una sola procedura non
esistono inconvenienti ad utilizzarla all'interno del programma
chiamante.
Questo significa che se una variabile X viene utilizzata come
variabile locale all'interno del main program, ad esempio, puo'
essere usato lo stesso identificatore all'interno di una
sottoprocedura senza che la prima venga modificata da questa.



Biblioteche o librerie.

Tralasceremo la notazione algebrica per definire il concetto di librerie.
All'interno del linguaggio C nemmeno la funzione printf e' originaria di questo, ma e' universalmente disponibile all'interno di tutti i compilatori C.
Quando un sottoprogramma o una funzione puo' essere comune a piu'
programmi allora e' possibile inserire questa all'interno di una libreria e utilizzarla al momento del bisogno.
La creazione di librerie potrebbe essere un mezzo di comunicazione tra programmatori.
Perche' riscrivere piu' volte un algoritmo, ad esempio di ricerca, e non invece inserirlo in una biblioteca di sottoprogrammi ?
Per potere inserire un programma in una data libreria bisogna compilare il sorgente, in modo da ricavare un file .OBJ, e unirlo in questa forma alla lib scelta.



Strutture di dati.

Vedremo ora cosa si intende per struttura di dati.Ricordo che un tipo e' costituito da un insieme di valori e dalle operazioni possibili su detto insieme.
Per struttura si intende un insieme di una o piu' variabili anche di tipo diverso raggruppate sotto un unico nome per consentirne un trattamento piu' comodo.
In pascal ad esempio si intendono per struttura i records e difatti questa gode di un certo parallelismo con il concetto di record comune in tutti i file.
Infatti nel concetto di files il record altro non e' che un insieme di dati che descrivono uno stesso oggetto.

Si veda il seguente esempio:

/* Indirizzi */

var nome,cognome,via,citta':carattere;
var cap,telefono,numero_via: interi;

oppure

struttura records |inizio;
|var nome,cognome,via,citta':carattere;
|var cap,telefono,numero_via:interi;
|fine;

Questo modo di trattare raggruppando sotto un solo nome una struttura di dati che puo' essere notevolmente complessa ha lo scopo di permettere un trattamento piu' comodo.
Le strutture difatti aiutano ad organizzare dati complessi in quanto permettono di trattare un gruppo di variabili in relazione tra loro come un'unita' e non come entita' separate.


Ad esempio :

tipo GIORNI:(lunedi, martedi, mercoledi, giovedi .....)

potremo allora dichiarare

var A1, A2:GIORNI;

e da questo

A1 <- 'lunedi';A2 <- 'martedi'

Gli elementi o variabili nominati in una struttura sono chiamati membri.

In particolare nel linguaggio C ci sono un numero di restrizioni sulle strutture.
Le regole essenziali sono che le operazioni che si possono eseguire su di una struttura sono prendere il suo indirizzo ed accedere ad uno dei suoi membri.
Per questo alle strutture non si puo' assegnare o non si possono copiare come un tutt'uno e non si possono passare come valori ad altre funzioni.
Una struttura di dati puo' essere descritta dalla rappresentazione fisica come l'indirizzo, la lunghezza ecc. oltre ai legami che tra queste informazioni.


Un esempio in C :


struct record {
char nome_cliente[30];
char nome_prodott[30];
int prezzo_prodot;
char data_vendita[20];
int numero_fatt;
};

Il discorso relativo alle strutture diventa particolarmente interessante nel momento in cui si vuole gestire dei file mediante indici o, sempre ad esempio, liste.
Un metodo abbastanza utilizzato per la gestione di un indice e' quello di posizionare le chiavi su alberi.
Partendo da una radice si potrebbe posizionare ogni successivo elemento inserito sul braccio sinistro oppure sul destro dell'albero in base ad una comparazione con l'elemento occupante la posizione (nodo) precedente.
Supponendo che i maggiori occupino i bracci a sinistra e i minori
a destra l'inserimento delle stringhe AA, AC, AN, AB, AD
creerebbero

AA
/ \
AC
/ \
AN AB
/ \
AD

In questo modo sarebbe possibili facilitare e sveltire le procedure di ricerca mediante una struttura del tipo

struct _string {
char *stringa;
struct _string *sinistra;
struct _string *destra;
};

in cui *stringa contiene la stringa assegnata mentre le due dichiarazioni ricorsive di strutture sarebbero puntatori ai bracci sinistra e destra dell'albero.
E' facile comprendere che in caso di ricerca di un determinato elemento non sarebbe necessario lo scorrimento di tutto il file ma il percorso potrebbe essere guidato.
Per ora tralasciamo il modo per accedere ai membri di una struttura in quanto lo vedremo nei capitoli riguardanti il linguaggio.



Ricorsivita'.

Lo studio dei fenomeni legati alla ricorsivita' puo' dare luogo a sviluppi complessi.
Parlando di modularita' dei programmi abbiamo visto che una sottoprocedura veniva richiamata dal programma principale.
Una definizione e' ricorsiva quando si definisce qualcosa in termini di se stesso.
In altre parole una funzione e' ricorsiva quando al suo interno compare una chiamata alla procedura stessa.

Concludiamo il discorso fatto fino ad ora per iniziare a vedere effettivamente il linguaggio C.
Fino a questo punto abbiamo accennato ai vari tipi di dati trattati dal linguaggio ed ad alcune istruzioni per i controlli di flusso.
Gli argomenti verranno ripetuti nei capitoli seguenti ma in modo piu' approfondito.
In altre parole questa e' stata solo una "sgrossata" destinata a coloro che non hanno mai avuto nozioni riguardanti la programmazione strutturata.
Un ultima nota prima di iniziare con quanto detto.
Nei corsi che ho tenuto gli anni scorsi ho notato che molti alunni provvenienti dalla programmazione in Basic o da linguaggi ad alto livello facevano una grossa confusione su quanto riguardava i tipi numerici e alfanumerici.
L'impressione che danno questi linguaggi e' quella di aver a che fare con entita' distinte.
In altri termini non e' possibile, ad esempio in basic, fare una somma del tipo

A$ = "A":B = 5
C = A$ + B

L'idea che dovete tenere sui tipi di dati in linguaggio C deve essere piu' affine a quella dell'assembler ove la definizione di un tipo o di un altro influisce solo per quanto riguarda la lunghezza in bytes riservati al tipo stesso.
In linguaggio C una somma come quella presentata nel seguente esempio non sarebbe per nulla errata.

char a = 'A';

main()
{
int c;
c = 5;
printf("%d", a+c);
}

Il risultato sarebbe 70 ('A'= ASCII 65 + C = 5).

Fine Parte 1

RaYoZ
Admin
Admin

Messaggi : 1040
Punti : 2245
Data d'iscrizione : 03.04.10
Età : 22
Località : immerso nei pensieri

Tornare in alto Andare in basso

Vedere l'argomento precedente Vedere l'argomento seguente Tornare in alto

- Argomenti simili

 
Permesso di questo forum:
Non puoi rispondere agli argomenti in questo forum