Dalam program C, gunakan algoritma carian binari untuk mencari nombor rasional tanpa menggunakan aritmetik titik terapung

Dalam masalah ini, kita diberi susunan nombor rasional yang disusun. Kita perlu menggunakan algoritma carian binari untuk mencari elemen tertentu bagi susunan nombor rasional ini tanpa menggunakan operasi titik terapung.

Nombor rasional ialah nombor yang dinyatakan dalam bentuk p/q, di mana p dan q adalah kedua-dua integer. Contohnya, ⅔, ⅕.

Carian binari ialah teknik carian yang mencari elemen dengan melihat di tengah tatasusunan.

Digunakan untuk mencari elemen dalam tatasusunan nombor rasional yang diisih menggunakan carian binari, di mana operasi titik terapung tidak dibenarkan. Kami akan membandingkan pengangka dan penyebut untuk mengetahui unsur mana yang lebih besar atau unsur mana yang akan dijumpai.

Contoh

Jom buat program untuk ini,

#include <stdio.h>
struct Rational {
   int p;
   int q;
};
int compare(struct Rational a, struct Rational b) {
   if (a.p * b.q == a.q * b.p)
      return 0;
   if (a.p * b.q > a.q * b.p)
      return 1;
   return -1;
}
int binarySearch(struct Rational arr[], int l, int r, struct Rational x) {
   if (r >= l) {
      int mid = l + (r - l)/2;
   if (compare(arr[mid], x) == 0) return mid;
   if (compare(arr[mid], x) > 0)
      return binarySearch(arr, l, mid-1, x);
   return binarySearch(arr, mid+1, r, x);
   }
   return -1;
}
int main() {
   struct Rational arr[] = {{1, 4}, {2, 3}, {3, 2}, {7, 2}};
   struct Rational x = {3, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   printf("Element found at index %d", binarySearch(arr, 0, n-1, x));
}

Output

Element found at index 2

Atas ialah kandungan terperinci Dalam program C, gunakan algoritma carian binari untuk mencari nombor rasional tanpa menggunakan aritmetik titik terapung. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!