使用C++編寫，找出前三個項為等差數列，後三個項為等比數列的四元組數量

在本文中，我們將描述找出四元數的所有可能方法，其中前 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.中。其中所有四元組都應該是確定的。這是一個例子-

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.

尋找解決方案的方法

現在，我們將描述兩個不同的尋找解決方案的方法-

暴力方法

這是一個簡單的方法使用四個巢狀循環來解決這個問題，然後檢查前三個元素是否在A.P 中。如果是，則檢查後 3 個元素是否在 G.P 中。如果是，則將計數變數加 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)。

結論

在本文中，我們解決了尋找四元數的問題，其中前三項在AP 中，後三項在GP 中，我們討論了使用Bruteforce[ O( n4) ] 和Efficient 方法[ O(n2) ] 解決此問題的兩種方法.

#我們使用C 解決了這個問題，這也可以用其他各種語言解決這個問題，例如java、python 、C 或任何其他程式語言。

以上是使用C++編寫，找出前三個項為等差數列，後三個項為等比數列的四元組數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！