Homework A.A. 2013/2014

Informazioni

Quest pagina contiene le informazioni relative agli Homework assegnati agli studenti.

Gli Homework consegnati saranno verificati automaticamente. In particolare si verificherà:

  • che la compilazione non generi errori
  • che l'esecuzione sia corretta su diversi input
  • che non ci sia eccessiva somiglianza con altri Homework consegnati

La verifica di similarità sarà anch'essa effettuata in modo automatico. In caso di copiatura, si riterranno nulli sia gli elaborati del copiante che del copiato.

Gli Homework dovranno essere consegnati entro la relativa scadenza che sarà comunicata in classe e che sarà ben visibile nella pagina delle consegne. Non si accetteranno proroghe.

La consegna si effettua online alla pagina Consegna Homework. Per consegnare è necessario registrarsi su Twiki a questa pagina.

Il superamento degli Homework permetterà di non sostenere la prova di laboratorio ed, eventualmente, di disporre anche di un bonus di incremento di 1 o due punti punto sul voto finale come descritto in Modalità d'esame.

In caso vi siano domande o problemi, potete rivolgetevi a Simone Silvestri (silvestris@diNOSPAM.uniroma1.it)

Regole generali

1) Seguire esattamente le specifiche dell'input e dell'output.

2) Non includere getchar(), scanf(), System("pause") o qualunque altra chiamata che blocchi l'esecuzione del programma alla fine del codice dell'esercizio (utilizzatele se volete per provare il funzionamento ma non includete le istruzioni di attesa alla fine del file nella versione inviata).

3) Leggere l'input con scanf semplici. Es: scanf("%d",&n) per leggere un intero n, non inserire stampe del tipo printf("Inserisci il valore\n");

4) Inviare un unico file .zip contenente tutti i sorgenti (.c) degli esercizi dell'Homework. ATTENZIONE: non si deve fare una cartella contenente i file sorgenti e poi fare il .zip della cartella, ma si deve creare un file .zip contenente solo i file .c. Controllare bene l'estensione dei file inseriti nel file .zip, essa deve essere (.c) e non (.cc o altro).

5) Vanno inviati SOLO i sorgenti di codice e NON i file compilati (.out, .exe).

6) Il nome da dare ai file contenenti i sorgenti c è: NomeCognome.NumEsercizio.c . Per Paolino Paperino: PaolinoPaperino.1.c per il primo esercizio, PaolinoPaperino.2.c per il secondo, PaolinoPaperino.3.c per il terzo e così via. Il nome da dare al file zip è: NomeCognome.zip. Sulle macchine del laboratorio di calcolo ciò si ottiene col seguente comando di shell (relativamente ai sorgenti dell'esempio):

$ zip PaolinoPaperino.zip PaolinoPaperino.1.c PaolinoPaperino.2.c PaolinoPaperino.3.c

Per verifica si può impartire il comando:

$ unzip PaolinoPaperino.zip

che estrae i file contenuti nel file zip e li ricrea nello stesso direttorio.

7) Per inviare i sorgenti C:

7.1) E' necessario essere iscritti al sito twiki.di.uniroma1.it (si può fare dal link: TWikiRegistration) .

7.2) Creare un file .zip contenente tutti i sorgenti degli esercizi dell'Homework

7.3) Collegarsi alla pagina Consegna Homework

7.4) Inserire i propri dati (wikiname e password sono i dati di accesso a twiki)

7.5) Cliccare su "Browse" (o "Sfoglia", a seconda della lingua del vostro browser internet) e selezionare il file .zip contentente le vostre soluzioni

7.3) Cliccare su "spedisci la tua soluzione!" per effettuare la consegna

7.4) Riceverete una e-mail di conferma a cui non bisogna inviare reply

8) Se le soluzioni vengono inviate più di una volta, ogni nuovo invio sovrascrive i precedenti. Verrà quindi considerato l'ultima versione da voi inviata.

Risultati

  • I risultati del terzo Homework si possono trovare qui
  • I risultati del secondo Homework si possono trovare qui
  • I risultati del primo Homework si possono trovare qui
  • I risultati dell'Homework di prova si possono trovare qui

Homework da consegnare

  • Homework 3 - Consegna entro: 20 Giugno 2014 ore 24:00

Esercizio 1
Un albero binario e' definito attraverso la seguente struttura:

typedef struct int_bin_tree{

   int key;
   struct int_bin_tree *left;
   struct int_bin_tree *right;

}int_bin_tree;

