Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải)

 Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
Gồm một dòng duy nhất là đáp án cần tìm 
Ví dụ: 
Input: 
5 3 
10 30 40 50 20 
Output: 30
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
Câu 1: (4.0 điểm) Sử dụng chiến lược tham lam để giải bài toán sau: 
a. Mô tả cách làm
Để tim số nhỏ nhất, ta áp dụng chiến lược tham lam (Greedy) theo các quy tắc sau:
- Kiểm tra điều kiện: Nếu 푠 > 9 × hoặc ( 푠 = 0 và > 1 ), bài toán không có lời giải (trả 
về -1). Nếu 푠 = 0 và = 1, kết quả là 0 .
- Khởi tạo: Giữ lại 1 đơn vị cho chữ số đầu tiên (hàng cao nhất) để đảm bảo số có đúng 
chữ số (không bắt đầu bằng số 0). Khi đó, tổng còn lại cẩn phân bổ là 푠 ―1.
- Phân bổ từ phải sang trải: Duyệt từ hàng đơn vị ( ―1) ngược về hàng thứ hai (1). Tại mỗi 
vị trí, ta điền chữ số lớn nhất có thể, tức là value = min(푠,9). Sau đó cập nhật 푠 = 푠 ― 
value.
- Hoàn tất chữ số đầu tiên: Sau khi điền xong ―1 chữ số từ bên phải, giá trị còn lại của 푠 
cộng với 1 đơn vị đã giữ lại ban đầu sẽ là chữ số đầu tiên.
b. Phân tích đánh giá độ phức tạp của thuật toán. 
Độ phức tạp thời gian: Thuật toán thực hiện một vòng lặp duy nhất từ ―1 đến 1 để xác 
định các chữ số. Do đó, độ phức tạp thời gian là ( ).
Độ phức tạp không gian: Chúng ta sử dụng một mảng hoặc chuỗi có kích thước để lưu trữ 
kết quả, vì vậy độ phức tạp không gian là ( ).
c. Cài đặt (.cpp)
#include
using namespace std;
void findSmallest(int s, int d) {
if (s == 0) {
(d == 1) ? cout << 0 : cout << -1;
return;
}
if (s > 9 * d) {
cout << -1;
return;
}
vector res(d);
s -= 1; // Giữ lại 1 cho chữ số đầu tiên
for (int i = d - 1; i > 0; i--) {
if (s > 9) {
res[i] = 9;
s -= 9;
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
} else {
res[i] = s;
s = 0;
}
}
res[0] = s + 1; // Chữ số đầu tiên
for (int i = 0; i < d; i++) cout << res[i];
}
int main() {
int s, d;
if(cin >> s >> d) findSmallest(s, d);
return 0;
}
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: 
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. 
Gọi [푖] là chi phí nhỏ nhất để chú ếch nhảy từ hòn đá thứ 1 đến hòn đá thứ 푖. Để đến được 
hòn đá 푖, chú ếch phải nhảy từ một trong các hòn đá trước đó là 푗 ∈ {푖 ―1,푖 ―2, ,푖 ― } với 
điều kiện 푗 ≥ 1. Bài toán lớn tìm [푛] được chia thành các bài toán con tìm [푖] với 푖 < 푛.
b. Giải bài toán con cơ sở. 
Tại hòn đá xuất phát (viên đá thứ 1), chi phí để chú ếch đứng tại đó là:
 [1] = 0
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. 
Để tìm [푖], ta xét tất cả các vị trí 푗 mà từ đó có thể nhảy một bước tới 푖. Mối liên hệ được 
xác định bởi:
 [푖] = min   [푗] + |ℎ푖 ― ℎ푗|
 max(1,푖 ― ) ≤ 푗 < 푖
