GCD adalah singkatan dari Pembagi Persekutuan Terbesar. Ini digunakan untuk menghitung HCF (Faktor Persekutuan Tertinggi), i. e. , FPB (Pembagi Persekutuan Terbesar) untuk dua bilangan adalah bilangan yang dapat membagi kedua bilangan tersebut dengan sempurna
Ruang Lingkup Pasal
- Pada artikel ini, kita akan mempelajari cara menghitung GCD dua angka dengan python
- Artikel ini menjelaskan apa itu GCD dalam istilah matematika dan bagaimana kita dapat mengimplementasikan GCD yang sama dengan python
- Kami akan membahas berbagai metode untuk menghitung FPB dua angka dengan menggunakan
- fungsi gcd()
- pengulangan
- loop
- Algoritma Euclidean
Pengantar GCD dari dua angka dengan Python
FPB (Pembagi Persekutuan Terbesar) adalah istilah matematika yang menjelaskan penghitungan faktor persekutuan terbesar dari dua bilangan. GCD dari dua atau lebih bilangan bulat yang tidak semuanya nol adalah bilangan bulat positif terbesar yang membagi kedua bilangan bulat tersebut
GCD juga dikenal sebagai HCF (Faktor Persekutuan Tertinggi)
Dalam contoh ini, kita akan melihat cara menghitung GCD dari dua bilangan. Contoh. Ada dua angka, 4 dan 10. Berapa GCD/HCF dari 4 dan 10?
Saat kita membahas definisi GCD, ini memberi tahu kita faktor persekutuan tertinggi yang membagi dua angka. Dalam kasus 4 dan 10, faktor persekutuan tertinggi adalah 2
Menghitung GCD menggunakan fungsi gcd()
Ada berbagai metode untuk menghitung GCD dari dua angka. Salah satu caranya adalah dengan menggunakan fungsi gcd() yang tersedia di modul matematika dengan python
Catatan. Untuk menghitung gcd dari dua angka menggunakan fungsi gcd(). Adalah wajib untuk mengimpor modul matematika. Jika modul matematika tidak diimpor, ia akan melemparImportError
Sintaks Sintaks fungsi gcd()
Parameter
- x 'x' adalah bilangan bulat non-negatif yang GCD/HCF-nya harus kita hitung
- y 'y' juga merupakan bilangan bulat non-negatif yang GCD/HCF-nya harus kita hitung
Kembali Jenis matematika. fungsi gcd() akan mengembalikan bilangan bulat non-negatif, faktor persekutuan tertinggi i. e. , FPB dari x,y
Catatan. Jika kita memasukkan x dan y keduanya sebagai 0. Fungsi ini akan mengembalikan 0, dan jika kita menggunakan tipe data lain selain intit akan throwTypeError
Contoh
Memasukkan
# math module contains the gcd function import math # now, let's calculate the gcd of 2 numbers. x = 10 y = 4 hcf = math.gcd(x,y) print(f"The GCD of {x} and {y} is {hcf}.") _
Keluaran
:::
Menggunakan Rekursi untuk menghitung GCD
Kami sekarang akan menggunakan teknik Rekursi untuk menghitung GCD dari dua angka
Memasukkan
def gcd(x,y): if y == 0: return x else: return gcd(y,x%y) print(gcd(100,3))
Keluaran
Menggunakan Algoritma Euclidean untuk menghitung GCD
Algoritma Euclidean adalah algoritma yang paling efisien untuk menghitung GCD dari dua bilangan
Jadi, algoritma Euclidean menyatakan bahwa pertama-tama kita menyimpan angka yang lebih besar dan angka yang lebih kecil, kemudian kita membagi angka yang lebih besar dengan angka yang lebih kecil dan menyimpan sisanya.
Sisa yang disimpan harus dibagi dengan angka yang lebih kecil, dan terus ulangi proses ini hingga sisanya sama dengan 0
Contoh. Kami memiliki dua angka, 24 dan 54. Sekarang menurut Algoritma Euclidean, kita membagi 54%24 = 6 dan menyimpan 6. Sekarang bagi 24%6 = 0. Sekarang sisa kita adalah 0. Jadi, hasil kita adalah 6i. e. , PBT dari 24 dan 54 adalah 6
Menggunakan LOOP
Memasukkan
x = 24 y = 54 while y: x,y = y, x%y print(x)
Keluaran
MENGGUNAKAN REKURSI
Memasukkan
def gcd(x,y): if x == y or y == 0: return x if x == 0: return y else: if x>y: return gcd(x-y,y) else: return gcd(x,y-x) print(gcd(27,90)) _
Keluaran
Menggunakan Loops untuk menghitung GCD
Memasukkan
x = 24 y = 100 n = min(x,y) hcf = 0 for i in range(1,n+1): if x%i == 0 and y%i == 0: hcf = i print(hcf)
Keluaran
Penjelasan. n menyimpan nilai minimum dari nilai x dan y karena HCF (faktor persekutuan tertinggi) dari dua bilangan selalu berada di antara 1 dan minimum dari dua bilangan. Jadi, n dapat menyimpan nilai minimum dari dua angka
Perulangan for akan berjalan sebanyak n+1 kali karena n+1 eksklusif dalam perulangan for. Untuk setiap langkah, periksa apakah kedua angka dapat dibagi dengan nilai saat ini. Jika kedua nilai dapat dibagi dengan nilai loop for saat ini, maka hcf akan menjadi nilai loop for saat ini. Setelah sukses mengeksekusi for loop, program kita akan menghasilkan HCF (faktor persekutuan tertinggi) dari x dan y