praktikum 14.Menggunakan teknik pemrograman divide and conquer

Kumpulan Soal Praktikum Bahasa C

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.

Codingan:

#include <stdio.h> // Fungsi untuk mencari bilangan terbesar dalam array int findMax(int arr[], int start, int end) { // Basis: Jika hanya ada satu elemen dalam array, kembalikan nilai tersebut if (start == end) { return arr[start]; } // Bagi array menjadi dua bagian int mid = (start + end) / 2; // Panggil rekursif pada kedua bagian dan cari bilangan terbesar int max1 = findMax(arr, start, mid); int max2 = findMax(arr, mid + 1, end); // Bandingkan dan kembalikan bilangan terbesar di antara keduanya 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]); } // Panggil fungsi findMax untuk mencari bilangan terbesar int max = findMax(arr, 0, n - 1); printf("Bilangan terbesar dalam array adalah: %d\n", max); return 0; }

Hasil:

Output Program

Analisa Program:

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) 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.

Klik untuk melihat jawaban

Codingan:

#include <stdio.h> // Fungsi untuk menghitung perpangkatan bilangan menggunakan algoritma Divide and Conquer double power(double base, int exponent) { // Basis: Jika eksponen adalah 0, kembalikan 1 if (exponent == 0) { return 1; } // Rekursif: Hitung perpangkatan bilangan dengan eksponen yang lebih kecil double temp = power(base, exponent / 2); // Jika eksponen genap, hasil perpangkatan adalah kuadrat dari hasil rekursif if (exponent % 2 == 0) { return temp * temp; } // Jika eksponen ganjil 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); // Panggil fungsi power untuk menghitung perpangkatan double result = power(base, exponent); printf("Hasil perpangkatan: %.2lf\n", result); return 0; }

Hasil:

Output Program

Analisa Program:

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.

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.

Klik untuk melihat jawaban

Codingan:

#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) { // Basis: Jika ukuran array adalah 1 atau kurang, array sudah terurut if (size <= 1) { return; } // Menghitung ukuran array bagian kiri dan kanan int mid = size / 2; int leftSize = mid; int rightSize = size - mid; // Membuat array bagian kiri dan kanan int left[leftSize], right[rightSize]; // Menyalin elemen-elemen ke array bagian kiri dan kanan for (int i = 0; i < mid; i++) { left[i] = arr[i]; } for (int i = mid; i < size; i++) { right[i - mid] = arr[i]; } // Rekursif: Memanggil mergeSort untuk array bagian kiri dan kanan mergeSort(left, leftSize); mergeSort(right, rightSize); // Menggabungkan dua array bagian menjadi array utama 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]); } // Panggil fungsi mergeSort untuk mengurutkan array mergeSort(arr, size); printf("Array terurut: "); for (int i = 0; i < size; i++) { printf("%d ", arr[i]); } printf("\n"); return 0; }

Hasil:

Output Program

Analisa Program:

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..

Eka Kurniawan Zein

Program Studi: Teknologi Informasi

"Pengalaman adalah guru yang terbaik, hari ini harus lebih baik dari hari kemarin."

Dosen Pembimbing: Pak Totok Mulyono