Soal Relasi
Rekursi untuk Matematika Informatika 4
1) 01) Solusi homogen dari relasi
rekurensi bn + bn-1 – 6 bn-2 = 0 dengan
kondisi batas b0 = 0 , b1
= 1 adalah
a. bn(h) = A1 (-3)n + A2 . 2n c. (a +
3) (a - 2)
b. bn(h) =
(-3)n +
. 2n
d. b0(h)
= A1 (-3)0 + A2 . 20
Jawab
bn +
bn-1 – 6 bn-2
= 0
= a2
+ a -
6 = 0
= (a +
3) (a - 2)
= 0
a1 =
-3 a2 = 2.
solusi homogen = bn(h) = A1 a1n + A2 a2n => bn(h) = A1 (-3)n + A2 . 2n
Dengan kondisi batas
b0 = 0 dan b1 = 1 , maka:
b0(h)
= A1 (-3)0 + A2 . 20 =>
0 = A1 + A2 .
b1(h)
= A1 (-3)1 + A2 . 21 =>
1 = -3 A1 + 2 A2
maka akan diperoleh
harga A1
=
(-
) dan A2 =
jawab homogen dari
relasi rekurensi bn + bn-1 – 6bn-2 = 0 adalah
bn(h)
=
(-3)n
+
. 2n
02) Mana diantara berikut yang merupakan solusi
dari relasi rekurensi dari :
an
+ 4 an-1 + 4 an-2 = 2n .
a.
an(h) = (A1 nm-1 + A2 nm-2)
a1n , an(h) = (A1 n + A2 ) (-2)n
.
b. an(h) = (A1 n + A2 ) (-2)n
.
c. an(h) = (A1 nm-1 + A2 nm-2)
a1n ,
d. an(h) = (A1 nm-1) an(h)
= (A1 n + A2 )
(-2)n .
Jawab
:
Relasi rekurensi homogen : an + 4
an-1 + 4 an-2 =0.
Persamaan karakteristiknya
adalah a2 + 4 a
+ 4 = 0
(a + 2) ( a + 2) = 0
hingga diperoleh akar-akar
karakteristik a1 = a2 = -2 ,
m = 2,
Oleh karena akar-akar
karakteristiknya ganda,
maka solusi homogennya berbentuk an(h) = (A1 nm-1 + A2 nm-2)
a1n , an(h)
= (A1 n + A2 )
(-2)n .
03)
Diketahui : Suatu barisan c0, c1,
c2, … didefinisikan secara rekursif sebagai berikut :
Untuk semua bilangan bulat k ≥ 2,
Ck = (ck-1 + k) (ck-2 + 1)
Dengan kondisi awal c0 = 1 dan c1 = 2.
Ditanya : Hitunglah c5 !
A. C5 = 90
B. C5 = 92
C. C5 = 84
D. C5 = 94
Penyelesaian :
Oleh karena barisan didefinisikan secara rekursif, maka
c5 tidak bisa dihitung secara langsung, tetapi harus terlebih dahulu menghitung
c2, c3 dan c4.
·
c2 = c1 + 2 c0 + 1 =
2 + 2.1 + 1 = 5
·
c3= c2 + 3 c1 + 1 =
5 + 3.2 + 1
= 12
·
c4= c3 + 4 c2 + 1 =
12 + 4.5 + 1
= 33
·
c5= c4 + 5 c3 + 1 =
33 + 5.12 + 1 = 94
Jadi, c5 = 94
04)
Tentukan
solusi homogen dari relasi rekurensi
bn + bn-1 – 6 bn-2 = 0 dengan kondisi batas b0 = 0 , b1
= 1 .
a. bn(h) =
. 3n +
. 2n
b. bn(h) =
(-3)n
+ 2n .
c.
bn(h) =
(-3)n
+
. 2n .
d. bn(h) =
(-2)n
+
. 3n
Penyelesaian :
Relasi rekurensi tersebut adalah relasi rekurensi homogen, karena
f(n)=0.
Persamaan karakteristik dari relasi rekurensi bn + bn-1 – 6 bn-2
= 0
adalah a2 + a
- 6 = 0 atau (a + 3) ( a - 2) = 0
hingga diperoleh akar-akar karakteristik a1 = -3
dan a2 = 2.
Oleh karena akar-akar karakteristiknya berbeda, maka solusi
homogennya berbentuk bn(h)
= A1 a1n
+ A2 a2n Þ bn(h)
= A1 (-3)n + A2
. 2n.
Dengan kondisi batas b0
= 0 dan b1 = 1 , maka
b0(h) = A1 (-3)0 + A2
. 20 Þ 0
= A1 + A2 .
b1(h) = A1 (-3)1 + A2
. 21 Þ 1
=
-3 A1 + 2 A2 .
bila diselesaikan maka akan diperoleh harga A1 = (-1/5) dan A2
= 1/5 , sehingga jawab homogen dari relasi rekurensi bn + bn-1 – 6 bn-2
= 0 adalah
bn(h) =
(-3)n
+
. 2n .
05)
Tentukan
solusi homogen dari relasi rekurensi
4 an - 20 an-1 + 17 an-2
– 4 an-3 = 0.
a. an(h) = (A1 n + A2 ) (½)n
+ A1 . 4n.
b. an(h) = (A2 n - A1 ) (½)n
+ A3 . 4n.
c. an(h) = (A1 n - A2 ) (½)n
+ A3 . 3n.
d.
an(h) = (A1 n + A2 ) (½)n
+ A3 . 4n.
Penyelesaian :
Persamaan karakteristiknya : 4 a3 - 20 a2 + 17 a
- 4 = 0
akar-akar karakteristiknya ½ , ½ dan 4
solusi homogennya berbentuk an(h) = (A1 n + A2 ) (½)n
+ A3 . 4n.
06)
Diketahui
relasi rekurensi Sn = 2Sn-1 dengan syarat awal S0 = 1. Selesaikan untuk suku
ke-n!
a.
2n
b. 4n
c. n
d. 2
Penyelesaian
Dengan iterasi diperoleh:
Sn
= 2Sn-1
=
2 (2Sn-2) = 2Pangkat2 Sn-2
=
2pangkat3 Sn-3
= ………
= 2n S0
=
2n
07)
1.
Berapa banyak kah bilangan Fibonacci antara 10 sampai dengan 100?
(A)
90
(B)
9
(C) 5
(D)
10
Jawab
:
Dari
tabel di atas, terlihat bahwa bilangan Fibonacci yang terletak antara 10 hingga
100 adalah sebanyak 5 (lima) buah, yaitu suku ke-6 (13), suku ke-7 (21), suku
ke-8 (34), suku ke-9 (55), dan suku
ke-10 (89). Dengan demikian, jawabannya adalah (C) 5.
08)
Dengan
mengambil satu harga n kemudian anda menjumlahkan bilangan-bilangan tsb mulai
dari f1 s.d. fn maka berapakah n terkecil agar jumlah itu > 150?
(A)
9
(B) 10
(C)
11
(D)
15
Jawab
:
Dari
tabel di atas juga, dapat kita ketahui bahwa nilai n terkecil agar jumlah
seluruh bilangan Fibonacci dari f1 hingga fn > 150 adalah sebesar 10 (n=10),
yang akan menghasilkan jumlah sebesar
231 (diperoleh dari = 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89, yang
merupakan bilangan fibonacci dari suku ke-1 hingga suku ke-10). Sehingga,
jawaban yang benar adalah (B) 10.
1 09) Selesaikan relasi rekurensi an = 7an -1 ,
n > 1, a2= 98
a. an = 7n (2) , n > 1
b. an = 7n (1) , n > 0
c. an = 7n , n > 2
d. an = 7n (2) , n > 0
d.
Penyelesaian:
Untuk
n = 1 maka a1 = 7 a0 a2 = 7 a1 = 7 (7 a0) = 72 a0 dari a2 = 98 maka 98 = 49 a0
sehingga
diperoleh a0 = 2. Jika relasi rekurensi tersebut dideretkan terus akan diperoleh :
a3 = 7 a2 = 7 (7pangkat2 a0) = 7pangkat3 a0
..........dan seterusnya
sehingga penyelesaian umum dari relasi
rekurensi di atas adalah
an = 7n (2) , n > 0
10) Jika
diketahui Hanoi Tower memiliki 5 cakram berapakah langkah paling singkat untuk
menyelesaikan permainan tersebut? (Dengan menggunakan rumus (2n – 1)
dimana n adalah banyaknya cakram).
a. 16 cara
b. 64 cara
c. 32 cara
d. 8 cara
e. semua jawaban salah
Jawab :
5 Cakram = 25
Jadi jawabannya 25 = 32 (c)
Tidak ada komentar:
Posting Komentar