Bài giảng Toán rời rạc - Nguyễn Lê Minh

Toán rời rạc 
Chương 1: THUẬT TOÁN 
GV: Nguyễn Lê Minh 
Bộ môn: Công nghệ thông tin 
12/3/2021 
1 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
2 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
3 
1. Khái niệm thuật toán 
Thuật toán là một tập hữu hạn các bước, các phép toán cơ bản được sắp xếp theo một trình tự nhất định để từ thông tin đầu vào của bài toán sau một tập hữu hạn các bước đó sẽ đạt được kết quả ở đầu ra như mong muốn. 
Input 
Algorithm 
Output 
12/3/2021 
4 
1. Khái niệm thuật toán 
Thông thường, thuật toán dùng để giải một lớp các bài toán cụ thế. Gồm 2 thành phần chính: 
Input : Thông tin bài toán đã cho 
Output : Thông tin cần tìm hoặc trả lời câu hỏi cần thiết 
Ví dụ: 
S = a *b 
12/3/2021 
5 
1. Khái niệm thuật toán 
Ví dụ : Giải phương trình bậc nhất P(x): a x + b = 0 , ( a , b là các số thực) 
Input : a, b 
Output : Kết quả P(x) 
Mô tả thuật toán: 
Nếu a = 0 
Nếu b = 0 thì P(x) có nghiệm bất kì 
Nếu b 0 thì P(x) vô nghiệm 
Nếu a 0 
P(x) có duy nhất một nghiệm x = -b/a 
12/3/2021 
6 
1. Khái niệm thuật toán 
Ví dụ 2 : Kiểm tra một số nguyên X có chia hết cho 5 không ? 
Input : X 
Output : Kết quả kiểm tra Result 
Mô tả thuật toán: 
Bước 1: Tìm số dư r của phép chia x cho 5 
Bước 2: Kiểm tra 
Nếu r = 0 thì result = True 
Nếu r 0 thì result = False 
12/3/2021 
7 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
8 
2 . Tính chất của thuật toán 
Tính dừng 
Tính xác định 
Tính đúng 
Ðầu vào và đầu ra (input/output) 
Tính hiệu quả 
Tính tổng quát 
12/3/2021 
9 
2 . Tính chất của thuật toán 
Tính dừng : T huật toán phải bao đảm được kết thúc sau một số hữu hạn bước . 
Tính dừng là tính dễ bị vi phạm, thường là do sai sót khi trình bày thuật toán dẫn đến “ L ặp vô tận ”. 
12/3/2021 
10 
2 . Tính chất của thuật toán 
Thuật toán phải có tính xác định : các bước trong thuật toán phải được xác định rõ ràng, có thể thực thi được, không gây mập mờ, nhập nhằn g , tùy chọn. 
12/3/2021 
11 
2 . Tính chất của thuật toán 
Thuật toán phải có T ính đúng đắn : để đảm bảo kết quả tính toán hay các thao tác mà máy tính thực hiện được là chính xác. 
Trong một kỳ thi kiểm tra không phải tất cả các học sinh điều đưa ra được lời giải “ đúng ”. 
Khi thiết kế thuật toán cần kiểm nghiệm và chỉnh sửa nhiều lần để có được một thuật toán đúng. 
12/3/2021 
12 
2 . Tính chất của thuật toán 
Ðầu vào và đầu ra (input/output): M ọi thuật toán đều có đại lượng vào và ra. 
Tính hiệu quả: Một bài toán có thể có nhiều thuật toán khác nhau để giải, một thuật toán tốt thì nó phải hiệu quả, tính hiệu quả của thuật toán được đánh giá dựa trên một số tiêu chuẩn như khối lượng tính toán , không gian và thời gian khi thuật toán được thi hành. 
Tính tổng quát: T huật toán có tính tổng quát là thuật toán phải áp dụng được cho mọi trường hợp của bài toán chứ không phải chỉ áp dụng được cho một số trường hợp riêng lẻ nào đó. 
12/3/2021 
13 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
14 
3. Các cách biểu diễn của thuật toán 
Sơ đồ khối 
Liệt kê 
Mã giả 
12/3/2021 
15 
3. Các cách biểu diễn của thuật toán 
Phương pháp liệt kê 
Tại mỗi bước sử dụng ngôn ngữ tự nhiên để diễn tả công việc phải làm. 
Các bước được đánh số thứ tự, bước có số thứ tự nhỏ hơn được thực hiện trước. 
Ưu điểm: Dễ hiểu, dễ thực hiện. 
Khuyết điểm: P hụ thuộc cách trình bày của người thiết kế , khó áp dụng cho những thuật toán có tính phức tạp. 
12/3/2021 
16 
3. Các cách biểu diễn của thuật toán 
Ví dụ : Giải phương trình b ậ c nhất P(x): ax +b = 0 : 
Input: a,b 
Output: Kết quả giải phương trình. 
Bước 1 : Nhập vào 2 số thực a, b 
Bước 2 : Kiểm tra nếu a = 0 thực hiện: 
Bước 2.1 : Nếu b = 0 thì phương trình vô số nghiệm 
Bước 2.2 : Nếu b 0 thì phương trình vô nghiệm 
Bước 3 : Khi a 0 phương trình có nghiệm x=-b/a 
Bước 4 : Kết thúc thuật toán 
12/3/2021 
17 
3. Các cách biểu diễn của thuật toán 
Phương pháp sơ đồ khối 
Sử dụng các hình khối để biểu diễn các lệnh hay thao tác. 
Sử dụng mũi tên để biểu diễn thứ tự thực hiện. 
Ưu điểm: D iễn đạt khoa học, có tính nhất quán, dễ hiểu và dễ kiểm tra. 
Khuyết điểm: P hải vẽ nhiều hình, cồng kềnh, không phù hợp với các thuật toán phức tạp. 
12/3/2021 
18 
3. Các cách biểu diễn của thuật toán 
Hình 
Ý nghĩa 
Bắt đầu thuật toán 
Kết thúc thuật toán 
Nhập dữ liệu 
Xuất dữ liệu 
Begin 
End 
Input 
Out put 
12/3/2021 
19 
3. Các cách biểu diễn của thuật toán 
Hình 
Ý nghĩa 
Câu lệnh rẽ nhánh 
Nếu đúng thì thực hiện nhánh Đ 
Nếu sai thì thực hiện nhánh S 
Biểu diễn thực hiện công việc A 
Biểu diễn việc gọi chương trình con A 
Hướng của thuật toán 
End 
Biểu thức 
Đ 
S 
A 
A 
12/3/2021 
20 
3. Các cách biểu diễn của thuật toán 
12/3/2021 
21 
3. Các cách biểu diễn của thuật toán 
12/3/2021 
22 
3. Các cách biểu diễn của thuật toán 
Phương pháp mã giả 
Dựa trên các ngôn ngữ bậc cao (Pascal, C...) 
Sử dụng ngôn ngữ tự nhiên con người 
Ưu điểm: T ương tự ngôn ngôn ngữ lập trình và ngôn ngữ tự nhiên , chuyển từ thuật toán sang chương trình dễ dàng. 
Khuyết điểm: Viết như cách biểu diễn liệt kê, khó bao quát với những bài toán nhiều chương trình. Phải làm quen với những ngôn ngữ mới. 
12/3/2021 
23 
3. Các cách biểu diễn của thuật toán 
Ví dụ: Tính tổng n số tự nhiên đầu tiên 
Nhập n 
i :=0 
s :=0 
REPEAT 
	s=s+i ; 
	 	i=i+1 ; 
