使用 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

开启您的职业生涯

通过完成课程获得认证

开始学习
广告