C++ で書かれており、最初の 3 項が等差数列で最後の 3 項が等比数列である 4 倍体の数を求めます。-C++-php.cn

C++ で書かれており、最初の 3 項が等差数列で最後の 3 項が等比数列である 4 倍体の数を求めます。

王林

リリース： 2023-08-30 14:09:03

転載

1263 人が閲覧しました

C++ で書かれており、最初の 3 項が等差数列で最後の 3 項が等比数列である 4 倍体の数を求めます。

この記事では、最初の 3 項に A.P. を、最後の 3 項に G.P. を使用してクォータニオンを見つけるすべての可能な方法について説明します。まずは等差数列（A.P.）と等比数列（G.P.）の基本的な定義について説明します。

等差数列 (A.P.) - 共通偏差 (d) が同じか一定である一連の数値であり、連続する 2 つの数値の差が一定であることを意味します。例: 1,3,5,7,9 | d = 2

幾何級数 (G.P.) - これは、公比 (r) が同じである一連の数値です。 , これは、前の数値に固定の数値を乗算できることを意味します。例: 3, 6, 12, 24, .... | r = 2

この問題では、インデックス 4 倍体 (a 、 b、c、d) の数を決定する必要があります。その結果、arr[a]、arr[b]、および arr[c] は A.P. にあり、arr[d]、arr[c]、および arr[b] は G.P. にあります。その中のすべての 4 タプルは決定的である必要があります。例は次のとおりです -

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.

ログイン後にコピー

解決策を見つける方法

次に、解決策を見つける 2 つの異なる方法について説明します-

ブルートフォースメソッド

こここれは、4 つのネストされたループを使用してこの問題を解決し、最初の 3 つの要素が A.P. にあるかどうかを確認する簡単な方法です。「はい」の場合、最後の 3 つの要素が GP にあるかどうかを確認します。その場合は、count 変数に 1 を加えます。ただし、この方法の 時間計算量は O(n4) であるため、非常に時間がかかります。

効率的な方法

< p>この方法では、最初に各配列要素の数を見つけ、次にこれら 2 つの要素を 2 番目と 3 番目の数値とみなし、両方のネストされたループを実行します。その後、最初の要素は arr になります。 [b] – (arr[c] – arr[b])、4 番目の要素は 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

ログイン後にコピー

上記のコードの説明

このコードでは、組み合わせ論を使用して、2 つのネストされた要素を使用して 2 番目と 3 番目の要素を実行します。をループし、arr[a] – (arr[c] – arr[b]) を使用して最初の要素を検索し、4 番目の要素 arr[c] * arr[c] / arr[b] を検索します。 。したがって、2 番目と 3 番目の要素を固定しておくと、A と B によってインデックス付けされた四元数の数は、最初の数値 * 4 番目の数値の数になります。上記のコードの 時間計算量 は O(n2) です。