Bài toán – Dãy chia hết
Xét một dãy gồm N số nguyên tuỳ ý. Giữa các số nguyên đó ta có thể đặt các dấu + hoặc – để thu được các biểu thức số học khác nhau. Ta nói dãy số là chia hết cho K nếu một trong các biểu thức thu được chia hết cho K. Hãy viết chương trình xác định tính chia hết của một dãy số đã cho.
Dữ liệu vào: Lấy từ một file văn bản có tên là DIV.INP có cấu trúc như sau:
– Dòng đầu là hai số N và K (2 ≤ N ≤ 10 000, 2 ≤ K ≤ 100), cách nhau bởi dấu trống.
– Các dòng tiếp theo là dãy N số có trị tuyệt đối không quá 10 000 cách nhau bởi dấu trống hoặc dấu xuống dòng.
Dữ liệu ra: Ghi ra file văn bản DIV.OUT số 1 nếu dãy đã cho chia hết cho K và số 0 nếu ngược lại.
Thuật toán
Để giải bài toán này, ta cần kiểm tra xem có tồn tại một tổng con nào đó trong dãy số ban đầu chia hết cho K hay không.
Ta có thể áp dụng kỹ thuật duyệt qua các tổng con của dãy số để giải quyết bài toán này. Dưới đây là thuật toán chi tiết:
- Đọc dữ liệu vào từ file DIV.INP.
- Dùng một biến “sum” để tính tổng các phần tử trong dãy số ban đầu.
- Nếu tổng “sum” chia hết cho K thì ghi số 1 vào file DIV.OUT và kết thúc chương trình.
- Nếu không, ta sẽ thử tất cả các tổng con có thể của dãy số ban đầu và kiểm tra xem tổng con đó chia hết cho K hay không. Nếu có ít nhất một tổng con nào đó chia hết cho K thì ghi số 1 vào file DIV.OUT và kết thúc chương trình.
- Nếu không tìm thấy tổng con nào chia hết cho K thì ghi số 0 vào file DIV.OUT và kết thúc chương trình.
Dưới đây là mã giả của thuật toán trên:
Đọc dữ liệu vào từ file DIV.INP
Tính tổng của dãy số ban đầu và lưu vào biến "sum"
Nếu tổng "sum" chia hết cho K thì ghi số 1 vào file DIV.OUT và kết thúc chương trình.
Nếu không:
Duyệt qua tất cả các tổng con của dãy số ban đầu:
Nếu tổng con đó chia hết cho K thì ghi số 1 vào file DIV.OUT và kết thúc chương trình.
Ghi số 0 vào file DIV.OUT và kết thúc chương trình.
Cài đặt bài toán với Python
# Đọc dữ liệu vào từ file DIV.INP
with open("DIV.INP", "r") as f:
n, k = map(int, f.readline().split())
a = list(map(int, f.read().split()))
# Tính tổng của dãy số ban đầu
sum = 0
for x in a:
sum += x
# Kiểm tra nếu tổng chia hết cho K thì ghi số 1 và kết thúc chương trình
if sum % k == 0:
with open("DIV.OUT", "w") as f:
f.write("1\n")
exit()
# Duyệt qua tất cả các tổng con của dãy số ban đầu
for i in range(n):
s = 0
for j in range(i, n):
s += a[j]
# Nếu tổng con đó chia hết cho K thì ghi số 1 và kết thúc
if s % k == 0:
with open("DIV.OUT", "w") as f:
f.write("1\n")
exit()
# Nếu không tìm thấy tổng con nào chia hết cho K thì ghi số 0 và kết thúc chương trình
with open("DIV.OUT", "w") as f:
f.write("0\n")
Cài đặt bài toán với C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main() {
// Mở file đầu vào DIV.INP
ifstream fin("DIV.INP");
// Đọc số lượng phần tử và số nguyên K
int n, k;
fin >> n >> k;
// Đọc dãy số
vector<int> a(n);
for (int i = 0; i < n; i++) {
fin >> a[i];
}
// Tính tổng của dãy số ban đầu
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
// Kiểm tra nếu tổng chia hết cho K thì ghi số 1 và kết thúc chương trình
if (sum % k == 0) {
ofstream fout("DIV.OUT");
fout << 1 << endl;
return 0;
}
// Duyệt qua tất cả các tổng con của dãy số ban đầu
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = i; j < n; j++) {
s += a[j];
// Nếu tổng con đó chia hết cho K thì ghi số 1 và kết thúc
if (s % k == 0) {
ofstream fout("DIV.OUT");
fout << 1 << endl;
return 0;
}
}
}
// Nếu không tìm thấy tổng con nào chia hết cho K thì ghi số 0 và kết thúc chương trình
ofstream fout("DIV.OUT");
fout << 0 << endl;
return 0;
}