PRAKTIKUM 14: Menggunakan teknik pemrograman divide and conquer

 IV. Alat/Bahan

• Komputer dengan lingkungan pemrograman C (misalnya, GCC atau Dev-C++).

• Editor teks untuk menulis kode C. Code::Blocks

• Compiler atau interpreter untuk menjalankan kode C.

• Buku atau materi referensi tentang pemrograman dalam bahasa C.

• .Modul 14 Menggunakan teknik pemrograman divide and conquer.

V. Prosedur Praktikum

Praktekan Latihan Berikut:

Soal Praktek 1: Pencarian Bilangan Terbesar

1. Buatlah program dalam bahasa C yang menggunakan algoritma Divide and Conquer untuk

mencari bilangan terbesar dalam sebuah array. Program tersebut harus memiliki fitur sebagai

berikut:

✓ Menerima input array bilangan dari pengguna.

✓ Menggunakan algoritma Divide and Conquer untuk mencari bilangan terbesar dalam array.

✓ Menampilkan bilangan terbesar kepada pengguna.

Soal Praktek 2: Perpangkatan dengan Rekursi

2. Buatlah program dalam bahasa C yang menggunakan algoritma Divide and Conquer untuk

menghitung perpangkatan suatu bilangan. Program tersebut harus memiliki fitur sebagai

berikut:

✓ Menerima input bilangan dasar dan eksponen dari pengguna.

✓ Menggunakan algoritma Divide and Conquer untuk menghitung perpangkatan bilangan

dasar dengan eksponen tertentu.

✓ Menampilkan hasil perpangkatan kepada pengguna.

Soal Praktek 3: Pengurutan Data dengan Merge Sort

3. Buatlah program dalam bahasa C yang menggunakan algoritma Divide and Conquer untuk

mengurutkan data dalam sebuah array menggunakan merge sort. Program tersebut harus

memiliki fitur sebagai berikut:

✓ Menerima input array bilangan dari pengguna.

✓ Menggunakan algoritma Divide and Conquer dengan merge sort untuk mengurutkan array.

✓ Menampilkan array yang terurut kepada pengguna.

1. Jawaban Soal Praktek 1: Pencarian Bilangan Terbesar

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

int findMax(int arr[], int start, int end) {

    if (start == end) {

        return arr[start];

    }

    int mid = (start + end) / 2;

    int max1 = findMax(arr, start, mid);

    int max2 = findMax(arr, mid + 1, end);

    return (max1 > max2) ? max1 : max2;

}

