Cho bốn mảng A[], B[], C[] và D[]. Mục tiêu là tìm tất cả các bộ bốn (quadruples) các phần tử của các mảng này sao cho A[i] + B[j] + C[k] + D[l] = x. Tất cả bốn mảng có cùng số phần tử N.
Ta thực hiện bằng cách duyệt từng mảng một lần và so sánh nếu A[i] + B[j] + C[k] + D[l] == x. Nếu đúng tăng biến đếm.
Hãy hiểu qua các ví dụ.
Đầu vào
A[]={ 1,2,3 }; B[]={ 2,3,2 }; C[]={ 4,3,1 }; D[]={ 3,1,1 }; X=12
Đầu ra
Số bộ bốn: 4
Giải thích
Các bộ bốn (A[i] B[j] C[k] D[l]): (2,3,4,3), (3,2,4,3), (3,3,3,3), (3,2,4,3). Tổng số bộ bốn: 4
Đầu vào
A[]={ 1,1,1 }; B[]={ 2,2,2 }; C[]={ 3,3,3 }; D[]={ 4,4,4 }; X=15
Đầu ra
Số bộ bốn: 0
Giải thích
Không có cặp phần tử nào thỏa mãn.
Phương pháp sử dụng trong chương trình dưới đây
- Nhận mảng nguyên A[], B[], C[], D[] cùng độ dài khởi tạo với số ngẫu nhiên.
- Biến N lưu độ dài chung.
- Hàm
countQuads(int a[], int b[], int c[], int d[], int x, int n)nhận tất cả mảng với độ dài n và trả về count. - Duyệt bằng bốn vòng lặp cho mỗi mảng.
- Vòng ngoài 0 <= i < n cho a[], vòng trong 0 <= j < n cho b[], vòng tiếp 0 <= k < n cho c[], vòng trong cùng 0 <= l < n cho d[].
- So sánh nếu a[i]+b[j]+c[k]+d[l]==x. Nếu đúng tăng count.
- Sau tất cả vòng lặp count sẽ chứa số bộ bốn có tổng x.
- Trả về count làm kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int countQuads(int a[], int b[], int c[], int d[], int x, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
for (int l = 0; l < n; l++) {
int sum = a[i] + b[j] + c[k] + d[l];
if(sum == x) {
count++;
cout << endl << a[i] << " " << b[j] << " " << c[k] << " " << d[l];
}
}
}
}
}
return count;
}
int main() {
int A[] = { 1,1,1 };
int B[] = { 2,2,2 };
int C[] = { 3,3,3 };
int D[] = { 4,4,4 };
int X = 15;
int N = 3; // độ dài mỗi mảng
cout << endl << "Số bộ bốn: " << countQuads(A, B, C, D, X, N);
return 0;
}
Đầu ra
Nếu chạy mã trên sẽ cho kết quả sau:
Số bộ bốn: 0