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

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  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)입니다.