UNTIL (i>n) 
Xuất s 
12/3/2021 
24 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
25 
3. Các cấu trúc cơ bản của thuật toán 
Rẽ nhánh 
Tuần tự 
Lặp 
12/3/2021 
26 
4 . Các cấu trúc cơ bản của thuật toán 
Cấu trúc tuần tự: 
Gồm nhiều bước, sắp xếp theo trình tự nhất định, chương trình được thực hiện theo các bước đã tạo sẵn. 
Trong biểu diễn thuật toán bằng phương pháp liệt kê từng bước cấu trúc tuần tự được thể hiện ở việc mô tả cụ thể bước thứ i thực hiện: Bước 1, Bước 2, Bước 2.1, . . 
Khi dùng sơ đồ khối ta sử dụng	 để biểu diễn thứ tự thực hiện của thuật toán. 
12/3/2021 
27 
4 . Các cấu trúc cơ bản của thuật toán 
Cấu trúc rẽ nhánh: 
Là cấu trúc kiểm tra một điều kiện, khi điều kiện đúng chương trình sẽ thực hiện theo nhánh đúng, khi điều kiện sai chương trình sẽ thực hiện theo nhánh sai. 
12/3/2021 
28 
4 . Các cấu trúc cơ bản của thuật toán 
Cấu trúc lặp: 
Là cấu trúc lặp đi lặp lại một hành động nhiều lần: 
Số lần lặp xác định trước. 
Số lần lặp không xác định trước. 
12/3/2021 
29 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
30 
4 . Một số thuật toán cơ bản 
Tính chu vi và diện tích hình tròn 
Cho 3 số a,b,c. In ra màn hình 3 số sau khi đã cộng thêm 1 
Nhập n. Nếu n>0, in ra màn hình n sau khi bình phương 
Tính tổng dãy số p = 1+2+3+...+n 
Tính tích dãy số p = 1x2x3x...xn 
Tìm n min thỏa mãn S = 1 + ½ + 1/3 + ... + 1/n >= 3 
12/3/2021 
31 
4 . Một số thuật toán cơ bản 
Kiểm tra xem N có phải là 1 số nguyên tố không ? 
Ý tưởng : 
Nếu N=1 -> N không là số nguyên tố 
Nếu 14 -> N là số nguyên tố 
Nếu N >= 4 : Tìm ước i > 1 của N 
	 + Nếu i N không phải số nguyên tố ( vì N có ít nhất 3 ước N, i, 1) 
	 + Nếu i=N -> N là số nguyên tố 
