Pembahasan Ujian Akhir Semester (UAS) Algoritma dan Pemrograman Tahun 2025 - UAMAT25

Berikut merupakan pembahasan soal UAS mata kuliah Algoritma dan Pemrograman tahun 2025 pada Prodi S1 Matematika, Departemen Matematika dan Sains Data, Universitas Andalas. Lihat Soal.

---

Soal Nomor 1

Pendekatan

Jika diperhatikan dengan seksama, barisan (sequence) yang diperlihatkan pada soal merupakan barisan fibonacci dengan elemen pertama yaitu $1$ dan elemen kedua yaitu $2$. Karena soal ini melibatkan barisan, maka pendekatan paling intuitif yang dapat dilakukan yaitu menggunakan array dan menggunakan sifat barisan fibonacci untuk menambahkan elemen lain ke dalam array tersebut melalui proses looping. Karena diminta menggunakan Python, kita dapat menggunakan alternatif array pada Python, yaitu List. Sebenarnya, array dan list pada Python memiliki sifat yang nyaris sama. Hanya terdapat sedikit perbedaan, yaitu array hanya dapat diisi oleh 1 tipe data sedangkan list pada python dapat diisi dengan beragam tipe data.

Solusi

Algoritma:

1. input nilai $n$
2. inisasi list fib = [1, 2]
3. cek. a. Jika $n<=2$, cetak "input nilai n > 2" b. Jika $n>2$, maka: 1. lakukan iterasi dari $i=2$ hingga $i=n$. Untuk setiap nilai $i$ tersebut, lakukan: 1. hitung variabel ai sebagai ai = a[i-2] + a[i-1] 2. tambahkan ai sebagai elemen terakhir dari list fib
4. cetak fib

Kode Program

n = int(input("input nilai n: "))
fib = [1, 2]
if n <= 2:
  print("input nilai n > 2")
else:
  for i in range(2, n):
    fib.append(fib[i-1] + fib[i-2])
print(fib)

Soal Nomor 2

Pendekatan

Ide penyelesaian soal ini cukup sederhana. suatu bilangan $x$ merupakan faktor dari bilangan lain, yaitu $y$, jika $ymodx=0$ ($y$ habis dibagi $x$). Oleh karena itu, pendekatan paling intuitif (sekaligus naif) yang dapat kita lakukan adalah dengan input $n$ (sesuai soal), melakukan iterasi mulai dari $i=1$ hingga $i=n$, kemudian cek apakah $n\%i=0$. Jika benar, maka $i$ merupakan faktor dari $n$. Karena soal secara spesifik meminta untuk menuliskan proses ini dalam sebuah prosedur (fungsi), maka kita akan menggunakan fungsi.

Solusi

Algoritma:

1. input nilai $n$.
2. lakukan iterasi dari $i=1$ hingga $i=n$. Untuk setiap nilai $i$ tersebut, lakukan: 1. jika $n\%i=0$, maka cetak $i$

Kode Program

def faktor(n):
  for i in range(1, n+1):
    if n%i == 0:
      print(f"{i} ", end="")
 
# contoh
faktor(10)

Teknik Pro

Solusi di atas sebenarnya sudah cukup baik, dan sudah cukup untuk menjawab soal di atas, terlebih lagi tidak ada batasan waktu komputasi. Akan tetapi, pada soal-soal tingkat lanjut yang membutuhkan efisiensi waktu, langkah di atas sangat boros waktu karena jika input nya adalah $n$, maka perlu dilakukan iterasi sebanyak $n$ kali. Jika $n=1000$, maka perlu ada $1000$ iterasi. Kita dapat mempercepat proses ini menjadi 2 kali lebih cepat! bagaimana caranya?

Perhatikan bahwa jika kita punya bilangan bulat $n$, maka faktor-faktor nya pastilah berada di interval $1$ hingga $n/2$, kecuali $n$ itu sendiri. Misalnya, jika kita punya $n=100$, tidak ada faktornya yang bernilai lebih dari $50$ kecuali $100$ itu sendiri. Ini berlaku untuk semua bilangan bulat $n$. Oleh karena itu, jika kita butuh efisiensi waktu (dan ingin terlihat keren), kita bisa memodifikasi iterasinya menjadi hanya sampai $n/2$, bukan $n$. dengan begitu, waktu komputasi kita berkurang setengah dan kecepatan komputasi kita menjadi 2 kali lebih cepat.

Contoh yang lebih baik:

def faktor(n):
  for i in range(1, n//2+1):
    if n%i == 0:
      print(f"{i} ", end="")
  print(n)
 
# contoh
faktor(10)

Soal Nomor 1

Pendekatan

Soal ini pada intinya meminta kita untuk mengurutkan data (angka) pada sebuah list yang diberikan, kemudian menentukan nilai terbesar dan terkecilnya. Sebenarnya, terdapat banyak algoritma pengurutan yang dapat kita gunakan untuk menyelesaikan masalah ini, seperti Bubble Sort, Merge Sort, Insertion Sort, dan masih banyak lagi. Akan tetapi, mungkin algoritma yang paling sederhana dan paling intuitif untuk digunakan (terutama untuk soal ini) adalah algortima bubble sort, jadi kita akan menggunakan algoritma bubble sort. Pelajari lebih lanjut tentang bubble sort.

Pada dasarnya, bubble sort bekerja dengan cara sebagai berikut. misalkan terdapat list x dengan panjang n yang akan kita urutkan dari yang terkecil hingga terbesar. maka, langkah nya yaitu :

1. untuk i = 0 sampai n-1 (artinya, ulangi untuk tiap elemen), ulangi :
   1. ambil elemen pertama dan kedua. bandingkan.
      1. jika elemen kedua lebih kecil daripada elemen pertama, balik posisi nya. sehingga elemen kedua (yang lama) menjadi elemen pertama (yang baru).
      2. jika elemen kedua lebih besar atau sama dengan elemen pertama, jangan dibalik. biarkan saja.
   2. ambil elemen kedua dan ketiga. bandingkan dan olah seperti nomor 1.
   3. ambil elemen ketiga dan ke empat. bandingkan dan olah seperti nomor 1 … … ulangi sampai elemen terakhir

Kemudian, untuk mengambil nilai terbesar dan terkecil, cukup ambil nilai yang berada pada indeks pertama dan terakhir. Untuk melihat secara visual bagaimana algoritma bubble sort bekerja, lihat visualisasi ini.

Solusi

Algoritma:

1. misal list tersebut adalah arr
2. hitung panjang list, misalkan panjangnya $n$.
3. Selama $n>1$, ulangi langkah berikut:
   1. untuk $i$ mulai dari $0$ hingga $n-1$, ulangi langkah berikut:
      1. jika arr[i] < arr[i+1], maka tukar posisi kedua nilai ini. Contoh, jika awalnya 2, 3, maka ganti jadi 3, 2 (kita menggunakan tanda > karena urutan yang diminta adalah descending, dari besar ke kecil. jika urutan yang diminta adalah ascending, maka gunakan tanda <).
   2. kurangi nilai $n$, yaitu $n=n-1$
4. print arr.

Kode Program

# contoh array yang diberikan
arr = [2, 5,4, 6,2,12, 4, 100,43, 65, 11, 7, 98, 31]
 
# solusi
n = len(arr)
while n>1:
  for i in range(n-1):
    if arr[i] > arr[i+1]:
      arr[i], arr[i+1] = arr[i+1], arr[i]
  n -= 1
 
print(f"hasil urutan descending: {arr}")
print(f"bilangan terbesar: {arr[0]}")
print(f"bilangan terkecil: {arr[-1]}")