NGI.Home > Forum
  EOLO HOME  OFFERTE INTERNET WIRELESS EOLO  FORMULA ADSL
   
   
WEBMAIL
   
 
  > Register  
  > FAQ  
  > Members List  
 
  > Calendar  
  > Today's Posts  
   
 

Go Back   NGI Forum > Tech & Tech > Developer's Zone

Reply
 
Thread Tools Rate Thread
Old 23rd December 2010, 11:49   #1
Arėsius
Soft computer
 
Arėsius's Avatar
 
Join Date: Feb 2000
Posts: 67,478
[Impariamo il C] Lezione 12

Buongiorno.

Nelle puntate precedenti del corso collaborativo di programmazione:
  1. installazione dell'IDE, cenni di architettura degli elaboratori
  2. sintassi del C, programmazione strutturata
  3. ancora sulla sintassi, i tipi di dato, le variabili
  4. variabili parte seconda: gli array
  5. introduzione delle funzioni
  6. operatori aritmetici e logici
  7. costrutti di selezione
  8. costrutti di iterazione
  9. ancora sull'iterazione
  10. array multipli e struct
  11. ricorsione
In questo capitolo:
  • ancora sulla ricorsione
  • organizzazione della memoria (heap, stack)
  • i puntatori

Ancora sulla ricorsione

Abbiamo visto, nelle ultime lezioni, tre concetti importanti:
  1. iterazione
  2. ricorsione
  3. strutture dati complesse
In informatica si dice che programmazione = algoritmi + strutture dati, e in fondo č vero, tutto si riduce a questo. Facendo ancora mente locale, sappiamo che gli algoritmi richiedono costrutti di selezione e iterazione.

Esiste inoltre un teorema che ci garantisce che qualsiasi programma iterativo puņ essere reso ricorsivo e viceversa.

La ricorsione č potente, espressiva, e ci consente di risolvere problemi talvolta difficili in maniera elegante. Perņ, ovviamente, ha un trade-off. Ripensiamo un attimo al programma Fibonacci: in sostanza la funzione richiama al suo interno sé stessa per calcolare sotto-problemi pił piccoli. Ad esempio, vale questa equivalenza:

Fibonacci(5) = Fibonacci(4) + Fibonacci(3)

Ma noi sappiamo che possiamo esplodere Fibonacci(4) e Fibonacci(3) in altre chiamate ricorsive, quindi

Fibonacci(5) = ( Fibonacci(3)+Fibonacci(2) ) + ( Fibonacci(2) + Fibonacci(1) )

...e possiamo ancora esplodere Fibonacci(3) e Fibonacci(2)...

Fibonacci(5) = ( ( Fibonacci(2) + Fibonacci(1) ) + Fibonacci(1)+Fibonacci(0) ) + ( ( Fibonacci(1) + Fibonacci(0) ) + Fibonacci(1) )

...e infine il Fibonacci(2) rimanente:

Fibonacci(5) = ( ( ( Fibonacci(1) + Fibonacci(0) ) + Fibonacci(1) ) + Fibonacci(1)+Fibonacci(0) ) + ( ( Fibonacci(1) + Fibonacci(0) ) + Fibonacci(1) )

Questi sono tutti passi base, raggiunti i quali la funzione smette di operare ricorsivamente e ritorna il risultato, che viene "rispedito" alle funzioni chiamanti e utilizzato per effettuare le somme.

Quello che abbiamo intuito, ma ancora non esplicitato, č che il nostro programma deve tenere da qualche parte, in memoria, le informazioni sulle somme parziali che effettuiamo, per poter computare l'equazione finale che abbiamo "appiattito". Ricordiamoci che, nella dichiarazione di funzione, specifichiamo un tipo di valore di ritorno, che corrisponde a riservare un blocco di memoria adatta a immagazzinarlo. Inoltre, anche l'operatore somma sappiamo essere una vera funzione, quindi anch'esso occuperą memoria.

Funzioni ricorsive costringono il programma a continuamente riservare nuova memoria. Dunque, c'č questo svantaggio: possono occupare tantissima memoria perché viene a crearsi un albero di chiamate



e dobbiamo tenere da qualche parte tutti i valori che le foglie assumono, per poi utilizzarli in Fibonacci(5).

