TANPA MENGGUNAKAN ARRAY, buatlah program Python yang dapat menentukan FPB

Berikut ini adalah pertanyaan dari unknown pada mata pelajaran TI untuk jenjang Sekolah Dasar

TANPA MENGGUNAKAN ARRAY, buatlah program Python yang dapat menentukan FPB dari dua bilangan bulat yang bernilai besar. Spesifikasi program:- menerima input 2 bilangan dalam bentuk a^b.
- mencetak FPB dari kedua bilangan yang diinput.
Contoh output/hasil running program dengan input 20^22 dan 15^17:
Bilangan pertama: 20^22
Bilangan kedua: 15^17
FPB dari 20^22 dan 15^17 adalah 762939453125.
________________
Note: ini soal dari sepupu saya siswa sebuah SMK.

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

Kode Program Python

def fpb(a, b, tampilkan_proses = False):
   # Diberikan 2 bilangan a dan b
   # Mengembalikan FPB(a, b)
   # tampilkan_proses: jika true, akan menampilkan proses
   if (b == 0):
       return a
   if (tampilkan_proses):
       print("{m:d} : {n:d} = {mdivn:d} * {n:d} + {mmodn:d}"
           .format(m = a, n = b, mdivn = a // b, mmodn = a % b))
   return fpb(b, a % b, tampilkan_proses)

# Program Utama
if __name__ == '__main__':
   # Input dua bilangan berpangkat
   # a^b dan c^d
   [a, b] = [int(item) for item in
       input("Bilangan pertama (a^b): ").split("^")]
   [c, d]= [int(item) for item in
       input("Bilangan kedua (c^d): ").split("^")]
   tampilkan_proses = input("Tampilkan proses (y/t) ? ") == "y"
   # Pencarian FPB
   if (tampilkan_proses):
       print("============================")
       print("Mencari FPB dengan Euclid ...")
   x = fpb(a**b, c**d, tampilkan_proses)
   # Output hasil
   print("============================")
   print("⇒ FPB dari {m:d}^{n:d} dan {o:d}^{p:d} adalah {q:d}.\n\n"
       .format(m = a, n = b, o = c, p = d, q = x))
### END OF PROGRAM ###

Pembahasan

Algoritma Utama FPB

Karena batasannya adalah tidak boleh menggunakan array (dalam Python: list), maka kita bisa menggunakan algoritma pembagian berulang Euclidean. Program di atas menggunakan algoritma Euclidean yang diimplementasikan secara rekursifpada fungsifpb(a, b, tampilkan_proses). Parameter utamanya adalah adanb, sedangkan parameter ketiga hanya sebagai flag untuk menampilkan proses atau tidak.

Fungsi fpb(...) tersebut pada dasarnya adalah sebagai berikut.
def fpb(a, b):
   # Diberikan 2 bilangan a dan b
   # Mengembalikan FPB(a, b)
   if (b == 0):
       return a
   return fpb(b, a % b)

Algoritma Pendukung

Pada bagian input, saya tetap menggunakan list hanya agar dapat memisahkan string masukan dengan fungsi split("^"), dan hasil splitlangsung disimpan pada 4 variabel yaituadanb untuk bilangan pertama, serta cdand untuk bilangan kedua. Proses selanjutnya adalah pertanyaan mau menampilkan proses pencarian FPB, atau tidak.

Pada bagian output, program tinggal mencetak semua nilai variabel input dan output dengan format string sedemikian rupa sehingga sesuai dengan output yang diharapkan.

Catatan: Untuk menyederhanakan persoalan, tidak ada error checking terhadap input dari user, karena dipandang kurang signifikan terhadap persoalan.

Contoh Hasil Eksekusi

  • Proses tidak ditampilkan
    Bilangan pertama (a^b): 20^22
    Bilangan kedua (c^d): 15^17
    Tampilkan proses (y/t) ? t
    ============================
    ⇒ FPB dari 20^22 dan 15^17 adalah 762939453125.
  • Proses ditampilkan
    Bilangan pertama (a^b): 20^22
    Bilangan kedua (c^d): 15^17
    Tampilkan proses (y/t) ? y
    ============================
    Mencari FPB dengan Euclid ...
    41943040000000000000000000000 : 98526125335693359375 = 425704754 * 98526125335693359375 + 51395491027832031250
    98526125335693359375 : 51395491027832031250 = 1 * 51395491027832031250 + 47130634307861328125
    51395491027832031250 : 47130634307861328125 = 1 * 47130634307861328125 + 4264856719970703125
    47130634307861328125 : 4264856719970703125 = 11 * 4264856719970703125 + 217210388183593750
    4264856719970703125 : 217210388183593750 = 19 * 217210388183593750 + 137859344482421875
    217210388183593750 : 137859344482421875 = 1 * 137859344482421875 + 79351043701171875
    137859344482421875 : 79351043701171875 = 1 * 79351043701171875 + 58508300781250000
    79351043701171875 : 58508300781250000 = 1 * 58508300781250000 + 20842742919921875
    58508300781250000 : 20842742919921875 = 2 * 20842742919921875 + 16822814941406250
    20842742919921875 : 16822814941406250 = 1 * 16822814941406250 + 4019927978515625
    16822814941406250 : 4019927978515625 = 4 * 4019927978515625 + 743103027343750
    4019927978515625 : 743103027343750 = 5 * 743103027343750 + 304412841796875
    743103027343750 : 304412841796875 = 2 * 304412841796875 + 134277343750000
    304412841796875 : 134277343750000 = 2 * 134277343750000 + 35858154296875
    134277343750000 : 35858154296875 = 3 * 35858154296875 + 26702880859375
    35858154296875 : 26702880859375 = 1 * 26702880859375 + 9155273437500
    26702880859375 : 9155273437500 = 2 * 9155273437500 + 8392333984375
    9155273437500 : 8392333984375 = 1 * 8392333984375 + 762939453125
    8392333984375 : 762939453125 = 11 * 762939453125 + 0
    ============================
    ⇒ FPB dari 20^22 dan 15^17 adalah 762939453125.

Atau, silahkan amati gambar yang disertakan agar lebih jelas

Kode Program Pythondef fpb(a, b, tampilkan_proses = False):    # Diberikan 2 bilangan a dan b    # Mengembalikan FPB(a, b)    # tampilkan_proses: jika true, akan menampilkan proses    if (b == 0):        return a    if (tampilkan_proses):        print(Kode Program Pythondef fpb(a, b, tampilkan_proses = False):    # Diberikan 2 bilangan a dan b    # Mengembalikan FPB(a, b)    # tampilkan_proses: jika true, akan menampilkan proses    if (b == 0):        return a    if (tampilkan_proses):        print(Kode Program Pythondef fpb(a, b, tampilkan_proses = False):    # Diberikan 2 bilangan a dan b    # Mengembalikan FPB(a, b)    # tampilkan_proses: jika true, akan menampilkan proses    if (b == 0):        return a    if (tampilkan_proses):        print(

Semoga dengan pertanyaan yang sudah terjawab oleh henriyulianto dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Wed, 26 Oct 22