Algoritma Iteratif-STA561

Endang Yuliani

Iteratif Loop dengan for

Algoritma menentukan bilangan terbesar

  1. Baca data \(x_i\) (i=15,18,10,8,20)
  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\)

Syntax R

x<-c(15,18,10,8,20)
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

Algoritma Menghitung Banyaknya Angka Kelipatan 2

x=c(2,6,4,8,5,9)
count=0
for(val in x){
  if(val%%2==0)
    count=count+1
}
print(count)
## [1] 4

Iteratif Loop dengan while

Algoritma

  1. X=1
  2. E=2
  3. C=X
  4. \(X=X-(5X^2-1.25)/10X\)
  5. $E=abs(X-C)
  6. Jika \(E>10^(-5)\), lanjutka kelangkah 3, selainnya iterasi berakhir.

Syntax R

X=1
E=2
while(E>10**(-5)){
  C=X
  X=X-(5*X**2-1.25)/(10*X)
  E=abs(X-C)
}
X
## [1] 0.5

Flowchart kembalian uang dari suatu vending machine. Uang pecahan yang tersedia pada mesin tersebut terdiri dari pecahan 10,5 dan 1

Syntax R

x<-28 #sejumlah uang yang akan dipecah
i<-0
y<-x-10
while(y>=0){
  i<-i+1
  x<-y
  y<-y-10
}

j<-0
y<-x-5
while(y>=0){
  j<-j+1
  x<-y
  y<-y-5
}

k<-0
y<-x-1
while(y>=0){
  k<-k+1
  x<-y
  y<-y-1
}

print(paste("Uang 10 sebanyak", i,"lembar"))
## [1] "Uang 10 sebanyak 2 lembar"
print(paste("Uang 5 sebanyak", j,"lembar"))
## [1] "Uang 5 sebanyak 1 lembar"
print(paste("Uang 1 sebanyak", k,"lembar"))
## [1] "Uang 1 sebanyak 3 lembar"

Membentuk Deret Fibonacci

fibonacci=function(n){
  if(n==1){
    x=0
  }else{
    x=c(0,1)
    while(length(x)<n){
      position=length(x)
      new=x[position]+x[position-1]
      x=c(x,new)
    }
  }
  return(x)
}

#memanggil deret fibonacci 25
fibonacci(25)
##  [1]     0     1     1     2     3     5     8    13    21    34    55    89
## [13]   144   233   377   610   987  1597  2584  4181  6765 10946 17711 28657
## [25] 46368

Pengurutan (Sort) Data

Misalkan saja ada sebuah vektor \(x=[3,1,4,1,5,9,2,6,5]\), buat program untuk mengurutkan vektor tersebut dari kecil ke besar, kemudian bandingkan hasilnya dengan fungsi sort! Gunakan algoritme pada slide kuliah ke-16 !

Jawaban:

Untuk melakukan pengurutan, iterasi yang akan digunakan terdiri dari dua tingkat,

  1. iterasi untuk memastikan semua elemen diperiksa

  2. Iterasi untuk mengakses elemen-elemen vektor yang digunakan untuk penukaran antar elemen

Pada iterasi tingkat kedua nilai-nilai yang besar akan semakin terdorong ke-belakang sehingga elemen-elemen belakang vektor tidak perlu diperiksa lagi. Misal pada saat iterasi tingkat pertama sama dengan 3 maka elemen yang akan dibandingkan hanya dari element 1 sampai 7 saja (ingat ada j+1). Semakin meningkat iterasi tingkat 1 maka banyaknya iterasi tingkat 2 semakin mengecil (pada kasus ini diakomodir dengan n_x-i).

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

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

#jumlah amatan 
n_x <- length(x)

#iterasi tingkat 1
for(i in 1:(n_x-1)){
  #iterasi tingkat 2
  for(j in 1:(n_x-i)) {
    # Pemeriksaan kondisi apakah elemen ke-j+1 lebih kecil dari elemen ke-j
    if(x_sort[j+1] < x_sort[j]) {
      # jika terpenuhi
      #Buat tempat sementara untuk menyimpan elemen ke-j yang akan ditukar
      tmp <- x_sort[j]
      # Ganti nilai elemen ke-j dengan nilai yang ada pada elemen ke j+1
      x_sort[j] <- x_sort[j+ 1]
      # Ganti nilai elemen j+1 dengan nilai yang ada dalam objek temp
      x_sort[j+1] <- tmp
    }
  }
  }

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

Pendugaan Jumlah Deret Tak Hingga

Susunlah sintaks R untuk penjumlahan deret berikut!

\(z = \frac{2}{5}+\frac{3}{40}+\frac{6}{135}+\frac{11}{320}+\frac{18}{625}+\frac{27}{1080}+...\)

hint: Cari terlebih dahulu formula/rumus dari deret tersebut

Jawaban:

Rumus dari deret tersebut adalah

\(z=\Sigma_{n=1}^{\infty} \frac{n^2 +2n + 3}{5n^{3}}\)

  1. Menuliskan rumus fungsi dalam bentuk function
fz <- function(n){
  ((n^2) - 2*n + 3) / (5*n^3)
}
  1. Mendefinisikan kriteria stopping
stopping_criteria <- function(y_current,y_before){
  abs(y_current-y_before)
}
  1. Mendefinisikan nilai-nilai awal
#nilai awal kriteria stopping
error <- 10
#nilai awal deret
z0 <- 0
# nilai awal iterasi
n <- 1
  1. Menuliskan iterasi untuk mencari jumlah deret
while (error>0.00001) {
  z <- z0 + fz(n)
  error <- stopping_criteria(z,z0)
  z0 <- z
  n <- n+1
}
# final result
z 
## [1] 2.159406
# criteria stopping
error
## [1] 1e-05