Contoh Algoritma divide dan conquer

• Skema Umum Algoritma Divide and Conquer

procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n .... n0 then {ukuran masalah sudah cukup kecil }
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi r upa-masalah, masing-masing berukuran n/k
for masing-masing dari r upa-masalah do
DIVIDE_and_CONQUER(n/k)
endfor
COMBINE solusi dari r upa-masalah menjadi solusi masalah semula }
endif


• Jika pembagian selalu menghasilkan dua upa-masalah yang berukuran sama:

procedure DIVIDE_and_CONQUER(input n : integer)
{ Menyelesaikan masalah dengan algoritma D-and-C.
Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer

Algoritma
if n ... n0 then {ukuran masalah sudah cukup kecil }
SOLVE upa-masalah yang berukuran n ini
else
Bagi menjadi 2 upa-masalah, masing-masing berukuran n/2
DIVIDE_and_CONQUER(upa-masalah pertama yang berukuran n/2)
DIVIDE_and_CONQUER(upa-masalah kedua yang berukuran n/2)
COMBINE solusi dari 2 upa-masalah
endif

Persoalan Minimum dan Maksimum (MinMaks)

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

Penyelesaian dengan Algoritma Brute Force

procedure MinMaks1(input A : TabelInt, n : integer,
output min, maks : integer)
{ Mencari nilai minimum dan maksimum di dalam tabel A yang berukuran n elemen, secara brute force.
Masukan: tabel A yang sudah terdefinisi elemen-elemennya
Keluaran: nilai maksimum dan nilai minimum tabel
}
Deklarasi
i : integer

Algoritma:
min... A1 { inisialisasi nilai minimum}
maks...A1 { inisialisasi nilai maksimum }
for i...2 to n do

if Ai <> maks then
maks...Ai
endif

endfor

sumber :Bahan Kuliah ke-5 IF2251 Strategi Algoritmik
Algoritma Divide and Conquer Departemen Teknik Informatika
Institut Teknologi Bandung
2004