pertemuan 6 sm 1

7/22/2019 Pertemuan 6 Sm 1

1/27

POLITEKNIK HARAPAN BERSAMA

MATEMATIKA 1


2/27


RekursiAda kalanya kita mengalami kesulitan untukmendefinisikan suatu obyek secara eksplisit.

Mungkin lebih mudah untuk mendefinisikan obyektersebut dengan

menggunakan dirinya sendiri. Inidinamakan sebagai proses rekursif.

Kita dapat mendefinikan barisan, fungsidanhimpunansecara rekursif.


3/27


Barisan yang didefinisikan secara rekursif

Contoh:

Barisan bilangan pangkat dari 2

an= 2nuntuk n = 0, 1, 2, .

Barisan ini dapat didefinisikan secara rekursif:

a0= 1

an+1= 2an untuk n = 0, 1, 2,

Langkah-langkah untuk mendefinisikan barisan secara rekursif:

1. Langkah basis: Spesifikasi anggota awal.

2. Langkah rekursif: Berikan aturan untuk membangun anggota barudari anggota yang telah ada.


4/27


Berikan definisi rekursif dari an

=rn, dengan rN,

r0 dan n bilangan bulat positif.

Solusi:Definisikan a0=r

0=1

dan an+1=r. an untuk n = 0, 1, 2,

Contoh barisan yang didefinisikansecara rekursif


5/27


Fungsi yang didefinisikan

secara rekursifLangkah-langkah untuk mendefinisikan fungsi dengan

domain bilangan cacah:

1. Langkah basis: Definisikan nilai fungsi pada saat nol.

2. Langkah rekursif: Berikan aturan untuk mencarinilai fungsi untuk setiap bilangan bulat berdasarkannilai fungsi pada bilangan bulat yang lebih kecil.

Definisi seperti itu disebut rekursifatau definisi

induktif.


6/27


f(0) = 3

f(n + 1) = 2f(n) + 3

Maka

f(0) = 3

f(1) = 2f(0) + 3 = 23 + 3 = 9

f(2) = 2f(1) + 3 = 29 + 3 = 21

f(3) = 2f(2) + 3 = 221 + 3 = 45

f(4) = 2f(3) + 3 = 245 + 3 = 93

Contoh fungsi yang didefinisikansecara rekursi


7/27


Fungsi Rekursif

Fungsi yang berisi definisi dirinya sendiri

Fungsi yang memanggil dirinya sendiri

Prosesnya terjadi secara berulang-ulang

Yang perlu diperhatikan adalah stopping role


8/27


Bagaimana kita dapat mendefinisikan fungsifaktorial f(n) = n! secara rekursif?

f(0) = 1

Karena (n+1)! = n! (n+1) maka

f(n + 1) = (n + 1)f(n)

f(0) = 1f(1) = 1 f(0) = 1 1 = 1

f(2) = 2 f(1) = 2 1 = 2

f(3) = 3 f(2) = 3 2 = 6

f(4) = 4 f(3) = 4 6 = 24

Contoh fungsi yang didefinisikansecara rekursif (2)


9/27


Contoh fungsi yang didefinisikan

secara rekursif (3)

Bagaimana kita dapat

mendefinisikan fungsi

secara rekursif?

n

k

