Kamis, 24 November 2016

Contoh Soal Algoritma Perhitungan Pangkat Secara Rekursif



function Pangkat ( x : integer, n : integer) à integer
// algoritma untuk menghitung nilai xn secara rekursif
kamus :
            x, n : integer
Algoritma :
            //input : x  dan  n 
            if ( n = 0 ) then
               return  1
            else
               return  ß  x * Pangkat (x, n - 1)
            endif
            //output : nilai xn
endfunction


Tampilan Perhitungan Pangkat Secara Rekursif

     
    Penyelesaian :

          1.     Tentukan Parameter ukuran input : n
          2.     Operasi Dasar :
                           Base case : (n = 0) 
               Recursive case : ( x * Pangkat (x, n-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(0) = 0                  untuk   n = 0

          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 : 5, maka recursion treenya(pohon rekursifnya) selalu sama.                    Banyak komputasi / pemanggilan fungsi rekursif tetap ( 5 kali ).
                   Jadi : tidak 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(0) = 0                                   untuk   n = 0 ( base case/kasus dasar )
                 T(n) =  T(n – 1) + 1                 untuk   n > 0 (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(0) disubstitution ke T(n – i) pada bentuk umum T(n).
T(n) = T(n - i) + i
T(n) = T(0) + i
T(n) = 0 + i
T(n) = i

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

Sehingga
T(n) = i
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