Il più grande divisore comune con Python

Un fattore è un numero che può entrare in un altro numero senza un resto. Un dividendo divide un divisore per dare il quoziente. Se il dividendo e il divisore sono un numero intero e se il quoziente ha un resto di zero (nessun resto), allora il divisore è chiamato un fattore del dividendo. Il più grande divisore comune è abbreviato, g.C.D o semplicemente GCD. Un altro nome per il massimo divisore comune è il più alto fattore comune, abbreviato H.C.F.

Trovare g.C.F per definizione

Il problema è trovare il fattore comune più alto chiamato anche il più grande divisore comune per i numeri 108 e 240.

Soluzione:

Tutti i fattori superiori a 1 sono inseriti nella tabella seguente:

108: 2 3 4 6 9 12 18 27 36 54 108
240: 2 3 4 5 6 8 10 12 15 16 20 24 30 48 60 120 240

La prima riga ha i fattori di 108 in ordine crescente. La seconda riga ha i fattori di 240 in ordine crescente.

I fattori comuni (divisori) per 108 e 240 sono: 2, 3, 4, 6 e 12.

Per ispezione, il più grande fattore (divisore) comune ai numeri 108 e 240 è 12. Cioè, GCD o H.C.F per 108 e 240 è 12.

Scrivere un programma che troverà il GCD, come spiegato sopra, richiederà troppo tempo. Due metodi più brevi per trovare il GCD sono: GCD per sottrazione e GCD per divisione.

GCD per sottrazione

Per ispezione dalla tabella sopra, GCD per 108 e 240 è 12. Ciò significa che se 12 viene aggiunto ripetutamente, il risultato diventerà 108, il che è più piccolo di entrambi i numeri. Se l'aggiunta di 12 continua, il risultato diventerà 240 che è il più grande di entrambi i numeri. Questo è:

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Questo è:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Che significa:

108 + 132 = 240

Se il GCD può essere aggiunto ripetutamente per fornire uno qualsiasi dei numeri (108 e 240) da cui è richiesto il GCD, potrebbe essere possibile fare ripetutamente una sorta di sottrazione, a cominciare dai numeri forniti per avere il GCD. In effetti, è possibile fare ripetutamente un particolare tipo di sottrazione e ottenere il GCD. Questo inizia con la differenza dei numeri dati.

Problema: trova il più grande divisore comune (fattore comune più alto) per 108 e 240 per sottrazione.

Soluzione:

240 - 108 = 132
132 - 108 = 24
108 - 24 = 84
84 - 24 = 60
60 - 24 = 36
36 - 24 = 12
24 - 12 = 12
12 - 12 = 0

Tra 108 e 240, 240 è il numero maggiore. Dopo la differenza di questi numeri dati, la differenza della differenza risultante (132 per il primo passaggio) e il sub -traed (108 per il primo passaggio) sono ottenute ripetutamente fino a quando la differenza finale è zero. Nei passaggi, il numero più piccolo viene sottratto dal numero maggiore. 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 è 6, allora i passaggi senza programmazione saranno:

6 - 1 = 5
5 - 1 = 4
4 - 1 = 3
3 - 1 = 2
2 - 1 = 1
1 - 1 = 0

Il GCD qui è 1. Ci sono sei passaggi qui e non sette 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 funzione per il più grande divisore comune per sottrazione, in Python, è:

DEF GCDS (A, B):
Se a == B:
restituire a
Se a> b:
restituire GCDS (A - B, B)
altro:
restituire GCDS (A, B - A)

La prima affermazione si occupa dell'ultimo passaggio di matematica. L'istruzione composta successiva (if/else) fa la sottrazione tra il minuend e la differenza, a seconda di quale è più grande.

Guarda approfondita le subtrazioni di matematica GCD

240 - 108 = 132
132 = 12 x 11 (132 ha 12 come fattore)
132 - 108 = 24
24 = 12 x 2 (24 ha 12 come fattore)
108 - 24 = 84
84 = 12 x 7 (84 ha 12 come fattore)
84 - 24 = 60
60 = 12 x 5 (60 ha 12 come fattore)
60 - 24 = 36
36 = 12 x 3 (36 ha 12 come fattore)
24 - 12 = 12
12 = 12 x 1 (12 ha un fattore o 12 - stesso)
24 - 12 = 12
12 = 12 x 1 (12 ha un fattore o 12 - stesso)

L'ultimo passo ha una differenza di 0. Segna la fine delle fasi di sottrazione e fornisce il GCD come sub -traend o minuend.

GCD per divisione

