Lewati ke konten utama

Subbab 3.5 Menyelesaikan Masalah Kombinatorial secara Rekursif

Dalam bagian ini, kita menyajikan contoh masalah kombinatorial yang solusinya dapat dihitung secara rekursif. Dalam Bab 9, kita akan kembali membahas masalah-masalah ini dan memperoleh solusi yang lebih ringkas lagi. Masalah pertama kita telah dibahas dalam bab pengantar.

Contoh 3.3.

Suatu keluarga yang terdiri atas \(n\) garis digambar pada bidang dengan ketentuan (1) setiap pasangan garis berpotongan dan (2) tidak ada tiga garis yang berpotongan pada titik yang sama. Misalkan \(r(n)\) menyatakan banyaknya daerah yang terbentuk ketika bidang dibagi oleh garis-garis tersebut. Jelas bahwa \(r(1)=2\text{,}\) \(r(2)=4\text{,}\) \(r(3)=7\text{,}\) dan \(r(4)=11\text{.}\) Untuk menentukan \(r(n)\) bagi semua bilangan bulat positif, cukup perhatikan bahwa \(r(1)=2\) dan, jika \(n>1\text{,}\) \(r(n)=n+r(n-1)\text{.}\) Rumus ini diperoleh dari pengamatan berikut. Jika garis-garis itu kita beri label \(L_1\text{,}\) \(L_2, \dots, L_n\text{,}\) maka \(n-1\) titik pada garis \(L_n\) tempat garis tersebut memotong garis-garis lain dalam keluarga itu membagi \(L_n\) menjadi \(n\) ruas, dua di antaranya tak berhingga. Setiap ruas ini berada di dalam suatu daerah yang ditentukan oleh \(n-1\) garis pertama, dan ruas tersebut kini membagi daerah itu menjadi dua. Dengan demikian, terbentuk \(n\) daerah lebih banyak daripada banyaknya daerah yang ditentukan oleh \(n-1\) garis. Keadaan ini diperlihatkan dalam Gambar 3.4, dengan garis yang memuat tiga titik sebagai \(L_4\text{.}\) Garis-garis lain membaginya menjadi empat ruas. Keempat ruas tersebut kemudian membagi daerah yang lebih besar sehingga terbentuk daerah \(1\) dan \(5\text{,}\) \(2\) dan \(6\text{,}\) \(7\) dan \(8\text{,}\) serta \(4\) dan \(9\text{.}\)
dijelaskan secara terperinci setelah gambar
Empat garis digambar pada bidang sedemikian rupa sehingga setiap pasangan garis berpotongan dan tidak ada tiga garis yang berpotongan pada satu titik. Pada salah satu garis, ketiga titik potong dengan tiga garis lainnya ditandai dengan titik. Daerah-daerah yang ditentukan oleh garis-garis tersebut diberi nomor dari \(1\) hingga \(11\text{.}\)
Gambar 3.4. Garis dan daerah pada bidang
Dengan rumus rekursif tersebut, kita memperoleh \(r(5)=5+11=16\text{,}\) \(r(6)=6+16=22\text{,}\) dan \(r(7)=7+22=29\text{.}\) Bahkan dengan perhitungan tangan, menghitung \(r(100)\) tidak akan terlalu merepotkan. Kita dapat menyelesaikannya sebelum makan siang.

Contoh 3.5.

Papan kotak-kotak berukuran \(2\times n\) akan dipasangi ubin persegi panjang berukuran \(2\times1\) dan \(1\times2\text{.}\) Carilah rumus rekursif untuk banyaknya pengubinan, yaitu \(t(n)\text{.}\) Jelas bahwa \(t(1)=1\) dan \(t(2)=2\text{.}\) Jika \(n>2\text{,}\) perhatikan persegi panjang yang menutupi petak di sudut kanan atas. Jika persegi panjang itu vertikal, bagian sebelumnya merupakan pengubinan \(n-1\) kolom pertama. Jika persegi panjang itu horizontal, persegi panjang tepat di bawahnya juga horizontal, dan bagian sebelum keduanya merupakan pengubinan \(n-2\) kolom pertama. Hal ini menunjukkan bahwa \(t(n)=t(n-1)+t(n-2)\text{.}\) Secara khusus, \(t(3)=1+2=3\text{,}\) \(t(4)=2+3=5\text{,}\) dan \(t(5)= 3+5=8\text{.}\)
Sekali lagi, jika benar-benar diperlukan, kita dapat memperoleh \(t(100)\) dengan perhitungan tangan, sedangkan suatu sistem aljabar komputer dapat memperoleh \(t(1000)\text{.}\)