Trong đó |ℎ푖 ― ℎ푗| là chi phí nhảy từ hòn đá 푗 sang hòn đá 푖.
d. Lập bảng phương án dựa trên công thức đã tìm. 
Ta sử dụng một mảng một chiều kích thước 푛 +1. Bảng phương án được lấp đầy tuần tự 
từ 푖 = 2 đến 푛. Với mỗi 푖, ta duyệt qua tối đa trạng thái trước đó để tìm giá trị nhỏ nhất.
e. Truy vết. 
Để tìm con đường mà chú ếch đã đi, ta dùng một mảng trace [푖] để lưu chỉ số 푗 đã tối ưu hóa 
giá trị cho [푖].
- Khi tính [푖], nếu chọn được 푗 thỏa mãn công thức min, ta gán trace [푖] = 푗.
- Truy vết ngược từ 푛:푛→trace[푛]→trace[trace[푛]] →1.
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
f. Cài đặt. 
#include 
#include 
#include 
#include 
using namespace std;
const int INF = 1e9;
int main() {
 int n, k;
 if (!(cin >> n >> k)) return 0;
 vector h(n + 1);
 for (int i = 1; i > h[i];
 vector dp(n + 1, INF);
 dp[1] = 0;
 for (int i = 2; i <= n; i++) {
 for (int j = 1; j <= k; j++) {
 if (i - j >= 1) {
 dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
 }
 }
 }
 cout << dp[n] << endl;
 return 0;
}
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
 ĐỀ SỐ 7
 TRƯỜNG ĐẠI HỌC SÀI GÒN ĐỀ THI KẾT THÚC HỌC PHẦN
 Môn: Phân tích & thiết kế giải thuật
 ĐỀ 1
 Thời gian: 90 phút (không kể thời gian giao đề)
Câu 1. (2,0 điểm)
a. Cho các hàm số f(n) = log3 n2 và g (n) = log4 n, đổi số n nguyên dương. Chứng minh f(n) 
và g(n) có cùng độ tăng.
 2
b. Cho hàm số T (n) = n(n+1) + 2nlog2 n, đổi số n nguyên dương, chứng minh T (n) = O (n ).
Câu 2. (2,0 điểm) Cho a là một số thực khác không, n là một số nguyên không âm. Tính độ 
phức tạp của giải thuật sau.
Pow(a,n)
1. if n = 0 return 1
2. else t ← Pow(a,⌊n/2⌋)
3. if n mod 2 = 0 //n chia hết cho 2
4. return t^* t
5. else return t^* t^* a
Câu 3. (4,0 điểm) Cho n số thực x1, x2, ,xn. Khoảng cách giữa hai số thực xi và xj được 
định nghīa là |xi – xj|. Hai số xi và xj được gọi là cặp số gần nhau nhất nếu khoảng cách giữa 
chúng là nhỏ nhất trong tất cả các khoảng cách giữa các cặp số trong các số x1, x2, ,xn.
a. Áp dụng chiến lược thiết kế trực tiếp, viết một giải thuật để tính khoảng cách giữa cặp số 
gần nhau nhất trong n số đã cho.
b. Áp dụng các chiến lược thiết kế thích hợp, viết một giải thuật hiệu quả hơn giải thuật đã 
viết trong câu a để tính khoảng cách giữa cặp số gần nhau nhất trong n số đã cho.
c. Tính độ phức tạp về thời gian của các giải thuật đã viết ở câu a và b.
Câu 4. (2 điểm) Một số đồng xu được đặt trong một bảng kích thước n x m, mỗi ô chỉ có 
nhiều nhất một đồng xu. Một robot di chuyển từ ô (1,1) đến ô (n, m), mỗi bước di chuyển đi 
được một ô, đến ô bên phải hoặc ô phía dưới (không di chuyển theo các đường chéo của 
bảng). Khi robot đến một ô có đồng xu nó luôn luôn nhặt đồng xu đó. Ký hiệu C0 là số đồng 
xu có trong ô (i, j), i = 1, ,n và j = 1, .m.
a. Thiết lập hệ thức truy hồi tính số đồng xu nhiều nhất mà robot có thể nhặt được khi di 
chuyển từ ô (1,1) đến ô (n, m)
b. Viết giải thuật qui hoạch động để tính số đồng xu nhiều nhất mà robot có thể nhặt được 
khi đến ô (n, m) dựa trên hệ thức truy hồi đã thiết lập trong câu a.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
Câu 1. (2,0 điểm)
 2ln 4
a. Vì là một hằng số dương khác không, nên và có cùng độ tăng .
 ln 3 (푛) (푛) (Θ(log 푛))
 2
b. Ta có: (푛) = 푛 + 푛 +2푛log2 푛. Theo định nghĩa ký hiệu Big-O, ta cẩn tìm > 0 và 푛0 
 2
sao cho (푛) ≤ .푛 với mọi 푛 ≥ 푛0.
Với 푛 ≥ 1, ta luôn có:
 • 푛 ≤ 푛2
 2
 • log2 푛 < 푛⇒2푛log2 푛 < 2푛
 2 2 2 2 2
Do đó: (푛) ≤ 푛 + 푛 +2푛 = 4푛 Chọn = 4 và 푛0 = 1. Vậy (푛) = (푛 ).
Câu 2. (2,0 điểm) Ta có hệ thức truy hồi: (푛) = (⌊푛/2⌋) + Θ(1)
Theo định lý Master (hoặc phương pháp thế), với = 1, = 2, (푛) = 1:푛log = 푛log2 1 =
푛0 = 1. Vi (푛) = Θ(1), nên trường hợp 2 của định lý Master xảy ra: (푛) = Θ(log 푛).
Câu 3. (4,0 điểm) 
a. Giải thuật trực tiếp (Brute-force): Duyệt qua tất cả các cặp số ( 푖, 푗 ) và tính khoảng cách.
b. Giải thuật hiệu quả hơn (Sử dụng Sắp xếp): Chiến lược: Sắp xếp dãy số tǎng dần, khi đó 
cặp số gần nhau nhất chắc chắn là hai số đứng cạnh nhau.
c. Độ phức tạp thời gian:
 푛(푛 1)
- Giải thuật a: Sử dụng 2 vòng lặp lổng nhau, số cặp là . Độ phức tạp là 2 .
 2 (푛 )
- Giải thuật b: * Bước sắp xếp tốn (푛log 푛) (nếu dùng QuickSort hoạ̌c MergeSort).
- Bước duyệt một vòng lặp tốn (푛).
- Tổng độ phức tạp là (푛log 푛).
Câu 4. (2 điểm)
a. Hệ thức truy hồi: Gọi 퐹(푖,푗) là số đổng xu tối đa robot nhặt được khi đến ô (푖,푗). Để đến 
được ô (푖,푗), robot chỉ có thể đi từ ô phía trên (푖 ―1,푗) hoặc ô bên trái (푖,푗 ―1). Hệ thức truy 
hồi:
퐹(푖,푗) = max{퐹(푖 ― 1,푗),퐹(푖,푗 ― 1)} + 푖푗
Với điều kiện biên:
- 퐹(1,1) = 11
- 퐹(1,푗) = 퐹(1,푗 ―1) + 1푗 với 푗 > 1 (hàng đầu tiên)
- 퐹(푖,1) = 퐹(푖 ―1,1) + 푖1 với 푖 > 1 (cột đầu tiên)
b. Giải thuật Quy hoạch động:
Giả sử chúng ta có một bảng kích thước 3x4 với vị trí các đồng xu (Cij) như sau
Kết luận: Số đồng xu nhiều nhất Robot nhặt được là 3.
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
 ĐỀ SỐ 8
 TRƯỜNG ĐẠI HỌC ĐỀ THI CUỐI KỲ II
 CÔNG NGHỆ THÔNG TIN 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 đề)
