Homework (compito per casa) 4

Massimo Comun Divisore con l'Algoritmo di Euclide (per numeri interi di lunghezza arbitraria)

Vedi anche: DomandeHomework404, SoluzioneHomework404, RisultatiHomework404

---

---

Descrizione

Il massimo comun divisore di due numeri e' il più grande divisore comune dei due numeri. Ad esempio, il massimo comun divisore di 24 e 36 è 12. Esiste un antichissimo modo per determinare il Massimo Comun Divisore (MCD) di due numeri interi strettamente positivi, dovuto a Euclide, definito dalle seguenti equazioni ricorsive:

• MCD(n,n) = n
• MCD(m,n) = MCD(m-n,n) se m>n
• MCD(m,n) = MCD(m,n-m) se n>m

Scopo del programma sarà quello di implementare l'algoritmo di Euclide, in modo che funzioni con interi di dimensione arbitraria, quindi con un numero di cifre non previsto a priori. Dovrete implementare gli interi come liste di cifre decimali. Vi suggerisco di implementare almeno tre funzioni: uguale, minore e differenza. uguale dira' se due interi così rappresentati sono uguali. minore dirà se il primo è minore del secondo. differenza restituisce una lista di cifre che rappresenta la differenza di due interi rappresentati come liste di cifre.

Il vostro programma dovrà:

Input

• prendere in input una sequenza di cifre decimali. Qualsiasi numero minore di 0 o maggiore di 9 sarà interpretato come un terminatore di un numero. Il primo terminatore dividerà il primo numero dal secondo, mentre il secondo terminatore indicherà la fine dell'input.

Output

• produrre in output il Massimo Comun Divisore dei due numeri. Il numero andrà stampato stampando ciascuna cifra con il formato:

 
%1d

in modo che il numero appaia come una sequenza di cifre senza spazi tra una cifra e l'altra.

IMPORTANTE

• non far produrre al programma altri output oltre a quelli richiesti.

Ecco un esempio di input del programma:

 
1
9
7
2
6
1
0
6
4
-1
5
1
0
7
9
1
8
2
0
10

In questo caso il programma dovrà calcolare l'MCD tra 197261064 e 510791820 e restituire in output il numero 21252. I numeri dell'esempio cadono ancora nel campo intero, ma il vostro programma dovrà funzionare correttamente anche se i numeri in input e output hanno centinaia o migliaia di cifre (certamente finchè c'è memoria...).

Attenzione NON producete nessuna altra scritta oltre i numeri, altrimenti il test automatico del vostro programma fallirà miseramente!

Come compilare ed eseguire il programma

• usate un editor per scrivere il testo del programma e salvatelo in formato testo semplice in un file con l'estensione .c (ad esempio di nome trexpuno.c)
  • NON usate Word, Openoffice, Kword, Abiword che introducono caratteri strani
• compilate (e contemporaneamente linkate) il programma con il comando

gcc -g -o mcd mcd.c

• eseguite il programma scrivendo

./mcd

Come consegnare il programma

• Avete tempo fino a Mercoledì 22 Dicembre alle ore 23.59 (ora sono le 12:25 del 31).
• Consegnate il testo del programma sorgente C da voi scritto. Io lo compilerò e testerò.
• Usate esclusivamente la pagina di consegna. Non verranno accettate spedizioni via email.

• Set ALLOWTOPICCHANGE = DocentiProg1Group

-- IvanoSalvo - 09 Dec 2004