PROVA PRATICA DEL 16 SETTEMBRE 2005 - n.43

Indicazioni per la consegna

Nella consegna della prova pratica e' importante che gli studenti rispettino le seguenti indicazioni. Se tali indicazioni non vengono rispettate, c'e' il rischio che un esercizio, pur essendo stato svolto correttamente, venga valutato come errato.

E' importante che il codice consegnato includa solamente lo svolgimento della procedura richiesta. A tale codice infatti vengono automaticamente attaccati la definizione delle strutture dati e una procedura main per testare quanto consegnato.

Ad esempio, prendiamo un esercizio che utilizza le seguenti strutture dati:

typedef enum Uno {a,b,c} Uno;

typedef struct Due{
int a[3];
int b[3];
} Due;

Se a partire da queste strutture dati l'esercizio chiede di consegnare una procedura int proc (Uno u, Due d), lo studente dovra' consegnare SOLAMENTE il seguente codice:

/*Eventuali procedure di supporto e variabili globali
utilizzate per lo svolgimento dell'esercizio*/
int proc (Uno u, Due d){
bla bla bla /* codice della procedura */
}

E' importante che NON vengano inseriti nella consegna dell'esercizio le istruzioni #include <...>, la procedura main e la definizione delle strutture dati.

Attenzione! Nella consegna di ogni esercizio, dovete inserire TUTTE le eventuali procedure o funzioni di supporto che sono necessarie per la verifica automatica di quell'esercizio (se riutilizzate una procedura definita in un altro esercizio, dovete reinserirla!).

Tema d'esame n. 43: Numeri Amicabili

Due numeri si dicono amicabili se la somma dei divisori di ciascuno di essi, escluso il numero stesso, è uguale all'altro.
Sono amicabili 220 e 284 perché i divisori di 220 sono 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 la cui somma dà 284. Mentre i divisori di 284 sono 1, 2, 4, 71, 142, la cui somma dà 220.
Si conoscono almeno 40.000 coppie di numeri amicabili. Si congettura che le coppie siano infinite. I numeri in coppia finora trovati sono entrambi pari o entrambi dispari, ma non si conosce la ragione per cui non possa esserci una coppia costituita da un numero pari e uno dispari.

Si considerino i seguenti tipi per rappresentare liste semplici di interi.

typedef struct ListaElem{
int primo;
int secondo;
struct ListaElem* next;
} ListaElem;

typedef ListaElem* ListaCoppie;

Funzioni da implementare

  1. int amicabili(int a, int b);
    Restituisce 1 se gli interi (positivi) a e b sono numeri amicabili, e 0 altrimenti.
  2. ListaCoppie seleziona_amicabili(ListaCoppie l);
    Restituisce una nuova lista con gli elementi della lista l che sono coppie di numeri amicabili. La lista l non deve essere modificata.
  3. int conta_amicabili(ListaCoppie l);
    E' una funzione ricorsiva che restituisce il numero di elementi della lista l che contengono coppie di interi amicabili.