Esistono tecniche, come la tail recursion, che evitano questa occupazione di memoria. Non le vedremo nel corso.



Organizzazione della memoria

Facciamo di nuovo mente locale a come funziona il computer. La CPU elabora i dati che prende dalla memoria. Quindi, nella RAM ci saranno i nostri dati, che abbiamo visto possono essere costanti e variabili (semplici, array, strutture, ecc):
  • dati
Perņ, la CPU deve sapere come elaborare questi dati, quindi avremo anche il programma in memoria:
  • dati
  • programma
perņ, in base a quanto detto poco fa, sappiamo che dev'esserci una parte della memoria che andrą ad ospitare i valori di ritorno delle nostre funzioni e, sopratutto, dovrą gestire tutta la faccenda della ricorsione. Questa area di memoria č chiamata stack (cioč pila, catasta). Ogni volta che chiamiamo una funzione sullo stack:
  • verranno copiati i parametri che gli passiamo
  • verranno creati i blocchi di memoria che conterranno il valore di ritorno
  • verranno creati i blocchi di memoria per le variabili con scopo locale (cioč quelle usate solo nella funzione)
  • e altre cose di cui non vi interessa.
Questo bel pezzo di memoria - chiamato record di attivazione - viene allocato tutte le volte che usiamo una funzione. Di nuovo, occhio alla ricorsione! Diamo un'occhiata ad uno schema:



Questo č grossomodo quello che succede nella vostra RAM quando fate partire un programma: il sistema operativo delimita un'area di memoria e dice: "okay, il codice del programma (compilato) lo piazzo quģ, i dati lģ, da quģ in poi č tutto riservato per lo stack".

Ad ogni chiamata a funzione, il sistema operativo crea un nuovo record di attivazione, ci piazza dentro i dati che passiamo come parametri e riserva un'area di memoria per il valore di output, scritto il quale elimina il record, "liberando" memoria. E' un processo automatico, ma vedremo che puņ avere degli effetti collaterali non prevedibili legati al fatto che il dato ritornato rimane in un'area di memoria che ora č libera!

Osserviamo, inoltre, che non possiamo usare memoria infinita per lo stack. Al di lą del fatto che la RAM stessa non č infinita, si vede dal disegno che lo stack finisce dove inizia un'altra roba chiamata heap. Vedremo nelle prossime lezioni che lo heap (binario) ci consente di allocare dinamicamente la memoria che vogliamo.

Dunque, tirando le somme, quando lanciate un programma il sistema operativo gli assegna una fetta di RAM in cui far stare:
  • programma
  • dati
  • stack
  • heap
il totale dello spazio č finito, e in particolare stack e heap si rosicchiano memoria a vicenda. Che succede, quindi, se facciamo troppe chiamate ricorsive? Si verifica il cosidetto stack overflow. Dunque, ci scontriamo con i limiti architetturali: non tutti gli algoritmi ricorsivi sono eseguibili sui computer odierni*.


* La veritą č molto peggiore: esistono addirittura algoritmi ricorsivi che nessun computer potrą mai eseguire, se non producendo output approssimati.


I puntatori

"E va bene, abbiamo parlato della memoria e la sua organizzazione, ma questo non era un corso di C"? Ebbene, č venuto il momento di cominciare a sondare le vere potenzialitą di questo linguaggio.


Ricordiamo un attimo la lezione sulle variabili: le abbiamo viste come blocchi di memoria da utilizzare. Questi blocchi hanno delle etichette con un nome sopra. Ad esempio, facendo

Code:
float f = 3.14;
di fatto realizziamo un nuovo blocco con scritto sopra "f", che conterrą il numero in virgola mobile "3.14".

Naturalmente, il computer non ragiona a etichette ma ogni variabile avrą un preciso indirizzo in memoria. La RAM č organizzata infatti in tantissime celle, ognuna identificata da un numero naturale:



In questo esempio, la nostra variabile č floating point, quindi usa 4 byte. La variabile č allocata a partire dall'indirizzo 248440.


Ora, questo fatto degli indirizzi č del tutto mascherato al programmatore. Voi potete tutta la vita ignorare questo fatto e programmare in C tranquillamente come avete fatto finora. Ciononostante, vedremo che il poterci "riferire" alle precise locazioni di memoria in cui risiedono i nostri dati conferisce al C/C++ una grande potenza, che si riflette su una maggiore difficoltą e, sopratutto, nella capacitą di incasinarsi la vita in maniera devastante.


Ora un po' di sintassi e qualche ultima considerazione. Come scopro l'indirizzo preciso in cui risiede la mia variabile? Attraverso l'operatore "&":

Code:
float f=3.14;
printf("%p", &f);    // si noti la "p" di pointer
La "& commerciale" prende la variabile e ci ritorna il suo indirizzo preciso in memoria. Ma dove abbiamo gią visto la "e commerciale"? Nella scanf!

Code:
int a;
scanf("%d", &a);
Questo perché? perché la scanf deve leggere un input da tastiera e "metterlo" in una variabile.

Esercizio 1: perché alla scanf non passiamo la variabile direttamente ma il suo indirizzo?


Si puņ anche operare al contrario, ovvero creare una variabile che non contenga davvero un dato bensģ un puntatore al dato. Questo avviene con l'operatore di deferenziazione "*"

Code:
int* puntatore; 
int a;
puntatore = &a;
scanf("%d", puntatore);

/* le seguenti istruzioni stampano lo stesso valore */
printf("%d\n", *puntatore);  
printf("%d\n", a);
Osserviamo l'uso dell'operatore di deferenziazione. Nel primo caso ci consente di dichiarare una variabile di tipo puntatore. Si osservi che nella dichiarazione di puntatore č anche necessario specificare il tipo di dato puntato (in questo caso intero). Questo perché (come abbiamo visto prima nel disegno) le variabili occupano pił di un blocco di memoria.

Nel secondo caso, usiamo l'operatore per "recarci" nella locazione di memoria e "estrarre" il dato, e quindi ha esattamente lo stesso comportamento della variabile puntata.


Esercizio 2: creare una struct fatta di due campi: un intero e un puntatore alla struct stessa.


Esercizio 3: provare a capire cosa succede in questo codice:

Code:
void main() {
char s[11]="hello world";
unsigned int i;
for (i=0; i<11; i++)
    printf("%c", *(s+i));
}
Attached Images
File Type: gif stackheap.gif (1.2 KB, 638 views)
__________________
Lode a Bacco, in saecula saeculorum.
Emergent

Last edited by Arėsius; 23rd December 2010 at 12:20.
Arėsius is offline   Reply With Quote
Old 23rd December 2010, 12:01   #2
Ray
Portatore del Cagnazzo
 
Ray's Avatar
 
Join Date: Jun 2000
Location: Modena
Posts: 6,292
Occhio all'immagine hotlinkata da baidu che non si vede
__________________
Ray, TnT Soldiers
Ray is offline   Reply With Quote
Old 23rd December 2010, 12:05   #3
Niymiae
Five Leaf Clover
 
Niymiae's Avatar
 
Join Date: Mar 1999
Location: Magrathea
Posts: 3,216
lo faccio o non lo faccio, lo faccio o non lo faccio...
__________________
the e.UGO Xperience
The HyperIntelligent Shade of the color Green™
Who the hell do you think I am?
Niymiae on X360 Live and Steam

••
Niymiae is offline   Reply With Quote
Old 23rd December 2010, 12:13   #4
Gioz
viso alla parete
 
Gioz's Avatar
 
Join Date: Jan 2009
Location: Autogrill
Posts: 5,330
Quote:
Originally Posted by Niymiae View Post
lo faccio o non lo faccio, lo faccio o non lo faccio...
Guarda su YouTube: click
YT Thumbnail

__________________
(12:08) Gioz: ieri primo ban su agorą, un coppino di 24h
(12:09) Mr_MiMe: perchč? hai detto che dio esiste?

Gioz is offline   Reply With Quote
Old 23rd December 2010, 12:17   #5
Niymiae
Five Leaf Clover
 
Niymiae's Avatar
 
Join Date: Mar 1999
Location: Magrathea
Posts: 3,216
Comunque, intanto:
Spoiler:

