Konsep Dasar divide and conque

 Konsep Dasar divide and conque dalam bahasa C

Divide and Conquer (Pecah dan Kuasai) adalah paradigma desain algoritma yang melibatkan pemecahan suatu masalah besar menjadi submasalah yang lebih kecil, menyelesaikan submasalah tersebut secara rekursif, dan kemudian menggabungkan solusi submasalah untuk mendapatkan solusi akhir masalah asli. Konsep ini sangat umum dalam desain algoritma dan dapat digunakan untuk memecahkan berbagai jenis masalah.

Berikut adalah penjelasan konsep dasar Divide and Conquer:

1. Divide (Pecah)

• Tahap pertama adalah memecah masalah besar menjadi submasalah yang lebih kecil. Pemecahan ini dilakukan hingga masalah mencapai ukuran yang cukup kecil untuk dipecahkan secara langsung.

2. Conquer (Kuasai)

• Tahap ini melibatkan penyelesaian submasalah yang dihasilkan dari tahap pemecahan. Submasalah dipecahkan secara rekursif. Jika ukuran submasalah sudah cukup kecil, solusi dapat dihitung langsung.

3. Combine (Gabung)

• Tahap terakhir adalah menggabungkan solusi dari submasalah untuk membentuk solusi akhir dari masalah asli. Proses ini mengintegrasikan solusi dari setiap submasalah menjadi solusi keseluruhan.

kita akan mengimplementasikan divide and conque kedalam kode bahasa C

1.

#include <stdio.h>

int findMax(int arr[], int left, int right) {
    if (left == right) {
        return arr[left];
    } else {
        int mid = (left + right) / 2;
        int maxLeft = findMax(arr, left, mid);
        int maxRight = findMax(arr, mid + 1, right);

        // Membandingkan hasil dari kedua subarray
        return (maxLeft > maxRight) ? maxLeft : maxRight;
    }
}

int main() {
    int n;

    // Meminta pengguna untuk memasukkan jumlah elemen dalam array
    printf("Masukkan jumlah elemen dalam array: ");
    scanf("%d", &n);

    // Meminta pengguna untuk memasukkan elemen array
    int arr[n];
    printf("Masukkan elemen array:\n");
    for (int i = 0; i < n; i++) {
        printf("Elemen %d: ", i + 1);
        scanf("%d", &arr[i]);
    }

    // Menggunakan algoritma Divide and Conquer untuk mencari bilangan terbesar
    int maxNumber = findMax(arr, 0, n - 1);

    // Menampilkan bilangan terbesar kepada pengguna
    printf("Bilangan terbesar dalam array: %d\n", maxNumber);

    return 0;
}

output :

Penjelasan singkat:

1. Fungsi findMax:

   • Fungsi ini adalah implementasi algoritma Divide and Conquer untuk mencari bilangan terbesar dalam array.
   • Jika array hanya memiliki satu elemen, kembalikan elemen tersebut.
   • Jika array memiliki lebih dari satu elemen, pecah array menjadi dua bagian, cari bilangan terbesar di masing-masing bagian, dan bandingkan hasilnya.

2. Fungsi main:

   • Meminta pengguna untuk memasukkan jumlah dan elemen array.
   • Memanggil fungsi findMax untuk mencari bilangan terbesar.
   • Menampilkan bilangan terbesar kepada pengguna.

Program ini memanfaatkan paradigma Divide and Conquer untuk menemukan bilangan terbesar dalam array. Semoga membantu!

2.

#include <stdio.h>

double pangkat(double dasar, int eksponen) {
    if (eksponen == 0) {
        return 1;
    } else {
        // Memecah masalah menjadi submasalah dengan eksponen setengah
        double hasilSetengah = pangkat(dasar, eksponen / 2);

        // Menggabungkan solusi dari submasalah untuk mendapatkan hasil akhir
        if (eksponen % 2 == 0) {
            return hasilSetengah * hasilSetengah;
        } else {
            return dasar * hasilSetengah * hasilSetengah;
        }
    }
}

int main() {
    double bilanganDasar;
    int eksponen;

    // Meminta pengguna untuk memasukkan bilangan dasar dan eksponen
    printf("Masukkan bilangan dasar: ");
    scanf("%lf", &bilanganDasar);
    printf("Masukkan eksponen: ");
    scanf("%d", &eksponen);

    // Menggunakan algoritma Divide and Conquer untuk menghitung perpangkatan
    double hasilPangkat = pangkat(bilanganDasar, eksponen);

    // Menampilkan hasil perpangkatan kepada pengguna
    printf("Hasil perpangkatan: %.2lf\n", hasilPangkat);

    return 0;
}