PHẦN 1: PHÂN TÍCH THUẬT TOÁN
Câu 1 (3 điểm). (G1.)
a. Hãy dùng định nghĩa của các ký hiệu tiệm cận (không dùng định lý, không dùng lim) để 
chứng minh các nhận định sau:
 • Nếu (푛) ∈ ( (푛)) và (푛) ∈ ( (푛)) thì ( (푛)) = ( (푛))
 1
 • (푛log 푛 ― 2푛 + 8) = Ω 푛log 푛
 2 2 2
b. Hãy sắp xếp 07 hàm số bên dưới theo thứ tự tăng dần của "order of growth", và có giải 
thích ngắn gọn cách thực hiện. Ký hiệu: log là log cơ số 2, là số Pi .
 푛 log 푛
 1(푛) = 푛 5(푛) = 푛
 4 푛2
 2(푛) = 푛(log 푛) 6(푛) = 2
 푛 푛
 푛/2
 3(푛) =        푖푗 7(푛) = 푛3
 푖=1 푗=1
 푛1/2
 4(푛) = 
Câu 2 (3 điểm) (G2.)
2.1. Cho giải thuật sau đây:
function(double a[], int n) // a[0..n-1] là mảng gồm n số thực
{
 QuickSort(a,0,n-1); // sắp xếp mảng a
 for ( j=1 to n-1)
 D[ j-1 ]=a[ j ] - a[ j-1 ]; //D là mảng chứa các số thực
 min=0;
 for ( j=1 to n-2)
 if ( D[j ]<D[min ])
 min=j;
 print a[min], a[min+1]; // in ra màn hình 2 giá trị
}
Yêu cầu: 
a. Lời gọi hàm function (a,n) sẽ trả về (hay in ra màn hình) kết quả là thông tin gì?
b. Hãy phân tích độ phức tạp của giải thuật trên.
2.2. Xét một giải thuật đệ quy như sau:
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
waste (n)
{
 if(n==0) return 0;
 for( i=1 to n)
 for( j=1 to n)
 print i,j,n;
 for( i=1 to 3)
 waste(n/2);
} 
Yêu cầu:
a. Thành lập phương trình đệ quy (hay còn gọi là hệ thức truy hồi) của giải thuật nêu trên, 
kèm giải thích ngắn gọn cách thành lập.
b. Giải phương trình đệ quy để xác định độ phức tạp của giải thuật trên dùng phương pháp 
truy hồi, còn gọi là thay thế (Backward substitution) hoặc dùng phương pháp đoán nghiệm 
(Guessing and Induction).
Lưu ý: Đối với phương pháp đoán nghiệm, có thể dùng định lý Master để đoán một nghiệm 
f(n) và dùng chứng minh quy nạp để chứng tỏ rằng (푛) ≤ (푛),∀푛.
PHẦN 2: THIẾT KẾ THUẬT TOÁN
Câu 3 (2 điểm) (G3.)
Bài toán "Các dãy con tăng có tổng cho trước" được mô tả như sau: Cho một dãy số nguyên 
dương ( 0, 1, , 푛―1) và một số nguyên dương M. Tìm tất cả các dãy con tăng của dãy số 
đã cho sao cho tổng của các phần tử trong dãy con bằng M. Biết rằng, dãy con của một dãy 
số là dãy có được sau khi loại bỏ bớt một hay một số phần tử và vẫn duy trì thứ tự (trước, 
sau) như trong dãy ban đầu. Ví dụ, cho dãy (7,1,4,3,5,6) và M = 11, các dãy con thỏa mãn 
ràng buộc là (1, 4, 6) và (5,6).
Yêu cầu: Hãy thiết kế một thuật toán để giải bài toán trên bằng phương pháp Quay lui 
(Backtracking). Thuật toán phải được trình bày dưới dạng mã giả, có chú thích và minh hoạ 
qua ví dụ trên cho người đọc dễ hiểu.
SV CHİ CHỌN LÀM 1 TRONG 2 CÂU BÊN DƯỚI (CÂU 4 HOẶC CÂU 5)
Câu 4 (2 điểm) (G 3. )
Cho bài toán được mô tả như sau: Cho một số nguyên dương có n chữ số, hãy tìm cách xóa 
đi k chữ số trong số nguyên trên sao cho kết quả thu được là một số nhỏ nhất có thể. Ví dụ, 
cho số 2070880 nếu phải xóa đi 2 chữ số thì số nhỏ nhất thu được là 880 (xóa số 2 đầu tiên 
và số 7 ), hoặc cho số 27819 , nếu phải xóa 2 chữ số thì kết quả của bài toán là 219 .
Yêu cầu: Trình bày ý tưởng và thuật toán để giải bài toán trên bằng phương pháp Tham lam 
(Greedy). Thuật toán phải được trình bày dưới dạng mã giả, có chú thích và minh hoạ qua 
các ví dụ trên cho người đọc dễ hiểu.
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
Câu 5 (2 điểm) (G 3.)
Cho một dãy các số nguyên a gồm n phần tử, tìm một dãy con dài nhất của a thỏa điều kiện 
"hai phần tử liền kề chênh nhau một đơn vị". Ví dụ, cho dãy a gồm các phần tử là {9, 
8,3,4,3,7,5}, những dãy con dài nhất có hiệu giữa các phần tử liền kề nhau là một có thể là 
{9,8,7},{3,4,3},{3,4,5}.
Yêu cầu: Trình bày ý tưởng và thuật toán để giải bài toán trên bằng phương pháp Quy hoạch 
động (Dynamic Programming). Trình bày ý tưởng gồm các bước: 
1) Thành lập phương trình quy hoạch động; 
2) Tạo bảng lưu trữ kết quả của các bài toán con khi giải lần đầu; 
3) Xác định lời giải của bài toán ban đầu. Minh họa các bước thực hiện của cách giải đã đề 
xuất cho dãy a gồm 14 phần tử là {4,1,3,8,9,6,2,7,5,3,10,6,3,4}.
 ----------HẾT----------
 De-Thi.com Bộ đề ôn thi môn Phân tích & Thiết kế giải thuật (Có lời giải) - De-Thi.com
 ĐÁP ÁN
