15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật

 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
cout << arr[i] << " "; 
 } 
cout << endl; 
} 
int main() { 
int arr[] = {4, 7, 2, 10, 15, 14, 8, 10, 8, 5}; 
int n = sizeof(arr) / sizeof(arr[0]); 
cout << "Mang truoc khi sap xep: "; 
printArray(arr, n); 
bubbleSort(arr, n); 
cout << "Mang sau khi sap xep: "; 
printArray(arr, n); 
return 0; 
} 
- Đánh giá độ phức tạp: 
Thuật toán Bubble Sort lặp qua mảng và so sánh từng cặp phần tử liền kề. Tổng số lần lặp 
của thuật toán là n (số lượng phần tử trong mảng). 
Mỗi lần lặp, thuật toán thực hiện n−i−1 lần so sánh (với i là số lần lặp bên ngoài). 
Do đó, tổng số so sánh là:
 푛―2
 ∑푖=0  (푛 ― 푖 ― 1) = (푛 ― 1) + (푛 ― 2) +  + 1
Đây là tổng của dãy số hạng từ 1 đến n−1, tức là (n×(n−1))/2, có thể gọi là O(n2) trong 
trường hợp trung bình và trường hợp xấu nhất. 
Vì vậy, độ phức tạp thời gian của Bubble Sort là O(n2). 
Câu 4: Bài toán “Cái ba lô” 
Phương án: 
- Gọi X=(X1, X2, , Xn) với Xi là số nguyên không âm, là một phương án. 
- Xi là số đồ vật thứ i 
- Cần tìm X sao cho: 
X1g1+ X2g2 +  + Xngn <=W 
F(X) = X1v1 + X2v2 +  + Xnvn => Max 
Ta có:
- W = 53 - X = (Xa, Xb, Xc, Xd) 
Xa = 53/18 = 2 => Trọng lượng còn lại là: 53-2*18 = 17 
Xb = 17/10 = 1 => Trọng lượng còn lại là: 17-1*10 = 7 
Xc = 7/4 = 1 => Trọng lượng còn lại là: 7=1*4 = 3 
Xd = 3/2 = 1 => Trọng lượng còn lại là: 3-1*2 = 1 
Ta có: X = (2, 1, 1, 1) 
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
Vậy với ba lô đã cho ta có thể mang được: 
2 đồ vật A; 1 đồ vật B; 1 đồ vật C; 1 đồ vật D 
Tổng trọng lượng có thể mạng là: 2*18 + 1*10 + 1*4 + 1*2 = 52 < W 
Tổng giá trị tương ứng ba lô mang được là: 2*30 + 1*24 + 1*9 + 1*3 = 96
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 ĐỀ SỐ 5
 TRƯỜNG ĐH GIAO THÔNG ĐỀ THI KẾT THÚC HỌC PHẦN
 VẬN TẢI – TP.HCM Môn: Phân tích & thiết kế giải thuật
 Thời gian: 90 phút (không kể thời gian giao đề)
 ĐỀ 1
Lưu ý: Phần phân tích, diễn giải, mô tả, làm nộp trên file PDF, source code nộp file .cpp 
Câu 1: (4.0 điểm) Sử dụng chiến lược tham lam để giải bài toán sau: 
Cho một tập hợp n công việc trong đó mỗi công việc i có thời hạn di >=1 và lợi nhuận 
pi>=0. Mỗi lần chỉ có thể thực hiện một công việc. Mỗi công việc mất 1 đơn vị thời gian để 
hoàn thành. Lợi nhuận kiếm được khi và chỉ khi công việc được hoàn thành đúng thời hạn. 
Nhiệm vụ là tìm ra tập hợp con các công việc lợi nhuận đạt cao nhất. 
Yêu cầu: 
a. Mô tả cách làm. 
b. Phân tích đánh giá độ phức tạp của thuật toán. 
c. Cài đặt. 
Input:
 Mã công việc di pi
