(Menyeberangkan Barang Bawaan)
Misalkan seorang Petani tiba ditepi sebuah sungai.Pemuda tersebut membawa seekor kambing, seekor srigala dan sekeranjang sayur. Mereka bermaksud hendak menyeberangi sungai .Petani itu menemukan sebuah perahu kecil yang hanya dapat memuat satu bawaannya setiap kali menyeberang. Situasinya dipersulit dengan kenyataan bahwa serigala tidak dapat ditinggal berdua edengan kambing (karena srigala akan memakan kambing) atau kambing tidak dapat ditinggal berdua dengan sekeranjang sayur (karena kambing akan memakan sayur). Buatlah algoritma untuk menyeberangkan Petani dan seluruh bawaannya itu sehingga mereka sampai keseberang sungai dengan selamat.
Penyelesaian
Misalkan sisi sungai kita namakan A dan sisi sungai seberang kita namakan B. Keadaan awalnya. Disisi A ada pemuda (P), srigala (S),kambing (K) dan sayur (Y).Keadaan akhir yang kita inginkan adalah disisi B ada pemuda (p), srigala (S), kambing (K) dan sayur (Y)
PROGRAM menyeberangi_sungai
Program untuk menyeberangkan Petani (p) dan tiga barang bawaaannya: srigala (s) ,kambing (K) dan sekeranjang sayur (Y) dengan sebuah perahu kecil yang hanya dapat memuat 2 item (pemuda dan salah satu bawaanya). Srigala tidak dapat ditinggal berdua dengan kambing (karena srigala akan memangsa kambing)atau kambing tidak dapat ditinggal berdua dengan sekeranjang sayur(karena kambing akan memakan sayur).
AlGORITMA
- Petani menyeberangkan kambing dari sisi A ke sisi B
{ sisi A: (- , S , K , Y ) sisi B: (P , – , K , -) }
- Petani menyeberang sendiri dari sisi B ke sisi A
{ sisi A: ( P, S , K , Y ) sisi B: (- , – , K , -) }
- Petani menyeberangkan srigala dari sisi A ke sisi B
{ sisi A: (- , – , – , Y ) sisi B: (P , S , K , -) }
- Petani menyeberangkan kambing dari sisi B ke sisi A
{ sisi A: (P, – , K , Y ) sisi B: (- , S , – , -) }
- Petani menyeberangkan sayur dari sisi A ke sisi B
{ sisi A: (- , – , K , – ) sisi B: (P , S , – , Y) }
- Petani menyeberang sendiri dari sisi B ke sisi A
{ sisi A: ( P, – , K , – ) sisi B: (- , – , K , Y) }
- Petani menyeberangkan kambing dari sisi A ke sisi B
{ sisi A: (- , – , – , – ) sisi B: (P , S , K , Y) }
Memindahkan Besi
Tiga buah cakram yang masing-masing berdiameter berbeda mempunyai lubang dititik pusatnya.Ketiga cakram tersebut dimasukan pada sebuah batang besi A sedemikian sehingga cakram yang berdiameter lebih besar selalu terletak dibawah cakram yang berdiameter lebih kecil .Tulislah Algoritma untuk memindahkan seluruh cakram tersebut ke batang besi B; setiap kali hanya satu cakram yang boleh dipindahkan, tetapi pada setiap perpindahan tidak boleh ada cakram yang ebih besar berada diatas cakram kecil.Batang besi C dapat dipakai sebagai tempat peralihan dengan tetap memegang aturan yang telah disebutkan.
Program Memindahkan_besi
Program memindahkan tiga cakram besi . Ketiga cakram tersebut dimasukan pada sebuah batang besi A sedemikian sehingga cakram yang berdiameter lebih besar selalu terletak dibawah cakram yang berdiameter lebih kecil .pindahkan ke batang besi B; setiap kali hanya satu cakram yang boleh dipindahkan, tetapi pada setiap perpindahan tidak boleh ada cakram yang ebih besar berada diatas cakram kecil.Batang besi C dapat dipakai sebagai tempat peralihan dengan tetap memegang aturan yang telah disebutkan.( cakram besi diameter terbesar kita namai dengan C1 dan untuk yang pertengahan di sebut C2 yang terakhir C3
ALGORITMA
- Pasangkan cakram besi pada batang besi A dengan urutan dari bawah keatas C1, C2 ,C3
- Pindahkan C3 ke batang besi B
- Pindahkan C2 ke batang besi C
- Pindahkan C3 ke batang besi C
- Pindahkan C1 ke batang besi B
- Pindahkan C3 ke batang besi A
- Pindahkan C2 ke batang besi B
Pindahkan C3 ke batang besi B
