Praktikum 14 (Coding Bahasa C: Pemrograman divide and conquer)

 

Praktikum 14 (Pemrograman Divide and Conquer)

A. Persoalan

1. Pencarian Bilangan Terbesar:

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.

2. Perpangkatan Dengan Rekursi: 

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.

3. Pengurutan Data Dengan Merge Sort:

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. 

B. Jawaban

1. Pencarian Bilangan Terbesar:

• Koding Bahasa C:
  
  #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:
  
  
  

2. Perpangkatan Dengan Rekursi:

• Koding Bahasa C:
  
  #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, hasil perpangkatan adalah kuadrat hasil rekursif dikalikan dengan bilangan dasar

      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:
  
  
  

3. Pengurutan Data Dengan Merge Sort:

• Koding Bahasa C:
  
  #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: