Homework3 < Programmazione1

Tags: view all tags
 <H2>Homework 3</H2>

<!--
<div style="background:#F4FA58; padding:10px; text-align:center">
<a href="/~prog1/formHW3.html">Pagina di consegna di Homework 3</a>
</div>
-->

<DIV ALIGN="justify" style="margin-left:5%; margin-right:10%">
<OL>
<LI>
Si considerino le seguenti definizioni in C:
<pre>
#define NTELAIOSIZE     17       // lunghezza numero di telaio 

typedef struct {
    char *nome;        // nome proprietario (stringa allocata dinamicamente)
    char *cognome;     // cognome proprietario (stringa allocata dinamicamente)
    char telaio[NTELAIOSIZE];   // numero di telaio (codice alfanumerico)
    struct {
        int g;
        int m;
        int a;
    } imm;    // data di immatricolazione
    
} Autoveicolo;
</pre>

Implementare una funzione <code>Autoveicolo *create_archive(char *text_archive, int *pn)</code>
che crea e restituisce un array, allocato dinamicamente, di struct <code>Autoveicolo</code> i cui valori
sono contenuti nella stringa <code>text_archive</code> e ritorna in <code>*pn</code>
il numero di struct. La stringa <code>text_archive</code>
rispetta il seguente formato: 
<ul>
<li>
la stringa &egrave; suddivisa in linee (le linee sono terminate dal
carattere <code>'\n'</code>) e ogni linea contiene i dati di un autoveicolo.
</li>
<li>
ogni linea ha il seguente formato: 
<pre>
    <em>N</em>;<em>C</em>;<em>T</em>;<em>G</em>;<em>M</em>;<em>A</em>
</pre>
dove <em>N</em> e <em>C</em> sono il nome e il
cognome del proprietario, <em>T</em> &egrave; il numero di telaio e <em>G</em>, 
<em>M</em>, <em>A</em> sono giorno mese ed anno della data di immatricolazione.
Nessuna delle sequenze di caratteri <em>N</em>, <em>C</em>, <em>T</em>,
<em>G</em>, <em>M</em>, <em>A</em> contiene il carattere <code>';'</code>.
La sequenza <em>T</em> ha lunghezza pari a <code>NTELAIOSIZE</code>. Si assume che
la stringa <code>text_archive</code> rispetta il formato, pertanto la funzione non deve 
effettuare nessun controllo in tal senso.
Ad esempio, se la stringa <code>text_archive</code> &egrave;:
<pre>
Mario;Dell'Olio;ABCD1234567890GHT;12;1;2004
Laura;Di Carlo;ABBB0987654321HGT;3;10;1999
Maria Luisa;Crociani Sforza Pallavicini;NNNN1234567890BFB;25;11;2006
Giorgio;Verdoni;AAAA09876FFT54321;10;10;2009
</pre>
(gli a-capo corrispondono al carattere <code>'\n'</code>), allora
la funzione crea e restituisce il seguente array:
<pre>
[0] = {"Mario", "Dell'Olio", ABCD1234567890GHT, {12, 1, 2004}}
[1] = {"Laura", "Di Carlo", ABBB0987654321HGT, {3, 10, 1999}}
[2] = {"Maria Luisa", "Crociani Sforza Pallavicini", NNNN1234567890BFB, {25, 11, 2006}}
[3] = {"Giorgio", "Verdoni", AAAA09876FFT54321, {10, 10, 2009}}
</pre>
e scrive in <code>*pn</code> il valore <code>4</code>.
</li>
</ul>
</LI>
<BR>
<LI>
<p>
Un triangolo nel piano cartesiano pu&ograve; essere definito dalle coordinate dei suoi tre vertici. Si considerino in particolare le seguenti definizioni in C:

<pre>
typedef struct { 
	double x; 
	double y;
} Point;
</pre>

per rappresentare punti geometrici nel piano cartesiano (come coppie di coordinate);

<pre>
typedef struct {
	Point *v1, *v2, *v3;
	double area;
} Triangle;
</pre>
per rappresentare triangoli nel piano cartesiano, come aggregati di tre punti, pi&ugrave; il valore dell&#8217;area;

<pre>
struct genericList {
	void *info;
	struct genericList *next;
};
typedef struct genericList List;
</pre>

per rappresentare liste di elementi di tipo generico, in cui l&#8217;informazione in un singolo nodo &egrave; un puntatore a <code>void</code>.
</p>

