Cho một dãy số, chúng ta cần tìm số nhóm có kích thước 2 và 3 chia hết cho 3. Chúng ta có thể lấy tổng của hai và ba số kết hợp và kiểm tra xem chúng có chia hết cho 3 hay không.
Hãy xem một ví dụ.
Đầu vào
arr = [1, 2, 3, 4]
Đầu ra
4
Có 4 tổ hợp chia hết cho 3. Các tổ hợp đó là ...
[1, 2] [2, 4] [1, 2, 3] [2, 3, 4]
Thuật toán
-
Khởi tạo mảng.
-
Viết hai vòng lặp để nhận tất cả các kết hợp của kích thước hai.
-
Tính tổng của mỗi nhóm.
-
Nếu tổng chia hết cho 3 thì tăng số đếm.
-
-
Viết ba vòng lặp để nhận tất cả các kết hợp của kích thước ba.
-
Tính tổng của mỗi nhóm.
-
Nếu tổng chia hết cho 3 thì tăng số đếm.
-
-
Trả lại số đếm.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong C ++
#include <bits/stdc++.h>
using namespace std;
int getNumberOfGroupsDivisibleBy3(int arr[], int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int sum = arr[i] + arr[j];
if (sum % 3 == 0) {
count += 1;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int sum = arr[i] + arr[j] + arr[k];
if (sum % 3 == 0) {
count += 1;
}
}
}
}
return count;
}
int main() {
int arr[] = { 2, 3, 4, 5, 6, 1, 2, 4, 7, 8 };
int n = 10;
cout << getNumberOfGroupsDivisibleBy3(arr, n) << endl;
return 0;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
57