使用 C++ 找出前三项在 AP 中，后三项在 GP 中的四元组数
在这篇文章中，我们将描述寻找前3项在AP中，后3项在GP中的四元组个数的所有可能方法首先，我们将解释等差数列(AP)和等比数列的基本定义(GP)。
算术级数(AP)-它是一个数字序列，其中的公差(d)相同或恒定，这意味着两个连续数字的差异是恒定的。例如：1,3,5,7,9|d=2
GeometricProgression(GP)-它是一个数字序列，其中的公比(r)相同，这意味着我们可以通过将前一个数字与固定数字相乘来找到每一项。例如：3,6,12,24,....|r=2
在这个问题中，我们需要确定quadruples(a,b,c,d)N个整数的数组arr[]有多少个索引。因此，arr[a]、arr[b]和arr[c]在AP中，而arr[d]、arr[c]和arr[b]在GP中，其中所有四元组都应该是确定的。所以这是例子-
Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.
Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions.寻找解决方案的方法
现在，我们将描述两种不同的方法来找到解决方案-
蛮力方法
解决这个问题的一个简单的方法是使用四个嵌套循环，然后检查前三个元素是否在AP中，如果是，则检查后3个元素是否在G.P。如果是，则将count变量增加1。但是，这种方法很耗时，因为它的时间复杂度为O(n4)。
有效的方法
在这种方法中，我们首先找到每个数组元素的计数，然后将两个元素视为第二个和第三个数字并运行两个嵌套循环，那么第一个元素将是arr[b]–(arr[c]–arr[b])并且第四个元素将是arr[c]*arr[c]/arr[b]。
示例
#include <bits/stdc++.h>
using namespace std;
int main (){
unordered_map < int, int >map;
int arr[] = { 2, 6, 1, 4, 2 };
int size = sizeof (arr) / sizeof (arr[0]);
//处理每个元素并增加计数
for (int a = 0; a < size; a++)
map[arr[a]]++;
int count = 0;
// Running two nested loops for second & third element
for (int b = 0; b < size; b++){
for (int c = 0; c < size; c++){
if (b == c)
continue;
//减少计数
map[arr[b]]--;
map[arr[c]]--;
//使用共同差异找到第一个元素
int first = arr[b] - (arr[c] - arr[b]);
//使用GP查找第四个元素
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0){
//如果不相等则增加计数
if (arr[b] != arr[c])
count += map[first] * map[fourth];
else
count += map[first] * (map[fourth] - 1);
}
map[arr[b]]++;
map[arr[c]]++;
}
}
cout <<"四元组数： " << count;
return 0;
}输出结果四元组数： 2
以上代码说明
在此代码中，我们使用组合数学，并为第二个和第三个元素使用两个嵌套循环，并使用arr[a]–(arr[c]–arr[b])查找第一个元素和使用arr[c]*arr[c]/arr[b]。因此，通过保持第二个和第三个元素固定，A和B索引的四元组的数量是第一个数字*第四个数字的计数。这里上面代码的时间复杂度是O(n2)。
结论
在本文中，我们解决了前三项在AP中，后三项在GP中的四元组数的问题，我们讨论了使用Bruteforce[O(n4)]和Efficient两种方法来解决这个问题接近[O(n2)]。
我们使用C++解决了这个问题，这可以用其他各种语言（如java、python、C或任何其他编程语言）来解决这个问题。