Contoh 3.6.

Sebut suatu string terner baik jika string itu tidak pernah memuat \(2\) yang langsung diikuti oleh \(0\text{;}\) jika tidak demikian, sebut string itu buruk. Misalkan \(g(n)\) adalah banyaknya string baik dengan panjang \(n\text{.}\) Jelas bahwa \(g(1)=3\) karena semua string dengan panjang \(1\) bersifat baik. Selain itu, \(g(2)=8\) karena satu-satunya string buruk dengan panjang \(2\) adalah \((2,0)\text{.}\) Sekarang, perhatikan nilai \(n\) yang lebih besar daripada \(2\text{.}\)
Bagi himpunan string baik dengan panjang \(n\) menjadi tiga bagian menurut karakter terakhirnya. String baik yang berakhir dengan \(1\) dapat diawali oleh sembarang string baik dengan panjang \(n-1\) sehingga terdapat \(g(n-1)\) string semacam itu. Hal yang sama berlaku bagi string baik yang berakhir dengan \(2\text{.}\) Namun, untuk string baik yang berakhir dengan \(0\text{,}\) kita harus lebih berhati-hati. Kita dapat menempatkan sebelum \(0\) suatu string baik dengan panjang \(n-1\text{,}\) asalkan string tersebut tidak berakhir dengan \(2\text{.}\) Terdapat \(g(n-1)\) string baik dengan panjang \(n-1\text{,}\) dan tepat \(g(n-2)\) di antaranya berakhir dengan \(2\text{.}\) Oleh karena itu, terdapat \(g(n-1)-g(n-2)\) string baik dengan panjang \(n\) yang berakhir dengan \(0\text{.}\) Dengan demikian, jumlah keseluruhan string baik dengan panjang \(n\) memenuhi rumus rekursif \(g(n) = 3g(n-1) - g(n-2)\text{.}\) Jadi, \(g(3) = 3\cdot8 -3= 21\) dan \(g(4)= 3\cdot21-8= 55\text{.}\)
Sekali lagi, \(g(100)\) dapat dihitung dengan tangan, sedangkan komputer berspesifikasi sederhana pun dapat diminta menghitung \(g(5000)\text{.}\)

Subbagian 3.5.1 Menentukan Faktor Persekutuan Terbesar

Teorema dasar berikut sesungguhnya memuat lebih banyak hal daripada yang mungkin Anda duga, meskipun sekilas hanya menyatakan fakta yang telah Anda kenal sejak kelas dua sekolah dasar.

Bukti.
Kita membuktikan pernyataan keberadaan. Bagian ketunggalan hanya memerlukan aljabar tingkat sekolah menengah. Jika teorema ini tidak berlaku, misalkan \(t\) adalah bilangan bulat positif terkecil yang memiliki bilangan bulat \(m\) dan \(n\) dengan \(m+n=t\text{,}\) tetapi tidak terdapat bilangan bulat \(q\) dan \(r\) yang memenuhi \(m=qn+r\) dan \(0\le r\lt n\text{.}\)
Pertama, perhatikan bahwa \(n\neq 1\) karena, jika \(n=1\text{,}\) kita dapat mengambil \(q=m\) dan \(r=0\text{.}\) Selain itu, tidak mungkin \(m=1\) karena, jika \(m=1\text{,}\) kita dapat mengambil \(q=0\) dan \(r=1\text{.}\) Sekarang, pernyataan tersebut berlaku untuk pasangan \(m-1\text{,}\) \(n\) sehingga terdapat bilangan bulat \(q\) dan \(r\) sedemikian rupa sehingga
\begin{equation*} m-1 = q\cdot n+r\quad\text{and} \quad 0 \le r \lt n. \end{equation*}
Karena \(r\lt n\text{,}\) kita mengetahui bahwa \(r+1\le n\text{.}\) Jika \(r+1\lt n\text{,}\) maka
\begin{equation*} m = q\cdot n+(r+1)\quad\text{and} \quad 0 \le r+1 \lt n. \end{equation*}
Sebaliknya, jika \(r+1=n\text{,}\) maka
\begin{equation*} m = q\cdot n+(r+1)=nq+n=(q+1)n=(q+1)n+0. \end{equation*}
Kontradiksi ini menyelesaikan bukti.
Ingatlah bahwa bilangan bulat \(n\) merupakan pembagi dari bilangan bulat \(m\) jika terdapat bilangan bulat \(q\) sedemikian rupa sehingga \(m=qn\text{.}\) (Kita menulis \(n\mid m\) dan membacanya sebagai “\(n\) membagi \(m\)”.) Bilangan bulat \(d\) merupakan pembagi persekutuan dari bilangan bulat \(m\) dan \(n\) jika \(d\) membagi \(m\) maupun \(n\text{.}\) Faktor persekutuan terbesar (FPB) dari \(m\) dan \(n\text{,}\) yang ditulis \(\gcd(m,n)\text{,}\) adalah pembagi terbesar di antara semua pembagi persekutuan \(m\) dan \(n\text{.}\)
Berikut adalah penerapan yang sangat anggun dari teorema dasar sebelumnya:

