Bài tập lớn môn: Phân tích thiết kế thuật toán

MỤC LỤC
PHẦN I: MỞ ĐẦU ................................................................................... 3
1.Giới thiệu đề tài................................................................................... 3
2. Mục đích yêu cầu của đề bài .............................................................. 3
2.1. Mục đích ...................................................................................... 3
2.2. Yêu cầu ........................................................................................ 3
3. Phương pháp nghiên cứu ................................................................... 3
PHẦN II: NỘI DUNG .............................................................................. 5
1. Thuật toán Quay Lui .......................................................................... 5
1.1. Giới thiệu thuật toán .................................................................... 5
1.1.1. Khái niệm .............................................................................. 5
1.1.2. Ý tưởng .................................................................................. 5
1.1.3. Demo ..................................................................................... 5
1.2. Bài toán 8 hậu .............................................................................. 6
1.2.1. Giới thiệu ............................................................................... 6
1.2.2. Ý tưởng – Phân tích ............................................................... 6
1.2.3. Thuật toán .............................................................................. 7
1.2.4. Code demo ............................................................................. 8
1.2.5. Kết quả ................................................................................. 10
1.2.6. Nhận xét ............................................................................... 11
2. Nguyên lý thứ tự .............................................................................. 12
2.1. Giới thiệu ................................................................................... 12
2.2. Bài toán phân công công việc .................................................... 13
GVHD: Ths. Trịnh Thị Phú
1
SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán

2.2.1 Giới thiệu .............................................................................. 13
2.2.2. Ý tưởng – Phân tích ............................................................. 13
2.2.3. Thuật toán ............................................................................ 14
2.2.4. Code demo ........................................................................... 16
2.2.5. Kết quả ................................................................................. 21
2.2.6. Nhận xét ............................................................................... 22
3. Quy hoạch động ............................................................................... 22
3.1. Giới thiệu ................................................................................... 22
3.2. Bài toán tam giác số ................................................................... 23
3.2.1. Giới thiệu ............................................................................. 23
3.2.2. Ý tưởng – Phân tích ............................................................. 24
3.2.3. Thuật toán ............................................................................ 24
3.2.4. Code demo ........................................................................... 24
3.2.5. Kết quả ................................................................................. 26
3.2.6. Nhận xét ............................................................................... 26
PHẦN III – KẾT LUẬN ......................................................................... 27
Giáo viên hướng dẫn ............................................................................... 27
Ths. Trịnh Thị Phú .................................................................................. 27
Sinh viên thực hiện.................................................................................. 27
Hoàng Năng Hưng .................................................................................. 27
TÀI LIỆU THAM KHẢO....................................................................... 28

GVHD: Ths. Trịnh Thị Phú

2

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán

PHẦN I: MỞ ĐẦU
1.Giới thiệu đề tài
Trong khoa học máy tính, việc nghiên cứu về thuật toán có vai trò rất
quan trọng vì máy tính chỉ giải quyết được vấn đề khi đã có hướng dẫn giải rõ
ràng và đúng. Nếu hướng dẫn giải sai hoặc không rõ ràng thì máy tính không
thể giải đúng được bài toán. Thuật toán được định nghĩa là một dãy hữu
hạn các bước không mập mờ và có thể thực thi được, quá trình hành động
theo các bước này phải dừng và cho được kết quả như mong muốn. Để có thể
làm được một chương trình, dự án lớn nhất thiết phải cần thuật toán.
Hiện nay có rất nhiều thuật toán để hỗ trợ chúng ta trong việc lập trình.
Trong đó thuật toán quay lui, nguyên lý thứ tự và quy hoạch động rất đáng
được chú ý. Vì vậy, em xin chọn đề tài “Ứng dụng thuật toán quay lui,
nguyên lý thứ tự và quy hoạch động để giải một số bài toán điển hình”.
2. Mục đích yêu cầu của đề bài
2.1. Mục đích
Đề tài này giúp em củng cố, nâng cao kiến thức về môn học cấu trúc dữ
liệu và giải thuật. Từ đó hiểu sâu hơn và vận dụng vào trong các bài toán số
liệu thực tế đồng thời thông qua việc làm đề tài này giúp em biết được các
phương pháp nghiên cứu một vấn đề nhỏ nào đó.
2.2. Yêu cầu
Dùng ngôn ngữ lập trình C/C++ để cài đặt chương trình. Với dữ liệu
được nhập vào từ bàn phím.
3. Phương pháp nghiên cứu
 Tham khảo tài liệu: cấu trúc dữ liệu và giải thuật, trên mạng…
 Tìm hiểu thực tiễn, thực tế, quy cách, nhu cầu của bài toán.