kanf0

)(


10/27


Fibonacci Sepasang kelinci yang baru lahir (jantan dan

betina) ditempatkan pada suatu pembiakan.

Setelah dua bulan pasangn kelinci tersebutmelahirkan sepasang kelinci kembar (jantandan betina). Setiap pasangan kelinci yanglahir juga akan melahirkan sepasang kelinci

juga setiap 2 bulan. Berapa pasangan kelinciyang ada pada akhir bulan ke-12?


11/27


Fibo (2)


12/27


Fibo (3)

Deret Fibonacci adalah suatu deret

matematika yang berasal dari penjumlahandua bilangan sebelumnya.

1, 1, 2, 3, 5, 8, 13, 21,


13/27


Contoh terkenal: Bilangan Fibonacci

f0= 0, f1= 1

fn= fn-1+ fn-2, n=2,3,4,f0= 0

f1= 1

f2= f1+ f0= 1 + 0 = 1

f3= f2+ f1= 1 + 1 = 2

f4= f3+ f2= 2 + 1 = 3

f5= f4+ f3= 3 + 2 = 5f6= f5+ f4= 5 + 3 = 8

Tunjukkan bahwa untuk n 3,

fn < ndengan= (1+5)/2.


14/27


Himpunan yang

didefinisikan secara rekursif

Langkah-langkah dalam mendefinisikan suatu

himpunan secara rekursif:

1.Langkah basis:

Spesifikasi koleksi awal dari anggota

2.Langkah rekursif:Mendefinisikan aturan konstruksi anggota

baru dari anggota yang telah diketahui


15/27


Contoh himpunan yang didefinisikan secara

rekursif

Misalkan S didefinisikan secara rekursif oleh:

3 S

(x+y) S jika x S dan y S

Maka S adalah himpunan bilangan bulat positif yang habisdibagi 3.

Bukti:

Misalkan A himpunan yang beranggotakan semua bilanganbulat positif yang habis dibagi 3.

Untuk membuktikan bahwa A = S, harus ditunjukkan

A S and S A.

Bagian I:Akan dibuktikan A S, yaitu menunjukkan bahwa

setiap bilangan bulat positif yang habis dibagi 3 ada di S(dengan menggunakan induksi matematika).


16/27


Misalkan P(n): proposisi 3n anggota S.

1. Langkah basis:P(1) benar, karena 3 S.

2. Langkah induktif:

Asumsikan P(k) benar, yaitu 3k S.

Akan ditunjukkan P(k+1) juga benar, yaitu

3(k+1) S

Karena 3k Sdan 3 S, berdasarkan definisi rekursif dariS, 3k+3 = 3(k+1) juga ada di S.

3. Konklusi:

Jadi, setiap bilangan bulat positif yang habis dibagi 3 ada di S.

Kesimpulan dari bagian Iadalah A S.

Contoh himpunan yang didefinisikan secara

rekursif (2)


17/27


Contoh perluasan rekursiMisalkan didefinisikan

secara rekursif untuk (m,n)N x

N olehdan

nma

,

0jika,

0dan0jika,1

1,

,1

, nna

mnaa

nm

nm

nm

Tunjukkan bahwa

untuk setiap (m,n)N x N.

00,0 a

2/)1(, nnma nm


18/27


Problems Faktorial

5! = 5 x 4 x 3 x 2 x 1

4! = 4 x 3 x 2 x 1

Berarti 5! = 5 x 4!

Metode Iteratif

Salah satu cara untuk menghitung adalah denganmenggunakan loop, yang mengalikan masing-masing bilangandengan hasil sebelumnya. Penyelesaian dengan cara ini

dinamakan iteratif, yang mana secara umum dapatdidefinisikan sebagai berikut:

n! = (n)(n-1)(n-2) (1)


19/27


Faktorial RekursifMetode Rekursif

Cara lain untuk menyelesaikan permasalahan di atas

adalah dengan cara rekursi, dimana n! adalah hasil

kali dari n dengan (n-1)!. Untuk menyelesaikan (n-1)! adalah sama dengan n!,

sehingga (n-1)! adalah n-1 dikalikan dengan (n-2)!,

dan (n-2)! adalah n-2dikalikan dengan (n-3)! dan

seterusnya sampai dengan n = 1, kita menghentikan

penghitungan n!


20/27


FPB (Faktor Persekutuan Terbesar)

Misal FPB 228 dan 90: 228/90 = 2 sisa 48

90/48 = 1 sisa 42

48/42 = 1 sisa 6

42/6 = 7 sisa 0

FPB adalah hasil terakhir sebelum sisa = 0 adalah 6


21/27


Ilustrasi FPB rekursif

FPB(228,90) m>n

FPB(48,90) mn

FPB(42,48) mn

FPB(6,42) mn

FPB(0,6) m=0


22/27


Legenda Menara Hanoi

(oleh Edouard Lucas abad 19) Seorang biarawan memiliki 3 menara.

Diharuskan memindahkan 64 piringan emas.

Diameter piringan tersebut tersusun dari ukuran kecil ke besar.

Biarawan berusaha memindahkan semua piringan dari menara

pertama ke menara ketiga tetapi harus melalui menara keduasebagai menara tampungan.

Kondisi: Piringan tersebut hanya bisa dipindahkan satu-satu.

Piringan yang besar tidak bisa diletakkan di atas piringan yang lebihkecil.

Ternyata : mungkin akan memakan waktu sangat lama (sampaidunia kiamat).

Secara teori, diperlukan 264-1 perpindahan. Jika kita salahmemindahkan, maka jumlah perpindahan akan lebih banyak lagi.

Jika satu perpindahan butuh 1 detik, maka total waktu yangdibutuhkan lebih dari 500 juta tahun !!.


23/27


Tower of Hanoi


24/27


Tower of Hanoi

Algoritma:

Jika n==1, pindahkan pringan dari A ke C Jika tidak:

Pindahkan n-1 piringan dari A ke B menggunakan C

sebagai tampungan

Pindahkan n-1 piringan dari B ke C menggunakan Asebagai tampungan


25/27


Ilustrasi Tower of Hanoi


26/27


Proses Kerja


27/27


27

Soal latihan

Tentukan rumus (formula) rekursif barisan0, 3, 8, 15, 24,

Jika 2 merupakan faktor dari ,buktikan bahwa 2 juga merupakan faktordari

.

nn 2

)1()1( 2 nn

1.

2.

pertemuan 6 sm 1

Documents