int main() {

    int n;

    printf("Masukkan jumlah elemen dalam array: ");

    scanf("%d", &n);

    int arr[n];

    printf("Masukkan elemen-elemen array: ");

    for (int i = 0; i < n; i++) {

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

    }

    int max = findMax(arr, 0, n - 1);

    printf("Bilangan terbesar dalam array adalah: %d\n", max);

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas menerima input array bilangan dari pengguna

dan menggunakan algoritma Divide and Conquer untuk mencari

bilangan terbesar dalam array tersebut. Fungsi findMax

dipanggil secara rekursif untuk membagi array menjadi dua

bagian, mencari bilangan terbesar pada masing-masing bagian,

dan membandingkan keduanya untuk mengembalikan bilangan

terbesar secara keseluruhan. Hasil bilangan terbesar kemudian

ditampilkan kepada pengguna.

Program ini memanfaatkan teknik Divide and Conquer dengan

membagi masalah menjadi submasalah yang lebih kecil, mencari

solusi pada setiap submasalah, dan menggabungkan solusi-solusi

tersebut untuk mendapatkan solusi akhir.

2. Jawaban Soal Praktek 2: Perpangkatan dengan Rekursi

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

// Fungsi untuk menghitung perpangkatan bilangan menggunakan algoritma Divide and Conquer

double power(double base, int exponent) {

    if (exponent == 0) {

        return 1;

    }

    double temp = power(base, exponent / 2);

    if (exponent % 2 == 0) {

        return temp * temp;

    } else {

        if (exponent > 0) {

            return base * temp * temp;

        } else {

            return (temp * temp) / base;

        }

    }

}

int main() {

    double base;

    int exponent;

    printf("Masukkan bilangan dasar: ");

    scanf("%lf", &base);

    printf("Masukkan eksponen: ");

    scanf("%d", &exponent);

    double result = power(base, exponent);

    printf("Hasil perpangkatan: %.2lf\n", result);

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas menerima input bilangan dasar dan eksponen

dari pengguna dan menggunakan algoritma Divide and Conquer

untuk menghitung perpangkatan bilangan dasar dengan eksponen

tertentu. Fungsi power dipanggil secara rekursif untuk membagi

masalah menjadi submasalah yang lebih kecil, yaitu menghitung

perpangkatan bilangan dasar dengan eksponen yang lebih kecil,

dan menggabungkan solusi-solusi tersebut untuk mendapatkan

hasil perpangkatan akhir.

Program ini memanfaatkan teknik Divide and Conquer dengan

membagi masalah perpangkatan menjadi submasalah yang lebih

kecil, menghitung perpangkatan pada setiap submasalah, dan

menggabungkan hasilnya untuk mendapatkan hasil perpangkatan

akhir.

3. Jawaban Soal Praktek 3: Pengurutan Data dengan Merge Sort

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

// Fungsi untuk menggabungkan dua array yang terurut menjadi satu array terurut

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {

    int i = 0, j = 0, k = 0;

    // Membandingkan dan menggabungkan elemen-elemen dari dua array ke array utama secara berurutan

    while (i < leftSize && j < rightSize) {

        if (left[i] <= right[j]) {

            arr[k++] = left[i++];

        } else {

            arr[k++] = right[j++];

        }

    }

    // Menyalin elemen-elemen yang tersisa dari array kiri ke array utama

    while (i < leftSize) {

        arr[k++] = left[i++];

    }

    // Menyalin elemen-elemen yang tersisa dari array kanan ke array utama

    while (j < rightSize) {

        arr[k++] = right[j++];

    }

}

// Fungsi untuk melakukan merge sort pada array menggunakan algoritma Divide and Conquer

void mergeSort(int arr[], int size) {

    if (size <= 1) {

        return;

    }

    int mid = size / 2;

    int leftSize = mid;

    int rightSize = size - mid;

    int left[leftSize], right[rightSize];

    for (int i = 0; i < mid; i++) {

        left[i] = arr[i];

    }

    for (int i = mid; i < size; i++) {

        right[i - mid] = arr[i];

    }

    mergeSort(left, leftSize);

    mergeSort(right, rightSize);

    merge(arr, left, leftSize, right, rightSize);

}

int main() {

    int size;

    printf("Masukkan ukuran array: ");

    scanf("%d", &size);

    int arr[size];

    printf("Masukkan elemen array:\n");

    for (int i = 0; i < size; i++) {

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

    }

    mergeSort(arr, size);

    printf("Array terurut: ");

    for (int i = 0; i < size; i++) {

        printf("%d ", arr[i]);

    }

    printf("\n");

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program di atas menerima input array bilangan dari pengguna dan menggunakan algoritma

Divide and Conquer dengan merge sort untuk mengurutkan array tersebut. Fungsi

mergeSort dipanggil secara rekursif untuk membagi masalah menjadi submasalah yang

lebih kecil, yaitu mengurutkan dua bagian array, dan menggabungkan hasil pengurutan

tersebut menggunakan fungsi `merge, untuk menghasilkan array terurut secara keseluruhan.

Program ini memanfaatkan teknik Divide and Conquer dengan membagi array menjadi dua

bagian secara rekursif, mengurutkan setiap bagian array secara terpisah, dan kemudian

menggabungkan dua bagian array yang terurut menjadi satu array terurut. Algoritma merge

sort memiliki kompleksitas waktu O(n log n), di mana n adalah ukuran array, sehingga dapat

mengurutkan array dengan efisien.

Setelah array diurutkan menggunakan algoritma merge sort, program akan menampilkan

array yang terurut kepada pengguna..

Soal Praktek: Populasi hewan

1. Andi adalah seorang peneliti yang sedang mempelajari populasi hewan di sebuah hutan. Dia

ingin menggunakan algoritma Divide and Conquer untuk mencari jumlah total populasi dari

semua spesies hewan dalam hutan tersebut. Setiap spesies hewan memiliki jumlah individu

yang berbeda-beda. Andi memiliki data populasi hewan dalam bentuk array, di mana setiap

elemen array mewakili jumlah individu dari satu spesies hewan.

• Tugas Anda adalah membuat program dalam bahasa C yang menerima input data populasi

hewan dan menggunakan algoritma Divide and Conquer untuk menghitung jumlah total

populasi dari semua spesies hewan.

• Tulislah program C beserta penjelasan untuk menyelesaikan masalah tersebut.

1. Jawaban Soal Praktek Populasi Hewan

▪ Buka Text Editor Code::Blocks,

▪ Pilih menu klik file → New→Empty File

▪ Ketikan koding di bawah ini

#include <stdio.h>

// Fungsi Divide and Conquer untuk menghitung jumlah total populasi

int hitungTotalPopulasi(int populasi[], int awal, int akhir) {

    // Base case: jika hanya terdapat satu elemen dalam array

    if (awal == akhir) {

        return populasi[awal];

    }

    // Cari titik tengah array

    int tengah = (awal + akhir) / 2;

    // Rekursi pada dua bagian array dan gabungkan hasilnya

    int jumlahKiri = hitungTotalPopulasi(populasi, awal, tengah);

    int jumlahKanan = hitungTotalPopulasi(populasi, tengah + 1, akhir);

    // Kembalikan jumlah total populasi dari kedua bagian array

    return jumlahKiri + jumlahKanan;

}

int main() {

    int n;

    printf("Masukkan jumlah spesies hewan: ");

    scanf("%d", &n);

    int populasi[n];

    printf("Masukkan populasi hewan per spesies:\n");

    for (int i = 0; i < n; i++) {

        printf("Spesies %d: ", i + 1);

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

    }

    // Hitung jumlah total populasi menggunakan algoritma Divide and Conquer

    int totalPopulasi = hitungTotalPopulasi(populasi, 0, n - 1);

    printf("Jumlah total populasi hewan: %d\n", totalPopulasi);

    return 0;

}

▪ Klik menu file Save, ketikan nama

▪ Klik Build →Build and Run atau icon

▪ berikut hasilnya

Program ini menggunakan fungsi hitungTotalPopulasi() sebagai fungsi rekursif untuk

menghitung jumlah total populasi hewan.

Fungsi hitungTotalPopulasi() menerima parameter populasi[], awal, dan akhir yang

menunjukkan range bagian array yang sedang diproses.

Pada setiap pemanggilan rekursif, array populasi dibagi menjadi dua bagian.

Ketika hanya terdapat satu elemen dalam array (base case), fungsi akan mengembalikan

jumlah populasi tersebut.

Selama rekursi, fungsi akan memanggil dirinya sendiri pada dua bagian array dan

menggabungkan hasilnya.

Di dalam fungsi main(), program akan meminta pengguna untuk memasukkan jumlah

spesies hewan dan populasi masing-masing spesies.

Kemudian, program akan memanggil fungsi hitungTotalPopulasi() dengan parameter array

populasi dan range awal dan akhir.

Hasil jumlah total populasi akan ditampilkan ke layar.

Dengan menggunakan algoritma Divide and Conquer, program ini dapat menghitung jumlah

total populasi dari semua spesies hewan yang ada di hutan dengan efisien.

VI. Analisa dan Kesimpulan

Teknik pemrograman divide and conquer merupakan pendekatan yang kuat dalam pemecahan

masalah yang kompleks.

Dengan memahami konsep dasar dan mengimplementasikannya dalam pemrograman, kita dapat

mengatasi berbagai masalah dengan lebih efisien.

Penerapan divide and conquer dalam pemecahan masalah nyata dapat memberikan solusi yang

optimal dan efektif.

Penting untuk memahami struktur masalah dan merancang langkah-langkah yang tepat dalam

memecahkan submasalah untuk mencapai solusi akhir.