Pengertian Algoritma Divide and Conquer dan Contoh Program Menggunakan Algoritma Divide and Conquer

Assalamu'alaikum warahmatullahi wabarakatuh

Sekali nulis maunya nulis terus. hehe :p
Kali ini saya mau berbagi tentang program C++ yang menggunakan Algoritma Divide and Conquer.

Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

• 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 ).
• Combine : Menggabungkan solusi masing-masing upa-masalah sehingga  membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, 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.

Nah di bawah ini merupakan contoh coding programnya:

#include <stdio.h>

#include <conio.h>

int a[100];

int max, min;

void maxmin(int i, int j) {

     int max1, min1, mid;

     if(i==j) {

          max=min=a[i];   }

     else if(i==j-1) {

           if(a[i]>a[j]) {

                max=a[i];

                min=a[j];  }

           else {

                max=a[j];

                min=a[i];  }

     }

     else {

           mid=(i+j)/2;

           maxmin(i, mid);

           max1=max;

           min1=min;

           maxmin(mid+1, j);

           if(max<max1)

                max=max1;

           if(min>min1)

                min=min1;  }

}

void main() {

     int i, num;

     clrscr();

     printf("\n\t\t\t   Maximum & Minimum \n\n");

     printf("\nMasukkan banyak angka: ");

     scanf("%d",&num);

     printf("\nMasukkan angkanya: \n");

     for(i=0;i<num;i++) {

           scanf("%d",&a[i]); }

     max=a[0];

     min=a[0];

     maxmin(0,num-1);

     printf("\nMaximum angka: %d\n", max);

     printf("Minimum angka: %d\n", min);

     getch();

}

Output dari program di atas adalah sebagai berikut:

Disini saya memasukkan sebanyak 7 data, dengan rincian: 12, 34, 56, 78, 90, 23, dan 89. Dan dapat kita lihat hasil dari programnya, program mendapatkan nilai maximum: 90 dan nilai minimum: 12

Logika dari coding program di atas adalah sebagai berikut:

#include <conio.h>

peryataan conio.h. adalah library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat. Tanpa menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti: gotoxy(), clrscr(), clreol().

#include <stdio.h>

Dalam c++ jika kita menginginkan penggunaan input dan output, atau bisa diartikan sebagai standard library yang berfungsi untuk I/O  package maksudnya digunakan jika kita ingin pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita.

int a[100];
int max, min;

Pernyataan diatas digunakan untuk mendeklarasikan variable. Untuk int a[100] artinya variable a bertipe data integer (bilangan bulat) array dan memiliki tampungan hingga 100 karakter. Sedangkan untuk int max, min artinya variable max dan min bertipe data integer (bilangan bulat).

void maxmin(int i, int j) {

Pernyataan diatas adalah procedure untuk melakukan penghitungan dengan identitas maxmin dengan variable utamanya integer i dan integer j.

if(i==j) {... }
Pernyataan diatas adalah kondisi utama (prioritas) sebuah percabangan dalam suatu program.

else if(i==j-1) {... }
Pernyataan diatas adalah kondisi kedua (alternative) sebuah percabangan dalam suatu program, pernyataan ini akan dieksekusi jika kondisi dalam pernyataan utama tidak terpenuhi.

else {... }

Sedangkan pernyataan diatas adalah kondisi terakhir sebuah percabangan dalam suatu program, pernyataan ini akan dieksekusi jika kondisi dalam pernyataan utama dan kedua tidak terpenuhi.

void main() {

Pernyataan diatas adalah main procedure (prosedur utama dalam program ini). Fungsinya sama seperti public.static.void.main(String args[]) { pada bahasa pemrograman java.

clrscr();
Pernyataan di atas digunakan untuk membersihkan layar ketika program dieksekusi.

printf("\n\t\t\t   Maximum & Minimum \n\n");

Pernyataan printf di atas digunakan untuk mencetak tulisan yang ada diantara tanda kutip “ ”, yaitu Maximum dan Minimum. Pernyataan \n digunakan agar tulisan utama yang dicetakada jedanya (enter) pada saat program dieksekusi, sedangkan pernyataan \t digunakan agar tulisan utama yang dicetak menjorok kedalam (tab) pada saat dieksekusi.

scanf("%d",&num);
Pernyataan scanf digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %d yang mengartikan data inputan akan ditampilkan dalam bentuk decimal, dan &num mengartikan data inputan akan disimpan sementara pada variable num.

for(i=0;i<num;i++) { scanf("%d",&a[i]); }

Pernyataan for di atas digunakan sebagai kondisi perulangan pada program, program akan mengeksekusi dimulai dari 0 hingga terpenuhi kondisi i<num , dan variable i akan terus bertambah 1 terpenuhi kondisi i<num. Hasil dari eksekusi perulangan di atass akan tersimpan kedalam baris pernyataan scanf(“%d”,&a[ i ]).

getch();

berguna unutk membaca sebuah karakter, bisa juga membaca tombol, getch() tidak akan menampilkan karakter dari tombol yang ditekan. Sebuah getch() bisa pula digunakan untuk menunggu sembarang tombol ditekan. Pada keadaan seperti ini, hasil dari fungsi ini tidak perlu diletakkan ke variable, atau dipascal dapat diartikan sebagai readln

Disini saya membuat programnya menggunakan TurboC++, untuk melihat hasil dari program yang kita buat terlebih dahulu kita harus menyimpan (save as) dengan format .c atau .cpp, jika telah kita simpan selanjutnya adalah mengkompile dengan langkah: Project > Compile atau bisa menekan Alt+F9, dan untuk melihat outputnya: Debug > Run atau bisa menekan Ctrl+F9.

Sekian yang dapat saya bagian mengenai Algoritma Divide and Conquer dan contoh programnya. Semoga bermanfaat bagi yang membacanya. Akhir kata, terima kasih dan ...

Wassalamu'alaikum warahmatullahi wabarakatuh