Tra 108 e 240, il GCD è maggiore di 1.

12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 = 108
12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 + 12 + 12 + 12 + 12 = 240

Questo è:

108 + 12 + 12 + 12 + 12 + 12 + 12 +12 +12 + 12 + 12 + 12 = 240

Che significa:

108 + 132 = 240

Questo è:

12 x 9 + 12 x 11 = 240

Inoltre, 108 = 12 x 9 e 240 = 12 x 20.

Ora, se il GCD può essere moltiplicato per un numero intero (intero positivo) per dare uno qualsiasi dei numeri (108 o 240) da cui è richiesto il GCD, potrebbe essere possibile fare ripetutamente una sorta di divisione, a cominciare da Dati numeri per avere il GCD. In effetti, è possibile fare ripetutamente un particolare tipo di divisione e ottenere il GCD. Questa divisione è una divisione modulo ripetuta speciale. Inizia con la divisione del modulo dei numeri indicati.

Nella divisione del modulo, quando il dividendo è diviso per il divisore, il resto per il quoziente è la risposta.

Problema: trova il più grande divisore comune (fattore comune più alto) per 108 e 240 dalla divisione del modulo:

Soluzione:

240 % 108 = 24 (i.e. 2 r 24)
108 % 24 = 12 (i.e. 4 r 12)
24 % 12 = 0 (i.e. 2 r 0)

All'ultima riga, dove il resto è zero, il divisore è il più grande divisore comune (fattore comune più alto).

Questo problema è trovare il GCD tra 108 e 240 per divisione. La soluzione qui ha fatto 3 passi. Il problema precedente era simile ma era cercare lo stesso GCD per sottrazione; E aveva 8 passi. Mentre la complessità temporale per il metodo di sottrazione è O (A + B), la complessità temporale per il metodo di divisione è O (log (A + B)).

Nella divisione del modulo, non importa se "A" sia più grande di B o B è più grande di "A"; Il resto è lo stesso numero intero positivo.

Trova matematicamente, il più grande divisore comune per divisione, per i numeri, 5 e 2.

Soluzione:

5 % 2 = 1
1 % 1 = 0

Il GCD è 1. Ciò aveva bisogno di due passi matematici.

Coding GCD per divisione

La parola, "divisione" qui si riferisce alla divisione modulo. La funzione è:

def gcdd (a, b):
if (a % b == 0):
Ritorno b
altro:
restituire GCDD (B, A % B)

La parte if dell'If/Else-costruct si occupa dell'ultima dichiarazione matematica, per le fasi della divisione del modulo. La parte altro si occupa dell'attuale divisione Modulo (risultante nel resto). Nella divisione del modulo, non importa se "A" sia più grande di B o B è più grande di "A"; Il resto è lo stesso numero intero positivo.

Per chiamare e stampare un GCD, è possibile utilizzare il seguente codice:

ret = GCDD (240, 108)
print (ret, end = '\ n')

Guarda approfondita le divisioni di matematica GCD

240 % 108 = 24 (il GCD tra 240 e 108 è 12)
24 = 12 x 2 (24 ha 12 come fattore)
108 % 24 = 12 (il GCD tra 108 e 24 è 12)
12 = 12 x 1 (12 ha 12 come fattore, stesso)
24 % 12 = 0 (il GCD tra 24 e 12 è 12)

È stato dimostrato qui, questo:

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. Pertanto, se il resto di una divisione non è zero, allora il più grande divisore comune tra i due numeri dati è lo stesso del più grande divisore comune tra il divisore e il resto. Questo scorre in passaggi diversi fino a quando il resto non è zero, anche se il GCD è 1.

L'ultimo passo ha un resto di 0. Segna la fine delle fasi della divisione del modulo e il GCD è il divisore.

Conclusione

Il più grande divisore comune può essere determinato da subtrazioni ripetute o da ripetute divisioni di modulo.

Se è per sottrazione, allora dopo la sottrazione dei numeri indicati, il resto delle subtrazioni è tra la differenza e il minuend, a seconda di quale è più grande. Quando la differenza è zero, la subtrahend è uguale al minuend e uno dei due è il GCD.

Se è per divisione, le divisioni ripetute sono divisioni di modulo. In questa situazione, dopo la divisione del modulo dei numeri indicati, il resto delle divisioni del modulo è tra il divisore e il resto, a seconda di quale è più grande. Quando il resto è zero, il divisore è il GCD. A rigor di termini, nella divisione del modulo, non importa se "A" sia più grande di B o B è più grande di "A"; Il resto è lo stesso numero intero positivo.