C プログラムでは、浮動小数点演算を使用せずに二分探索アルゴリズムを使用して有理数を検索します。

この問題では、ソートされた有理数の配列が与えられます。浮動小数点演算を使用せずに、この有理数の配列の特定の要素を検索するには、二分探索アルゴリズムを使用する必要があります。

有理数は、p/q の形式で表される数値です。p と q は整数です。たとえば、2/3、1/5。

二分探索は、配列の中央を検索して要素を見つける検索手法です。

は、浮動小数点演算が許可されていない二分探索を使用して、ソートされた有理数の配列内の要素を検索するために使用されます。分子と分母を比較して、どちらの要素が大きいか、またはどちらの要素が大きいかを調べます。

例

これのためのプログラムを作成しましょう、

#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));
}

出力

Element found at index 2

以上がC プログラムでは、浮動小数点演算を使用せずに二分探索アルゴリズムを使用して有理数を検索します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。