L'esercizio prevede lo sviluppo di una libreria per l'utilizzo di alberi binari che implementi le seguenti funzionalita':
- calcolo del numero di elementi contenuti nell'albero,
- verifica della presenza di un elemento con una certa chiave,
- calcolo del numero di occorrenze di una certa chiave,
- recupero del puntatore a un elemento con chiave massima,
- recupero del puntatore a un elemento con chiave minima,
- stampa ordinata delle chiavi degli elementi dell'albero,
- cancellazione di un elemento che ha una certa chiave.

In particolare, si devono implementare le seguenti funzioni:

   int num_nodes(int_bin_tree *tree)

La funzione ritorna il numero di nodi presenti nell'albero tree. Un albero vuoto ha zero nodi.

   int contains(int_bin_tree *tree, int x)

La funzione ritorna 1 se nell'albero tree e' presente almeno un nodo con chiave x.

   int occurrences(int_bin_tree *tree, int x)

La funzione ritorna il numero di elementi dell'albero tree aventi chiave x. La funzione ritorna 0 se l'albero e' vuoto.

   
   int_bin_tree* min_key(int_bin_tree *tree)

La funzione ritorna il puntatore al nodo dell'albero avente chiave minima, NULL se l'albero e' vuoto. Se sono presenti piu' nodi con chiave minima si puo' ritornare il puntatore ad uno qualsiasi di questi.

   int_bin_tree* max_key(int_bin_tree *tree)

La funzione ritorna il puntatore al nodo dell'albero avente chiave massima, NULL se l'albero e' vuoto. Se sono presenti piu' nodi con chiave massima si puo' ritornare il puntatore ad uno qualsiasi di questi.

   
   int * get_ordered_array(int_bin_tree *tree)

La funzione alloca un vettore di interi di dimensione pari al numero di elementi dell'albero. Il vettore deve contere le chiavi presenti nell'albero ordinate in modo crescente. Se l'albero e' vuoto la funzione ritorna NULL senza allocare nulla.

   
   int_bin_tree * delete(int_bin_tree *tree, int x)
La funzione elimina un nodo con chiave x dall'albero, se presente. Se sono presenti piu' elementi con chiave x si puo' eliminare uno qualsiasi di questi. La funzione ritorna il puntatore alla radice dell'albero.

Si deve modificare QUESTO file riempendo il corpo delle funzioni sopra elencate. Si possono tuttavia utilizzare funzioni ausiliarie. Il main prende in input un intero a ed una sequenza di interi positivi, terminata da un numero negativo. L'intero a serve a testare diverse funzioni, come spiegato in seguito, gli altri interi letti sono invece inseriti nell'albero. La funzione di inserimento insert() e' gia' implementata e non deve essere modificata.

L'homework e' suddiviso in tre parti. Nella prima parte (a = 1) si testeranno solamente le funzioni num_nodes(), contains() e occurencies(). Nella seconda parte (a = 2) si testeranno invece le funzioni min_key(), max_key(). Nella terza parte (a = 3) si testeranno infine le funzioni get_ordered_array() e delete(). Si deve comunque consegnare un unico file con estensione .1.c. La correzione verra' poi effettuata come se si trattasse di esercizi distinti.

Esempio 1 (a = 1)
Si inseriscono i valori
1
1
2
3
4
5
6
7
8
9
10
11
12
13
-1

Il programma deve stampare:
Num nodes 13
contains(0) = 0 occurences(0) = 0
contains(1) = 1 occurences(1) = 1
contains(2) = 1 occurences(2) = 1
contains(3) = 1 occurences(3) = 1
contains(4) = 1 occurences(4) = 1
contains(5) = 1 occurences(5) = 1
contains(6) = 1 occurences(6) = 1
contains(7) = 1 occurences(7) = 1
contains(8) = 1 occurences(8) = 1
contains(9) = 1 occurences(9) = 1
contains(10) = 1 occurences(10) = 1
contains(11) = 1 occurences(11) = 1
contains(12) = 1 occurences(12) = 1
contains(13) = 1 occurences(13) = 1
contains(14) = 0 occurences(14) = 0
...
contains(99) = 0 occurences(99) = 0

Esempio 2 (a = 2)
Si inseriscono i valori
2
1
2
3
4
5
6
7
8
9
10
11
12
13
-1

Il programma deve stampare
1
13

Esempio 3 (a = 3)
Si inseriscono i valori
3
5
5
5
5
3
3
3
5
5
5
1
1
1
3
3
5
5
-1

