Kamis, 24 November 2016

Contoh Soal Algoritma Menghitung Nilai Faktorial Bilangan N

           No comments   


Function Faktorial (input n : integer) à integer
{Menghasilkan Nilai n! / n faktorial, dan n tidak negatif}
Kamus :
                        {Tidak Ada}
Algoritma :
                        input(n)
                        if ( n = 0 ) then
                          return 1
                        else
                           return  ( n* Faktorial( n - 1) )
                        endif
endfunction

Bilangan Nilai n! secara rekursif

Penyelesaian :

             1.      Tentukan Parameter ukuran input : n

             2.      Operasi Dasar :
           Base case : (n = 0)
           Recursive case : ( n * Faktorial (n-1) )
           Pilih operasi dasar dari salah satu kondisi base case / recursive case ?

           Operasi dasar yang dipilih : *
           yang dilakukan n!/(n-i) kali setiap kali fungsi rekursif dipanggil
           Maka T(n) adalah T(n) = (n - 1) + 1                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.
            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) = T(0)
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
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