Dalam contoh ini, anda akan belajar mencari GCD dua nombor menggunakan dua kaedah yang berbeza: fungsi dan gelung dan, algoritma Euclidean
Untuk memahami contoh ini, anda harus mempunyai pengetahuan mengenai topik pengaturcaraan Python berikut:
- Fungsi Python
- Pengembaraan Python
- Hujah Fungsi Python
Faktor sepunya tertinggi (HCF) atau pembahagi biasa terbesar (GCD) dua nombor adalah bilangan bulat positif terbesar yang membahagi dua nombor yang diberikan dengan sempurna. Contohnya, HCF 12 dan 14 adalah 2.
Kod Sumber: Menggunakan Gelung
# 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))
Pengeluaran
HCF adalah 6
Di sini, dua bilangan bulat yang tersimpan dalam pemboleh ubah num1 dan num2 diteruskan ke compute_hcf()fungsi. Fungsi mengira HCF dua nombor ini dan mengembalikannya.
Dalam fungsi tersebut, pertama-tama kita menentukan yang lebih kecil dari dua nombor kerana HCF hanya boleh kurang atau sama dengan bilangan terkecil. Kami kemudian menggunakan forgelung untuk pergi dari 1 ke nombor itu.
Dalam setiap lelaran, kami memeriksa sama ada nombor kami membahagikan kedua-dua nombor input dengan sempurna. Sekiranya demikian, kami menyimpan nombor tersebut sebagai HCF. Setelah tamatnya gelung, kami akan memperoleh nombor terbesar yang membahagi kedua-dua nombor dengan sempurna.
Kaedah di atas senang difahami dan dilaksanakan tetapi tidak cekap. Kaedah yang lebih cekap untuk mencari HCF adalah algoritma Euclidean.
Algoritma Euclidean
Algoritma ini berdasarkan fakta bahawa HCF dua nombor membahagikan perbezaannya juga.
Dalam algoritma ini, kita membahagikan yang lebih besar dengan yang lebih kecil dan mengambil yang selebihnya. Sekarang, bahagikan yang lebih kecil dengan baki ini. Ulangi sehingga selebihnya 0.
Sebagai contoh, jika kita ingin mencari HCF 54 dan 24, kita bahagikan 54 dengan 24. Selebihnya adalah 6. Sekarang, kita bahagikan 24 dengan 6 dan selebihnya adalah 0. Oleh itu, 6 adalah HCF yang diperlukan
Kod 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 gelung sehingga y menjadi sifar. Pernyataan tersebut x, y = y, x % ymelakukan pertukaran nilai di Python. Klik di sini untuk mengetahui lebih lanjut mengenai menukar pemboleh ubah di Python.
Dalam setiap lelaran, kita meletakkan nilai y dalam x dan selebihnya (x % y)dalam y, secara serentak. Apabila y menjadi sifar, kita mempunyai HCF dalam x.
