Bài thực hành Môn Kỹ thuật lập trình | Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147 Mục lục nội dung
Bài thực hành số 04 – Tuần 15 ............................................................................................ 2
BÀI TẬP TRÊN LAB ......................................................................................................... 2
Bài tập 4.1. Đảo ngược một danh sách liên kết đơn ....................................................... 2
Bài tập 4.2. Một điểm trong không gian 2 chiều được biểu diễn bằng pair. Hãy viết
hàm tính diện tích tam giác theo tọa độ 3 đỉnhtrong đó, Point là kiểu được định nghĩa
trước trong trình chấm như sau: using Point = pair; ........................... 6
Bài tập 4.3. Một vector trong không gian 3 chiều được biểu diễn bằng tuple
double, double>. Hãy viết hàm tính tích có hướng của 2 vector, trong đó Vector là kiểu
được định nghĩa sẵn trong trình chấm như sau: using Vector = tupledouble>; ........................................................................................................................... 8
Bài tập 4.4. Cho hai std::vector, hãy xóa hết các phần tử chẵn, sắp xếp giảm dần các số
trong cả 2 vector và trộn lại thành một vector cũng được sắp xếp giảm dần ................ 10
Bài tập 4.5. Viết hàm void dfs(vector< list > adj) thực hiện thuật toán DFS
không sử dụng đệ quy trên đồ thị biểu diễn bằng danh sách kề .................................... 13
Bài tập 4.6. Viết hàm void bfs(vector< list > adj) thực hiện thuật toán BFS
không sử dụng đệ quy trên đồ thị biểu diễn bằng danh sách kề. Đồ thị có n đỉnh được
đánh số từ 1 đến n. Thuật toán BFS xuất phát từ đỉnh 1. Các đỉnh được thăm theo thứ
tự ưu tiên từ trái sang phải trong danh sách kề. Yêu cầu hàm trả ra thứ tự các đỉnh được
thăm (những đỉnh không thể thăm từ đỉnh 1 thì không phải in ra) ................................ 16
Bài tập 4.7. Viết các hàm thực hiện các phép giao và hợp của hai tập hợp được biểu
diễn bằng set .................................................................................................................. 18
Bài tập 4.8. Viết các hàm thực hiện các phép giao và hợp của hai tập hợp mờ được
biểu diễn bằng map ........................................................................................................ 21
Bài tập 4.9. Cài đặt thuật toán Dijkstra trên đồ thị vô hướng được biểu diễn bằng
danhsách kề sử dụng std::priority_queue ...................................................................... 25
BÀI TẬP VỀ NHÀ ........................................................................................................... 28
Bài tập 4.10. Xây dựng một máy tìm kiếm (search engine) đơn giản .......................... 28
Bài tập 4.11. Bảo vệ lâu đài ......................................................................................... 32
Bài tập 4.12. Lược đồ ................................................................................................... 36
Bài tập 4.13. Đếm xâu con ........................................................................................... 38 lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Bài thực hành số 04 – Tuần 15 BÀI TẬP TRÊN LAB
Bài tập 4.1. Đảo ngược một danh sách liên kết đơn. #include using namespace std; struct Node { int data; Node* next; lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147 Node(int data) { this->data = data; next = NULL; } };
// push a new element to the beginning of the list
Node* prepend(Node* head, int data) { //***************** // Lê
Khôi Nguyên - 20225147 if (head == NULL) { Node *node = new Node(data); head = node; return node; } Node *node = new Node(data); node->next = head; return node; //*****************/ }
// print the list content on a line void print(Node* head) { //***************** // Lê Khôi Nguyên - 20225147 if lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147 (head == NULL) return; do {
cout << head -> data << " ";
head = head -> next; } while (head != NULL); cout << endl; //*****************/ }
// return the new head of the reversed list Node* reverse(Node* head) { //*****************
// Lê Khôi Nguyên - 20225147 Node* prev = NULL; Node* current = head; Node* next = NULL; while (current != NULL) { next = current->next;
current->next = prev; prev = current; current = next; } return prev; lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147 //*****************/ } int main() { int n, u; cin >> n; Node* head = NULL;
for (int i = 0; i < n; ++i){ cin >> u; head = prepend(head, u); }
cout << "Original list: "; print(head); head = reverse(head);
cout << "Reversed list: "; print(head); return 0; } lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Bài tập 4.2. Một điểm trong không gian 2 chiều được biểu diễn bằng pair. Hãy viết hàm
tính diện tích tam giác theo tọa độ 3 đỉnhtrong đó, Point là kiểu được định nghĩa trước
trong trình chấm như sau: using Point = pair; // #include // #include // #include // #include // using namespace std; // using Point = pair; lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
double area(Point a, Point b, Point c) { //***************** // Lê
Khôi Nguyên - 20225147 double ab = sqrt(pow(b.first - a.first, 2) +
pow(b.second - a.second, 2)); double ac = sqrt(pow(c.first - a.first, 2) +
pow(c.second - a.second, 2)); double bc = sqrt(pow(b.first - c.first, 2) +
pow(b.second - c.second, 2)); double p = (ab + bc + ac) / 2; return
sqrt(p*(p - ab)*(p - ac)*(p - bc)); //*****************/ } // int main() {
// cout << setprecision(2) << fixed;
// cout << area({1, 2}, {2.5, 10}, {15, -5.25}) << endl; // return 0; // } lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Bài tập 4.3. Một vector trong không gian 3 chiều được biểu diễn bằng tupledouble, double>. Hãy viết hàm tính tích có hướng của 2 vector, trong đó Vector là kiểu
được định nghĩa sẵn trong trình chấm như sau: using Vector = tupledouble>; // #include // #include // #include // using namespace std; // using Vector = tuple; lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Vector cross_product(Vector a, Vector b) { //*****************
// Lê Khôi Nguyên - 20225147
double first = get<1>(a) * get<2>(b) - get<1>(b) * get<2>(a);
double second = get<2>(a) * get<0>(b) - get<2>(b) * get<0>(a);
double third = get<0>(a) * get<1>(b) - get<0>(b) * get<1>(a);
Vector c {first, second, third}; return c; //*****************/ } // int main() {
// cout << setprecision(2) << fixed; // Vector a {1.2, 4, -0.5}; // Vector b {1.5, -2, 2.5};
// Vector c = cross_product(a, b);
// cout << get<0>(c) << ' ' << get<1>(c) << ' ' << get<2>(c) << endl; // return 0; // } lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Bài tập 4.4. Cho hai std::vector, hãy xóa hết các phần tử chẵn, sắp xếp giảm dần các số
trong cả 2 vector và trộn lại thành một vector cũng được sắp xếp giảm dần. #include #include #include using namespace std; void
print_vector(const vector &a) {
for (int v : a) cout << v << ' '; cout << endl; } lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
void delete_even(vector &a) {
//***************** // Lê Khôi Nguyên -
20225147 vector a_odd; for (auto itr
= a.begin(); itr != a.end(); itr++) { if (abs(*itr) % 2 == 1) { a_odd.push_back(*itr); } } a = a_odd; // return a_odd; //*****************/ }
void sort_decrease(vector &a) { //*****************
// Lê Khôi Nguyên - 20225147
sort(a.begin(), a.end(), greater()); //*****************/ }
vector merge_vectors(const vector &a, const vector &b) { //***************** // Lê Khôi Nguyên - 20225147 vector c = a; vector d = b;
c.insert(c.end(), d.begin(), d.end()); sort_decrease(c); return c; lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147 // *****************/ } int main() { int m, n, u; std::vector a, b;
std::cin >> m >> n;
for(int i = 0; i < m; i++){ std:: cin >> u; a.push_back(u); } for(int i = 0; i < n; i++){ std:: cin >> u; b.push_back(u); }
delete_even(a); cout << "Odd elements of a: "; print_vector(a);
delete_even(b); cout << "Odd elements of b: "; print_vector(b);
sort_decrease(a); cout << "Decreasingly sorted a: "; print_vector(a); lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
sort_decrease(b); cout << "Decreasingly sorted b: "; print_vector(b);
vector c = merge_vectors(a, b);
cout << "Decreasingly sorted c: "; print_vector(c); return 0; }
Bài tập 4.5. Viết hàm void dfs(vector< list > adj) thực hiện thuật toán DFS không
sử dụng đệ quy trên đồ thị biểu diễn bằng danh sách kề.
Đồ thị có n đỉnh được đánh số từ 1 đến n. Thuật toán DFS xuất phát từ đỉnh 1. Các đỉnh
được thăm theo thứ tự ưu tiên từ trái sang phải trong danh sách kề. Yêu cầu hàm trả ra
thứ tự các đỉnh được thăm (những đỉnh không thể thăm từ đỉnh 1 thì không phải in ra). lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
void dfs(vector< list > adj) { stack S; vector visited(adj.size());
S.push(1); // Bắt đầu từ đỉnh số 1 //***************** lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
// Lê Khôi Nguyên - 20225147 while (!S.empty()) { int curr = S.top(); if (!visited.at(curr)){ cout << curr << endl; visited.at(curr) = true; } for (int vertex: adj[curr]) { if (visited.at(vertex)){ continue; } else { S.push(vertex); break; } } if (curr == S.top()) { S.pop(); } } // *****************/ } lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Bài tập 4.6. Viết hàm void bfs(vector< list > adj) thực hiện thuật toán BFS không
sử dụng đệ quy trên đồ thị biểu diễn bằng danh sách kề. Đồ thị có n đỉnh được đánh số từ
1 đến n. Thuật toán BFS xuất phát từ đỉnh 1. Các đỉnh được thăm theo thứ tự ưu tiên từ
trái sang phải trong danh sách kề. Yêu cầu hàm trả ra thứ tự các đỉnh được thăm (những
đỉnh không thể thăm từ đỉnh 1 thì không phải in ra). lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
void bfs(vector< list > adj) { queue Q; vector visited(adj.size());
Q.push(1); // Bắt đầu từ đỉnh số 1 //***************** // Lê Khôi Nguyên - 20225147 while (!Q.empty()) { int curr = Q.front(); if
(!visited[curr]) { cout << curr << endl; visited[curr] = true; } for (int vertex: adj[curr]) { if (visited[vertex]) continue; Q.push(vertex); } Q.pop(); } //*****************/ } lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
Bài tập 4.7. Viết các hàm thực hiện các phép giao và hợp của hai tập hợp được biểu diễn bằng set // #include // #include #include // using namespace std; lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
template set set_union(const set &a, const set &b) {
//***************** // Lê Khôi Nguyên - 20225147 set result;
std::set_union(a.begin(), a.end(), b.begin(), b.end(),
std::inserter(result, result.begin())); return result; //*****************/ }
template set set_intersection(const set &a, const set &b) {
//***************** // Lê Khôi Nguyên - 20225147
set result; std::set_intersection(a.begin(), a.end(),
b.begin(), b.end(), std::inserter(result,
result.begin())); return result; //*****************/ } // template
// void print_set(const std::set &a) { // for (const T &x : a) {
// std::cout << x << ' '; // }
// std::cout << std::endl; // } // int main() { lOMoAR cPSD| 61548706
Lê Khôi Nguyên - 20225147
// std::set a = {1, 2, 3, 5, 7};
// std::set b = {2, 4, 5, 6, 9};
// std::set c = set_union(a, b);
// std::set d = set_intersection(a, b);
// std::cout << "Union: "; print_set(c);
// std::cout << "Intersection: "; print_set(d); // return 0; // }