使用 C++ 從陣列中移除一個數字使其成為等比數列

給定一個元素陣列，我們需要在移除陣列中的任何一個元素後判斷陣列中的元素是否構成等比數列 (GP)。我們可以窮舉所有可能性，並透過觀察來確定第一個元素是假的，第二個元素是假的，或者這兩個元素將給出陣列的公比。

找到公比後，我們可以遍歷陣列以檢視所有元素是否遵循該規則。兩個基本條件是檢查第一個和第二個元素是否為假。

讓我們來看一些輸入/輸出場景，以便更好地理解該方法：

假設給定問題的輸入已經構成等比數列，因此無需從陣列中移除任何元素：

Input: {1, 2, 4, 8, 16}
Result: Already in GP

假設給定問題的輸入不構成等比數列，則可以透過兩種方式獲得輸出；如果移除任何元素都不能得到等比數列，則輸出列印為“不可能”：

Input: {1, 2, 3, 4, 5, 6}
Result: Not Possible

假設給定問題的輸入不構成等比數列，則可以透過兩種方式獲得輸出；如果移除一個元素可以得到等比數列，則輸出列印要移除的元素：

Input: {1, 4, 5, 16, 64, 256}
Result: Remove 5

示例

假設我們有一個數組，例如 [1,3,6,9,27,81]，如果我們從中移除元素 6，則該陣列將構成等比數列。

下面是一個程式，演示了在 C++ 中實現相同方法：

#include <iostream>
#include <vector>
using namespace std;
#define DOUBLE_COMPARE_LIMIT 1e-6
bool isEqual(double a, double b) {
   return (abs(a - b) < DOUBLE_COMPARE_LIMIT);
}
bool isGP(vector<double> arr, int index) {
   double previous = -1;
   double ratio = -1;
   for (int i = 0; i < arr.size(); i++) {
      if (i != index) {
         if (previous != -1) {
            if (ratio == -1) {
               ratio = arr[i] / previous;
            }
            else if (!isEqual(ratio, arr[i] / previous)) {
               return false;
            }
         }
         previous = arr[i];
      }
   }
   return true;
}
int solve(vector<double> arr) {
   if(isGP(arr, -1))
      return -2;

   if (isGP(arr, 0))
      return 0;
   
   if (isGP(arr, 1))
      return 1;
   double ratio = arr[1]/arr[0];
   for (int i = 2; i < arr.size(); i++) {
      if (!isEqual(ratio, arr[i]/arr[i-1])){
         return (isGP(arr, i))? i : -1;
      }
   }
   return -1;
}
int main() {
   vector<double> arr = {1,3,6,9,27,81};
   int index = solve(arr);
   if (index == -1) {
      cout << "Not possible";
   }
   else if(index == -2) {
      cout << "Already in GP";
   }
   else {
      cout << "Remove " << arr[index];
   }
   return 0;
}

輸出

Remove 6

陣列中元素的公比變為 3，起始元素為 1。因此陣列變為 [1, 3, 9, 27, 81]

結論

上述演算法執行完美。這是一個純粹的蠻力實現問題。我們使用一個函式來比較浮點值，因為可能會發生溢位。我們使用浮點數是因為公比可能是分數。DOUBLE_COMPARE_LIMIT 將比較浮點值到某個小數位，因為我們可能會有一個很長的結果或無窮小數。自己編寫程式碼一次，以更好地理解這個問題。

更新於：2022年8月10日

瀏覽量：111

開啟您的職業生涯

透過完成課程獲得認證

開始學習
廣告