output :

Penjelasan singkat:

1. Fungsi pangkat:

   • Fungsi ini adalah implementasi algoritma Divide and Conquer untuk menghitung perpangkatan.
   • Jika eksponen adalah 0, maka hasilnya adalah 1.
   • Jika eksponen ganjil, pemecahan masalah dilakukan dengan memanggil rekursif untuk eksponen setengah.
   • Jika eksponen genap, pemecahan masalah juga dilakukan dengan memanggil rekursif untuk eksponen setengah, tetapi hasilnya dikalikan dua kali.

2. Fungsi main:

   • Meminta pengguna untuk memasukkan bilangan dasar dan eksponen.
   • Memanggil fungsi pangkat untuk menghitung perpangkatan.
   • Menampilkan hasil perpangkatan kepada pengguna.

Program ini menggunakan pendekatan Divide and Conquer untuk menghitung perpangkatan dengan efisien. Semoga membantu!

3.

#include <stdio.h>
#include <stdlib.h>

// Fungsi untuk menggabungkan dua subarray yang terurut
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    // Buat dua subarray sementara
    int L[n1], R[n2];

    // Salin data ke subarray sementara L[] dan R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Gabungkan subarray kembali ke array utama
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Salin sisa elemen jika ada
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Fungsi utama merge sort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Temukan titik tengah array
        int m = l + (r - l) / 2;

        // Panggil rekursif mergeSort untuk kedua subarray
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Gabungkan subarray
        merge(arr, l, m, r);
    }
}

int main() {
    int n;

    // Meminta pengguna untuk memasukkan jumlah elemen dalam array
    printf("Masukkan jumlah elemen dalam array: ");
    scanf("%d", &n);

    // Meminta pengguna untuk memasukkan elemen array
    int arr[n];
    printf("Masukkan elemen array:\n");
    for (int i = 0; i < n; i++) {
        printf("Elemen %d: ", i + 1);
        scanf("%d", &arr[i]);
    }

    // Menggunakan algoritma Divide and Conquer (merge sort) untuk mengurutkan array
    mergeSort(arr, 0, n - 1);

    // Menampilkan array yang terurut kepada pengguna
    printf("Array yang terurut:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

output :

Program ini meminta pengguna untuk memasukkan jumlah dan elemen array, kemudian menggunakan algoritma Divide and Conquer (merge sort) untuk mengurutkan array tersebut. Setelah diurutkan, program menampilkan array yang terurut kepada pengguna.

Program ini menggunakan algoritma Merge Sort, yang merupakan algoritma pengurutan dengan pendekatan Divide and Conquer. Berikut adalah penjelasan singkat tentang program tersebut:

1. Fungsi merge:

   • Fungsi ini digunakan untuk menggabungkan dua subarray yang terurut menjadi satu array terurut.
   • Menerima tiga parameter: array arr, indeks awal l, indeks tengah m, dan indeks akhir r.
   • Membuat dua subarray sementara L dan R untuk menyimpan data.

2. Fungsi mergeSort:

   • Fungsi ini adalah implementasi algoritma Merge Sort.
   • Menerima tiga parameter: array arr, indeks awal l, dan indeks akhir r.
   • Jika l kurang dari r, fungsi akan mencari titik tengah m dan memanggil rekursif mergeSort untuk kedua subarray (sebelum dan setelah m).
   • Selanjutnya, memanggil fungsi merge untuk menggabungkan subarray yang terurut.

3. Fungsi main:

   • Meminta pengguna untuk memasukkan jumlah dan elemen array.
   • Memanggil fungsi mergeSort untuk mengurutkan array.
   • Menampilkan array yang terurut kepada pengguna.

4. Proses Pengurutan:

   • Algoritma Merge Sort membagi array menjadi dua bagian, kemudian mengurutkan masing-masing bagian secara rekursif.
   • Setelah itu, dua bagian yang terurut digabungkan kembali secara berurutan dengan menggunakan fungsi merge.

5. Output:

   • Program menampilkan array yang terurut setelah proses pengurutan selesai.

Program ini menunjukkan penerapan algoritma Divide and Conquer untuk mengurutkan array menggunakan Merge Sort. Pendekatan ini membantu meningkatkan efisiensi algoritma pengurutan. Semoga penjelasan ini membantu memahami program tersebut.