<p>
Implementare una funzione 
<code>List *buildSortedTriangles(List *listOfPoints)</code>
che riceva come argomento una lista di n istanze del tipo Point e restituisca una lista di istanze del tipo Triangle contenente tutti i possibili triangoli ottenibili con gli n punti. I triangoli costruiti devono avere il valore corretto del campo area, ed i triangoli della lista restituita devono essere ordinati in modo decrescente per area.
</p>

<p>
Si noti che la lista di ritorno <i>non</i> deve contenere coppie di triangoli che coincidano nell'insieme dei vertici, <i>anche se</i> in ordine diverso, ed anche se <code>listOfPoints</code> contiene punti uguali.
</p>

<p>
<i>Suggerimento:</i> l&#8217;area di un triangolo pu&ograve; essere calcolata usando la formula di Erone: <code>area = sqrt(p*(p-a)*(p-b)*(p-c))</code>, dove <code>p</code> &egrave; il semiperimetro, <code>a,b,c</code> sono le lunghezze dei tre lati e <code>sqrt()</code> &egrave; l'operazione di estrazione della radice quadrata (se i tre punti giacciono sulla stessa retta allora possiamo considerare di avere un triangolo degenere di area 0).

<p>
<i>Suggerimento:</i> Per prendere dimestichezza con le liste generiche, si consiglia di svolgere l'esercizio: [[http://www.dis.uniroma1.it/~tmancini/index.php?currItem=teaching.fondprog.materiale.libreriaesercizi.esercizio&fname=Q.20091218-2.genericList-print-add.c][Q.20091218-2.genericList-print-add.c]].

</LI>
<BR>
<LI>
<p>
Il triangolo di Tartaglia &egrave; una disposizione di numeri naturali in forma di triangolo che permette il calcolo dei coefficienti binomiali 

<table align=center><tr><td rowspan=2>choose(n,k) = <font size=+3>(</font></td><td>n</td><td rowspan=2><font size=+3>)</font></td></tr><tr><td>k</td></tr></table>

ovvero il numero di dispozioni semplici di n elementi in classi di k elementi. Eccone un esempio di 6 righe.

<pre>
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1    
</pre>


Sia T<sub>n,k</sub> il k-esimo numero nella n-esima riga del Triangolo di Tartaglia. Si può dimostrare che <code>choose(n,k) = T<sub>n+1,k+1</sub></code>.  
Inoltre &egrave; facile vedere che la regola che genera il Triangolo di Tartaglia (dati gli opportuni casi base) &egrave; la seguente: <code>T<sub>n,k</sub> = T<sub>n-1,k-1</sub> + T<sub>n-1,k</sub></code>.
</p>

<p>
Scrivere una funzione <u><i>ricorsiva</i></u> <code>int choose(int n, int k)</code> che, dati in input due interi <code>n >= 0</code>  e <code>k >=0</code>, calcoli <code>choose(n,k)</code> usando le propriet&agrave; del Triangolo di Tartaglia.
</p>

<p><i>Attenzione</i>: si richiede esplicitamente di scrivere una funzione <i>ricorsiva</i>. Funzioni anche corrette che non usano la ricorsione non saranno ritenute valide.

<p>
<div style="background: #DDDDDD; padding:6pt;">
<b>Domande & risposte</b>
   <dl>
   <dt><i>La definizione <code>choose(n,k) = T<sub>n+1,k+1</sub></code> &egrave; errata?</i></dt>
   <dd><b>No</b>, assumendo che le righe e le colonne del triangolo siano numerate a partire da 1 (prima riga, seconda riga, ..., prima colonna, seconda colonna, ...)
   </dd>
   <dt><i>&Egrave; possibile definire una funzione non ricorsiva <code>choose(...)</code> che a sua volta invoca una funzione ricorsiva?</i></dt>
   <dd><b>No</b>, si richiede esplicitamente che la funzione <code>choose(...)</code> sia ricorsiva.</dt>
   </dl>
</div>

</LI>

<LI>
<p>
Un frattale &egrave; un oggetto geometrico che si ripete nella sua struttura allo stesso modo su scale diverse, ovvero che non cambia aspetto anche se visto con una lente di ingrandimento (auto-similarit&agrave;). In particolare il seguente triangolo &egrave; un frattale. 
</p>

