Question

Tugas Alpro

Rancanglah sebuah fungsi dengan Python atau C++ yang dapat menghitung jumlah digit dari sebuah bilangan hingga jumlah digitnya menjadi bilangan satuan (0 sampai 9).
Sebagai contoh:
Contoh 1:
Input = 12345
Proses:
∘ 1+2+3+4+5 = 15
∘ 1+5 = 6
∘ Maka, output dari program dengan input 12345 adalah 6.
Contoh 2:
Input = 99999
Proses:
∘ 9+9+9+9+9 = 45
∘ 4+5 = 9
∘ Maka, output dari program dengan input 99999 adalah 6.

_____________
Mohon bantuannya...

Answer 1

Kode Program (Python)

def jumlah_digit_iteratif(n):
   jum = 0
   while (n > 0 or jum > 9):
       if (n == 0):
           n = jum
           jum = 0
       jum += n % 10
       n //= 10
   return jum

def jumlah_digit_rekursif(n):
   if (n < 10): return n
   jum = jumlah_digit_rekursif(n // 10)
   n %= 10
   return jumlah_digit_rekursif(jum + n)

def jumlah_digit(n):
   return 0 if (n == 0) else (
       9 if (n % 9) == 0 else n % 9
   )
   # Ekuivalen dengan:
   # if (n == 0): return 0
   # if (n % 9 == 0): return 9
   # else return (n % 9)

### Program Utama
if __name__ == '__main__':
   n = int(input('\nMasukkan sebuah bilangan asli: '))
   print(f'=> jumlah_digit_iteratif({n}) = {jumlah_digit_iteratif(n)}')
   print(f'=> jumlah_digit_rekursif({n}) = {jumlah_digit_rekursif(n)}')
   print(f'=> jumlah_digit({n}) = {jumlah_digit(n)}')
### Akhir Program Utama
__________________

Pembahasan

Untuk menghitung jumlah digit dari sebuah bilangan secara berulang sampai jumlah digitnya merupakan bilangan satuan, kita bisa melakukan 3 pendekatan.

Pendekatan 1: Brute-force

Pendekatan brute-force dilakukan berdasarkan "cara manual" kita menghitung.

Misalnya, diberikan bilangan 12345. Langkah penghitungan:

• 1+2+3+4+5 = 15
• 1+5 = 6

Untuk pendekatan ini, setidaknya terdapat 2 metode untuk pendekatan ini, yaitu metode iteratif dan rekursif.

Algoritma dengan metode iteratif (parameter: n)

1. Inisialisasi: jum = 0
2. Looping:
   Selama n > 0 atau jum > 9, lakukan:
      Jika n = 0, maka:
          n = jum
          jum = 0
      jum = jum + n mod 10
      n = n div 10
3. Kembalikan nilai jum

Algoritma dengan metode rekursif (parameter: n)

1. Jika n < 10, kembalikan nilai n.
2. Jika tidak:
      jum = jumlah digit dari (n div 10)
      n = n mod 10
      Kembalikan jumlah digit dari (jum + n)

Pendekatan 2: Dengan prinsip keterbagian oleh 9

Semua bilangan bulat n dapat direpresentasikan dengan:
n = 9x + k, dengan x, k ∈ ℤ.

• Jika n kelipatan 9, maka k = 0, jumlah digit secara berulang hingga jumlah digitnya merupakan bilangan satuan pasti sama dengan 9.
• Sedangkan jika n bukan kelipatan 9, maka k ≠ 0, jumlah digit secara berulang hingga jumlah digitnya merupakan bilangan satuan sama dengan k.

Maka, kita dapat mengkonstruksi sebuah algoritma yang lebih elegan dibanding dua algoritma pada pendekatan 1 di atas, dengan kompleksitas waktu yang lebih singkat dan sederhana.

Algoritma

1. Jika n = 0, maka kembalikan 0.
2. Jika n mod 9 = 0, maka kembalikan 9.
   Jika tidak, maka kembalikan n mod 9.

__________________

Ketiga algoritma tersebut diimplementasikan pada program di atas. Mau menggunakan yang mana, silahkan pilih. Dari sudut pandang kompleksitas waktu, algoritma terakhir adalah yang paling efisien.

Contoh hasil eksekusi dapat dilihat pada gambar.