Trong bài viết này, chúng tôi sẽ mô tả mọi cách tiếp cận có thể để tìm số phần tư trong đó 3 số hạng đầu tiên trong A.P. và 3 số cuối cùng trong G.P. Đầu tiên, chúng tôi sẽ giải thích định nghĩa cơ bản của cấp số học (A.P.) Và cấp số nhân hình học (G.P.).
Cấp số học (A.P.) - Là dãy số trong đó hiệu chung (d) giống nhau hoặc không đổi nghĩa là hiệu của hai số liên tiếp là không đổi. Ví dụ:1,3,5,7,9 | d =2
Tiến trình hình học (G.P.) - Là một dãy số trong đó các tỉ số chung (r) giống nhau, nghĩa là ta có thể tìm từng số hạng bằng cách nhân số liền trước với số cố định. Ví dụ:3, 6, 12, 24, .... | r =2
Trong bài toán này, chúng ta cần xác định xem có bao nhiêu phần tư chỉ số (a, b, c, d) từ một mảng arr [] gồm N số nguyên. Kết quả là arr [a], arr [b] và arr [c] thuộc A.P. và arr [d], arr [c] và arr [b] thuộc G.P. trong đó tất cả các phần tư phải được xác định. Đây là ví dụ -
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. Phương pháp tiếp cận để tìm giải pháp
Bây giờ, chúng tôi sẽ mô tả hai cách tiếp cận khác nhau để tìm ra giải pháp -
Phương pháp tiếp cận vũ phu
Đó là một cách tiếp cận đơn giản để giải quyết vấn đề này bằng cách sử dụng bốn vòng lặp lồng nhau, sau đó kiểm tra xem ba phần tử đầu tiên có trong A.P hay không, sau đó kiểm tra xem 3 phần tử cuối cùng có trong G.P hay không. Nếu có, sau đó tăng biến đếm lên 1. Tuy nhiên, cách tiếp cận này tốn nhiều thời gian vì độ phức tạp về thời gian của nó là O (n4) .
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, trước tiên chúng ta tìm số lượng của mọi phần tử mảng, sau đó coi cả hai phần tử là số thứ hai và thứ ba và chạy hai vòng lặp lồng nhau, khi đó phần tử đầu tiên sẽ là arr [b] - (arr [c] - arr [b]) và phần tử thứ tư sẽ là arr [c] * arr [c] / arr [b] .
Ví dụ
#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;
} Đầu ra
Number of quadruples: 2
Giải thích về Quy tắc trên
Trong mã này, chúng tôi đang sử dụng Phép tổ hợp và sử dụng hai vòng lặp lồng nhau cho phần tử thứ hai và thứ ba và tìm phần tử đầu tiên bằng arr [a] - (arr [c] - arr [b]) và phần tử thứ tư với arr [c] * arr [c] / arr [b] . Do đó, số của các phần tư theo chỉ số A và B là số đếm của số đầu tiên * số thứ tư, bằng cách giữ cố định phần tử thứ hai và thứ ba. Đây là độ phức tạp về thời gian của mã trên là O (n2) .
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề tìm Số phần tư trong đó ba số hạng đầu tiên trong AP và ba số hạng cuối cùng trong GP và chúng tôi đã thảo luận về hai cách tiếp cận để giải quyết vấn đề này bằng cách sử dụng Bruteforce [O (n4)] và Efficient cách tiếp cận [O (n2)].
Chúng tôi đã giải quyết vấn đề này bằng cách sử dụng C ++ và điều này có thể giải quyết vấn đề này bằng nhiều ngôn ngữ khác nhau như java, python, C hoặc bất kỳ ngôn ngữ lập trình nào khác.