Tìm số còn thiếu trong Tiến trình hình học trong C ++

Giả sử chúng ta có một mảng biểu diễn các phần tử của tiến trình hình học theo thứ tự. Thiếu một phần tử. Chúng ta phải tìm ra yếu tố còn thiếu. Vì vậy, nếu arr =[1, 3, 27, 81], đầu ra là 9, vì 9 bị thiếu.

Sử dụng tìm kiếm nhị phân, chúng ta có thể giải quyết vấn đề này. Chúng ta sẽ đi đến phần tử giữa, sau đó kiểm tra xem tỷ lệ giữa ở giữa và cạnh ở giữa có giống với tỷ lệ chung hay không. Nếu không, thì phần tử bị thiếu sẽ xuất hiện giữa các chỉ số giữa và giữa + 1. Nếu phần tử ở giữa là phần tử thứ n / 2 trong GP, thì phần tử bị thiếu nằm ở nửa bên phải, ngược lại ở nửa bên trái.

Ví dụ

#include <iostream>
#include <cmath>
using namespace std;
class Progression {
   public:
   int missingUtil(int arr[], int left, int right, int ratio) {
      if (right <= left)
         return INT_MAX;
      int mid = left + (right - left) / 2;
      if (arr[mid + 1] - arr[mid] != ratio)
         return (arr[mid] * ratio);
      if (mid > 0 && arr[mid] / arr[mid - 1] != ratio)
         return (arr[mid - 1] * ratio);
      if (arr[mid] == arr[0] * pow(ratio, mid))
         return missingUtil(arr, mid + 1, right, ratio);
         return missingUtil(arr, left, mid - 1, ratio);
   }
   int missingElement(int arr[], int n) {
      int ratio = pow(arr[n-1]/arr[0], 1.0/n);
         return missingUtil(arr, 0, n - 1, ratio);
   }
};
int main() {
   Progression pg;
   int arr[] = {1, 3, 27, 81};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "The missing element is: " << pg.missingElement(arr, n);
}

Đầu ra

The missing element is: 9