Cho mảng Arr[] số nguyên độ dài n và một số M. Mảng chỉ chứa số nguyên dương. Mục tiêu là đếm các bộ ba phần tử của Arr[] có tích bằng M.
Ta thực hiện bằng cách dùng ba vòng lặp for. Tăng count nếu arr[x]*arr[y]*arr[z]=M và x!=y!=z. (0 <= x,y,z < n).
Hãy hiểu qua các ví dụ.
Đầu vào
arr[] = { 1,2,3,0,2,4 }, M=24
Đầu ra
Số bộ ba có tích M: 2
Giải thích
Các bộ ba arr[x]*arr[y]*arr[z]==M. Arr[]=[1,2,3,0,2,4]=(2,3,4)→2×3×4=24. Arr[]=[1,2,3,0,2,4]=(3,2,4)→3×2×4=24. Tổng bộ ba: 2
Đầu vào
arr[] = {2,2,2,2,2}, M=6
Đầu ra
Số bộ ba có tích M: 0
Giải thích
Mọi bộ ba đều có tích bằng 8. Tổng bộ ba: 0
Phương pháp sử dụng trong chương trình dưới đây
- Nhận mảng nguyên Arr[] khởi tạo với số ngẫu nhiên.
- Biến N lưu độ dài Arr[].
- Hàm
productisM(int arr[], int n, int m)nhận mảng, độ dài trả về bộ ba có tích bằng m. - Khởi tạo biến count = 0 cho số bộ ba.
- Duyệt mảng bằng ba vòng lặp for cho mỗi phần tử bộ ba.
- Vòng ngoài 0 <= i < n-2, vòng giữa i < j < n-1, vòng trong j < k < n.
- Kiểm tra nếu arr[i]*arr[j]*arr[k] == m. Nếu đúng tăng count.
- Sau tất cả vòng lặp count chứa tổng số bộ ba thỏa mãn.
- Trả về count làm kết quả.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int productisM(int arr[], int n, int m) {
int count = 0;
for (int i = 0; i < n-2; i++) {
for (int j = i+1; j < n-1; j++) {
for (int k = j+1; k < n; k++) {
int prod = arr[i] * arr[j] * arr[k];
if(prod == m) {
count++;
}
}
}
}
return count;
}
int main() {
int Arr[] = { 1,2,3,0,2,4 };
int N = 6; // độ dài mảng
int M = 24;
cout << endl << "Số bộ ba có tích M: " << productisM(Arr, N, M);
return 0;
}
Đầu ra
Nếu chạy mã trên sẽ cho kết quả sau:
Số bộ ba có tích M: 4