数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 查找四元组的数量，其中前三个项构成等差数列，后三个项构成等比数列
在本文中，我们将描述找到满足以下条件的四元组数量的所有可能方法：前 3 项构成等差数列，后 3 项构成等比数列。首先，我们将解释算术级数 (A.P.) 和几何级数 (G.P.) 的基本定义。
算术级数 (A.P.) - 这是一个数列，其中公差 (d) 相同或恒定，这意味着两个连续数字的差是恒定的。例如：1、3、5、7、9 | d = 2
几何级数 (G.P.) - 这是一个数列，其中公比 (r) 相同，这意味着我们可以通过将前一个数字乘以固定数字来找到每个项。例如：3、6、12、24、... | r = 2
在这个问题中，我们需要确定从 N 个整数的数组 arr[ ] 中有多少个索引四元组 (a、b、c、d)。因此，arr[a]、arr[b] 和 arr[c] 构成等差数列，而 arr[d]、arr[c] 和 arr[b] 构成等比数列，其中所有四元组都应该是确定的。以下是一个示例 -
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.解决方法
现在，我们将描述两种不同的方法来找到解决方案 -
暴力方法
这是一种使用四个嵌套循环解决此问题的简单方法，然后检查前三个元素是否构成等差数列。如果是，则检查后三个元素是否构成等比数列。如果是，则将计数变量加 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]);
// Processing every elent and increasing the count
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;
// Decreasing the count
map[arr[b]]--;
map[arr[c]]--;
// Finding the first element using common difference
int first = arr[b] - (arr[c] - arr[b]);
// Finding the fourth element using GP
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0){
// Increment count if not equal
if (arr[b] != arr[c])
count += map[first] * map[fourth];
else
count += map[first] * (map[fourth] - 1);
}
map[arr[b]]++;
map[arr[c]]++;
}
}
cout <<"Number of quadruples: " << count;
return 0;
}输出
Number of quadruples: 2
以上代码的解释
在此代码中，我们使用组合数学，并使用两个嵌套循环来获取第二个和第三个元素，并使用arr[a] – (arr[c] – arr[b])找到第一个元素，并使用arr[c] * arr[c] / arr[b]找到第四个元素。因此，通过 A 和 B 索引得到的四元组的数量是第一个数字和第四个数字的计数，在保持第二个和第三个元素固定的情况下。此处，上述代码的时间复杂度为O(n2)。
结论
在本文中，我们解决了查找四元组数量的问题，其中前三个项构成等差数列，后三个项构成等比数列，并且我们讨论了两种使用蛮力 [O(n4)] 和高效方法 [O(n2)] 解决此问题的方法。
我们使用 C++ 解决了此问题，并且可以使用其他各种语言（如 Java、Python、C 或任何其他编程语言）来解决此问题。
90 次浏览
