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

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 16:15 del 29).
  • 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.

-- IvanoSalvo - 09 Dec 2004

Edit | Attach | Watch | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r6 - 2004-12-20 - IvanoSalvo






 
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