Bukti.
Perhatikan persamaan \(m=q\cdot n+r\text{,}\) yang ekuivalen dengan \(m-q\cdot n = r\text{.}\) Jika suatu bilangan \(d\) membagi \(m\) dan \(n\text{,}\) maka \(d\) juga harus membagi \(r\text{.}\) Demikian pula, jika \(d\) membagi \(n\) dan \(r\text{,}\) maka \(d\) juga harus membagi \(m\text{.}\)
Berikut adalah cuplikan kode yang menghitung FPB dari \(m\) dan \(n\) ketika \(m\) dan \(n\) merupakan bilangan bulat positif dengan \(m\ge n\text{.}\) Kita menggunakan notasi yang lazim, m%n, untuk menyatakan sisa \(r\) dalam persamaan \(m=q\cdot n+r\text{,}\) dengan \(0\le r \lt n\text{.}\)
Anda dapat mengubah nilai 12 dan 5 pada sel SageMath di atas dalam versi HTML buku ini untuk menghitung FPB bilangan bulat lainnya. Namun, ingatlah bahwa kode tersebut mengasumsikan \(m\geq n\text{!}\)
Kelemahan pendekatan ini adalah penggunaan memori yang agak boros akibat pemanggilan fungsi secara rekursif. Tidaklah sulit untuk membuat kode yang menghitung FPB dari \(m\) dan \(n\) hanya dengan perulangan, i.e., tanpa pemanggilan rekursif. Dengan sedikit pekerjaan tambahan, kode semacam itu juga dapat dirancang untuk menyelesaikan masalah persamaan Diofantin berikut:
Melalui contoh berikut, mari kita lihat cara menggunakan Algoritma Euklides untuk menuliskan \(\gcd(m,n)\) dalam bentuk \(am+bn\) dengan \(a,b\in\ints\text{.}\)

Contoh 3.10.

Tentukan FPB \(d\) dari \(3920\) dan \(252\text{,}\) lalu tentukan bilangan bulat \(a\) dan \(b\) sedemikian rupa sehingga \(d=3920a+252b\text{.}\)
Penyelesaian.
Dalam menyelesaikan masalah ini, kita memperagakan Algoritma Euklides sedemikian rupa sehingga kita dapat menentukan \(a\) dan \(b\) dengan bekerja mundur. Pertama, perhatikan bahwa
\begin{equation*} 3920 = 15\cdot 252 + 140. \end{equation*}
Sekarang, Algoritma Euklides memberi tahu kita bahwa \(\gcd(3920,252)=\gcd(252,140)\text{,}\) sehingga kita menuliskan
\begin{equation*} 252 = 1\cdot 140 + 112. \end{equation*}
Dengan melanjutkan proses ini, kita memperoleh \(140= 1\cdot 112 + 28\) dan \(112 = 4\cdot 28+0\text{,}\) sehingga \(d=28\text{.}\)
Untuk menentukan \(a\) dan \(b\text{,}\) kini kita menelusuri mundur persamaan-persamaan yang telah diperoleh sebelumnya, “menyelesaikannya” terhadap suku sisa, lalu melakukan substitusi. Kita mulai dengan
\begin{equation*} 28 = 140-1\cdot 112. \end{equation*}
Namun, kita mengetahui bahwa \(112=252-1\cdot 140\text{,}\) sehingga
\begin{equation*} 28=140-1(252-1\cdot 140) = 2\cdot 140 - 1\cdot 252. \end{equation*}
Akhirnya, \(140 = 3920-15\cdot 252\text{,}\) sehingga sekarang kita memperoleh
\begin{equation*} 28= 2(3920-15\cdot 252) - 1\cdot 252 = 2\cdot 3920-31\cdot 252. \end{equation*}
Oleh karena itu, \(a=2\) dan \(b=-31\text{.}\)

