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