PHẦN 1: PHÂN TÍCH THUẬT TOÁN
Câu 1 (3 điểm).
a. Chứng minh bằng định nghĩa các ký hiệu tiệm cận
*Chứng minh nếu 품(풏) ∈ 푶(풇(풏)) và 풇(풏) ∈ 푶(품(풏)) thì 푶(풇(풏)) = 푶(품(풏)):
- Theo định nghĩa ( (푛)), vì (푛) ∈ ( (푛)) nên tổn tại hằng số 1 > 0 và 푛1 sao cho 
(푛) ≤ 1. (푛) với mọi 푛 ≥ 푛1.
- Vì (푛) ∈ ( (푛)), tồn tại hằng số 2 > 0 và 푛2 sao cho (푛) ≤ 2. (푛) với mọi 푛 ≥ 푛2.
- Từ hai điều trên, ta thấy (푛) và (푛) có cùng tốc độ tăng (tức là (푛) = Θ( (푛)) ).
- Do đó, tập hợp các hàm bị chặn trên bởi (푛) cũng chính là tập hợp các hàm bị chặn trên 
bởi (푛). Vậy ( (푛)) = ( (푛)).
*Chứng 퐦퐢퐧퐡(풏퐥퐨퐠 풏 ― 풏 + ) = 훀 풏퐥퐨퐠 풏 :
 1
