Divide And Conquer

Nama  : Rahman Azis
Npm   : 58414787
Kelas  : 1IA24

Divide and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut imperes.

Sekarang strategi tersebut  menjadi strategi fundamental di dalam ilmu komputer dengan nama Divide and Conquer

.

Definisi

Divide:  membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),

Conquer: memecahkan (menyelesaikan) masing-masing upa-masalah (secara  rekursif), dan

Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula

Obyek permasalahan yang dibagi :

            masukan (input) atau instances yang berukuran n seperti:

            - tabel (larik),

            - matriks,

            - eksponen,

            - dll, bergantung pada masalahnya.

Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif

Skema Program Algoritma Divide dan Conquer

Cotoh Soal Dan Penjelasan Jawabannya

Persoalan : Misalnya diketahui table A yang berukuran n eleman sudah berisi nilai integer. Kita ingin menentukan nilai minimum dan nilai maksimum sekaligus di dalam table tersebut. Misalkan tabel A berisi elemen-elemen sebagai berikut :

Ide dasar algoritma secara Divide and Conquer :

Disini Saya Akan Menjelaskan Bahwa Pada Soal Diatas Kita Hanya Perlu Memisahkan Urutan Angka

Dan Tentukan Min dan Maks Pada Tiap Bagian Kelompok Angka yang dipisahkan Dengan cara Solve

Lalu COMBINE/Gabungkan Angka Tersebut Lagi Hingga Menjadi 1 Kelompok 

Catatan : Berarti Pada Algoritma dan Conquer ini Kita Hanya Perlu Mencari Min Dan Maksnya Saja