Tags:
create new tag
view all tags

Homework 3

  1. Si considerino le seguenti definizioni in C:
    #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;
    

    Implementare una funzione Autoveicolo *create_archive(char *text_archive, int *pn) che crea e restituisce un array, allocato dinamicamente, di struct Autoveicolo i cui valori sono contenuti nella stringa text_archive e ritorna in *pn il numero di struct. La stringa text_archive rispetta il seguente formato:

    • la stringa è suddivisa in linee (le linee sono terminate dal carattere '\n') e ogni linea contiene i dati di un autoveicolo.
    • ogni linea ha il seguente formato:
          N;C;T;G;M;A
      
      dove N e C sono il nome e il cognome del proprietario, T è il numero di telaio e G, M, A sono giorno mese ed anno della data di immatricolazione. Nessuna delle sequenze di caratteri N, C, T, G, M, A contiene il carattere ';'. La sequenza T ha lunghezza pari a NTELAIOSIZE. Si assume che la stringa text_archive rispetta il formato, pertanto la funzione non deve effettuare nessun controllo in tal senso. Ad esempio, se la stringa text_archive è:
      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
      
      (gli a-capo corrispondono al carattere '\n'), allora la funzione crea e restituisce il seguente array:
      [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}}
      
      e scrive in *pn il valore 4.

  2. Un triangolo nel piano cartesiano può essere definito dalle coordinate dei suoi tre vertici. Si considerino in particolare le seguenti definizioni in C:

    typedef struct { 
    	double x; 
    	double y;
    } Point;
    

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

    typedef struct {
    	Point *v1, *v2, *v3;
    	double area;
    } Triangle;
    
    per rappresentare triangoli nel piano cartesiano, come aggregati di tre punti, più il valore dell’area;

    struct genericList {
    	void *info;
    	struct genericList *next;
    };
    typedef struct genericList List;
    

    per rappresentare liste di elementi di tipo generico, in cui l’informazione in un singolo nodo è un puntatore a void.

    Implementare una funzione List *buildSortedTriangles(List *listOfPoints) 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.

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

    Suggerimento: l’area di un triangolo può essere calcolata usando la formula di Erone: area = sqrt(p*(p-a)*(p-b)*(p-c)), dove p è il semiperimetro, a,b,c sono le lunghezze dei tre lati e sqrt() è 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).

    Suggerimento: Per prendere dimestichezza con le liste generiche, si consiglia di svolgere l'esercizio: Q.20091218-2.genericList-print-add.c.


  3. Il triangolo di Tartaglia è una disposizione di numeri naturali in forma di triangolo che permette il calcolo dei coefficienti binomiali

    choose(n,k) = (n)
    k

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

    1
    1   1
    1   2   1
    1   3   3   1
    1   4   6   4   1
    1   5  10  10   5   1    
    

    Sia Tn,k il k-esimo numero nella n-esima riga del Triangolo di Tartaglia. Si pu˛ dimostrare che choose(n,k) = Tn+1,k+1. Inoltre è facile vedere che la regola che genera il Triangolo di Tartaglia (dati gli opportuni casi base) è la seguente: Tn,k = Tn-1,k-1 + Tn-1,k.

    Scrivere una funzione ricorsiva int choose(int n, int k) che, dati in input due interi n >= 0 e k >=0, calcoli choose(n,k) usando le proprietà del Triangolo di Tartaglia.

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

    Domande & risposte
    La definizione choose(n,k) = Tn+1,k+1 è errata?
    No, assumendo che le righe e le colonne del triangolo siano numerate a partire da 1 (prima riga, seconda riga, ..., prima colonna, seconda colonna, ...)
    È possibile definire una funzione non ricorsiva choose(...) che a sua volta invoca una funzione ricorsiva?
    No, si richiede esplicitamente che la funzione choose(...) sia ricorsiva.

  4. 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.

    n=65 n=33 n=17

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

    Attenzione: si richiede esplicitamente di scrivere una funzione ricorsiva (o una funzione che a sua volta invochi una funzione ricorsiva). Funzioni anche corrette che non usano la ricorsione non saranno ritenute valide.

Edit | Attach | Watch | Print version | History: r8 < r7 < r6 < r5 < r4 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r8 - 2010-01-24 - ToniMancini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback