BÁO CÁO BÀI TẬP TTNT môn Công nghệ thông tin | Trường Đại Học Nha Trang

lOMoAR cPSD| 58490434 lOMoAR cPSD| 58490434
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC NHA TRANG
KHOA CÔNG NGHỆ THÔNG TIN ——————— ——————– BÁO CÁO BÀI TẬP PROJECT MÔN HỌC: TRÍ TUỆ NHÂN TẠO Giảng viên hướng Nguyễn Đình : dẫn Cường
Họ và tên sinh viên
: Nguyễn Tuấn Kiệt MSSV : 62130887 Lớp học phần : HETTNT lOMoAR cPSD| 58490434 Nha Trang – 8/2023 MỤC LỤC
I. Bài tập cài đặt thuật toán......................................................................................................................3
1. Bài tập về thuật toán BFS (Line3_BFS.cpp)....................................................................................3
a. Mô tả bài toán..................................................................................................................................3 b. Giải thích code và cách
giải.............................................................................................................4 c. Độ phức tạp giải
thuật......................................................................................................................7
2. Bài toán TSP (TSP.cpp).....................................................................................................................8
a. Mô tả bài toán..................................................................................................................................8 b. Giải thích code và cách
giải.............................................................................................................8 c. Độ phức tạp giải
thuật....................................................................................................................10
3. Bài toán tô màu đồ thị (toMauDoThi.cpp)....................................................................................11
a. Mô tả bài toán................................................................................................................................11 b. Giải thích code và cách
giải...........................................................................................................11 c. Độ phức tạp giải
thuật....................................................................................................................13
4. Bài toán bốc sỏi (bocsoi.cpp)..........................................................................................................13
a. Mô tả bài toán................................................................................................................................13 b. Giải thích code và cách
giải...........................................................................................................14 c. Độ phức tạp giải
thuật....................................................................................................................15
II. Bài tập thực hành trên lớp.................................................................................................................15
1. Đổi tiền (doitien.cpp).......................................................................................................................15
a. Mô tả bài toán................................................................................................................................15 b. Giải thích code và cách
giải...........................................................................................................16 c. Độ phức tạp giải
thuật....................................................................................................................16
2. Trò chơi tictactoe (tictactoe.cpp)....................................................................................................17
a. Mô tả bài toán................................................................................................................................17 b. Giải thích code và cách
giải...........................................................................................................17 c. Độ phức tạp giải
thuật....................................................................................................................19 lOMoAR cPSD| 58490434
3. Puzzle (Puzzle.cpp)..........................................................................................................................20
a. Mô tả..............................................................................................................................................20 b. Giải thích code và cách
giải........................................................................................................20 c. Độ phức tạp giải
thuật.................................................................................................................23
4. Tìm số nguyên tố lớn nhất (timSoNTMax.cpp).............................................................................24
a. Mô tả bài toán................................................................................................................................24 b. Giải thích code và cách
giải...........................................................................................................24 c. Độ phức tạp thuật
toán...................................................................................................................25
5. Xây d ng máy ch IIS làm server multimedia cho video H.264, music mpự ủ
3......................................26 a. T ng quan vềề IIS serverổ
.................................................................................................................26 b. Các bước thực
hiện........................................................................................................................26 6. Cài đ t Ubuntu ch y trền nềền windowsặ ạ
............................................................................................29 7. Thiềtế l p m ng lan truy c p máy ch t
xa qua kềết nốếi sshậ ạ ậ ủ ừ .............................................................33 a. T ng quan vềề SSHổ
..........................................................................................................................33 b. T ng quan vềề SSHổ
..........................................................................................................................33 c. Xây d ng máy ch FTPự ủ
...................................................................................................................37 8. S d ng Toolkit
multimedia ffmpeg, ffplay th c hi n cống vi cử ụ ự ệ ệ ......................................................41 III.Kềết Lu nậ
................................................................................................................................................43 TÀI LIỆU
THAM KHẢO.......................................................................................................................44 lOMoAR cPSD| 58490434
I. Bài tập cài đặt thuật toán
1. Bài tập về thuật toán BFS (Line3_BFS.cpp) a. Mô tả bài toán
Trò chơi Line là trò chơi di chuyển các viên bi trong một hình vuông 9 x 9 ô.
Bi được ăn khi tạo thành các hàng, cột, đường chéo gồm 5 viên bi liên tiếp cùng màu.
Một thuật toán được sử dụng trong trò chơi là tìm đường đi để di chuyển một
viên bi. Giả sử trò chơi Line tổng quát có n dòng, n cột. Đánh số các dòng từ 1 đến
n theo thứ tự từ trên xuống dưới, đánh số các cột từ 1 đến n theo thứ tự từ trái sang
phải. Giả sử có một viên bi tại ô (y, x) – dòng y cột x, bi có thể di chuyển đến 1 trong
4 ô (y+1, x), (y-1, x), (y, x+1), (y, x-1), nếu ô đó đang trống. Cho vị trí bắt đầu và vị
trí kết thúc của viên bi, hãy viết chương trình cho biết đường đi ngắn nhất của viên
bi (qua ít ô nhất). Dữ liệu nhập: gồm các dòng sau
• Dòng thứ nhất gồm năm số n, sy, sx, dy, dx, mỗi số cách nhau một khoảng
trắng (2 ≤ n ≤ 30; 1 ≤ sy, sx, dy, dx ≤ n). sy là chỉ số dòng, sx là chỉ số cột của
viên bi cần di chuyển. dy là chỉ số dòng, dx là chỉ số cột của vị trí cần di chuyển viên bi đến.
• Trong n dòng tiếp theo, mỗi dòng gồm n số nguyên 0 hoặc 1, mỗi số cách
nhau một khoảng trắng, biểu thị tình trạng của trò chơi. Số 1 nghĩa là vị trí ô
đó có bi, số 0 nghĩa là vị trí ô đó đang trống. lOMoAR cPSD| 58490434
(Dữ liệu cho bảo đảm tại ô (sy, sx) có giá trị là 1, tại ô (dy, dx) có giá trị là 0) Dữ liệu xuất:
Nếu tìm được đường đi ngắn nhất:
• Dòng đầu tiên in ra số nguyên m là chiều dài (số ô) của đường đi. (bao gồm
cả ô đầu tiên của viên bi và ô đích)
• Trong m dòng tiếp theo, dòng thứ I in ra hai giá trị yi, xi là vị trí ô thứ I trong
đường đi, hai số cách nhau một khoảng trắng.
(Nếu có nhiều đường đi cùng ngắn nhất, chỉ cần in ra một đường đi bất kỳ) Nếu
không tìm được đường đi: in ra 0.
b. Giải thích code và cách giải
Để giải quyết bài toán trò chơi Line, ta sử dụng thuật toán tìm đường đi ngắn
nhất trong một ma trận. Dưới đây là phần giải thích chi tiết về cách code hoạt động:
Khai báo cấu trúc Point để đại diện cho một ô trên ma trận. Mỗi Point có hai
thuộc tính y và x lưu trữ tọa độ dòng và cột của ô tương ứng. struct Point { int y, x; };
Hàm isValidMove(int y, int x, int n) kiểm tra xem một bước di chuyển từ ô
(y, x) có hợp lệ hay không. Nó trả về true nếu ô đó nằm trong ma trận kích thước
nxn và không có viên bi, ngược lại trả về false.
Bool isValidMove(int y, int x, int n) {
return (y >= 0 && y < n && x >= 0 && x < n); }
Hàm findShortestPath(vector> &board, Point start, Point end)
tìm đường đi ngắn nhất từ ô start đến ô end trên ma trận board. Để làm điều này,
thuật toán sử dụng BFS (Breath-First Search) trong đó duyệt qua các ô kề của ô hiện
tại để tìm đường đi. Các bước chính trong hàm này bao gồm:
vector findShortestPath(vector> &board, Point start, Point end) { lOMoAR cPSD| 58490434
int n = board.size(); vector> visited(n,
vector(n, false)); vector> parent(n, vector(n, {-1, -1})); queue q; q.push(start);
visited[start.y][start.x] = true; int dy[] = {1, -1, 0, 0}; int dx[] = {0, 0, 1, -1}; while (!q.empty()) { Point current = q.front(); q.pop();
if (current.y == end.y && current.x == end.x) {
// Tìm thấy đích, truy vết để lấy đường đi vector path; Point p = end;
while (p.y != start.y || p.x != start.x) { path.push_back(p); p = parent[p.y][p.x]; } path.push_back(start);
reverse(path.begin(), path.end()); return path; } for (int I = 0; i<4; i++) { int ny = current.y + dy[i]; int nx = current.x + dx[i];
if (isValidMove(ny, nx, n) && !visited[ny][nx] && board[ny][nx] == 0) { q.push({ny, nx}); visited[ny][nx] = true; parent[ny][nx] = current; } } }
// Không tìm thấy đường đi return {}; }
Khởi tạo ma trận visited và parent để lưu trạng thái đã được thăm và tọa độ cha của mỗi ô. lOMoAR cPSD| 58490434
Đưa ô start vào hàng đợi q và đánh dấu ô này là đã thăm.
Duyệt qua hàng đợi q cho đến khi nó trống:
Lấy ra ô đầu tiên từ hàng đợi và gán cho current.
Kiểm tra nếu current là ô đích (end), thì truy vết từ end đến start để lấy đường
đi và trả về đường đi đó.
Duyệt qua các ô kề của current (4 hướng: lên, xuống, trái, phải):
Kiểm tra xem ô kề có hợp lệ (nằm trong ma trận và không có viên bi) và chưa được thăm.
Nếu hợp lệ, đưa ô kề vào hàng đợi, đánh dấu là đã thăm và ghi nhận current là cha của ô kề đó.
Nếu không tìm thấy đường đi, trả về một vector rỗng.
Trong hàm main(), đầu tiên đọc các dữ liệu đầu vào: kích thước ma trận n, tọa
độ ô bắt đầu sy và sx, tọa độ ô đích dy và dx. Sau đó, đọc ma trận board từ đầu vào. Int main() { int n, sy, sx, dy, dx;
cin >> n >> sy >> sx >> dy >> dx;
vector> board(n, vector(n));
for (int I = 0; I < n; i++) {
for (int j = 0; j < n; j++) { cin >> board[i][j]; } }
Point start = {sy – 1, sx – 1}; Point end = {dy – 1, dx
– 1}; vector path = findShortestPath(board, start, end); if (path.empty()) {
cout << 0 << endl; } else { int m =
path.size(); cout << m <<
endl; for (int I = 0; I < m; i++) {
cout << path[i].y + 1 << “ “ << path[i].x + 1 << endl; } } lOMoAR cPSD| 58490434 return 0; }
Tạo điểm bắt đầu start và điểm đích end dựa trên tọa độ đầu vào.
Gọi hàm findShortestPath() để tìm đường đi ngắn nhất từ start đến end trên
board. Lưu kết quả vào vector path.
Kiểm tra nếu path rỗng, tức là không tìm được đường đi, in ra 0. Ngược lại,
in ra độ dài của đường đi m và các tọa độ của các ô trên đường đi.
c. Độ phức tạp giải thuật
Độ phức tạp của thuật toán trên được xác định bởi số lần truy cập vào các ô
trong ma trận. Giả sử kích thước của ma trận là n và số ô trong ma trận không phải là viên bi là m.
Khởi tạo ma trận visited và parent có độ phức tạp O(n^2), với n là kích thước ma trận.
• Trong hàm findShortestPath, ta sử dụng BFS để duyệt qua các ô trên ma trận:
• Duyệt qua tất cả các ô trên ma trận, có độ phức tạp O(n^2).
• Mỗi ô sẽ được thêm vào hàng đợi q một lần và được duyệt qua một lần, có độ phức tạp là O(1).
• Trong trường hợp tốt nhất, khi ô đích được tìm thấy ngay từ ô bắt đầu, ta chỉ
duyệt qua một số lượng nhỏ các ô, có độ phức tạp là O(1).
• Trong trường hợp xấu nhất, khi không tìm thấy đường đi hoặc đường đi là
đường dài nhất, ta có thể duyệt qua tất cả các ô trên ma trận, có độ phức tạp là O(n^2).
• Vì vậy, độ phức tạp của BFS trong trường hợp xấu nhất là O(n^2).
Sau khi tìm được đường đi, ta truy vết từ ô đích đến ô bắt đầu để lấy đường đi.
Truy vết có độ phức tạp O(m), với m là số ô không phải là viên bi trên đường đi.
Tổng kết lại, độ phức tạp của thuật toán trên là O(n^2 + m). Trong trường hợp
tốt nhất, khi ô đích được tìm thấy ngay từ ô bắt đầu, độ phức tạp là O(n^2). Trong
trường hợp xấu nhất, khi không tìm thấy đường đi hoặc đường đi là đường dài nhất,
độ phức tạp là O(n^2 + m).
2. Bài toán TSP (TSP.cpp) a. Mô tả bài toán
Bài toán TSP (Traveling Salesman Problem) là một bài toán quan trọng trong
lý thuyết đồ thị và được áp dụng rộng rãi trong thực tế. Bài toán đặt ra câu hỏi: "Làm lOMoAR cPSD| 58490434
thế nào để một người bán hàng đi qua tất cả các thành phố một lần và quay trở lại
thành phố xuất phát, sao cho khoảng cách di chuyển là ngắn nhất?".
Bài toán TSP được mô hình hóa dưới dạng một đồ thị đơn vô hướng, trong đó
các đỉnh đại diện cho các thành phố và các cạnh đại diện cho khoảng cách giữa các
thành phố. Mục tiêu của bài toán là tìm một chu trình Hamiltonian (một chu trình đi
qua tất cả các đỉnh đúng một lần) có chi phí nhỏ nhất.
Bài toán TSP là một bài toán tối ưu hóa tổ hợp NP-khó, có nghĩa là không có
giải thuật đa thức thời gian để giải quyết bài toán cho tất cả các trường hợp. Do đó,
các giải thuật heuristic và phương pháp tìm kiếm cục bộ thường được sử dụng để
giải quyết bài toán TSP.
Các ứng dụng của bài toán TSP rất đa dạng, bao gồm lập kế hoạch giao hàng,
lập lịch sản xuất, tối ưu hóa quỹ đạo máy bay, tối ưu hóa tuyến đường vận tải, và
nhiều ứng dụng khác trong kinh doanh và khoa học.
b. Giải thích code và cách giải
Để giải quyết bài toán TSP (Traveling Salesman Problem) ta có thể sử dụng
phương pháp Branch and Bound (nhánh cận). Bài toán TSP đặt ra câu hỏi: Nếu có
một người bán hàng phải đi qua tất cả các thành phố để bán hàng và quay trở lại
thành phố ban đầu, thì hãy tìm chu trình ngắn nhất mà anh ta có thể thực hiện.
Dưới đây là cách mà code hoạt động:
• INF được sử dụng để biểu diễn một giá trị vô cùng, thường được sử dụng để so
sánh với các giá trị khác để tìm giá trị nhỏ nhất. const int INF = 1e9; Biến toàn cục:
int n; // S l ng đnh trong đ thố ượ ỉ ồ ị
int graph[20][20]; // Ma tr n tr ng s c a đ th (t i đa 20 đnh)ậ ọ ố ủ ồ ị ố ỉ
vector path; // Chu trình Hamiltonian t m th iạ ờ vector
best_path; // Chu trình Hamiltonian t t nh tố
ấ int best_cost = INF; // Chi
phí c a chu trình Hamiltonian t t nh tủ ố ấ
• n là số lượng đỉnh trong đồ thị. lOMoAR cPSD| 58490434
• graph là ma trận trọng số của đồ thị, thể hiện khoảng cách giữa các đỉnh.
• path là một vector để lưu trữ chu trình Hamiltonian tạm thời.
• best_path lưu trữ chu trình Hamiltonian tốt nhất tìm thấy.
• best_cost lưu trữ chi phí của chu trình Hamiltonian tốt nhất. Hàm isSafe:
bool isSafe(int v, int pos, vector& visited, int cost_so_far) {
// Ki m tra xem có c nh n i đnh cu i c a chu trình tể ạ ố ỉ ố ủ
ạm th i và v hay khôngờ if (graph[path[pos - 1]][v] == 0) return false;
// Ki m tra xem đnh v đã đ c thăm ch a và n u đã thăm thì không thêm vàoể ỉ ượ
ư ế chu trình if (visited[v]) return false;
// N u chi phí t đnh tr c đó t i v t quá best_cost thì không thêm vàoế ừ ỉ ướ ớ
ượ chu trình if (cost_so_far + graph[path[pos - 1]][v] >= best_cost) return false; return true; }
• Hàm này kiểm tra xem có thể thêm đỉnh v vào chu trình tạm thời tại vị trí pos hay không.
• Kiểm tra xem có cạnh nối giữa đỉnh cuối cùng của chu trình tạm thời và v hay không.
• Kiểm tra xem đỉnh v đã được thăm chưa.
• Kiểm tra xem nếu thêm chi phí từ đỉnh trước đó tới v vượt quá best_cost thì có
nên thêm v vào chu trình tạm thời không. Hàm TSP_BranchAndBound:
void TSP_BranchAndBound(int pos, vector& visited, int cost_so_far) { //
N u đã đi qua t t c các đnh, thì ki m tra xem có t o thành chu trìnhế ấ ả ỉ ể ạ
Hamiltonian hay không if (pos == n) { if (graph[path[pos - 1]][path[0]] != 0) {
int curr_cost = cost_so_far + graph[path[pos - 1]][path[0]]; // Tính t ng chi phíổ
if (curr_cost < best_cost) { best_cost = curr_cost; best_path = path; lOMoAR cPSD| 58490434 } } return; }
// Duy t qua t t c các đnh còn l i đ xem có thêm vào chu trình t m th iệ ấ ả ỉ ạ
ể ạ ờ không for (int v = 0; v < n; v++) { // Thay đ i t v = 1 thành v = 0ổ ừ
if (isSafe(v, pos, visited, cost_so_far)) { path[pos] = v; visited[v] = true;
TSP_BranchAndBound(pos + 1, visited, cost_so_far + graph[path[pos - 1]][v]); visited[v] = false; } } }
• Đây là hàm chính để tìm chu trình Hamiltonian tốt nhất.
• Nếu đã đi qua tất cả các đỉnh, thì kiểm tra xem có tạo thành chu trình Hamiltonian
hay không và cập nhật kết quả tốt nhất nếu cần.
• Duyệt qua tất cả các đỉnh còn lại để thử thêm vào chu trình tạm thời. Hàm main:
• Nhập số lượng đỉnh n và ma trận trọng số graph.
• Nhập đỉnh xuất phát starting_vertex.
• Khởi tạo biến và chu trình tạm thời.
• Gọi hàm TSP_BranchAndBound để tìm chu trình tốt nhất.
• In kết quả: chu trình tốt nhất, chi phí và đỉnh xuất phát.
• Chương trình này sử dụng phương pháp Branch and Bound để tối ưu hóa việc
duyệt qua tất cả các đỉnh để tìm chu trình Hamiltonian tốt nhất.
c. Độ phức tạp giải thuật
Độ phức tạp của giải thuật trong đoạn mã trên phụ thuộc vào cách mà thuật
toán Branch and Bound được thực hiện trong việc giải quyết bài toán TSP. Chúng
ta sẽ phân tích độ phức tạp từng phần của mã để hiểu rõ hơn: Hàm isSafe:
• Độ phức tạp của hàm này là O(1). Các kiểm tra được thực hiện trong hằng số thời gian. Hàm TSP_BranchAndBound: lOMoAR cPSD| 58490434
• Đây là hàm quan trọng thực hiện tìm kiếm và thu thập thông tin về chu trình Hamiltonian tốt nhất.
• Trong trường hợp tốt nhất, thuật toán có thể tìm thấy một chu trình Hamiltonian
ngay từ đầu, mất O(1) thời gian.
• Trong trường hợp xấu nhất, thuật toán phải thử tất cả các khả năng (backtracking)
để tìm ra chu trình Hamiltonian tốt nhất. Điều này có thể xảy ra khi đồ thị rất lớn
và không có các giới hạn dừng sớm. Trong trường hợp này, độ phức tạp sẽ là
O(n!), với n là số lượng đỉnh. Hàm main:
• Nhập ma trận trọng số có độ phức tạp là O(n^2), với n là số lượng đỉnh.
• Gọi hàm TSP_BranchAndBound có độ phức tạp tùy thuộc vào thời gian mất để tìm chu trình tốt nhất.
Tổng cộng, độ phức tạp của giải thuật này có thể được xấp xỉ là O(n!) trong
trường hợp xấu nhất. Tuy nhiên, giải thuật thường được cải tiến và kết hợp với các
cách thức để giảm số lượng các trường hợp được thử, như cắt tỉa (pruning), để tối
ưu hóa thời gian chạy thực tế.
3. Bài toán tô màu đồ thị (toMauDoThi.cpp) a. Mô tả bài toán
Bài toán tô màu đồ thị là một bài toán trong lĩnh vực lý thuyết đồ thị và tối ưu
hóa mà tác vụ chính là gán một tập màu cho các đỉnh trong đồ thị sao cho không có
hai đỉnh kề nhau có cùng màu. Mục tiêu là tìm cách tô màu tối ưu sao cho số màu sử dụng là nhỏ nhất.
b. Giải thích code và cách giải
Đây là một chương trình C++ để tô màu đồ thị bằng thuật toán BFS. Thuật
toán này sử dụng một hàng đợi để lưu trữ các đỉnh của đồ thị và duyệt qua các đỉnh
theo chiều rộng, tô màu cho từng đỉnh trong quá trình duyệt.
Mã nguồn bao gồm các phần sau:
Khai báo các biến và thư viện:
• numNodes: số lượng đỉnh trong đồ thị. numEdges: số lượng cạnh trong đồ
thị. graph: một vector chứa danh sách kề của các đỉnh trong đồ thị. lOMoAR cPSD| 58490434
• colors: một vector chứa màu của từng đỉnh trong đồ thị.
• startNode: đỉnh bắt đầu để tô màu.
• visited: một vector chứa trạng thái của các đỉnh đã được thăm hay chưa.
• nodeQueue: một hàng đợi để lưu trữ các đỉnh trong quá trình duyệt đồ thị. Hàm colorGraph:
void colorGraph(vector>& graph, vector& colors, int startNode)
{ int numNodes = graph.size();
vector visited(numNodes, false); queue nodeQueue; nodeQueue.push(startNode); visited[startNode] = true; while (!nodeQueue.empty()) {
int currentNode = nodeQueue.front(); nodeQueue.pop();
for (int neighbor : graph[currentNode]) { if (!visited[neighbor]) { nodeQueue.push(neighbor); visited[neighbor] = true;
// Gán màu cho đnh hàng xóm ch a đ c tô màuỉ ư
ượ for (int color = 1; color <= numNodes;
color++) { bool isColorAvailable = true;
for (int adj : graph[neighbor]) { if (colors[adj] == color) {
isColorAvailable = false; break; } } if (isColorAvailable) { colors[neighbor] = color; break; } } } } } }
• Duyệt qua các đỉnh của đồ thị bắt đầu từ đỉnh startNode.
• Tại mỗi đỉnh, kiểm tra các đỉnh hàng xóm và gán màu cho đỉnh hàng xóm chưa được tô màu.
• Nếu đỉnh hàng xóm đã được tô màu, kiểm tra xem màu đã được dùng hay
chưa. Nếu đã dùng, thử một màu khác. lOMoAR cPSD| 58490434 Hàm main:
• Nhập số lượng đỉnh và số lượng cạnh của đồ thị từ người dùng.
• Nhập các cạnh của đồ thị và lưu chúng vào graph.
• Nhập đỉnh bắt đầu để tô màu.
• Gọi hàm colorGraph để tô màu đồ thị. In ra kết quả của màu của từng đỉnh.
Thuật toán tô màu BFS được sử dụng để tô màu đồ thị bằng cách duyệt qua
các đỉnh theo chiều rộng. Khi tô màu cho một đỉnh, thuật toán sẽ kiểm tra các đỉnh
hàng xóm và gán màu cho đỉnh hàng xóm chưa được tô màu. Nếu đỉnh hàng xóm đã
được tô màu, thuật toán sẽ kiểm tra xem màu đã được dùng hay chưa. Nếu đã dùng,
thử một màu khác. Quá trình này được lặp lại cho tất cả các đỉnh trong đồ thị.
c. Độ phức tạp giải thuật
Độ phức tạp của giải thuật tô màu đồ thị bằng BFS trong chương trình này là
O(V+E), trong đó V là số đỉnh của đồ thị và E là số cạnh của đồ thị. Điều này bởi vì
thuật toán BFS duyệt qua tất cả các đỉnh và cạnh một lần, với mỗi đỉnh và cạnh được
duyệt qua đúng một lần, do đó độ phức tạp là O(V+E).
Trong hàm colorGraph, vòng lặp trong đó tìm màu cho đỉnh hàng xóm chưa
được tô màu có thể tăng độ phức tạp của giải thuật lên đến O(V^2), nếu đồ thị có
một số lượng lớn các đỉnh hàng xóm. Tuy nhiên, trong trường hợp tốt nhất, mỗi đỉnh
chỉ có một đỉnh hàng xóm và số lượng màu được sử dụng là hẹp, do đó độ phức tạp
của giải thuật sẽ là O(V+E).
Vì vậy, độ phức tạp của giải thuật tô màu đồ thị bằng BFS trong chương trình
này là O(V+E), với một số trường hợp xấu nhất có độ phức tạp là O(V^2).
4. Bài toán bốc sỏi (bocsoi.cpp) a. Mô tả bài toán
Trò chơi Bốc Sỏi, còn được gọi là trò chơi Nim, là một trò chơi hai người
chơi, trong đó mỗi người lần lượt bốc một số lượng sỏi từ các đống sỏi, và người
chơi cuối cùng còn lại đóng vai trò là người thua.
Trò chơi này có thể chơi với số lượng đống sỏi và số lượng sỏi trong mỗi đống
khác nhau. Trong mỗi lượt, người chơi có thể bốc bất kỳ số lượng sỏi từ một đống
sỏi nào đó. Điều quan trọng là người chơi phải bốc ít nhất một viên sỏi.
Ví dụ, nếu có 3 đống sỏi với số lượng sỏi lần lượt là 3, 5 và 7, người chơi có
thể bốc bất kỳ số lượng sỏi từ bất kỳ đống sỏi nào, nhưng phải bốc ít nhất một viên
sỏi. Người chơi cuối cùng còn lại đóng vai trò là người thua. lOMoAR cPSD| 58490434
Trò chơi Bốc Sỏi là một trò chơi rất thú vị và có ứng dụng rộng rãi trong lý
thuyết trò chơi và thông tin. Nó được sử dụng để giải quyết nhiều vấn đề trong toán
học, bao gồm cả các vấn đề tối ưu và lý thuyết đồ thị.
b. Giải thích code và cách giải
• Khởi tạo đống sỏi ban đầu:
• Mảng piles được khởi tạo với số lượng sỏi trong mỗi đống ban đầu.
• Trong ví dụ của bạn: piles[0] = 5, piles[1] = 4, và piles[2] = 7.
• Vòng lặp chính (While loop):
• Chương trình bắt đầu một vòng lặp vô hạn để chơi trò chơi cho đến khi một người chơi thua.
• Hiển thị trạng thái đống sỏi:
• Hàm displayPiles được gọi để hiển thị trạng thái hiện tại của các đống sỏi.
• Lấy lựa chọn từ người chơi:
• Người chơi được yêu cầu chọn một trong các đống sỏi.
• Sau đó, họ cũng được yêu cầu chọn số lượng sỏi muốn lấy khỏi đống đã chọn.
• Cập nhật trạng thái đống sỏi:
• Số lượng sỏi mà người chơi đã chọn bị loại bỏ khỏi đống sỏi tương ứng bằng
cách giảm giá trị của piles[selectedPile] đi stonesToRemove.
• Kiểm tra điều kiện thua:
• Sau khi mỗi nước đi của người chơi, chương trình kiểm tra xem tất cả các
đống sỏi có trống hết hay không.
• Nếu tất cả đống đều trống (không còn sỏi), chương trình thông báo người chơi
đã thua và vòng lặp kết thúc. • Lặp lại vòng lặp:
• Chương trình quay lại bước 3 và tiếp tục vòng lặp cho đến khi một người chơi thua. Ví dụ:
Người chơi chọn đống 2 và lấy 2 sỏi. Đống 2 sẽ trở thành "O O".
Người chơi chọn đống 3 và lấy 4 sỏi. Đống 3 sẽ trở thành "O O O O".
Người chơi chọn đống 1 và lấy 3 sỏi. Đống 1 sẽ trở thành "O". ...
Khi một người chơi không còn đống nào có sỏi, chương trình thông báo họ đã thua. lOMoAR cPSD| 58490434
Lưu ý rằng code chỉ cung cấp một giao diện dòng lệnh đơn giản. Bạn có thể
phát triển chương trình thêm để cải thiện giao diện người dùng, thêm tính năng và tùy chỉnh luật chơi.
c. Độ phức tạp giải thuật
Vòng lặp chính (While loop):
• Vòng lặp chính sẽ chạy cho đến khi có người chơi thua, điều này xảy ra khi
tất cả đống sỏi đã trống.
• Độ phức tạp: O(N), trong đó N là tổng số sỏi ban đầu.
Hiển thị trạng thái đống sỏi:
• Hiển thị trạng thái các đống sỏi, số lượng sỏi trong mỗi đống. Độ phức tạp:
O(N), với N là số lượng đống sỏi.
Lấy lựa chọn từ người chơi:
• Nhập lựa chọn của người chơi và số lượng sỏi muốn lấy. Độ phức tạp: O(1),
vì việc nhập có thể coi là hằng số.
Cập nhật trạng thái đống sỏi:
• Giảm giá trị của phần tử trong mảng piles để thể hiện việc loại bỏ sỏi. Độ
phức tạp: O(1), vì chỉ là việc gán giá trị mới cho mảng.
Kiểm tra điều kiện thua:
• Lặp qua tất cả các đống để kiểm tra xem có đống nào còn sỏi hay không.
Độ phức tạp: O(N), với N là số lượng đống sỏi.
Vậy tổng cộng, độ phức tạp chính của mã nguồn trò chơi bốc sỏi này là O(N),
với N là tổng số lượng sỏi ban đầu và số lượng đống sỏi. Điều này có nghĩa là độ
phức tạp của chương trình tương ứng với kích thước của dữ liệu đầu vào.
II. Bài tập thực hành trên lớp
1. Đổi tiền (doitien.cpp) a. Mô tả bài toán
Bài toán đổi tiền là một bài toán thực tế và phổ biến, mà chúng ta thường gặp trong
cuộc sống hàng ngày. Bài toán này đặt ra câu hỏi: "Nếu bạn có một số tiền cần trả lOMoAR cPSD| 58490434
lại và một loạt các đồng tiền khác nhau, bạn có thể trả lại số tiền đó bằng cách sử
dụng ít đồng tiền nhất?" Đề bài:
Cho một số tiền cần đổi và một danh sách các đồng tiền có mệnh giá khác nhau, tìm
cách trả lại số tiền cần đổi bằng cách sử dụng ít đồng tiền nhất. b. Giải thích code và
cách giải Hàm greedyCoinChange:
• Đầu vào: amount (số tiền cần đổi) và coins (mảng các đồng tiền có mệnh giá khác nhau).
• Khai báo một vector result để lưu trữ các đồng tiền cần trả lại.
• Khai báo biến coinIndex để lưu chỉ số của đồng tiền mà chúng ta đang xét, bắt
đầu từ đồng tiền lớn nhất. Vòng lặp while:
• Trong khi amount còn lớn hơn 0 và coinIndex còn lớn hơn hoặc bằng 0 (chưa xét hết các đồng tiền).
• Kiểm tra nếu mệnh giá của đồng tiền tại coinIndex nhỏ hơn hoặc bằng amount.
• Nếu điều kiện đúng, chúng ta trừ amount bằng mệnh giá của đồng tiền này và thêm nó vào vector result.
• Nếu điều kiện sai, chúng ta chuyển sang đồng tiền nhỏ hơn bằng cách giảm giá trị của coinIndex. Hàm main:
• Đầu vào: amount và coins đã được khai báo.
• Gọi hàm greedyCoinChange để tìm cách trả lại số tiền amount bằng cách sử dụng
các đồng tiền từ coins.
• Hiển thị số lượng đồng tiền cần trả lại và danh sách đồng tiền bằng phương thức của vector change.
• Với đầu vào là amount = 47 và coins = {10, 5, 1}, kết quả sẽ là 8 đồng tiền (10
10 10 10 5 1 1 1) cần trả lại để tổng cộng là 47 đồng. Ví dụ: lOMoAR cPSD| 58490434
• Giả sử bạn cần trả lại 47 đồng và có các đồng tiền 1, 5 và 10 đồng. Bạn muốn
biết cách trả lại số tiền này bằng số lượng ít đồng tiền nhất.
c. Độ phức tạp giải thuật
Độ phức tạp của bài toán đổi tiền có thể được tối ưu bằng cách sử dụng thuật toán
động (dynamic programming) hoặc phương pháp tham egoái, có độ phức tạp tùy
thuộc vào cách bạn tiếp cận. Trong trường hợp cơ bản, độ phức tạp là O(N), trong
đó N là số tiền cần đổi.
Trong một số trường hợp đặc biệt, bài toán đổi tiền có thể trở nên phức tạp hơn, ví
dụ như khi có các đồng tiền không phải là bội số của nhau hoặc có ràng buộc phức tạp khác.
2. Trò chơi tictactoe (tictactoe.cpp) a. Mô tả bài toán
Trò chơi Tic Tac Toe (còn gọi là X-O) là một trò chơi giữa hai người chơi,
trong đó họ thay phiên nhau đặt các ký hiệu của họ (X hoặc O) vào một lưới 3x3.
Mục tiêu của trò chơi là tạo được một dãy liên tiếp gồm ba ký hiệu của mình (theo
hàng ngang, hàng dọc hoặc đường chéo), hoặc điền hết bảng mà không có ai thắng.
Trò chơi kết thúc khi một người chơi thắng hoặc hết bàn cờ.
b. Giải thích code và cách giải
void drawBoard(const std::vector>& board) {
for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3;
++j) { std::cout << board[i][j]; if
(j < 2) { std::cout << " | "; } } std::cout << std::endl; if (i < 2) {
std::cout << "---------" << std::endl; } } }
Hàm drawBoard được sử dụng để vẽ bàn cờ Tic Tac Toe. Nó duyệt qua mảng
2D board và in ra các ký hiệu 'X', 'O' hoặc khoảng trắng để tạo ra bàn cờ. Dấu | và -
-------- được dùng để vẽ đường phân chia giữa các hàng và các cột. lOMoAR cPSD| 58490434
bool checkWin(const std::vector>& board, char symbol) {
for (int i = 0; i < 3; ++i) { if (board[i][0] == symbol &&
board[i][1] == symbol && board[i][2] == symbol) { return true;
} if (board[0][i] == symbol && board[1][i] == symbol &&
board[2][i] == symbol) { return true; } }
if (board[0][0] == symbol && board[1][1] == symbol && board[2][2] == symbol) { return true;
} if (board[0][2] == symbol && board[1][1] == symbol && board[2][0] == symbol) { return true; } return false; }
Hàm checkWin kiểm tra xem người chơi có thắng trò chơi hay không. Nó duyệt qua
các hàng, cột và đường chéo để kiểm tra xem có ba ký hiệu giống nhau của người
chơi đang được kiểm tra (được truyền qua biến symbol) hay không. int main() {
std::vector> board(3, std::vector(3, ' ')); // Bàn
c 3x3ờ char currentPlayer = 'X'; // Ng i ch i hi n t iườ ơ ệ ạ
std::cout << "Chao mung den voi tictactoe!" << std::endl;
for (int move = 0; move < 9; ++move) { drawBoard(board);
int row, col; std::cout << "Nguoi choi " << currentPlayer << ", nhap hang va cot (02): ";