GVHD: Ths. Trịnh Thị Phú
3
SVTH: Hoàng Năng Hưng



Bài tập lớn môn: Phân tích thiết kế thuật toán
 Xin ý kiến, hướng dẫn của giáo viên hướng dẫn.

GVHD: Ths. Trịnh Thị Phú

4

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
PHẦN II: NỘI DUNG
1. Thuật toán Quay Lui
1.1. Giới thiệu thuật toán
1.1.1. Khái niệm
Quay lui (Backtracking) là một kĩ thuật thiết kế giải thuật dựa trên đệ
quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong
số các lựa chọn khả dĩ và đệ quy.
1.1.2. Ý tưởng
Ta giả sử đáp số của bài toán là một bộ có n thành phần (x1,x2,…,xn) và
giả sử đã xác định được i – 1 thành phần x1,x2,…,xi-1. Để xác định xi, ta xét tất
cả các khả năng có thể của xiđánh số các khả năng này là 1,…,ni. Với mỗi khả
năng j của xi ta kiểm tra xem khả năng j có chấp nhận được hay không. Nếu
chấp nhận khả năng j thì xác định xi theo j, sau đó lại xét: nếu i = n thì ta được
1 đáp số, ngược lại tiếp tục xác định xi+1. Khi đã xét tất cả khả năng có thể của
xi, ta lần ngược lại bước trước để xác định một khả năng kế tiếp của xi – 1.
1.1.3. Demo
void Try(int i)
{
for (int j = 1; j < ni; j ++)

{
if ( <Chấp nhận j >)
{
<Xác định xi theo j>
if (i==n)
<Ghi nhận cấu hình>;
GVHD: Ths. Trịnh Thị Phú

5

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
else Try(i + 1);
}
}
}
1.2. Bài toán 8 hậu
1.2.1. Giới thiệu
Là bài toán đặt tám quân hậu trên bàn cờ vua kích thước 8 × 8 sao cho
không có quân hậu nào có thể "ăn" được quân hậu khác, hay nói khác đi
không quân hậu nào có để di chuyển theo quy tắc cờ vua.
1.2.2. Ý tưởng – Phân tích
Lời giải của bài toán là một cách xếp tám quân hậu trên bàn cờ sao cho
không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đường
chéo. Bài toán tám quân hậu có thể tổng quát hóa thành bài toán đặt n quân
hậu trên bàn cờ n × n (n ≥ 4).
Do yêu cầu của bài toán là tìm các vị trí để đặt n quân hậu nên thay vì sử
dụng mảng 2 chiều ta chỉ cần sử dụng mảng một chiều h[0..n - 1] trong

