<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 è 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> è 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> è: <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ò 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ù il valore dell’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’informazione in un singolo nodo è 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’area di un triangolo può essere calcolata usando la formula di Erone: <code>area = sqrt(p*(p-a)*(p-b)*(p-c))</code>, dove <code>p</code> è il semiperimetro, <code>a,b,c</code> sono le lunghezze dei tre lati e <code>sqrt()</code> è 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 è 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 è facile vedere che la regola che genera il Triangolo di Tartaglia (dati gli opportuni casi base) è 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à 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> è 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>È 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 è 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à). In particolare il seguente triangolo è 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ò vedere la proprietà di auto-similarità è evidente. Il triangolo principale è 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> -->
This topic: Programmazione1
>
WebHome
>
HW0910
>
Homework3
Topic revision: r8 - 2010-01-24 - ToniMancini
Copyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback