Program C/C++ ditulis menggunakan algoritma isihan gabungan untuk mengira logaritma terbalik dalam tatasusunan?

Kiraan pembalikan yang berlaku semasa mengisih tatasusunan yang diberikan dipanggil kiraan pembalikan. Masalah songsang ialah masalah klasik yang boleh diselesaikan menggunakan algoritma isihan gabungan. Dalam masalah ini v kita akan mengira semua elemen di sebelah kirinya yang lebih besar daripadanya dan menambah kiraan pada output. Logik ini dilengkapkan dalam fungsi cantuman jenis cantumkan.

Untuk memahami topik ini dengan lebih baik, mari kita ambil contoh. Mari kita pertimbangkan dua sub-tatasusunan yang terlibat dalam proses penggabungan -

Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5

Penjelasan dalam susunan nombor

tatasusunan, cari songsangnya Bilangan pusingan. Jika (i A[j]) maka pasangan (i, j) dipanggil penyongsangan tatasusunan A. Kita perlu mengira semua pasangan sedemikian dalam arr

Sebagai contoh, terdapat 5 penyongsangan dalam tatasusunan

(9,6), (9,4), (9,5), (6,4), (6 ,5)

1. Bandingkan nilai unsur antara satu sama lain.

2 Jika nilai pada indeks yang lebih rendah adalah lebih tinggi, naikkan pembilang.

3. Paparkan hasilnya.

Contoh

#include <stdio.h>
int Merge(int arr[], int aux[], int low, int mid, int high) {
   int k = low, i = low, j = mid + 1;
   int inversionCount = 0;
   while (i <= mid && j <= high) {
      if (arr[i] <= arr[j]) {
         aux[k++] = arr[i++];
      } else {
         aux[k++] = arr[j++];
         inversionCount += (mid - i + 1); // NOTE
      }
   }
   while (i <= mid)
   aux[k++] = arr[i++];
   for (int i = low; i <= high; i++)
      arr[i] = aux[i];
   return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
   if (high == low) // if run size == 1
      return 0;
   int mid = (low + ((high - low) >> 1));
   int inversionCount = 0;
   inversionCount += MergeSort(arr, aux, low, mid);
   inversionCount += MergeSort(arr, aux, mid + 1, high);
   inversionCount += Merge(arr, aux, low, mid, high);
   return inversionCount;
}
int main() {
   int arr[] = { 1, 9, 6, 4, 5 };
   int N = 5;
   int aux[N];
   for (int i = 0; i < N; i++)
      aux[i] = arr[i];
   printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1));
   return 0;
}

Atas ialah kandungan terperinci Program C/C++ ditulis menggunakan algoritma isihan gabungan untuk mengira logaritma terbalik dalam tatasusunan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!