<table align=center>
<tr align=center valign=bottom>
<td>
<textarea rows=31 cols=65 readonly style="font-family:monospace">
                               OOO                               
                                O                                
                             OOOOOOO                             
                              OOOOO                              
                           OOO OOO OOO                           
                            O   O   O                            
                         OOOOOOOOOOOOOOO                         
                          OOOOOOOOOOOOO                          
                       OOO OOOOOOOOOOO OOO                       
                        O   OOOOOOOOO   O                        
                     OOOOOOO OOOOOOO OOOOOOO                     
                      OOOOO   OOOOO   OOOOO                      
                   OOO OOO OOO OOO OOO OOO OOO                   
                    O   O   O   O   O   O   O                    
                 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO                 
                  OOOOOOOOOOOOOOOOOOOOOOOOOOOOO                  
               OOO OOOOOOOOOOOOOOOOOOOOOOOOOOO OOO               
                O   OOOOOOOOOOOOOOOOOOOOOOOOO   O                
             OOOOOOO OOOOOOOOOOOOOOOOOOOOOOO OOOOOOO             
              OOOOO   OOOOOOOOOOOOOOOOOOOOO   OOOOO              
           OOO OOO OOO OOOOOOOOOOOOOOOOOOO OOO OOO OOO           
            O   O   O   OOOOOOOOOOOOOOOOO   O   O   O            
         OOOOOOOOOOOOOOO OOOOOOOOOOOOOOO OOOOOOOOOOOOOOO         
          OOOOOOOOOOOOO   OOOOOOOOOOOOO   OOOOOOOOOOOOO          
       OOO OOOOOOOOOOO OOO OOOOOOOOOOO OOO OOOOOOOOOOO OOO       
        O   OOOOOOOOO   O   OOOOOOOOO   O   OOOOOOOOO   O        
     OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO OOOOOOO     
      OOOOO   OOOOO   OOOOO   OOOOO   OOOOO   OOOOO   OOOOO      
   OOO OOO OOO OOO OOO OOO OOO OOO OOO OOO OOO OOO OOO OOO OOO   
    O   O   O   O   O   O   O   O   O   O   O   O   O   O   O 
</textarea>
</td>
<td>
<textarea rows=15 cols=33 readonly style="font-family:monospace">
               OOO               
                O                
             OOOOOOO             
              OOOOO              
           OOO OOO OOO           
            O   O   O            
         OOOOOOOOOOOOOOO         
          OOOOOOOOOOOOO          
       OOO OOOOOOOOOOO OOO       
        O   OOOOOOOOO   O        
     OOOOOOO OOOOOOO OOOOOOO     
      OOOOO   OOOOO   OOOOO      
   OOO OOO OOO OOO OOO OOO OOO   
    O   O   O   O   O   O   O   
</textarea>
</td>
<td>
<textarea rows=7 cols=17 readonly style="font-family:monospace">
       OOO       
        O        
     OOOOOOO     
      OOOOO      
   OOO OOO OOO   
    O   O   O    
</textarea>
</td>
</tr>
<tr align=center style="font-size:100%">
<td><code>n=65</code></td>
<td><code>n=33</code></td>
<td><code>n=17</code></td>
</table>


<p>
Come si pu&ograve; vedere la propriet&agrave; di auto-similarit&agrave; &egrave; evidente. Il triangolo principale &egrave; composto da quattro parti: una al centro vuota e tre in cui lo stesso pattern usato per costruire il triangolo principale viene applicato ricorsivamente per costruire tre triangoli di dimensione minore. 

Si scriva una funzione 
<code>void fractalTriangle(int n, char M[][n])</code>
che, data la dimensione della larghezza <code>n</code> del triangolo (nelle figure <code>n=65, 33, 17</code>, si noti che deve essere <code>n = 2<sup>k</sup> + 1</code> per qualche naturale <code>k</code>) ed una matrice di caratteri <code>M</code> di <code>n</code> colonne (e numero di righe sufficienti) riempita inizialmente con il carattere <code>' '</code> (spazio), 'disegni' nella matrice <code>M</code> il triangolo di dimensione <code>n</code> usando il carattere <code>'O'</code> (O maiuscola). L'algoritmo per il disegno deve essere <u><i>ricorsivo</i></u>. Il triangolo deve essere disegnato a partire dalla prima riga della matrice (ad es., il triangolo della figura di sinistra --<code>n=65</code>-- deve terminare alla riga di indice 29 di <code>M</code>).
</p>

<p><i>Attenzione</i>: si richiede esplicitamente di scrivere una funzione <i>ricorsiva</i> (o una funzione che a sua volta invochi una funzione ricorsiva). Funzioni anche corrette che non usano la ricorsione non saranno ritenute valide.
</p>
</LI>
</OL>
</DIV>

<!--
<div style="background:#F4FA58; padding:10px; text-align:center">
<a href="/~prog1/formHW3.html">Pagina di consegna di Homework 3</a>
</div>
-->