Subbagian 3.5.2 Pengurutan

Salah satu masalah komputasi yang paling umum dan mendasar adalah pengurutan: jika diberikan suatu barisan \(a_1,a_2,\dots,a_n\) yang terdiri atas \(n\) bilangan bulat yang semuanya berbeda, susun ulang bilangan-bilangan tersebut agar berada dalam urutan menaik. Di sini, kita menjelaskan strategi rekursif sederhana untuk menyelesaikan tugas tersebut. Strategi ini dikenal sebagai urut gabung (Merge Sort), dan merupakan salah satu dari beberapa algoritma pengurutan yang optimal. Mata kuliah pengantar ilmu komputer membahas topik ini secara lebih mendalam. Dalam mata kuliah kita, kita hanya memerlukan suatu strategi yang baik, dan urut gabung sudah sesuai untuk keperluan kita.
Untuk menyajikan urut gabung, pertama-tama kita harus mengembangkan strategi untuk menyelesaikan suatu kasus khusus dari masalah pengurutan. Misalkan kita memiliki \(s+t\) bilangan bulat yang semuanya berbeda,
\begin{equation*} \{u_0,u_1,\dots,u_{s-1},v_0,v_1,\dots,v_{t-1}\} \end{equation*}
yang disusun sebagai dua daftar dengan \(u_0\lt u_1\lt \dots\lt u_{s-1}\) dan \(v_0\lt v_1\lt \dots\lt v_{t-1}\text{.}\) Bagaimana kita menggabungkan kedua barisan tersebut menjadi satu barisan menaik dengan panjang \(s+t\text{?}\) Bayangkan kedua barisan itu ditempatkan pada dua baris horizontal, yang satu tepat di bawah yang lain. Misalkan \(u\) adalah bilangan bulat terkecil dalam barisan pertama dan \(v\) adalah bilangan bulat terkecil dalam barisan kedua. Pada saat ini, berarti \(u=u_0\) dan \(v=v_0\text{,}\) tetapi bilangan bulat akan dihapus dari kedua barisan selama proses berlangsung. Meskipun demikian, arti \(u\) dan \(v\) tetap dipertahankan. Tetapkan pula \(i=0\text{.}\) Kemudian, ambil \(a_i\) sebagai nilai minimum dari \(u\) dan \(v\text{,}\) lalu hapus \(a_i\) dari barisan tempat nilai itu muncul. Setelah itu, naikkan \(i\) sebesar \(1\) dan ulangi prosesnya. Berikut adalah cuplikan kode untuk melakukan operasi penggabungan, dengan \(u_p\) kini ditulis sebagai u[p] dan \(v_q\) ditulis sebagai v[q].
Setelah memiliki strategi penggabungan yang baik, kita dapat dengan mudah mengembangkan strategi rekursif untuk mengurutkan. Jika diberikan suatu barisan \(a_1,a_2,\dots,a_n\) yang terdiri atas \(n\) bilangan bulat yang semuanya berbeda, tetapkan \(s=\lceil n/2\rceil\) dan \(t=\lfloor n/2\rfloor\text{.}\) Kemudian, misalkan \(u_i=a_i\) untuk \(i=1,2,\dots,s\) dan \(v_j=a_{s+j}\) untuk \(j=1,2,\dots,t\text{.}\) Urutkan kedua subbarisan tersebut, lalu gabungkan keduanya. Sebagai contoh konkret, jika diberikan barisan \((2,8,5,9,3,7,4,1,6)\text{,}\) kita membaginya menjadi \((2,8,5,9,3)\) dan \((7,4,1,6)\text{.}\) Kedua subbarisan ini diurutkan (melalui pemanggilan rekursif) menjadi \((2,3,5,8,9)\) dan \((1,4,6,7)\text{,}\) lalu kedua barisan terurut tersebut digabungkan.
Untuk waktu eksekusi, misalkan \(S(n)\) adalah banyaknya operasi yang diperlukan untuk mengurutkan barisan yang terdiri atas \(n\) bilangan bulat berbeda. Maka \(S(2n)\le2 S(n) + 2n\) karena jelas diperlukan \(2n\) langkah untuk menggabungkan dua barisan terurut yang masing-masing panjangnya \(n\text{.}\) Hal ini menghasilkan batas \(S(n) \lt C n\log n\) untuk suatu konstanta positif \(C\text{.}\) Dalam mata kuliah ilmu komputer, Anda akan mempelajari (di sini hal tersebut menjadi latihan) bahwa batas ini optimal.
SblmKe AtasLnjt