đó h[i] thuộc đoạn [0..n - 1] là vị trí (cột) của quân hậu thứ i. Với ví dụ ở trên
hình mảng h sẽ là: [3 6 2 7 2 4 1 5] (quân hậu hàng 0 sẽ ở cột 3, quân hậu
hàng 1 sẽ ở cột 6,..
Trong quá trình thử (đệ quy - quay lui), ta sẽ lần lượt đặt quân hậu tại
một số vị trí trong bàn cờ. Mỗi lần thử đặt một quân hậu tại một ô nào đó thì
phải đánh dấu các ô trong hàng, cột và hai đường chéo đi qua ô vừa đặt để các
lần thử tiếp theo không đặt quân hậu nào khác vào các ô này (vì chũng đã bị
khống chế bởi 1 quân hậu).

GVHD: Ths. Trịnh Thị Phú

6

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
Để tiện trong việc trình bày ý tưởng cũng như lập trình, ta sẽ ký hiệu các
đường chéo chính (theo hướng tây nam - đông bắc) và các đường chéo phụ
(theo hướng tây bắc - đông nam) như hình 2. Ta thấy ô (i, j) sẽ thuộc:
 Đường chéo chính có số thứ tự là (i + j).
 Đường chéo phụ có số thứ tự là (i - j + n).
Mỗi lần đặt một con hậu tại vị trí (i, j) nào đó, ta phải đánh dấu các ô trên
hàng i, cột j, đường chéo chính (i + j) và đường chéo phụ (i - j + n) để sau này
không được đặt con hậu nào vào những vị trí này. Do đó, thay vì phải lưu
phần đánh dấu cho tất cả các ô trên bàn cờ (nghĩa là cần một mảng n x n), ta
chỉ cần đánh dấu cho các hàng, cột, đường chéo chính và đường chéo phụ
tương ứng (nghĩa là cần hai mảng một chiều n phần tử để đánh dấu các hàng,
cột và cần thêm hai mảng một chiều 2n+1 phần tử để đánh dấu các đường
chéo).

1.2.3. Thuật toán
B1: Khai báo toàn cục biến n = 8, 1 mảng A[n], 1 mảng cot[n], 2 mảng đường
chéo chính, đường chéo phụ.
B2: Viết hàm vẽ bàn cờ và xuất kết quả:
B2.1: In ra số phương án kết quả
B2.2: Duyệt i chạy từ 0 -> n -1
B2.2.1: Duyệt j chạy từ 0 -> A[i] – 1
B2.2.1.1: In ra ký tự “ – “
B2.2.2: In ra ký tự “ H” (ký hiệu thay cho quân Hậu)
B2.3: Duyệt j chạy từ A[i] + 1 -> n
B2.3.1: In ra ký tự “ – “. Xuống dòng.
GVHD: Ths. Trịnh Thị Phú

7

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
B3: Viết hàm Try():
B3.1: Duyệt j chạy từ 0 -> n – 1
B3.1.1: Nếu cot[j] && cheoChinh[i + j] && cheoPhu[j - i + n]
B3.1.1.1: Gán A[i] = j, cot[j] = 0;
B3.1.1.2: Gán cheoChinh[i + j] = 0, cheoPhu[j - i + n] = 0;
B3.1.1.3: Nếu i == n thì gọi hàm xuat()
B3.1.1.4: Ngược lại thì try(i + 1)
B3.1.1.5: cot[j] = 1, cheoChinh[i + j] = 1, cheoPhu[j - i +
n] = 1;
B4: Viết hàm main():
B4.1: Duyệt i chạy từ 0 -> n – 1

B4.1.1: Gán cot[i] = 1;
B4.2: Duyệt i chạy từ 0 -> 2 * n – 1
B4.2.2: Gán cheoChinh[i] = 1, cheoPhu[i] = 1;
B4.3: Gọi hàm Try()
1.2.4. Code demo
Code được viết bằng ngôn ngữ C++ trên nền IDE Code::Blocks
#include <iostream>
#define n 8
int A[n], dem = 0;
char cot[n];
char cheoChinh[2 * n - 1], cheoPhu[2 * n - 1];
GVHD: Ths. Trịnh Thị Phú

8

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
void xuat()
{
int i, j;
std::cout << "Phuong an " << ++dem << std::endl;;
for (i = 0; i < n; i++)
{
for (j = 0; j < A[i]; j++)
std::cout << " -";
std::cout << " H";
for (j = A[i] + 1; j < n; j++)
std::cout << " -";

std::cout << std::endl << std::endl;
}
}
void Try(int i)
{
for (int j = 0; j < n; j++)
{
if (cot[j] && cheoChinh[i + j] && cheoPhu[j - i + n] == 1)
{
A[i] = j;
cot[j] = 0;
cheoChinh[i + j] = 0;
cheoPhu[j - i + n] = 0;
if (i == n - 1)
xuat();
else
Try(i + 1);
cot[j] = 1;
GVHD: Ths. Trịnh Thị Phú

9

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
cheoChinh[i + j] = 1;
cheoPhu[j - i + n] = 1;
}
}

}
int main()
{
int i;
for (i = 0; i{
cot[i] = 1;
}
for (i = 0; i< 2 * n; i++)
{
cheoChinh[i] = 1;
cheoPhu[i] = 1;
}
Try(0);
return 0;
}

1.2.5. Kết quả

Đây là 1 số kết quả từ màn hình Console:

GVHD: Ths. Trịnh Thị Phú

10

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán

1.2.6. Nhận xét
Có một giải thuật đơn giản tìm một lời giải cho bài toán n quân hậu
với n = 1 hoặc n ≥ 4:
 Chia 8 cho 12 lấy số dư r. (r = 8 với bài toán tám quân hậu).
 Viết lần lượt các số chẵn từ 2 đến n.
 Nếu số dư r là 3 hoặc 9, chuyển 2 xuống cuối danh sách.


Bổ sung lần lượt các số lẻ từ 1 đến n vào cuối danh sách, nhưng

nếu r là 8, đổi chỗ từng cặp nghĩa là được 3, 1, 7, 5, 11, 9, …
 Nếu r = 2, đổi chỗ 1 và 3, sau đó chuyển 5 xuống cuối danh sách.
GVHD: Ths. Trịnh Thị Phú

11

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
 Nếu r = 3 hoặc 9, chuyển 1 và 3 xuống cuối danh sách.


Lấy danh sách trên làm danh sách chỉ số cột, ghép vào danh sách

chỉ số dòng theo thứ tự tự nhiên ta được một lời giải của bài toán.
Bài toán tám quân hậu có 92 lời giải khác nhau. Nếu không phân biệt các
lời giải là ảnh của nhau qua phép đối xứng, phép quay bàn cờ thì chúng chỉ có
12 lời giải đơn vị. Với code ở bên trên ta hoàn toàn có thể chuyển thành bài
toán xếp hậu tổng quát bằng cách thay giá trị của n.

2. Nguyên lý thứ tự
2.1. Giới thiệu
Thuật giải Heuristic là một sự mở rộng khái niệm thuật toán. Nó thể hiện
cách giải bài toán với các đặc tính sau :
 Thường tìm được lời giải tốt (nhưng không chắc là lời giải tốt nhất).
 Giải bài toán theo thuật giải Heuristic thường dễ dàng và nhanh chóng
đưa ra kết quả hơn so với giải thuật tối ưu, vì vậy chi phí thấp hơn.
Thuật giải Heuristic thường thể hiện khá tự nhiên, gần gũi với cách suy
nghĩ và hành động của con người.
Có nhiều phương pháp để xây dựng một thuật giải Heuristic, trong đó
người ta thường dựa vào một số nguyên lý cơ sở như sau :
Nguyên lý vét cạn thông minh:
Trong một bài toán tìm kiếm nào đó, khi không gian tìm kiếm lớn, ta thường
tìm cách giới hạn lại không gian tìm kiếm hoặc thực hiện một kiểu dò tìm đặc
biệt dựa vào đặc thù của bài toán để nhanh chóng tìm ra mục tiêu.
Nguyên lý tham lam (Greedy):

GVHD: Ths. Trịnh Thị Phú

12

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
Lấy tiêu chuẩn tối ưu (trên phạm vi toàn cục) của bài toán để làm tiêu chuẩn
chọn lựa hành động cho phạm vi cục bộ của từng bước (hay từng giai đoạn)
trong quá trình tìm kiếm lời giải.
Nguyên lý thứ tự :
Thực hiện hành động dựa trên một cấu trúc thứ tự hợp lý của không gian khảo

sát nhằm nhanh chóng đạt được một lời giải tốt.
2.2. Bài toán phân công công việc
2.2.1 Giới thiệu
Một công ty nhận được hợp đồng gia công m chi tiết máy J1, J2,...,Jm.
Công ty có n máy gia công lần lượt là P1, P2, ...Pn. Mọi chi tiết đều có thể
được gia công trên bất kỳ máy nào. Một khi đã gia công một chi tiết trên một
máy, công việc sẽ tiếp tục cho đến lúc hoàn thành, không thể bị ngắt ngang.
Ðể gia công một công việc Ji trên một máy bất kỳ ta cần dùng một thời gian
tương ứng là ti. Nhiệm vụ của công ty là phải làm sao gia công xong toàn bộ n
chi tiết trong thời gian sớm nhất.
2.2.2. Ý tưởng – Phân tích
Xây dựng một thuật toán để tìm một phương án tối ưu L0 cho bài toán
này là một bài toán khó, đòi hỏi các kỹ thuật phức. Bây giờ ta xét đến một
thuật giải Heuristic rất đơn giản để giải bài toán này. Các bước thực hiện :
 Sắp xếp các công việc theo thứ tự giảm dần về thời gian gia công.
 Lần lượt sắp xếp các việc theo thứ tự đó vào máy còn dư nhiều thời
gian nhất.

GVHD: Ths. Trịnh Thị Phú

13

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
2.2.3. Thuật toán
B1: Tạo 1 struct công việc gồm thời gian để hoàn thành công việc và chỉ số
kiểu int.
B2: Tạo 1 struct may có lồng struct congViec + Tổng thời gian và số công

việc máy đã làm.
B3: Viết hàm nhập thời gian cho các công việc:
B3.1: Duyệt i chạy từ 0 -> n – 1
Nhập thời gian cho công việc.
Gán cV[i].chiSo = i + 1.
B4: Viết hàm xuất thông tin các công việc:
B4.1: Duyệt i chạy từ 0 -> n – 1
B4.2: In ra chỉ số công việc và thời gian công việc.
B5: Viết một hàm hoán vị công việc
B5.1: Hoán vị thời gian công việc.
B5.2: Hoán vị chỉ số công việc.
B6: Viết hàm sắp xếp công việc:
B6.1: Duyệt i chạy từ 0 -> n – 2, i++
B6.1.1: Duyệt j chạy từ i + 1 -> soCongViec – 1, j++
B6.1.1.1: Gọi hàm hoán vị công việc.
B7: Viết hàm khởi tạo máy:
B8: Viết hàm tìm máy có thời gian làm việc ít nhất:
B8.1: Gán int temp = 0, min = may[0].tongThoiGian;
GVHD: Ths. Trịnh Thị Phú
14
SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
B8.2: Duyệt i chạy từ 1 -> soMay – 1, i++
B8.2.2: Nếu min > may[i].tongThoiGian thì:
min = may[i].tongThoiGian;
temp = i;
B8.3: Trả về temp.
B9: Viết hàm chia công việc cho các máy:

B9.1: Duyệt i chạy từ 0 -> soCongViec – 1, i++
B9.1.1: Chọn máy có thời gian làm việc ít nhất.
B9.1.2: Thêm các công việc tiếp theo.
B10: Viết hàm xuất kết quả:
B10.1: Gán max = may[0].tongThoiGian;
B10.2: Duyệt i chạy từ 0 -> soMay, i++
B10.2.1: Nếu max < may[i].tongThoiGian thì gán lại.
B10.2.2: In ra tổng thời gian thực hiện và tổng thời gian hoàn
thành.
B11: Viết hàm main():
B11.1: Nhập số lượng máy, công việc:
B11.2:

Gọi

lần

lượt

các hàm khoiTaoMay, nhapCongViec,

sapXepCongViec, xuatCongViec, chiaCongViec, xuatKetQua.

GVHD: Ths. Trịnh Thị Phú

15

SVTH: Hoàng Năng Hưng

Bài tập lớn môn: Phân tích thiết kế thuật toán
2.2.4. Code demo

#include <iostream>
#define MAX 100

struct congViec
{
int thoiGian;
int chiSo;
};

struct May
{
int tongThoiGian;
int soCongViec;
congViec cV[MAX];
};

// Nhap thoi gian cho cac cong viec
void nhapCongViec(congViec cV[], int soCongViec)
{
int i;
for(i = 0; i < soCongViec; i++)
{
std::cout << "Nhap thoi gian cho cong viec thu " << i + 1 <<
":";
cV[i].chiSo = i + 1;
std::cin >> cV[i].thoiGian;
GVHD: Ths. Trịnh Thị Phú

16

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
}
}

// Xuat thong tin cac cong viec
void xuatCongViec(congViec cV[], int soCongViec)
{
int i;
for(i = 0; i < soCongViec; i++)
{
std::cout << " [" << cV[i].chiSo << "] = " << cV[i].thoiGian;
}
}

void hoanViCongViec(congViec &cV1, congViec &cV2)
{
congViec temp;
temp.thoiGian = cV1.thoiGian;
cV1.thoiGian = cV2.thoiGian;
cV2.thoiGian = temp.thoiGian;
temp.chiSo = cV1.chiSo;
cV1.chiSo = cV2.chiSo;
cV2.chiSo = temp.chiSo;
}

void sapXepCongViec(congViec cV[], int soCongViec)
{
int i, j;
for(i = 0; i < soCongViec - 1; i++)
for(j = i + 1; j < soCongViec; j++)
if(cV[i].thoiGian < cV[j].thoiGian)
GVHD: Ths. Trịnh Thị Phú

17

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
hoanViCongViec(cV[i], cV[j]);
}

void khoiTaoMay(May may[], int soMay)
{
int i;
for(i = 0; i < soMay; i++)
{
may[i].tongThoiGian = 0;
may[i].soCongViec = 0;
}
}
int mayLamItNhat(May may[], int soMay)
{
int i, temp = 0;
int min = may[0].tongThoiGian;

for(i = 1; i < soMay; i++)
{
if(min > may[i].tongThoiGian)
{
min = may[i].tongThoiGian;
temp = i;
}
}
return temp;
}
void chiaCongViec(May may[], int soMay, congViec cV[], int
soCongViec)
{
GVHD: Ths. Trịnh Thị Phú

18

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
int temp, k, i;
for(i = 0; i < soCongViec; i++)
{
temp = mayLamItNhat(may, soMay);
k = may[temp].soCongViec;
may[temp].tongThoiGian += cV[i].thoiGian;
may[temp].cV[k].thoiGian = cV[i].thoiGian;
may[temp].cV[k].chiSo = cV[i].chiSo;
may[temp].soCongViec ++;

}
}
void xuatKetQua(May may[], int soMay)
{
int i, j;
int max = may[0].tongThoiGian;
for(i = 0; i < soMay; i++)
{
if(max < may[i].tongThoiGian)
max = may[i].tongThoiGian;
std::cout << std::endl << "May " << i + 1 << ":";
std::cout << std::endl << "Tong thoi gian thuc hien: " <<
may[i].tongThoiGian;
std::cout << std::endl <<"Thuc hien cac cong viec : ";
for(j = 0; j < may[i].soCongViec; j++)
{
std::cout << "[" << may[i].cV[j].chiSo << "] ";
}
}
std::cout << std:: endl << "\nThoi gian de hoan thanh cac cong
GVHD: Ths. Trịnh Thị Phú

19

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
viec la : " << max << " h" << std::endl;
}

int main()
{
congViec cV[MAX];
May may[MAX];
int soMay, soCongViec;

std::cout << "Bai toan phan viec" << std::endl;
do
{
std::cout << "Nhap so may: ";
std::cin >> soMay;
if(soMay < 0 || soMay > 100)
std::cout << "\nLoi. Moi ban nhap lai!";
}
while(soMay < 0 || soMay > 100);

do
{
std::cout << "Nhap so cong viec: ";
std::cin >> soCongViec;
if(soCongViec < 0 || soCongViec > 100)
std::cout << "\nLoi. Moi ban nhap lai!";
}
while(soCongViec < 0 || soCongViec > 100);

GVHD: Ths. Trịnh Thị Phú

20

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
khoiTaoMay(may, soMay);
nhapCongViec(cV, soCongViec);
sapXepCongViec(cV, soCongViec);
std::cout << "\nCac cong viec duoc sap theo thoi gian giam dan:
" << std::endl;
xuatCongViec(cV, soCongViec);
chiaCongViec(may, soMay, cV, soCongViec);
xuatKetQua(may, soMay);
std::cout << std::endl;
return 0;
}
2.2.5. Kết quả
Đây là 1 kết quả từ màn hình Console:
Nếu trường hợp có 3 máy P1, P2, P3 và 6 công việc với thời gian là t1 = 2,
t2 = 5, t3 = 8, t4 = 1, t5 = 5, t6 = 1. ta có một phương án phân công như sau :

GVHD: Ths. Trịnh Thị Phú

21

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
2.2.6. Nhận xét
Phướng án kia đúng, nhưng vẫn chưa tối ưu hết mức. Nếu gọi T* là thời

gian để gia công xong n chi tiết máy do thuật giải Heuristic đưa ra và T0 thời
gian tối ưu thì người ta đã chứng minh được rằng:

T* 4 1
 
To 3 M
với M là số máy. Với kết quả này, ta có thể xác lập được sai số mà chúng ta
phải gánh chịu nếu dùng Heuristic thay vì tìm một lời giải tối ưu. Chẳng hạn
với số máy là 2 (M = 2) ta có:

T*
7

To
6
và đó chính là sai số cực đại mà trường hợp ở trên đã gánh chịu. Theo công
thức này, số máy càng lớn thì sai số càng lớn.
Trong trường hợp M lớn thì tỷ số 1/ M xem như bằng 0 . Như vậy, sai
số tối đa là 33%. Tuy nhiên, khó tìm ra được những trường hợp mà sai số
đúng bằng giá trị cực đại, dù trong trường hợp xấu nhất. Thuật giải Heuristic
trong trường hợp này rõ ràng đã cho chúng ta những lời giải tương đối tốt.
3. Quy hoạch động
3.1. Giới thiệu
Trong quá trình học tập, chúng ta gặp rất nhiều các bài tập về Toán - Tin.
Các bài tập dạng này rất phong phú và đa dạng. Thực tế chưa có thuật toán
hoàn chỉnh có thể áp dụng cho mọi bài toán. Tuy nhiên người ta đã tìm ra một
số thuật toán chung như chia để trị, tham ăn, quay lui,... Các thuật toán này có
thể áp dụng để giải một lớp khá rộng các bài toán hay gặp trong thực tế. Tiếp

GVHD: Ths. Trịnh Thị Phú

22

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
theo em muốn đề cập thêm một thuật toán nữa đó là thuật toán quy hoạch
động. Tư tưởng cơ bản của thuật toán là:
Để giải một bài toán ta chia bài toán đó thành các bài toán nhỏ hơn có
thể giải một cách dễ dàng. Sau đó kết hợp lời giải các bài toán con, ta có được
lời giải bài toán ban đầu. Trong quá trình giải các bài toán con đôi khi ta gặp
rất nhiều kết quả trùng lặp của các bài toán con. Để tăng tính hiệu quả, thay vì
phải tính lại các kết quả đó, ta lưu chúng vào một bảng. Khi cần lời giải của
một bài toán con nào đó ta chỉ cần tim trong bảng, không cần tính lại.
Tư tưởng của thuật toán quy hoạch động khá đơn giản. Tuy nhiên khi áp
dụng thuật toán vào trường hợp cụ thể lại không dễ dàng. Khi giải bài toán
bằng phương pháp này, chúng ta phải thực hiện hai yêu cầu quan trọng sau:


Tìm công thức truy hồi xác định nghiệm bài toán qua nghiệm các

bài toán con nhỏ hơn.


Với mỗi bài toán cụ thể, ta đề ra phương án lưu trữ nghiệm một

cách hợp lý để từ đó có thể truy cập một cách thuận tiện nhất.
3.2. Bài toán tam giác số
3.2.1. Giới thiệu

Hình dưới đây biểu diễn một tam giác số:

Hãy viết chương trình tính tổng lớn nhất các số trên con đường bắt đầu
từ đỉnh và kết thức ở đáy.
 Mỗi bước có thể đi chéo xuống phía trái hoặc đi chéo xuống phía phải.
 Số lượng hàng trong tam giác lớn hơn 1 nhưng bé hơn 100.
 Các số trong tam giác đều là các số nguyên từ 0 đến 99.
GVHD: Ths. Trịnh Thị Phú
23
SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
3.2.2. Ý tưởng – Phân tích
Xem tam giác đề bài là một ma trận có dòng 1 là a[1][1], dòng 2 là
a[2][1] a[2][2],...dòng n là a[n][1], a[n][2],…, a[n][n] gọi F[i][j] là tổng lớn
nhất của 1 đường đi từ đỉnh tam giác xuống ô a[i][j] , vì để đến a[i][j] chúng
ta có thể đi từ a[i - 1][j - 1] hoặc a[i - 1][j] nên công thức quy hoạch động là:
F[i][j] = max(F[i - 1][j], F[i - 1][j - 1]) + a[i][j]
3.2.3. Thuật toán
B1: Nhập số dòng tam giác.
B2: Khai báo mảng mảng 2 chiều là tam giác.
B3: Nhập dòng 1.
B4: Duyệt i chạy từ 2 -> n
B4.1: Nhập a[i][1] và gán a[i][1] = a[i][1] + a[i - 1][1]
B4.2: Duyệt j chạy từ 2 -> i – 1
B4.2.1: Nhập a[i][j]
B4.2.2: Nếu a[i - 1][j - 1] > a[i - 1][j] thì
a[i][j] = a[i][j] + a[i - 1][j - 1]
B4.2.3: Ngược lại a[i][j] = a[i][j]+a[i - 1][j]

B4.3: Nhập a[i][i] và gán a[i][i] = a[i][i] + a[i - 1][i - 1]
B5: Gán max = a[n][1]
B6: Duyệt j chạy từ 2 -> n
B6.1: Nếu a[n][j]> max thì max = a[n][j]
B7: In kết quả
3.2.4. Code demo
#include <iostream>
int main()
{
int n;
do
GVHD: Ths. Trịnh Thị Phú

24

SVTH: Hoàng Năng Hưng


Bài tập lớn môn: Phân tích thiết kế thuật toán
{
std::cout << "Nhap so dong: ";
std::cin >> n;
if(n < 1 || n >= 100)
std::cout << "Ban nhap qua gioi han so dong!" << std::endl;
}
while(n < 1 || n >= 100);

int a[n + 1][n + 1];
std::cin >> a[1][1];

for(int i = 2; i <= n; i++)
{
std::cin >> a[i][1];
a[i][1] = a[i][1] + a[i - 1][1];
for(int j = 2; j < i; j++)
{
std::cin >> a[i][j];
if(a[i - 1][j - 1] > a[i - 1][j])
a[i][j] = a[i][j] + a[i - 1][j - 1];
else
a[i][j] = a[i][j]+a[i - 1][j];
}
std::cin >> a[i][i];
a[i][i] = a[i][i] + a[i - 1][i - 1];
}

int max = a[n][1];

GVHD: Ths. Trịnh Thị Phú

25

SVTH: Hoàng Năng Hưng