Algoritma Iteratif

Pendahuluan

Algoritma iteratif digunakan apabila diperlukan perulangan dalam suatu program. Dalam pemrograman R algoritma iteratif dituangkan dalam beberapa fungsi.

Tipe Perulangan Deskripsi
repeat loop Executes a sequence of statements multiple times and abbreviates the codes that manages the loop variable.
while loop Repeat a statement or group of statements while a given condition is true. It tests the condition before executing the loop body
for loop Like a while statement, except that it tests the condition at the end of the loop body

Loop dengan for

Menggunakan for untuk mencari bilangan maksimal
Dengan algoritma:
1. Baca data \(x_i\)
2. i = 1
3. i = i + 1
4. Jika \(x_i<x_1\), lanjutkan ke langkah 5, selainnya pertukarkan nilai \(x_1\) dengan \(x_i\)
5. Jika i < n, lanjutkan ke langkah 3. Selainnya, print \(x_1\)

# data
x = c(15,18,10,8,20)

# iterasi dengan for  
n = length(x)
for (i in 2:n){
  if (x[i] > x[1]){
    a = x[1]
    x[1] = x[i]
    x[i] =a
  }
}
a = x[1]
a
[1] 20

Menggunakan for untuk mengurutkan data

Ada beberapa algoritma iteratif yang bisa diterapkan untuk melakukan pengurutan, yaitu buble sort, selection sort, insertion sort, merge sort, quick sort.

Buble Sort
Iterasi yang digunakan terdiri dari dua tingkat yaitu iterasi untuk memastikan semua elemen diperiksa, dan iterasi untuk mengakses elemen elemen vektor yang digunakan untuk penukaran elemen.

Contoh 1
Mengurutkan data {15,18,10,8,20}

# data
x = c(15,18,10,8,20)

# iterasi dengan for
n = length(x)
for (i in 1:(n-1)){
  for (j in (i+1):n){
    if (x[i] > x[j]){
      a = x[i]
      x[i] = x[j]
      x[j] = a 
    }
  }
}
x
[1]  8 10 15 18 20

Contoh 2
Mengurutkan data {3,1,4,1,5,9,2,6,5}

x <- c(3,1,4,1,5,9,2,6,5)

# Mendefinisikan objek baru yang akan digunakan untuk menampilkan hasil sortir
x_sort <- x

# Banyaknya amatan 
nx <- length(x)

# Iterasi tingkat 1
for (i in 1:(nx-1)) {
  # Iterasi tingkat 2
  for (j in 1:(nx-i)) {
    # Pemeriksaan kondisi apakah elemen ke-j lebih besar dari elemen ke-j+1
    if (x_sort[j] > x_sort[j+1]) {
      # Jika terpenuhi, lakukan algoritme penukaran
      tmp <- x_sort[j]
      x_sort[j] <- x_sort[j+1]
      x_sort[j+1] <- tmp
    }
  }
}

x_sort
[1] 1 1 2 3 4 5 5 6 9

Membandingkan hasilnya dengan fungsi sort

sort(x)
[1] 1 1 2 3 4 5 5 6 9

Membuat Fungsi Pengurutan

urut <- function(x){
  n = length(x)
  for (i in 1:(n-1)){
    for (j in (i+1):n){
      if (x[i] > x[j]){
        a = x[i]
        x[i] = x[j]
        x[j] = a 
      }
    }
  }
  return(x)
  }

Menggunakan fungsi

x <- c(3,1,4,1,5,9,2,6,5)
urut(x)
[1] 1 1 2 3 4 5 5 6 9

Menggambar Pola

# Membuat pola dasar
mat <- matrix(NA,6,6)
mat
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]   NA   NA   NA   NA   NA   NA
[2,]   NA   NA   NA   NA   NA   NA
[3,]   NA   NA   NA   NA   NA   NA
[4,]   NA   NA   NA   NA   NA   NA
[5,]   NA   NA   NA   NA   NA   NA
[6,]   NA   NA   NA   NA   NA   NA
# Membuat pola sesuai yang diinginkan
for (i in 1:6) {
  for (j in 1:(6-i+1)) {
    mat[i,j] <- 1
  }
}

# Hasil Akhir
mat
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    1    1    1    1    1
[2,]    1    1    1    1    1   NA
[3,]    1    1    1    1   NA   NA
[4,]    1    1    1   NA   NA   NA
[5,]    1    1   NA   NA   NA   NA
[6,]    1   NA   NA   NA   NA   NA