A 2 100
B 1 19
C 2 27
D 1 25
E 3 15
Output: C, A, E
Câu 2: (6.0 điểm) Sử dụng chiến lược quy hoạch động để giải bài toán sau: 
Bờm chơi trò chơi điện tử Lucky Luke đến màn phải điều khiển Lucky leo lên một cầu thang 
gồm N bậc. Các bậc thang được đánh số từ 1 đến N từ dưới lên trên. Lucky có thể đi lên một 
bậc thang, hoặc nhảy một bước lên hai bậc thang. Tuy nhiên một số bậc thang đã bị thủng do 
cũ kỹ và Lucky không thể bước chân lên được. Biết ban đầu, Lucky đứng ở bậc thang số 1 
(bậc thang số 1 không bao giờ bị thủng). Chơi đến đây, Bờm chợt nảy ra câu hỏi: có bao 
nhiêu cách để Lucky leo hết được cầu thang? (nghĩa là leo đến bậc thang thứ N). Bờm muốn 
nhờ bạn trả lời câu hỏi này. 
Yêu cầu: 
a. Phân tích, phân rã bài toán ban đầu về bài toán con cùng dạng và có kích thước nhỏ hơn. 
b. Giải bài toán con cơ sở. 
c. Xây dựng công thức, tìm mối liên hệ từ bài toán con với bài toán tổng quát hơn. 
d. Lập bảng phương án dựa trên công thức đã tìm. 
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
e. Truy vết. 
f. Cài đặt. 
Input 
Dòng đầu tiên: gồm 2 số nguyên N và K, là số bậc của cầu thang và số bậc thang bị hỏng (0 
< K < N < 105). 
Dòng thứ hai: gồm K số nguyên cho biết chỉ số của các bậc thang bị hỏng theo thứ tự tăng 
dần. 
Output 
In ra phần dư của số cách Lucky leo hết cầu thang.
 ----------HẾT----------
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 ĐÁP ÁN
Câu 1: (4.0 điểm)
a. Mô tả cách làm (Chiến lược Tham lam)
Đề đạt được lợi nhuận cao nhất, chúng ta cần ưu tiên các công việc có lợi nhuận ( 푖 ) lớn 
nhất và xếp chúng vào thời điểm muộn nhất có thể trong phạm vi thời hạn ( 푖) của chúng. 
Việc này giúp để dành các khoảng thời gian sớm hơn cho các công việc có thời hạn ngắn 
hơn.
Các bước thực hiện:
- Sắp xếp: Danh sách các công việc theo thứ tự lợi nhuận giảm dần.
- Khởi tạo: Tìm thời hạn lớn nhất ( _ ) để tạo một mảng các "khung giờ" (slots) trống 
từ 1 đến _ .
- Lựa chọn (Tham lam): Duyệt qua từng công việc đã sắp xếp:
- Tìm một khung giờ trống 푡 sao cho 푡 ≤ 푖 và 푡 là lớn nhất có thể.
- Nếu tìm thấy, đạ̌t công việc đó vào khung giờ 푡 và đánh dấu khung giờ này đã bị chiếm.
- Nếu không tìm thấy khung giờ nào trống trước 푖, bỏ qua công việc đó.
b. Phân tích đánh giá độ phức tạp
- Độ phức tạp thời gian:
- Sắp xếp các công việc: (푛log 푛).
- Duyệt qua 푛 công việc và tìm khung giờ trống: Trong trường hợp xấu nhất, mỗi công việc 
ta phải kiểm tra lại tất cả các khung giờ từ 푖 về 1 . Do đó, vòng lặp lồng nhau tốn (푛 × 
max_d ).
- Tổng quát: (푛2) nếu sử dụng mảng đánh dấu đơn giản. (Có thể tối ưu xuống (푛log 푛) 
bằng cấu trúc dữ liệu Disjoint Set Union - DSU).
- Độ phức tạp không gian: (푛) đề lưu trữ danh sách công việc và mảng các khung giờ.
c. Cài đặt (.cpp)
#include 
#include 
#include 
#include 
using namespace std;
// Cấu trúc lưu trữ thông tin công việc
struct Job {
 char id; // Mã công việc
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 int dead; // Thời hạn (deadline)
 int profit; // Lợi nhuận (profit)
};
// Hàm so sánh để sắp xếp lợi nhuận giảm dần
bool compare(Job a, Job b) {
 return (a.profit > b.profit);
}
void jobScheduling(Job arr[], int n) {
 // Bước 1: Sắp xếp theo lợi nhuận giảm dần
 sort(arr, arr + n, compare);
 vector result(n); // Mảng lưu kết quả các công việc được chọn
 vector slot(n, false); // Mảng đánh dấu các khung giờ đã bị chiếm
 // Bước 2 & 3: Duyệt qua từng công việc
 for (int i = 0; i < n; i++) {
 // Tìm khung giờ trống từ deadline trở về trước
 // (Sử dụng min(n, arr[i].dead) - 1 để tránh vượt quá chỉ số mảng)
 for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {
 if (slot[j] == false) {
 result[j] = arr[i].id; // Thêm mã công việc vào kết quả
 slot[j] = true; // Đánh dấu khung giờ đã được sử dụng
 break;
 }
 }
 }
 // In kết quả theo đúng thứ tự thời gian
 bool first = true;
 for (int i = 0; i < n; i++) {
 if (slot[i]) {
 if (!first) cout << ", ";
 cout << result[i];
 first = false;
 }
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 }
 cout << endl;
}
int main() {
 // Khởi tạo dữ liệu Input
 Job arr[] = { 
 {'A', 2, 100}, 
 {'B', 1, 19}, 
 {'C', 2, 27}, 
 {'D', 1, 25}, 
 {'E', 3, 15} 
 };
 int n = sizeof(arr) / sizeof(arr[0]);
 cout << "Ket qua cac cong viec thuc hien: ";
 jobScheduling(arr, n);
 return 0;
}
Câu 2: (6.0 điểm) 
a. Phân tích, phân rã bài toán:
 • Gọi 퐹[푖] là số cách để Lucky leo lên bậc thang thứ 푖(1 ≤ 푖 ≤ ).
 • Để tới bậc 푖, Lucky chỉ có thể đi từ bậc 푖 ―1 (lên 1 bậc) hoặc 푖 ―2 (lên 2 bậc).
 • Nếu bậc 푖 bị hỏng: 퐹[푖] = 0.
 • Nếu bậc 푖 an toàn: 퐹[푖] = 퐹[푖 ―1] + 퐹[푖 ―2].
 • Bài toán lớn 퐹[ ] được phân rã thành các bài toán con 퐹[푖] nhỏ hơn.
 b. Giải bài toán con cơ sở:
 • Bắt đầu: Lucky đứng ở bậc 1: 퐹[1] = 1.
 • Bậc 2: Nếu bậc 2 hỏng, 퐹[2] = 0. Nếu an toàn, 퐹[2] = 퐹[1] = 1 (chỉ có thể đi từ bậc 1 
 lên).
 • 퐹[0] = 0 (bậc 0 không tồn tại).