Es1 : Perché lo scanf ha bisogno di sapere dove (indirizzo di memoria) andare a mettere il valore che prende in entrata.
Es2 : struct test { int val; struct test *testpoint };
Es3 : Scorre l'indirizzo delle singole variabili char dell'array e stampa una alla volta il loro valore.


Non vedo i video
Mi č venuto un dubbio, tra l'altro. Poi faccio la domanda.
__________________
the e.UGO Xperience
The HyperIntelligent Shade of the color Green™
Who the hell do you think I am?
Niymiae on X360 Live and Steam

••

Last edited by Niymiae; 23rd December 2010 at 12:19.
Niymiae is offline   Reply With Quote
Old 23rd December 2010, 12:27   #6
Gioz
viso alla parete
 
Gioz's Avatar
 
Join Date: Jan 2009
Location: Autogrill
Posts: 5,330
Quote:
Originally Posted by Niymiae View Post
Non vedo i video
Fallo!
__________________
(12:08) Gioz: ieri primo ban su agorą, un coppino di 24h
(12:09) Mr_MiMe: perchč? hai detto che dio esiste?

Gioz is offline   Reply With Quote
Old 23rd December 2010, 12:28   #7
Arėsius
Soft computer
 
Arėsius's Avatar
 
Join Date: Feb 2000
Posts: 67,478
la riposta 3 Niymiae č corretta, ma stai analizzando l'epifenomeno. prova a dedurre cosa veramente sta avvenendo sotto il cofano!
__________________
Lode a Bacco, in saecula saeculorum.
Emergent

Last edited by Arėsius; 23rd December 2010 at 12:33.
Arėsius is offline   Reply With Quote
Old 23rd December 2010, 12:28   #8
nanomad
Dietro le sbarre
 
nanomad's Avatar
 
Join Date: Apr 2005
Location: Papia (olim Ticinum)
Posts: 5,221
Caricate le lezioni 11 e 12 sul wiki.
__________________
Rivuoi i video nel forum? Usa questa estensione (chrome)
Source & firefox version
"(...) the three great virtues of a programmer: laziness, impatience, and hubris." -- LarryWall
nanomad is offline   Reply With Quote
Old 23rd December 2010, 12:39   #9
Niymiae
Five Leaf Clover
 
Niymiae's Avatar
 
Join Date: Mar 1999
Location: Magrathea
Posts: 3,216
Quote:
Originally Posted by Arėsius View Post
la riposta 3 Niymiae č corretta, ma stai analizzando l'epifenomeno. prova a dedurre cosa veramente sta avvenendo sotto il cofano!
Tu hai chiesto cosa succede, non come
__________________
the e.UGO Xperience
The HyperIntelligent Shade of the color Green™
Who the hell do you think I am?
Niymiae on X360 Live and Steam

••
Niymiae is offline   Reply With Quote
Old 23rd December 2010, 12:51   #10
Niymiae
Five Leaf Clover
 
Niymiae's Avatar
 
Join Date: Mar 1999
Location: Magrathea
Posts: 3,216
Comunque:

Spoiler:

Invece di utilizzare la notazione s[i] che punta alla variabile contenuta nell'indirizzo di memoria della relativa posizione dell'array, utilizzi un puntatore ad s, (*s) per andare a prendere il primo elemento (inizio) dell'array, e poi prendi tutti gli indirizzi successivi per intervallo di memoria char (essendo un inizializzazione di array la locazione in memoria dei singoli char č appunto consecutiva, perché vengono instanziate tutti nello stesso momento), ritrovando quindi tutti i singoli elementi dell'array.
__________________
the e.UGO Xperience
The HyperIntelligent Shade of the color Green™
Who the hell do you think I am?
Niymiae on X360 Live and Steam

••

Last edited by Niymiae; 23rd December 2010 at 12:53.
Niymiae is offline   Reply With Quote
Old 23rd December 2010, 13:53   #11
Arėsius
Soft computer
 
Arėsius's Avatar
 
Join Date: Feb 2000
Posts: 67,478
Niymiae ci sei vicinissimo che cosa č "s"?

-----

Sull'argomento, vi propongo un estratto da "alice through the looking glass" di Carroll.



“You are sad,” the Knight said in an anxious tone: “let me sing you a song to comfort you.”