12/3/2021 
32 
4 . Một số thuật toán cơ bản 
Tính tổng dãy số 
Tính tích dãy số 
Tìm kiếm một số có trong dãy hay không 
Đếm số lượng phần tử thỏa mãn điều kiện 
Tìm giá trị max, min 
Sắp xếp tăng, giảm dãy số 
12/3/2021 
33 
4 . Một số thuật toán cơ bản 
Tính tổng: Cho dãy n phần tử a 1 ,a 2 ,a 3 .... a n Hãy tính tổng ra dãy số trên 
Ý tưởng: 
Sử dụng một biến để tính tổng các phần tử. Ban đầu biến này bằng 0. 
- Duyệt từng phần tử và cộng phần tử vào biến tổng. 
12/3/2021 
34 
4 . Một số thuật toán cơ bản 
12/3/2021 
35 
4 . Một số thuật toán cơ bản 
Tính tổng: Cho dãy n phần tử a 1 ,a 2 ,a 3 .... a n Hãy tính tích ra dãy số trên 
Ý tưởng: tương tự như thuật toán tính tổng 
Sử dụng một biến để tính tích các phần tử. Ban đầu biến này bằng 1 (nếu biến ban đầu bằng 0 thí tích sẽ bằng 0 sai). 
Duyệt từng phần tử và nhân phần tử vào biến tích. 
12/3/2021 
36 
4 . Một số thuật toán cơ bản 
Tính tổng: Cho dãy n phần tử a 1 ,a 2 ,a 3 .... a n Kiểm tra số X có nằm trên dãy trên hay không ? 
Ý tưởng: 
Sử dụng một biến để đánh đánh dấu xem có tìm thấy phần tử X hay không. Ban đầu biến đánh dấu có giá trị là FALSE. 
Duyệt từng phần tử, nếu phần tử thứ i có giá trị bằng X thì gán biến đánh dấu là TRUE. 
12/3/2021 
37 
4 . Một số thuật toán cơ bản 
12/3/2021 
38 
4 . Một số thuật toán cơ bản 
Tính tổng: Cho dãy n phần tử a 1 ,a 2 ,a 3 .... a n Đếm xem trong dãy có bao nhiêu phần tử thỏa mãn điều kiện nào đó. 
Ý tưởng: 
Sử dụng một biến đếm số lượng phần tử 
Duyệt từng phần tử. 
Kiểm tra phần tử đó có thỏa điều kiện hay không, nếu thỏa điều kiện thì tăng biến đếm lên 1. 
12/3/2021 
39 
4 . Một số thuật toán cơ bản 
12/3/2021 
40 
4 . Một số thuật toán cơ bản 
Đếm số chẵn 
12/3/2021 
41 
4 . Một số thuật toán cơ bản 
Tính tổng: Cho dãy n phần tử a 1 ,a 2 ,a 3 .... a n Tìm phần tử Max – Min trong dãy số. 
Ý tưởng: 
Sử dụng một biến lưu giá trị max (min), ban đầu max = a 1 
Duyệt từng phần tử. 
Kiểm tra phần tử đó có lớn hơn biến giá trị max (nhỏ hơn giá trị min) nếu thỏa điều kiện biến max bằng phần tử đó. 
12/3/2021 
42 
4 . Một số thuật toán cơ bản 
Tìm max 
12/3/2021 
43 
4 . Một số thuật toán cơ bản 
Tính tổng: Cho dãy n phần tử a 1 ,a 2 ,a 3 .... a n Sắp xếp dãy số tăng giảm 
Ý tưởng: 
Duyệt từng phần tử: 
Phần tử đang duyệt được gọi là phần tử hiện tại 
Thực hiện một vòng lặp con, duyệt các phần tử còn lại. Nếu giá trị của phần tử được duyệt trong vòng lặp con bé hơn phần tử hiện tại thực hiện việc đổi ch ỗ 2 phần tử. 
12/3/2021 
44 
4 . Một số thuật toán cơ bản 
Tăng dần 
12/3/2021 
45 
Nội dung 
Khái niệm thuật toán 
Tính chất của thuật toán 
Các cách biểu diễn thuật toán 
Cấu trúc cơ bản của thuật toán 
Một số thuật toán cơ bản 
Bài tập 
12/3/2021 
46 
5. Bài tập 
1. V ẽ s ơ đồ khối biể u diễ n 	 t h uậ t to á n t ín h t rung bình cộng d ã y 	 số a 1 ,a 2 ,a 3 ,.,a n 
2. Vẽ sơ đồ thuật toán kiểm tra xem số N có phải là số nguyên tố hay không ? 
3. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a 1 ,a 2 ,a 3 ,.,a n , sắp xếp và in ra màn hình dãy số tăng dần. 
4. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a 1 ,a 2 ,a 3 ,.,a n , in ra màn hình dãy số theo chiều ngược lại . 
5. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a 1 ,a 2 ,a 3 ,.,a n , xuất ra màn hình 3 số âm lớn nhất trong dãy. 
6. Vẽ sơ đồ khối biểu diễn thuật toán nhập dãy số a 1 ,a 2 ,a 3 ,.,a n , tìm và in ra màn hình số xuất hiện nhiều lần nhất trong dãy trên. 
12/3/2021 
47