Cho mảng đã sắp xếp các số nguyên dương phân biệt. Tìm tất cả bộ ba (triplet) tạo thành cấp số nhân (GP) với công bội nguyên. Mảng [1,2,6,10,18,54] → (2,6,18) và (6,18,54).
Giải pháp: cố định mỗi phần tử từ thứ 2 làm giữa, tìm phần tử nhỏ hơn và lớn hơn. Với giữa arr[j], arr[i] và arr[k] thỏa: arr[j]/arr[i] = arr[k]/arr[j] = r.
Ví dụ mã nguồn
#include <iostream>
using namespace std;
void getTriplets(int arr[], int n) {
for (int j = 1; j < n - 1; j++) {
int i = j - 1, k = j + 1;
while (i >= 0 && k <= n - 1) {
while (arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0 && arr[j] / arr[i] == arr[k] / arr[j]) {
cout << "(" << arr[i] << ", " << arr[j] << ", " << arr[k] << ")" << endl;
k++;
i--;
}
if (arr[j] % arr[i] == 0 && arr[k] % arr[j] == 0) {
if (arr[j] / arr[i] < arr[k] / arr[j])
i--;
else
k++;
} else if (arr[j] % arr[i] == 0)
k++;
else
i--;
}
}
}
int main() {
int arr[] = {1, 2, 6, 10, 18, 54};
int n = sizeof(arr) / sizeof(arr[0]);
getTriplets(arr, n);
}
Kết quả đầu ra
(2, 6, 18) (6, 18, 54)