c. Công thức truy hồi:
Với 푖 từ 2 đến :
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 0 nu 푖 hng 
 퐹[푖] = (퐹[푖 ― 1] + 퐹[푖 ― 2]) (mod109 + 7) nu 푖 an toàn 
d. Lập bảng phương án (Ví dụ = 5, hỏng bậc 3):
 • 퐹[1] = 1
 • 퐹[2] = 퐹[1] = 1
 • 퐹[3] = 0 (hỏng)
 • 퐹[4] = 퐹[3] + 퐹[2] = 0 + 1 = 1
 • 퐹[5] = 퐹[4] + 퐹[3] = 1 + 0 = 1
Kết quả: 퐹[5] = 1.
e. Truy vết:
Không cẩn truy vết cụ thể từng bước đi, chỉ cần tính giá trị 퐹[ ] dựa trên bảng đã xây dựng 
từ 1 đến .
f. Cài đặt (.cpp)
#include 
#include 
using namespace std;
int main() {
 int N, K;
 cin >> N >> K;
 vector hỏng(N + 1, false);
 for (int i = 0; i < K; ++i) {
 int t;
 cin >> t;
 hỏng[t] = true;
 }
 vector F(N + 1, 0);
 long long MOD = 1e9 + 7;
 if (hỏng[1]) { // Bậc 1 không bao giờ hỏng theo đề
 cout << 0 << endl;
 return 0;
 }
 F[1] = 1;
 for (int i = 2; i <= N; ++i) {
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 if (hỏng[i]) {
 F[i] = 0;
 } else {
 F[i] = (F[i - 1] + F[i - 2]) % MOD;
 }
 }
 cout << F[N] << endl;
 return 0;
}
 DeThiHay.net 15 Đề thi và Đáp án Phân tích và Thiết kế giải thuật - DeThiHay.net
 ĐỀ SỐ 6
 TRƯỜNG ĐH GIAO THÔNG ĐỀ THI KẾT THÚC HỌC PHẦN
 VẬN TẢI – TP.HCM Môn: Phân tích & thiết kế giải thuật
 ĐỀ 2 Thời gian: 90 phút (không kể thời gian giao đề)
Lưu ý: Phần phân tích, diễn giải, mô tả, làm nộp trên file PDF, source code nộp file .cpp 
Câu 1: (4.0 điểm) Sử dụng chiến lược tham lam để giải bài toán sau: 
Tìm số nhỏ nhất có tổng chữ số s và số chữ số d ? 
Ví dụ 1: 
Đầu vào: s = 9, d = 2 
Đầu ra: 18 
Có thể có rất nhiều con số khác như 45, 54, 90, v.v. với tổng các chữ số là 9 và số chữ số là 
2. Nhỏ nhất trong số đó là 18. 
Ví dụ 2: 
Đầu vào: s = 20, d = 3 
Đầu ra: 299 
Yêu cầu: 
a. Mô tả cách làm. 
b. Phân tích đánh giá độ phức tạp của thuật toán. 
c. Cài đặt. 
Câu 2: (6.0 điểm) Sử dụng chiến lược quy hoạch động để giải bài toán sau: 
Cho n viên đá, viên đá thứ i có độ cao là ℎ푖. Con ếch đang đứng tại viên đá thứ nhất. Tại vị trí 
thứ i con ếch có thể nhảy sang 1 trong k hòn đá thứ i+1, i+2,,i+k với chi phí nhảy là 
|ℎ푖 − ℎ푗| với j là vị trí đáp của chú ếch. Hãy tìm chi phí ngắn nhất để chú ếch tới được hòn đá 
thứ n. 
Yêu cầu: 
a. Phân tích, phân rã bài toán ban đầu về bài toán con cùng dạng và có kích thước nhỏ hơn. 
b. Giải bài toán con cơ sở. 
c. Xây dựng công thức, tìm mối liên hệ từ bài toán con với bài toán tổng quát hơn. 
d. Lập bảng phương án dựa trên công thức đã tìm. 
e. Truy vết. 
f. Cài đặt. 
Input 
Dòng đầu gồm n là số lượng hòn đá và số k (1 ≤ n ≤ 105,1 ≤ k ≤ 100) 
Dòng sau gồm có n số, số thứ i thể hiện hi là chiều cao của viên đá thứ i (1 ≤ ℎ푖 ≤ 104) 
Output 
 DeThiHay.net