Contoh Korelasi Rekurensi: Codeword Enumeration
Jika sebelumnya telah dipaparkan pola hubungan rekurensi ihwal Menara Hanoi dan Kelinci Fibonacci, akan diuraikan pula di halaman ini Contoh lain dari Relasi Rekurensi berikutnya ialah Codeword Enumeration.
Kasus:
Suatu sistem komputer mengidentifikasi sebuah string dengan digit desimal. String dinyatakan valid jikalau string tersebut memuat digit 0 sebanyak bilangan genap. Sebagai contoh, string 1230407869 (banyak 0 dua) ialah valid sedangkan string 120987045608 tidak valid (banyak 0 tiga). Misalkan $a_n$ ialah banyaknya codeword dengan digit yang valid, temukanlah hubungan rekurensi untuk $a_n$
Solusi:
Jika n=1, maka $a_1=9$, Sebab dari 10 string satu-digit, hanya satu yaitu string 0 yang tidak valid. Relasi rekurensi untuk barisan ini sanggup diperoleh dengan memandang bagaimana string n-digit yang valid sanggup dibangun dari string n−1-digit. Ada dua cara untuk membentuk string n-digit yang valid dari string sebelumnya.
Pertama, sebuah string n-digit yang valid sanggup diperoleh dengan menambahkan string n−1 digit yang valid dengan angka selain 0. Penambahan ini sanggup dilakukan dengan 9 cara. Sehingga dengan cara ini, string n-digit yang valid sanggup dibuat dalam $9a_{n−1}$ cara.
Sumber http://www.marthamatika.com/
Suatu sistem komputer mengidentifikasi sebuah string dengan digit desimal. String dinyatakan valid jikalau string tersebut memuat digit 0 sebanyak bilangan genap. Sebagai contoh, string 1230407869 (banyak 0 dua) ialah valid sedangkan string 120987045608 tidak valid (banyak 0 tiga). Misalkan $a_n$ ialah banyaknya codeword dengan digit yang valid, temukanlah hubungan rekurensi untuk $a_n$
Solusi:
Jika n=1, maka $a_1=9$, Sebab dari 10 string satu-digit, hanya satu yaitu string 0 yang tidak valid. Relasi rekurensi untuk barisan ini sanggup diperoleh dengan memandang bagaimana string n-digit yang valid sanggup dibangun dari string n−1-digit. Ada dua cara untuk membentuk string n-digit yang valid dari string sebelumnya.
Pertama, sebuah string n-digit yang valid sanggup diperoleh dengan menambahkan string n−1 digit yang valid dengan angka selain 0. Penambahan ini sanggup dilakukan dengan 9 cara. Sehingga dengan cara ini, string n-digit yang valid sanggup dibuat dalam $9a_{n−1}$ cara.
Kedua, sebuah string n digit yang valid sanggup diperoleh dengan menambahkan 0 ke string dengan panjang n−1 yang tidak valid.(Ini menghasilkan sebuah string yang memuat digit 0 sebanyak bilangan genap alasannya string yang tidak valid dengan panjang n−1 memuat digit 0 sebanyak bilangan ganjil.) Banyaknya cara dengan jalan ini sanggup dilakukan sebanyak string n−1-digit yang tidak valid. Karena ada $10^{n−1}$ string digit desimal dengan panjang n−1, dan $a_{n−1}$ ialah valid, artinya ada $10^{n−1}−a_{n−1}$ string n-digit yang valid yang dibangun dengan cara kedua.
Berdasarkan aturan penjumlahan, banyaknya string yang valid dengan panjang n adalah
\begin{align*} a_n &= 9a_{n-1} + (10^{n-1} - a_{n-1})\\ &= 8a_{n-1} + 10^{n-1} \end{align*}
Post a Comment for "Contoh Korelasi Rekurensi: Codeword Enumeration"