Il più grande divisore comune con Java
Significato del più grande divisore comune
Un divisore è un numero intero (intero) che entrerà in un altro numero intero senza un resto. Il più grande divisore comune è meglio spiegato con un'illustrazione. La tabella seguente mostra due numeri: 60 e 108, con tutti i loro divisori superiori a 1.
Ci sono divisori nella tabella che non sono comuni a 60 e 108. Tuttavia, 2 è un divisore comune per entrambi i numeri 60 e 108, ma non è il più grande divisore comune a 60 e 108. Divisor 3 è descritto allo stesso modo. Per ispezione del tavolo, il più grande divisore comune a 60 e 108 è 12. Nessun divisore sopra 12 è comune sia in 60 che in 108. Quindi 12 è il più grande divisore comune per 60 e 108.
Lo scopo di questo articolo è di spiegare come ottenere il più grande divisore comune per sottrazione o per divisione; Con la programmazione eseguita in Java.
GCD per sottrazione
Per ispezione dalla tabella sopra, il GCD per 60 e 108 è 12. Ciò significa che se 12 viene aggiunto ripetutamente, il risultato diventerà 60, più piccolo di entrambi i numeri. Se l'aggiunta di 12 continua, il risultato diventerà 108, maggiore di entrambi i numeri. Questo è:
12 + 12 +12 +12 + 12 = 60
12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108
Questo è:
60 + 12 + 12 + 12 + 12 = 108
Che significa:
60 + 48 = 108
Se l'aggiunta di GCD può portare a entrambi i numeri, forse una qualche forma di sottrazione continua verso il basso può portare al GCD. Questo è un fatto, come illustrato dai seguenti passaggi, a partire dalla differenza di 108 e 60:
108 - 60 = 48
60 - 48 = 12
48 - 12 = 36
36 - 12 = 24
24 - 12 = 12
12 - 12 = 0
Tra 60 e 108, 108 è il numero maggiore. Successivamente, la differenza della differenza risultante (48 per il primo passaggio) e il sub -traend (60 per il primo passaggio) è ottenuta ripetutamente fino a quando la risposta è zero. Nei passaggi, il numero più piccolo viene sottratto, il numero più grande. All'ultimo passaggio, il minuend e il subtrahend sono gli stessi. Questo stesso valore è il più grande divisore comune.
Lascia che i numeri il cui GCD sia necessario essere A e B. Se questi numeri non hanno GCD maggiore di 1, significa che il loro più grande divisore comune è 1. Nella programmazione, la complessità temporale per trovare il GCD mediante sottrazione è O (A+B). Se A è 1 e B è 5, i passaggi senza programmazione saranno:
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0
Il GCD qui è 1. Ci sono cinque passaggi qui e non sei passaggi di (A + B). Tuttavia, nella programmazione, il numero massimo possibile di operazioni di codice è ciò che viene preso come complessità temporale.
Coding GCD per sottrazione
La classe e il metodo per il più grande divisore comune mediante sottrazione in Java sono:
class gcdsint gcds (int a, int b)
if (a == b)
restituire a;
if (a> b)
restituire GCDS (A-B, B);
restituire GCDS (A, B-A);
Inizia con una dichiarazione per l'ultimo passaggio matematico quando entrambi i numeri risultanti sono uguali. Le due dichiarazioni successive sottraggono il numero più piccolo dal numero maggiore in modo ricorsivo. Una classe principale Java e il metodo principale di Java, per andare con la classe sopra, è:
Classe pubblica Mainpublic static void main (string args [])
GCDS OBJ = new GCDS ();
int ret = obj.GCDS (108, 60);
Sistema.fuori.println (ret);
L'output è 12.
GCD per divisione
La tabella sopra viene ripetuta qui per un facile riferimento:
I due numeri il cui GCD è necessario sono 60 e 108, con 108 il numero maggiore. La spiegazione di cui sopra per la sottrazione è iniziata con:
12 + 12 +12 +12 + 12 = 60
12 + 12 +12 +12 + 12 = 60 + 12 + 12 + 12 + 12 = 108
Questo è:
60 + 12 + 12 + 12 + 12 = 108
Che significa:
60 + 48 = 108
La divisione modulo è una divisione in cui la risposta è l'intero numero del quoziente e il resto è anche preso in considerazione. Considera il resto quando si dividono 108 per 60 e resti dei quozienti risultanti e i loro divisori corrispondenti.
108 % 60 = 48 (i.E 1 R 48)
60 % 48 = 12 (i.E 1 R 48)
48 % 12 = 0 (i.E 4 R 0)
La divisione del modulo termina quando il resto è 0. Il GCD è il divisore per l'ultimo passaggio. Era già noto, dall'altro metodo sopra, che il più grande divisore comune è 12.
108 mod 60 non è zero. Se il GCD tra 60 e 108 dovesse essere trovato mediante sottrazione, la prima differenza per il GCD tra 60 e 108 sarebbe 48 e si può dimostrare che il GCD tra 60 e 108 è 12. 60 mod 48 non è zero. Se il GCD tra 60 e 48 (il resto precedente) dovesse essere trovato mediante sottrazione, la prima differenza per il GCD tra 60 e 48 sarebbe 12 e si può dimostrare che il GCD tra 60 e 48 è 12. 48 mod 12 è zero e ha 0 resti. Se il GCD tra 48 e 12 dovesse essere trovato mediante sottrazione, la prima differenza per il GCD tra 48 e 12 sarebbe 36. 36 non è il GCD tra 48 e 12; Tuttavia, 36 è un multiplo di 12, che è il GCD.
Usando qualsiasi mezzo, il lettore può dimostrare con i passaggi precedenti che, dato che il GCD per 60 e 108 è 12, anche il GCD per 60 e 48 è 12; e il GCD per 48 e 12 è ancora 12.
Considera un altro esempio per trovare il GCD per divisione. Il problema ora è: trovare il GCD per divisione per i numeri 18 e 30.
Soluzione:
30 % 18 = 12 (i.e. 1 r 12)
18 % 12 = 6 (i.e. 1 r 6)
12 % 6 = 0 (i.e. 2 r 0)
Il GCD è 6, letto dall'ultima riga, dove il modulo è 0.
30 Mod 18 non è zero. Se il GCD tra 30 e 18 dovesse essere trovato mediante sottrazione, la prima differenza per il GCD tra 30 e 18 sarebbe 12 e si può dimostrare che il GCD tra 30 e 18 è 6. 18 Mod 12 non è zero. Se il GCD tra 18 e 12 dovesse essere trovato mediante sottrazione, la prima differenza per il GCD tra 18 e 12 sarebbe 6 e si può dimostrare che il GCD tra 18 e 12 è 6. 12 Mod 6 è zero. Se il GCD tra 12 e 6 dovesse essere trovato mediante sottrazione, la prima differenza per il GCD tra 12 e 6 sarebbe 6 e si può dimostrare che il GCD tra 12 e 6 è 6. 6 è anche un multiplo di 6 stesso, che è il GCD.
Usando qualsiasi mezzo, il lettore può dimostrare con i passaggi precedenti che, dato che il GCD per 30 e 18 è 6, anche il GCD per 18 e 12 è 6; e il GCD per 12 e 6 è ancora 6.
Ora considera il GCD ottenuto da 1 e 5 per divisione:
5 % 1 = 0 (i.e. 5 r 0)
C'è solo un passaggio (una riga) qui. Per terminare questa sezione, si noti che il divisore all'ultima riga, quando si cerca il GCD per divisione, è il GCD.
Inoltre, nota che:
GCD (A, B) = GCD (B, R)
Dove "A" e "B" sono due diversi numeri interi e "R" è il resto della divisione tra A e "B."" B "può essere più grande di" a "o" a "può essere più grande di b. Ciò significa che se il resto di una divisione non è zero, allora il più grande divisore comune tra i due numeri è lo stesso del più grande divisore comune tra il divisore e il resto. La prova per questa affermazione è stata illustrata sopra.
Questo può andare subito per la divisione Modulo, come sperimentato sopra fino a quando il resto è zero. Quando il resto è zero, questa regola ripetuta non regge. A rigor di termini, nella divisione Modulo, non importa se "A" sia più grande di B o B è più grande di "A"; Il resto è lo stesso numero intero positivo.
Coding GCD per divisione
Se il più grande divisore comune per la divisione tra 60 e 108 è richiesto matematicamente, allora i passaggi sarebbero
108 % 60 = 48 (i.E 1 R 48)
60 % 48 = 12 (i.E 1 R 48)
48 % 12 = 0 (i.E 4 R 0)
Si noti che è il numero più grande che si sta dividendo, il numero più piccolo. La classe Java e il metodo per fare questa divisione è:
class gcddint gcdd (int a, int b)
if (a % b == 0)
ritorno b;
restituire GCDD (B, A % B);
La prima dichiarazione nel metodo rappresenta l'ultimo passaggio matematico. La seconda affermazione fa la divisione modulo. Entrambe le dichiarazioni chiamano il metodo in modo ricorsivo. La complessità temporale per GCD per divisione è O (log (a + b)). Una buona classe principale e il metodo principale per questo codice sono:
Classe pubblica Mainpublic static void main (string args [])
GCDD OBJ = new GCDD ();
int ret = obj.GCDD (108, 60);
Sistema.fuori.println (ret);
L'output è 12.
Conclusione
Il più grande divisore comune può essere ottenuto sottraendo prima il numero più piccolo dal numero maggiore e quindi continuando a sottrarre il minuend dalla differenza o dalla differenza dal minuend, a seconda del numero più grande.
Il più grande divisore comune può anche essere ottenuto dividendo prima il numero maggiore per il numero più piccolo usando la divisione Modulo; e poi continuando a dividere il resto per il divisore o il divisore per il resto, a seconda di quale è più grande, ancora dalla divisione del modulo. A rigor di termini, nella divisione Modulo, non importa se "A" sia più grande di B o B è più grande di "A"; Il resto è lo stesso numero intero positivo.
Questo viene fatto a livello di programmazione in modo remoto.