ĐỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CÓ ĐÁP ÁN CÀI ĐẶT BẰNG NGÔN NGỮ C - ĐỀ SỐ 3
Cho dãy gồm n số tự nhiên phân biệt a1, a2, .., an và số tự nhiên B. Hãy liệt kê tất cả các phần tử của tập ;
Dữ liệu vào cho bởi file data.in theo khuôn dạng như sau:
-
Dòng đầu tiên ghi lại hai số tự nhiên n và B. Hai số được viết cách nhau bởi một vài khoảng trống.
-
Dòng kế tiếp ghi lại n số nguyên dương a1, a2,..,an. Hai số khác nhau được viết cách nhau bởi một vài kí tự trống.
Kết quả ra ghi lại trong file ketqua.out theo khuôn dạng sau:
-
Dòng đầu tiên ghi lại số tự nhiên k là số phần tử của tập D.
-
k dòng tiếp theo mỗi dòng ghi lại một vector nhị phân x = (x1, x2 ,.., xn) là phần tử của D. Hai thành phần khác nhau của vector x được viết cách nhau bởi một vài khoảng trống.
Ví dụ với n =7, B = 25, { a1, a2, a3, a4, a5, a6, a7} = {5, 10, 15, 20, 25, 30, 35} trong file data.in sẽ cho ta 3 phần tử của tập D tương ứng với 3 vector nhị phân độ dài n trong file ketqua.out dưới đây:
|
Data.in |
Ketqua.Out |
|
7 25 5 10 15 20 25 |
3 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 |
#include
#include
#include
#include
int n, b, C[100], X[100], max = 0;
ofstream dataout("C:/cau truc du lieu/dethi/ketqua3.out.txt");
/*
Tim so cac sau nhi phan co tong la so nhap tu tep
*/
int tinhF() {
int f = 0;
for (int i = 1; i <= n; i++)
f = f + C[i] * X[i];
return f;
}
void hienthi() {
for (int i = 1; i <= n; i++)
dataout << X[i] << " ";
dataout << endl;
}
int demthuchien(int k) {
for (int i = 0; i <= 1; i++) {
X[k] = i;
if (k == n) {
if (tinhF() == b) max++;
} else demthuchien(k + 1);
}
}
void thuchien(int k) {
for (int i = 0; i <= 1; i++) {
X[k] = i;
if (k == n) {
if (tinhF() == b) hienthi();
} else thuchien(k + 1);
}
}
main() {
ifstream data("C:/cau truc du lieu/dethi/data3.in.txt");
data >> n >> b;
for (int i = 1; i <= n; i++)
data >> C[i];
max = 0;
demthuchien(1);
dataout << max << endl;
thuchien(1);
}
