SoalRelasiRekursiuntukMatematikaInformatika
4
1)
Solusihomogendarirelasirekurensibn
+ bn-1 – 6 bn-2 = 0 dengan
kondisibatas 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.
solusihomogen = bn(h)= A1 a1n+ A2 a2n =>bn(h)= A1 (-3)n+ A2 . 2n
Dengankondisibatas 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
makaakandiperolehharga
A1
=
(-
) dan A2 =
jawabhomogendarirelasirekurensibn+ bn-1 – 6bn-2 = 0 adalah
bn(h)
=
(-3)n
+
. 2n
2) Manadiantaraberikut yang merupakansolusidarirelasirekurensidari :
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
:
Relasirekurensihomogen : an +
4 an-1 + 4 an-2 =0.
Persamaankarakteristiknyaadalah a2 + 4 a
+ 4 = 0
(a+ 2) (a + 2) = 0
hinggadiperolehakar-akarkarakteristika1 = a2 = -2 ,
m = 2,
Olehkarenaakar-akarkarakteristiknyaganda,
makasolusihomogennyaberbentuk an(h) = (A1 nm-1 + A2 nm-2)
a1n ,an(h)
= (A1 n + A2 )
(-2)n .
3)
Diketahui : Suatubarisan c0, c1,
c2, … didefinisikansecararekursifsebagaiberikut :
Untuksemuabilanganbulat k ≥ 2,
Ck = (ck-1 + k) (ck-2 + 1)
Dengankondisiawal c0 = 1 dan c1 = 2.
Ditanya :Hitunglah c5 !
Penyelesaian :
Olehkarenabarisandidefinisikansecararekursif, maka c5
tidakbisadihitungsecaralangsung, tetapiharusterlebihdahulumenghitung 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
A.
C5 = 90
B.
C5 = 92
C.
C5 = 84
D. C5 = 94
E.
4)
Tentukansolusihomogendarirelasirekurensibn
+ bn-1 – 6 bn-2 = 0
dengankondisibatas 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 :
Relasirekurensitersebutadalahrelasirekurensihomogen,
karenaf(n)=0.
Persamaankarakteristikdarirelasirekurensi bn + bn-1 – 6 bn-2
= 0
adalah a2 + a
- 6 = 0 atau (a+ 3) (a - 2) = 0
hinggadiperolehakar-akarkarakteristika1 = -3
dana2 = 2.
Olehkarenaakar-akarkarakteristiknyaberbeda,
makasolusihomogennyaberbentuk bn(h)
= A1a1n
+ A2 a2n Þ bn(h)
= A1 (-3)n + A2
. 2n.
Dengankondisibatas 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 .
biladiselesaikanmakaakandiperolehharga A1 = (-1/5) dan A2
= 1/5 , sehinggajawabhomogendarirelasirekurensibn + bn-1
– 6 bn-2 = 0 adalah
bn(h) =
(-3)n
+
.2n
.
5)
Tentukansolusihomogendarirelasirekurensi
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 :
Persamaankarakteristiknya : 4 a3 - 20 a2 + 17 a
- 4 = 0
akar-akarkarakteristiknya ½ , ½
dan 4
solusihomogennyaberbentuk an(h) = (A1 n + A2 ) (½)n
+ A3 . 4n.
6)
n -
n-1 =2n2,n
1,
dan
0 = 9
……
a)
5 +
(n) (n+1)(4n+2)
b)
9 +
(n) (n+1)(2n+1)
c)
2 +
(n+2)(n)(n+2n)
d)
9 +
(n)(n+1)(2n+1)
Jawaban B
Penyelesaian
f(n)
= 2n2,
sehinggasolusiumumnya :
n =
0 +
(i)
=
0 +
2
=
0+ 2
= 9 +
(n) (n+1)(2n+1)
7)
Diketahuirelasirekurensi
Sn = 2Sn-1 dengansyaratawal S0 = 1. Selesaikanuntuksukuke-n!
a.
2n
b. 4n
c. n
d. 2
PenyelesaianDenganiterasidiperoleh:
Sn
= 2Sn-1
=
2 (2Sn-2) = 2Pangkat2 Sn-2
=
2pangkat3Sn-3
= ………
= 2nS0
=
2n
8)
1.
Berapabanyakkahbilangan Fibonacci antara 10 sampaidengan 100?
(A)
90
(B)
9
(C) 5
(D)
10
Jawab
:
Dari
tabel di atas, terlihatbahwabilangan Fibonacci yang terletakantara 10 hingga
100 adalahsebanyak 5 (lima) buah, yaitusuku ke-6 (13), suku ke-7 (21), suku
ke-8 (34), suku ke-9 (55), dansuku ke-10 (89). Dengandemikian, jawabannyaadalah
(C) 5.
9)
Denganmengambilsatuharga
n kemudianandamenjumlahkanbilangan-bilangantsbmulaidari f1 s.d.fnmakaberapakah
n terkecil agar jumlahitu> 150?
(A)
9
(B) 10
(C)
11
(D)
15
Jawab
:
Dari
tabel di atasjuga, dapatkitaketahuibahwanilai n terkecil agar
jumlahseluruhbilanganFibonacci dari f1 hinggafn> 150 adalahsebesar 10
(n=10), yang akanmenghasilkanjumlahsebesar 231 (diperolehdari = 1 + 2 + 3 + 5 +
8 + 13 + 21 + 34 + 55 + 89, yang merupakanbilanganfibonaccidarisuku ke-1
hinggasuku ke-10). Sehingga, jawaban yang benaradalah (B) 10.
10)Selesaikanrelasirekurensi 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) = 72a0 dari a2 = 98 maka 98 = 49 a0
sehinggadiperoleh
a0 = 2. Jikarelasirekurensitersebutdideretkanterusakandiperoleh:
a3 = 7 a2 = 7 (7pangkat2 a0) = 7pangkat3 a0
..........danseterusnya
sehinggapenyelesaianumumdarirelasirekurensi
di atasadalah
an
= 7n (2) , n > 0
11) Jika
diketahui Hanoi Tower memiliki 5 cakramberapakahlangkah paling
singkatuntukmenyelesaikanpermainantersebut? (Denganmenggunakanrumus (2n
– 1) dimana n adalahbanyaknyacakram).
a. 16 cara
b. 64 cara
c. 32 cara
d. 8 cara
e. semuajawabansalah
Jawab :
5 Cakram = 25
Jadijawabannya
25 = 32 (c)
No Response to "TUGAS MATIF "
Posting Komentar