“Is it very long?” Alice asked, for she had heard a good deal of poetry that day.

“It’s long.” said the Knight, “but it’s very, very beautiful. Everybody that hears me sing it—either it brings the tears into their eyes, or else—”

“Or else what?” said Alice, for the Knight had made a sudden pause.

“Or else it doesn’t, you know. The name of the song is called ‘Haddocks’ Eyes.’ ”

“Oh, that’s the name of the song, is it?” Alice said, trying to feel interested.

“No, you don’t understand,” the Knight said, looking a little vexed. “That’s what the name is called. The name really isThe Aged, Aged Man.’ ”

“Then I ought to have said ‘That’s what the song is called’?” Alice corrected herself.

“No you oughtn’t: that’s quite another thing! The song is called ‘Ways and Means’ but that’s only what it’s called, you know!”

“Well, what is the song then?” said Alice, who was by this time completely bewildered.

“I was coming to that,” the Knight said. “The song really isA-sitting On a Gate’: and the tune’s my own invention.”

— Lewis Carroll
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arėsius is offline   Reply With Quote
Old 23rd December 2010, 14:06   #12
Niymiae
Five Leaf Clover
 
Niymiae's Avatar
 
Join Date: Mar 1999
Location: Magrathea
Posts: 3,216
Spoiler:

s č il puntatore al primo elemento dell'array.

Quando viene dichiarato un array vengono istanziate X aree di memoria corrispondenti alle X variabili che dovrą contenere l'array stesso.
Se quel codice funziona - e funziona:

*s = valore contenuto in quell'indirizzo di memoria.
Conseguentemente, s č un puntatore all'indirizzo di memoria del primo elemento dell'array.

Tra l'altro, avrei dovuto esplicitarlo subito ma non mi son soffermato a ragionare sulla questione matematica.

Incrementando di 1 s prendi l'elemento successivo = Incrementando di 1 s punti al successivo indirizzo di memoria allocata, vien da sé che deve sapere di quanto spostarsi = s č un char*, altrimenti non potrebbe funzionare cosģ.

La matematica dei puntatori


Sulla programmazione sono totalmente autodidatta, quindi a livello teorico non sono una cima su tutto.
Sulle risposte 1 e 2 non hai detto niente, devo considerarle esatte o errate?
__________________
the e.UGO Xperience
The HyperIntelligent Shade of the color Green™
Who the hell do you think I am?
Niymiae on X360 Live and Steam

••

Last edited by Niymiae; 23rd December 2010 at 14:13.
Niymiae is offline   Reply With Quote
Old 23rd December 2010, 14:12   #13
Arėsius
Soft computer
 
Arėsius's Avatar
 
Join Date: Feb 2000
Posts: 67,478
non avrei saputo spiegarlo meglio, bravo!

la 1 č corretta, ma ti domando: perché non basta passargli la variabile, per sapere dove risiede in memoria? non potevo, all'interno della funzione, scoprirlo con &variabile?

la 2 č perfetta.
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arėsius is offline   Reply With Quote
Old 23rd December 2010, 14:18   #14
Niymiae
Five Leaf Clover
 
Niymiae's Avatar
 
Join Date: Mar 1999
Location: Magrathea
Posts: 3,216
Sulla 2 ero sicuro al 100%, dopo posto in spoiler il perché
Spoiler:

1) Immagino che la scanf accetti in ingresso un indirizzo di memoria
2) No, perché la variabile non č inizializzata, ma solo dichiarata. Lo dico cosģ ma in realtą non sono affatto sicuro di quel che sto dicendo
__________________
the e.UGO Xperience
The HyperIntelligent Shade of the color Green™
Who the hell do you think I am?
Niymiae on X360 Live and Steam

••

Last edited by Niymiae; 23rd December 2010 at 14:21.
Niymiae is offline   Reply With Quote
Old 23rd December 2010, 14:22   #15
Arėsius
Soft computer
 
Arėsius's Avatar
 
Join Date: Feb 2000
Posts: 67,478
la risposta č in questa lezione. cosa c'č nel record di attivazione?
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arėsius is offline   Reply With Quote
Reply

Bookmarks

Thread Tools
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 04:44.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright 1998-2014 by NGI SpA