Loop dengan while

Deret Bilangan

Pendugaan jumlah deret tak hingga
\[\mathrm{z} = 1+\frac{5}{6}+\frac{7}{11}+\frac{9}{18}+...\] Tahapan penentuan pola

i 1 2 3 4 …
atas 3 5 7 9 … 2i+1
bawah 3 6 11 18 … \(i^2+2\)

Pola baris bilangan tersebut adalah
\[\mathrm{z} = \sum_{i=1}^{\infty} \frac{2i+1}{i^2+2}\]

e = 10
z0 = 0
i = 1
while (e > 10^(-5)){
  z1 = z0 + (2*i+1)/ (i^2+2)
  e = abs(z1-z0)
  z0 = z1
  i = i+1
}
z0
[1] 24.49101

Pendugaan jumlah deret tak hingga
\[\mathrm{z} = 2-\frac{6}{5}+\frac{8}{10}-\frac{10}{17}+\frac{12}{26}...\] Pola baris bilangan tersebut adalah
\[\mathrm{z} = \sum_{i=1}^{\infty} (-1)^{i+1} \frac{2i+2}{i^2+1}\]

e = 10
z0 = 0
i = 1
while (e > 10^(-5)){
  z1 = z0 + (-1)^(i+1)*((2*i+2)/ (i^2+1)) 
  e = abs(z1-z0)
  z0 = z1
  i = i+1
}
z0
[1] 1.267197

Pendugaan jumlah deret tak hingga
\[\mathrm{z} = \frac{2}{5}+\frac{3}{40}+\frac{6}{135}+\frac{11}{320}+\frac{18}{625}+\frac{27}{1080}...\] Pola baris bilangan tersebut adalah
\[\mathrm{z} = \sum_{n=1}^{\infty} \frac{n^2+2n+3}{5n^3}\]

# Menuliskan rumus fungsi dalam bentuk function
fz2 <- function(n){
  ((n^2) - 2*n + 3) / (5*n^3)
}

# Mendefinisikan nilai-nilai awal (initial value)
error <- 10 #Nilai awal kriteria berhenti
z0 <- 0 #Nilai awal deret
n <- 1 #Nilai awal iterasi

# Membuat iterasi untuk mencari jumlah deret
while (error>1e-6) {
  z <- z0 + fz2(n)
  error <- abs(z-z0)
  z0 <- z
  n <- n+1
}

# Hasil Akhir
z 
[1] 2.61992
# Banyaknya Iterasi
n
[1] 2e+05

Membuat fungsi deret dengan ketentuan

  • Jika inputnya hanya fungsi deret bilangan, outputnya adalah jumlah deret dan banyak iterasi
  • Jika inputnya fungsi deret bilangan dan bilangan n, outputnya adalah n dan suku ke-n dari deret tersebut
deret <- function(fx,n){
  if(missing(n)) {
    error <- 10 #Nilai awal kriteria berhenti
    z0 <- 0 #Nilai awal deret
    i <- 1 #Nilai awal iterasi
    
    # Membuat iterasi untuk mencari jumlah deret
    while (error>1e-6) {
      z <- z0 + fx(i)
      error <- abs(z-z0)
      z0 <- z
      i <- i+1
    }
    return(list(HasilAkhir=z,BanyakIterasi=i))
  } else {
    return(list(SukuKe=n, Nilai=fx(n)))
    }
}

Membuat fungsi persamaan deret bilangan

fz2 <- function(n){
  ((n^2) - 2*n + 3) / (5*n^3)
}

Menggunakan fungsi dengan input hanya berupa fungsi deret bilangan

deret(fz2)
$HasilAkhir
[1] 2.61992

$BanyakIterasi
[1] 2e+05

Menggunakan fungsi dengan input fungsi deret bilangan dan bilangan n

deret(fz2,5)
$SukuKe
[1] 5

$Nilai
[1] 0.0288

Referensi

Dito, Gerry Alfa dan Raharjo, Mulianto. (21 April 2021). Algoritma Iteratif. Retrieved from https://newlms.ipb.ac.id/

Wigena, Aji Hamim. (14 April 2021). STA561 Pemrograman Statistika: Algoritma Iteratif. Retrieved from https://newlms.ipb.ac.id/