TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA: CÔNG NGHỆ THÔNG TIN
BỘ MÔN: CÔNG NGHỆ PHẦN MỀM
ĐỀ THI CUỐI KỲ
Tên học phần: TOÁN RỜI RẠC
Mã học phần: …………23T_nh16………… Số tín chỉ: 3
Phương pháp đánh giá (*): tự luận có giám sát Thời gian làm bài: 75 phút
Đề số: Đ0001
☐Sinh viên được sử dụng tài liệu khi làm bài (tuy nhiên không được phép sử dụng
ChatGPT)
—-------------------------------------------------------------------------------------------------------------------------------
Họ tên: Nguyễn Văn Lợi Lớp:23T_Nhat1 MSSV:………102230026……………...
Sinh viên làm bài trực tiếp trên tệp này, lưu tệp với định dạng MSSV_HọTên.pdf và nộp bài thông
qua MSTeam:
Câu 1 (3 điểm) Gọi Bnlà số chuỗi độ dài nđược hình thành từ các ký tự {A, B, C, D, 1, 2, 3, 4, 5,
6, 7 }.
a) Đếm số chuỗi Bnsao cho Bnchỉ chứa đúng 2 ký tự số
# Trả lời: Trình bày và dán kết quả vào bên dưới:
Chuỗi B chỉ chứa đúng 2 kí tự số :
*n = 2 => chứa 2 số
Số chuỗi là = 21 chuỗi
*n= 3 => 2 số và 1 chữ
Số chuỗi là 4 * = 84 chuỗi
*n=4 =>2 số và 2 chữ
Số chuỗi là * = 126 chuỗi
* n =5 => 2 số và 3 chữ
Số chuỗi là * = 84 chuỗi
*n = 6=> 2 số và 4 chữ
Số chuỗi là
b) Lập hệ thức truy hồi để đếm số chuỗi Bnsao cho Bnkhông chứa hai ký tự số kề nhau.
# Trả lời: Trình bày cách xây dựng hệ thức truy hồi vào đây:
#Trả lời: Xác định điều kiện ban đầu của hệ thức truy hồi vào đây:
c) Hãy giải hệ thức truy hồi trên câu b)
# Trả lời: Trình bày cách giải ở đây:
# Trả lời: Công thức nghiệm nếu có:
Câu 2 (4 điểm) Cho tập X = {1, 2, …, n }, n . ∈ 𝑍, 𝑛 ≥1
a) Tìm hoán vị tiếp theo của hoán vị S = 653241 bằng phương pháp sinh
# Trả lời: Trình bày kết quả vào đây:
kết quả là : 653412
b) Viết chương trình liệt kê tập con k phần tử từ X ( n) sử dụng phương pháp sinh.𝑘 ∈ 𝑍, 0≤ 𝑘 ≤
# Trả lời: Dán code vào đây:
#include<stdio.h>
int n ,nn, countt = 1;
void printA( int b[], int n){
for(int i = 1; i <= n ; i++){
printf("%d ",b[i]);
}
printf("\n");
}
void print_C(int i ,int b[], int c[],int count){
int j = i;
if(count == nn+1 ){
printf("%d : ",countt++);
printA(c,nn);
return;
}
while(j != n-nn+1+count){
c[count] = b[j];
print_C(j+1,b,c,count+1);
j++;
}
return;
}
int main(){
printf("khoi tao n = ");
scanf("%d",&n);
printf("\nnhap k = ");
scanf("%d",&nn);
int b[n+1];
for(int i = 0; i<=n; i++){
b[i] = i;
}
int c[nn+1];
print_C(1,b,c,1);
}
# Trả lời: Dán kết quả thực thi vào đây:
khoi tao n = 5
nhap k = 4
1:1234
2:1235
3:1245
4:1345
5:2345
# Trả lời: Giải thích chi tiết cấu hình đầu tiên, cấu hình kết thúc, thuật toán sinh:
cấu hình đầu tiên là : 1 2 3 4
cấu hình kết thúc là : 2 3 4 5
thuật toán :
𝑎1< 𝑎2< 𝑎3< 𝑎4
sử dụng đệ quy theo từng lớp lớp ngoài cùng( khi tăng đến max của X phần tử thì lớp phía trước nó𝑎𝑛)
tăng lên 1 giá trị và làm mới chạy với +1 và chạy khi đến = n - k + 1 thì dừng chương trình𝑎𝑖−1 𝑎𝑖−1 𝑎0
c) Viết chương trình liệt kê tất cả các tập con của X sử dụng kết quả ở câu b)
# Trả lời: Dán code vào đây:
#include<stdio.h>
int n ,nn, countt = 1;
void printA( int b[], int n){
for(int i = 1; i <= n ; i++){
printf("%d ",b[i]);
}
printf("\n");
}
void print_C(int i ,int b[], int c[],int count){
int j = i;
if(count == nn+1 ){
printf("%d : ",countt++);
printA(c,nn);
return;
}
while(j != n-nn+1+count){
c[count] = b[j];
print_C(j+1,b,c,count+1);
j++;
}
return;
}
int main(){
printf("khoi tao n = ");
int m;
scanf("%d",&m);
for(int j = 0 ; j <= m; j++){
printf("k = %d\n",j);
n = m;
nn = j;
int b[n+1];
for(int i = 0; i<=m; i++){
b[i] = i;
}
int c[j+1];
print_C(1,b,c,1);
}
// print_C(b,1,3);
}
# Trả lời: Dán kết quả vào đây với trường hợp n = 4:
khoi tao n = 4
k=0
1 :
k=1
2 : 1
3 : 2
4 : 3
5 : 4
k=2
6 : 1 2
7 : 1 3
8 : 1 4
9 : 2 3
10 : 2 4
11 : 3 4
k=3
12 : 1 2 3
13 : 1 2 4
14 : 1 3 4
15 : 2 3 4
k=4
16:1234
Câu 3 (3 điểm) Cho phương trình X1 + X2 +....+ Xn = k
a) Viết chương trình liệt nghiệm không âm của phương trình trên bằng phương pháp sinh.
# Trả lời: Dán code vào đây:
# Trả lời: Dán kết quả thực thi vào đây:
b) Viết chương trình đếm nghiệm nguyên không âm của phương trình trên
# Trả lời: Dán code vào đây:
# Trả lời: Dán kết quả vào đây với trường hợp n = 5, k = 10
Tổng cộng có: 2 câu
Đà Nẵng, ngày 01 tháng 04 năm 2024
GIẢNG VIÊN BIÊN SOẠN ĐỀ THI
TRƯỞNG BỘ MÔN
(đã ký)