Dalam contoh ini, Anda akan belajar mencari GCD dari dua angka menggunakan dua metode berbeda: fungsi dan loop, serta algoritma Euclidean
Untuk memahami contoh ini, Anda harus memiliki pengetahuan tentang topik pemrograman Python berikut:
- Fungsi Python
- Rekursi Python
- Argumen Fungsi Python
Faktor persekutuan tertinggi (HCF) atau pembagi persekutuan terbesar (PBT) dari dua bilangan adalah bilangan bulat positif terbesar yang membagi sempurna dua bilangan yang diberikan. Misalnya, HCF 12 dan 14 adalah 2.
Kode Sumber: Menggunakan Loops
# Python program to find H.C.F of two numbers # define a function def compute_hcf(x, y): # choose the smaller number if x> y: smaller = y else: smaller = x for i in range(1, smaller+1): if((x % i == 0) and (y % i == 0)): hcf = i return hcf num1 = 54 num2 = 24 print("The H.C.F. is", compute_hcf(num1, num2))
Keluaran
HCF adalah 6
Di sini, dua bilangan bulat yang disimpan dalam variabel num1 dan num2 diteruskan ke compute_hcf()fungsi. Fungsi ini menghitung HCF dua angka ini dan mengembalikannya.
Dalam fungsinya, pertama-tama kita menentukan angka yang lebih kecil dari kedua angka tersebut karena HCF hanya boleh kurang dari atau sama dengan angka terkecil. Kami kemudian menggunakan forperulangan untuk beralih dari 1 ke angka itu.
Dalam setiap iterasi, kami memeriksa apakah bilangan kami membagi dengan sempurna kedua bilangan input. Jika demikian, kami menyimpan nomor tersebut sebagai HCF. Pada penyelesaian loop, kami berakhir dengan angka terbesar yang membagi kedua angka dengan sempurna.
Metode di atas mudah dipahami dan diterapkan tetapi tidak efisien. Metode yang jauh lebih efisien untuk menemukan HCF adalah algoritma Euclidean.
Algoritma euclidean
Algoritme ini didasarkan pada fakta bahwa HCF dari dua angka juga membagi perbedaannya.
Dalam algoritma ini, kita membagi yang lebih besar dengan yang lebih kecil dan mengambil sisanya. Sekarang, bagi yang lebih kecil dengan sisa ini. Ulangi sampai sisanya 0.
Misalnya, jika kita ingin mencari HCF dari 54 dan 24, kita bagi 54 dengan 24. Sisanya adalah 6. Sekarang, kita bagi 24 dengan 6 dan sisanya 0. Jadi, 6 adalah HCF yang dibutuhkan
Kode Sumber: Menggunakan Algoritma Euclidean
# Function to find HCF the Using Euclidian algorithm def compute_hcf(x, y): while(y): x, y = y, x % y return x hcf = compute_hcf(300, 400) print("The HCF is", hcf)
Di sini kita mengulang sampai y menjadi nol. Pernyataan x, y = y, x % yitu bertukar nilai dengan Python. Klik di sini untuk mempelajari lebih lanjut tentang menukar variabel dengan Python.
Dalam setiap iterasi, kami menempatkan nilai y di x dan sisanya (x % y)di y, secara bersamaan. Saat y menjadi nol, kita memiliki HCF di x.
