在本文中，我们将描述查找四元数的所有可能方法，其中前 3 项采用 A.P.，后 3 项采用 G.P.。首先，我们将解释算术级数（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]在A.P.中，而arr[d]、arr[c]和arr[b]在G.P.中。其中所有四元组都应该是确定的。这是例子 –
立即学习“C++免费学习笔记（深入）”；
Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }Output : 2Explanation: 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 : 2Explanation: 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.
寻找解决方案的方法
现在，我们将描述两种不同的寻找解决方案的方法 –
暴力方法
这是一种简单的方法使用四个嵌套循环来解决这个问题，然后检查前三个元素是否在 A.P 中。如果是，则检查后 3 个元素是否在 G.P 中。如果是，则将计数变量加 1。但是，这种方法非常耗时，因为其时间复杂度为 O(n4)。
高效方法
在这种方法中，我们首先找到每个数组元素的计数，然后将这两个元素视为第二个和第三个数字并运行两个嵌套循环，那么第一个元素将是 arr[b] – (arr[c ] – arr[b])，第四个元素将为 arr[c] * arr[c] / arr[b]。
示例
#include using namespace std;int main (){ unordered_map 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)。
结论
在本文中，我们解决了寻找四元数的问题，其中前三项在 AP 中，后三项在 GP 中，我们讨论了使用 Bruteforce[ O(n4) ] 和 Efficient 方法 [ O(n2) ] 解决此问题的两种方法.
我们使用 C++ 解决了这个问题，这也可以用其他各种语言解决这个问题，例如 java、python、C 或任何其他编程语言。
以上就是使用C++编写，找到前三个项为等差数列，后三个项为等比数列的四元组数量的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444101.html
微信扫一扫 
支付宝扫一扫 
