HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA KỸ THUẬT ĐIỆN TỬ I
BÁO CÁO THỰC HÀNH
MÔN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
NHÓM MÔN HỌC: 02
Giảng viên: TS. Phạm Hoàng Anh
Họ và tên: Đỗ Huy Hùng
Mã sinh viên: B23DCDT107
Hà Nội, 2025
MỤC LỤC
1. SINH TỔ HỢP.......................................................................................................3
1.1. Ý tưởng thuật toán..........................................................................................3
1.2. Lưu đồ thuật toán............................................................................................3
1.3. Chương trình và kết quả................................................................................4
2. SINH HOÁN VỊ.....................................................................................................5
2.1. Ý tưởng thuật toán..........................................................................................5
2.2. Lưu đồ thuật toán............................................................................................5
2.3. Chương trình và kết quả................................................................................6
3. HAHAHA...............................................................................................................7
3.1. Ý tưởng thuật toán..........................................................................................7
3.2. Lưu đồ thuật toán............................................................................................8
3.3. Chương trình và kết quả................................................................................8
4. SỐ THỨ TỰ HOÁN VỊ.......................................................................................10
4.1. Ý tưởng thuật toán........................................................................................10
4.2. Lưu đồ thuật toán..........................................................................................10
4.3. Chương trình và kết quả..............................................................................11
5. XÓA DỮ LIỆU TRONG DANH SÁCH LIÊN KẾT ĐƠN..............................12
5.1. Ý tưởng thuật toán........................................................................................12
5.2. Lưu đồ thuật toán..........................................................................................13
5.3. Chương trình và kết quả..............................................................................13
6. XÂU NHỊ PHÂN KẾ TIẾP.................................................................................15
6.1. Ý tưởng thuật toán........................................................................................15
6.2. Lưu đồ thuật toán..........................................................................................15
6.3. Chương trình và kết quả..............................................................................16
2
1. SINH TỔ HỢP
1.1. Ý tưởng thuật toán
Để sinh tất cả các tổ hợp gồm k phần tử từ n phần tử ta sử dụng quay lui.
Cụ thể:
Nhập số bộ test t, với mỗi bộ:
oNhập n, k.
oGọi Try(1).
Trong hàm Try(i): Tìm giá trị cho vị trí thứ i trong tổ hợp
oLặp j từ a[i-1]+1 đến n-k+i.
oGán a[i]=j.
oNếu i==k => In ra tổ hợp.
oNếu không => Gọi đệ quy Try(i+1).
1.2. Lưu đồ thuật toán
3
1.3. Chương trình và kết quả
#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define test int t; cin >> t; while(t--)
using namespace std;
void nhap(int a[], int n) {
% % for ( int i = 0; i < n; i++ ) cin >> a[i];
}
int n, k, a[1000000];
void In() {
% % for(int i=1; i<=k; i++) cout<<a[i];
% % cout<<" ";
}
void Try(int i) {
% % for(int j=a[i-1]+1; j<=n-k+i; j++) {
% % % % a[i]=j;
% % % % if(i==k) In();
% % % % else Try(i+1);
% % }
}
int main() {
% % test {
% % % % cin>>n>>k;
% % % % Try(1);
% % % % cout<<endl;
% % }
% % return 0;
}
4
2. SINH HOÁN VỊ
2.1. Ý tưởng thuật toán
Để sinh ra tất cả các hoán vị của dãy, ta sử dụng thuật toán quay lui.
Cụ thể:
Nhập số bộ test t, với mỗi bộ:
oNhập n.
oGọi Sinh(i) để bắt đầu sinh hoán vị tại vị trí đầu tiên.
Trong Sinh(i): Tìm giá trị cho vị trí i cho hoán vị.
oLặp j từ 1 đến n.
oNếu mark[j]==0:
mark[j]=1.
a[i]=j.
Nếu i==n => In ra hoán vị.
Nếu không => Gọi đệ quy Sinh(i+1).
mark[j]=0.
2.2. Lưu đồ thuật toán
5