- Ta cần tìm hằng số > 0 và 푛 sao cho 푛log 푛 ―2푛 +8 ≥ . 푛log 푛 với mọi 푛 ≥ 푛 .
 0 2 2 2 0
 2 8
 푛log2 푛 2푛 8 1
 log 푛 푛log 푛
- Xét giới hạn: 1 2 2 .
 lim  푛log2 푛 = lim  = 2
 푛→∞ 2 푛→∞ 1/2
- Vì giới hạn bằng 2 (một hằng số dương), theo định nghĩa tiệm cận, hàm số bên trái luôn lớn 
hơn hoạ̌c bằng một tỉ lệ hằng số của hàm số bên phải khi 푛 đủ lớn. Cụ thể, ta có thể chọn 
= 1 và 푛0 đủ lớn để thỏa mãn điều kiện.
b. Sắp xếp các hàm số theo thứ tự tǎng dần của "order of growth"
Thứ tự sắp xếp từ tǎng chậm nhất đến tăng nhanh nhất:
 푛1/2
1. 4(푛) = : Hàm mũ với số mũ căn bậc hai (tăng chậm nhất trong nhóm các hàm mũ).
 푛
2. 1(푛) = 푛: Hàm này hội tụ về 1 khi 푛→∞ (tăng rất chậm).
 4
3. 2(푛) = 푛(log 푛) : Hàm đa thức nhân với logarit.
 푛 푛 푛 푛
 1
4. : Giá trị tổng này xấp xỉ 4 (bậc đa thức 4 ).
 3(푛) =    푖푗     ≈ 4푛 푛
 푖=1 푗=1 1 1
 log 푛
5. 5(푛) = 푛 : Hàm siêu đa thức (tǎng nhanh hơn mọi đa thức nhưng chậm hơn hàm mũ 
cơ số hằng số).
 푛/2
6. 7(푛) = 푛 ⋅ 3 : Hàm mũ cơ số 3 ≈ 1.732.
 푛2
7. 6(푛) = 2 : Hàm mũ có số mũ là bình phương (tăng nhanh nhất).
Câu 2 (3 điểm).
2.1 Phân tích giải thuật function(double [], int n)
a. Ẏ nghĩa của lời gọi hàm:
*Thuật toán thực hiện các bước:
- Sắp xếp mảng tăng dần bằng QuickSort .
 De-Thi.com