C++로 작성하여 처음 세 항이 등차수열이고 마지막 세 항이 등비수열인 사중항의 수를 구합니다.-C++-php.cn

C++로 작성하여 처음 세 항이 등차수열이고 마지막 세 항이 등비수열인 사중항의 수를 구합니다.

王林

풀어 주다： 2023-08-30 14:09:03

앞으로

1241명이 탐색했습니다.

C++로 작성하여 처음 세 항이 등차수열이고 마지막 세 항이 등비수열인 사중항의 수를 구합니다.

이 기사에서는 처음 3개의 항이 A.P.이고 마지막 3개의 항이 G.P.인 쿼터니언을 찾는 가능한 모든 방법을 설명합니다. 먼저, 산술수열(A.P.)과 기하수열(G.P.)의 기본 정의를 설명하겠습니다.

산술 진행(A.P.) - 공차(d)가 동일하거나 일정한 수열입니다. 즉, 연속된 두 수의 차이가 일정하다는 의미입니다. 예: 1,3,5,7,9 | d = 2

Geometric Progression(G.P.) - 이것은 공통 비율(r)이 동일한 일련의 숫자입니다. 즉, 이전 값을 곱할 수 있습니다. 고정된 숫자로 번호를 매깁니다. 예: 3, 6, 12, 24, .... | r = 2

이 문제에서는 N 정수의 배열 arr[]에 몇 개의 인덱스 쿼드러플(a, b, c)이 있는지 확인해야 합니다. , 디). 결과적으로 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.

로그인 후 복사

해를 찾는 방법

이제 해를 찾는 두 가지 다른 방법을 설명하겠습니다. -

무차별 대입 방법

이것은 네 개의 중첩 루프를 사용하여 해결하는 간단한 방법입니다. 그런 다음 이 질문은 다음을 확인합니다. 처음 세 요소는 A.P에 있습니다. 그렇다면 마지막 3개 요소가 G.P.에 있는지 확인하세요. 그렇다면 count 변수에 1을 추가하십시오. 그러나 이 방법은 시간 복잡도가 O(n4)이므로 시간이 많이 걸립니다.

효율적인 방법

< p>이 방법에서는 먼저 각 배열 요소의 개수를 찾은 다음 이 두 요소를 두 번째와 세 번째 숫자로 간주하고 두 개의 중첩 루프를 실행한 다음 첫 번째 요소는 arr[b] – (arr[c ] – arr[b]) 네 번째 요소는 arr[c] * arr[c] / arr[b]입니다.

Example

#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;
}

로그인 후 복사

Output

Number of quadruples: 2

로그인 후 복사

위 코드 설명

이 코드에서는 두 번째와 세 번째 요소에 대해 두 개의 중첩 루프를 사용하고 arr[a] – (arr[c]를 사용하여 조합론을 사용합니다. 첫 번째 요소인 arr[b])와 네 번째 요소인 arr[c] * arr[c] / arr[b]를 찾습니다. 따라서 두 번째와 세 번째 요소를 고정시켜 A와 B에 의해 인덱싱된 쿼터니언의 수는 첫 번째 숫자 * 네 번째 숫자의 개수가 됩니다. 위 코드의 시간 복잡도는 O(n2)입니다.