Kamis, 24 November 2016

Contoh Soal Algoritma Menghitung Hasil Kali dari dua Bilangan ( a * b )

           No comments   


Function  kali ( input a,b : integer) à integer
Kamus :
                        {Tidak ada}
Algoritma :
                        Input (a,b)
                        if ( b = 1 ) then
                           return a
                        else
                           return  ( a  +  Kali(a, b – 1) )
                        endif

endfunction


Perkalian Bilangan a,b secara Rekursif

Penyelesaian
            1.      Tentukan Parameter ukuran input : b

            2.      Operasi Dasar :
       Base case : (b = 1)
       Recursive case : ( a + Kali (a, b-1) )
       Pilih operasi dasar dari salah satu kondisi base case / recursive case ?

       Operasi dasar yang dipilih : =            
       yang dilakukan 1 kali setiap kali fungsi rekursif dipanggil
       Maka T(n) adalah T(1) = 1                  untuk   b = 1

           3.      Perhatikan apakah butuh best, worst, dan average case ?
           Jika jumlah eksekusi suatu operasi dasar bervariasi(berbeda) untuk berbagai input berukuran                sama, maka dibutuhkan perhitungan best, worst, dan average case.

           Maka :
           Untuk input  n  tertentu misal : 4, maka recursion treenya(pohon rekursifnya) selalu sama.                    Banyak komputasi / pemanggilan fungsi rekursif berbeda.
           Jadi : Butuh best, worst, dan average case.

          4.      Tentukan hubungan / realasi recurrence, dengan sebuah kondisi awal, untuk jumlah waktu                    operasi dasar di eksekusi / di jalankan.

Jika T(n) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n dan             T(n - 1) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n-1.

Maka :  Hubungan T(n) dan T(n - 1) dinyatakan dengan
T(1) = 1                                   untuk   b = 1 ( base case/kasus dasar )
            T(n) =  T(n – 1) + 1                 untuk   b > 1 (recursive case/kasus rekursif)


          5.      Menyelesaikan solusi relasi rekurens yang didapat di nomor 4 (t(n))
·         Untuk mengetahui kelas efisiensi waktunya kita harus menemukan persamaan langsung ( non recursive ) dari T(n).
·         Menggunakan metode backward substitution, cari pola dari :
T(n) =  T(n – 1) + 1
T(n) =  (T(n – 2) + 1) + 1  =  T(n) =  T(n – 2) + 2
T(n) =  (T(n – 3) + 1 ) + 2 =  T(n) =  T(n – 3) + 3
Dan seterusnya

·         Pola atau bentuk umumyang didapat adalah
T(n) = T(n – i) + i

·         Nilai kondisi awal T(1) disubstitution ke T(n – i) pada bentuk umum T(n).
T(n) à T(n-i) = T(1)
T(n) = T(n - i) + i
T(n) = T(1) + i
T(n) = 1 + i
T(n) = i + 1

·         Subtitusi tersebut mensyaratkan 
T(n – i) = T(1)
   n – i  = 1
           i = n – 1
nilai  i = n – 1 disubtitusikan ke bentuk umum
T(n) = i + 1

Sehingga
T(n) = i + 1
T(n) = n – 1 + 1
T(n) = n
Jadi
T(n) merupakan anggota kelas n
           6.      Tentukan g(n) dimana t(n) termasuk salah satu O(g(n)),Ω(g(n)), atau Ɵ(g(n))
           Jadi : T(n) = n
          T(n) є O(n)
Sumber :


0 komentar:

Posting Komentar