Il programma deve stampare
1 1 1 3 3 3 3 3 5 5 5 5 5 5 5 5 5
Deleting 1
Num nodes 16
Deleting 1
Num nodes 15
Deleting 1
Num nodes 14
Deleting 3
Num nodes 13
Deleting 3
Num nodes 12
Deleting 3
Num nodes 11
Deleting 3
Num nodes 10
Deleting 3
Num nodes 9
Deleting 5
Num nodes 8
Deleting 5
Num nodes 7
Deleting 5
Num nodes 6
Deleting 5
Num nodes 5
Deleting 5
Num nodes 4
Deleting 5
Num nodes 3
Deleting 5
Num nodes 2
Deleting 5
Num nodes 1
Deleting 5
Num nodes 0

Errori comuni

  • Aggiunta di stampe: non si devono aggiungere stampe ulteriori a quelle previste dall'homework. Ad esempio, se l'output previsto per un esercizio e'
    5
    ed il programma stampa
    il risultato e' 5
    l'esercizio e' considerato errato. Le funzioni di stampa sono in genere fornite con il testo dell'homework e non vanno modificate.
  • Compilazione: I programmi devono compilare correttamente (senza nessun messaggio di errore e senza nessun warning) sotto Linux con il compilatore gcc.
    Attenzione i programmi C sono in genere compilabili in C++, ma il viceversa non è vero. Quindi NON utilizzare compilatori quali g++.
  • Sintassi for: Il C non permette la dichiarazioni di variabili all'interno dell'istruzione del ciclo for. Un istruzione del tipo:
    for(int i = 0; i < 5; i++)
    genera un errore di compilazione.
  • Estensioni: Nel sistema Windows le estensioni dei file sono di default nascoste. Se ad esempio si crea un file pippo.1.c, il file verrà visualizzato come pippo.1 (senza estensione .c). Se lo si rinomina come pippo.1.c, il risultato sara' un file pippo.1.c.c che non e' confonrme alle specifiche richieste. Si deve abilitare nelle opzioni cartella la visualizzazione delle estensioni di tutti i file.

Homework precedenti

Homework anni accademici precedenti

Topic attachments
ISorted ascending Attachment History Action Size Date Who Comment
C source code filec NomeCognomeHwProva2014.1.c r1 manage 0.5 K 2014-04-01 - 18:16 SimoneSilvestri  
C source code filec NomeCognomeHwProva2014.2.c r1 manage 0.7 K 2014-04-01 - 18:18 SimoneSilvestri  
C source code filec NomeCognomeHwProva2014.3.c r1 manage 0.8 K 2014-04-01 - 18:19 SimoneSilvestri  
C source code filec NomeCognome_hw1_2014.1.c r1 manage 0.3 K 2014-04-01 - 18:20 SimoneSilvestri  
C source code filec NomeCognome_hw1_2014.2.c r1 manage 0.5 K 2014-04-01 - 18:21 SimoneSilvestri  
C source code filec NomeCognome_hw1_2014.3.c r1 manage 1.7 K 2014-04-01 - 18:23 SimoneSilvestri  
C source code filec NomeCognome_hw_2_2014.1.c r1 manage 0.5 K 2014-05-06 - 11:50 SimoneSilvestri  
C source code filec NomeCognome_hw_2_2014.2.c r1 manage 0.9 K 2014-05-06 - 11:50 SimoneSilvestri  
C source code filec NomeCognome_hw_2_2014.3.c r1 manage 1.0 K 2014-05-06 - 11:50 SimoneSilvestri  
C source code filec NomeCognome_hw_3_2014.1.c r1 manage 2.6 K 2014-05-29 - 16:32 SimoneSilvestri  
HTMLhtml risultati_hw_1_2014.html r1 manage 140.8 K 2014-05-06 - 11:21 SimoneSilvestri  
HTMLhtml risultati_hw_2_2014.html r1 manage 133.1 K 2014-06-04 - 14:42 SimoneSilvestri  
HTMLhtml risultati_hw_3_2014.html r1 manage 107.2 K 2014-06-23 - 15:21 SimoneSilvestri  
HTMLhtml risultati_hw_prova_2014.html r1 manage 122.8 K 2014-03-28 - 19:53 SimoneSilvestri  
Edit | Attach | Watch | Print version | History: r77 < r76 < r75 < r74 < r73 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r77 - 2014-06-23 - SimoneSilvestri






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