資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
