HomeWork404 < Programmazione1/AA0506/PZ

Tags: view all tags

---++ Homework (compito per casa) 4 
---++ Massimo Comun Divisore con l'Algoritmo di Euclide (per numeri interi di lunghezza arbitraria)
 
Vedi anche: DomandeHomework404, SoluzioneHomework404, RisultatiHomework404
----
%TOC%
----

---+++ 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:
<pre style='background:lightgrey'> 
%1d
</pre>
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:
<pre style='background:lightgrey'> 
1
9
7
2
6
1
0
6
4
-1
5
1
0
7
9
1
8
2
0
10
</pre>
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...).


__%RED%Attenzione%FINE%__ 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
<pre style='background:lightgrey'>
gcc -g -o mcd mcd.c
</pre>
   * eseguite il programma scrivendo
<pre style='background:lightgrey'>
./mcd
</pre>


---+++ Come consegnare il programma

   * Avete tempo fino a *%RED%Mercoledì 22 Dicembre alle ore 23.59%FINE%* (ora sono le *%SERVERTIME{"$hou:$min del $day"}%*).
   * Consegnate *il testo del programma sorgente C* da voi scritto. Io lo compilerò e testerò.
   * Usate *esclusivamente* la <a href="/~prog1/consegna-Prog4.html">pagina di consegna</a>. Non verranno accettate spedizioni via email.

   * Set ALLOWTOPICCHANGE = Users.DocentiProg1Group

-- Users.IvanoSalvo - 09 Dec 2004