Giáo trình Nhập môn tin học - Phần II: Thuật toán

Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
1 
TRƯỜNG ĐẠI HỌC XÂY DỰNG 
KHOA CÔNG NGHỆ THÔNG TIN 
------------  ------------ 
GIÁO TRÌNH 
MÔN HỌC: NHẬP MÔN TIN HỌC 
PHẦN II – THUẬT TOÁN 
Giảng viên: ĐÀO TĂNG KIỆM 
Bộ môn : TIN HỌC XÂY DỰNG 
Hà nội 2011 
---------- 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
2 
PHẦN 2 
 GIẢI BÀI TOÁN TRÊN MÁY TÍNH – THUẬT TOÁN 
I. CẤC BƯỚC XÂY DỰNG CHƯƠNG TRÌNH VÀ GIẢI BÀI TOÁN TRÊN MÁY TÍNH 
 1. Thu thập dữ liệu để thiết kế chương trình (User Requirement): yêu cầu của 
bài toán về đầu vào, đầu ra, giao diện, hệ thống, người sử dụng, nội dung cần tính toán, 
xử lý  
 2. Phân tích bài toán và xây dựng giải thuật (Algorithm- Analyze -Code): thiết 
lập cấu trúc dữ liệu, cách lưu trữ, tìm kiếm, chọn phương pháp và cách giải -> xây dựng 
sơ đồ tổng thể và các thuật toán chi tiết cho bài toán hoặc viết Code của chương trình. 
 3. Chọn ngôn ngữ lập trình và viết chương trình (Write Program): giải quyết 
bài toán theo sơ đồ thuật toán đã lập. 
 4. Kiểm tra sự đúng đắn của chương trình (Test): thử nghiệm chương trình với 
các dữ liệu khác nhau có thể xảy ra trong bài toán để kiểm tra độ tin cậy của chương 
trình. Trong phần này có thể có một số giai đoạn : Kiểm tra từng mô đun trong chương 
trình ; Móc nối các mô đun với nhau. 
 5. Vận hành - Bảo trì ( Maintenance): Chương trình được đem ra xử dụng thực 
tế và nhận sự phản hồi của người sử dụng, khách hàng. Tùy thuộc vào chất lượng của 
chương trình nó có thể được kiểm tra và đăng ký bản quyền hoặc phải sửa chữa. 
II. KHÁI NIỆM VỀ THUẬT TOÁN VÀ GIẢI THUẬT 
1. Khái niệm về thuật toán 
Thuật toán là một chuỗi các phép xử lý thông tin, đưa ra phương pháp và trình tự giải 
một bài toán trên máy tính. ThuËt to¸n ®­îc hiÓu lµ c¸c b­íc, c¸c mÑo, luËt ®Ó thùc 
hiÖn c¸c qu¸ tr×nh xö lý th«ng tin. 
2. Các đặc trưng cơ bản: 
- Các qui định thể hiện sơ đồ thuật toán phải thống nhất và theo qui định chung nên 
mọi người đều có thể hiểu được sơ đồ thuật toán. 
3. Đặc điểm : 
- Thuật toán chỉ có nghĩa với người lập trình, máy tính không hiểu được. 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
3 
- Cùng một vấn đề có thể có nhiều phương án lập sơ đồ thuật toán khác nhau. 
- Thuật toán có thể mô tả các bước chính của bài toán (TT tổng quát) hoặc chi tiết 
từng bước giải của vấn đề (thuật toán chi tiết). 
- Thuật toán hay, cách giải ngắn, kết quả chính xác  phụ thuộc vào phương pháp 
giải, trình độ và kinh nghiệm của người lập trình. 
4. Các cấu trúc cơ bản của thuật toán 
- Cấu trúc tuần tự 
- Cấu trúc rẽ nhánh 
- Cấu trúc lặp 
5. Cách biểu diễn sơ đồ thuật toán 
Thông thường có 2 cách thể hiện sơ đồ thuật toán : theo sơ đồ khối và sơ đồ tuyến. 
Sơ đồ khối : là các bước lưu trữ, các phép xử lý thông tin được đặt trong các khối. 
Các khối nối với nhau bằng các đường liên lạc, đường phân chia, hợp, nối tiếp  
Sơ đồ tuyến :là tất cả các bước lưu trữ, xử lý TT  được ghi trên một đường liên tục 
từ trên xuống dưới. 
Ví dụ: 
 Cấu trúc Sơ đồ khối Cấu trúc Sơ đồ tuyến 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
4 
6. Ký hiệu cơ bản dùng trong sơ đồ thuật toán : 
Khối bắt đầu, kết thúc 
Khối nhập dữ liệu từ bàn phím- xuất dữ liệu ra màn hình 
Khối tính toán 
Khối kiểm tra- So sánh 
Khối nối tiếp 
Các đường liên lạc 
Ký hiệu chương trình con 
Các thiết bị xuất kết quả ra đĩa, giấy in 
7. Các bước cần chuẩn bị trước khi viết sơ đồ thuật toán: 
 Tổ chức dữ liệu cho chương trình : 
+ Xác định những số liệu nào cần nhập vào chương trình (là các dữ liệu do đầu bài 
cung cấp) 
+ Xác định các dữ liệu phát sinh trung gian trong quá trình tính toán, dữ liệu cần xuất 
kết quả (dựa theo yêu cầu của bài toán) 
+ Mỗi loại dữ liệu cần xác định các thông tin: 
- Số lượng biến 
- Cấu trúc dữ liệu: Loại biến ( đơn, mảng, bản ghi ) 
- Kiểu dữ liệu: nguyên, thực, bản ghi, kiểu mới tự đặt . . . 
- Tên của dữ liệu: tên biến, hằng, kiểu, bản ghi  ( người dùng tự đặt, nên đặt ngắn, 
viết tắt ý nghĩa của biến ) 
 Xác định các công thức tổng quát cần tính (chú ý nằm ngoài chu trình hoặc trong 
chu trình). 
 Trình tự các bước cần thực hiện: với những bài toán phức tạp cần thể hiện 2 loại 
sơ đồ: Sơ đồ thuật toán tổng quát (các khối thực hiện chính); Sơ đồ thuật toán chi 
tiết: diễn giải các bước thực hiện cho từng khối chính 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
5 
III. CÁC DẠNG THUẬT TOÁN CƠ BẢN 
1. Dạng thuật toán đơn giản – cấu trúc tuần tự 
 Khái niệm: Thuật toán đơn giản là các bước ( nhập dữ liệu, tính toán, xử lý, 
xuất kết quả) được thực hiện tuần tự từ trên xuống dưới theo đường mũi tên . 
 Ví dụ số 1: Viết sơ đồ thuật toán để tính : Chu vi đáy, Diện tích đáy, Diện tích 
xung quanh, Diện tích toàn phần, Thể tích của một hình trụ có kích thước bất 
kỳ. 
Phân tích : 
 + Dữ liệu cần nhập vào: Bán kính, chiều cao của hình trụ; Cấu trúc dữ liệu: biến 
đơn; Kiểu biến: số thực ; Đặt tên biến : R,H 
+ Cần tính: Đặt tên biến : CVD,DTD, DTXQ, DTTP, TT. 
Loại dữ liệu: biến đơn; Kiểu biến: số thực ; 
Các công thức: 
Chu vi đáy: CVD = 2∏R 
Diện tích đáy: DTD = ∏ R2 , Diện tích xung quanh: DTXD= CVD*h, 
Diện tích toàn phần : DTTP= DTXQ + 1* DTD , Thể tích TT= DTD*h ; 
+ Các dữ liệu cần xuất kết quả: các dữ liệu vừa tính: CVD,DTD, DTXQ, DTTP, TT 
Thể hiện sơ đồ: 
 Thuật toán Ví dụ 1 Thuật toán Ví dụ 2 
2. Dạng thuật toán phân nhánh 
 Khái niệm: Thuật toán phân nhánh là cấu trúc có ít nhất một khối kiểm tra hay so 
sánh, dựa vào kết quả kiểm tra, lựa chọn hướng tính toán. Có thể rẽ nhánh đôi 
hoặc nhiều nhánh, nhưng mỗi lần thực hiện, chỉ đi theo một nhánh. 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
6 
 Một số dạng tổng quát: a) 
b) 
 c) 
d) 
Giải thích các đại lượng : BTĐK- Biểu thức điều kiện. Kết quả của biểu thức chỉ nhận 
một trong 2 giá trị đúng hoặc sai. BTC- Biểu thức chọn, kết quả có thể là một hằng 
nguyên hoặc ký tự. Số lượng kết quả không hạn chế. 
Nhóm lệnh 1, 2 : là các lệnh trong miền tác dụng cần thực hiện khi giá trị biểu thức 
Đúng hoặc Sai. 
Các dạng: 
Dạng a) : Dạng phân nhánh đôi không đầy đủ, chỉ thực hiện khi biểu thức điiều kiện 
đúng. 
Dạng b) : Dạng phân nhánh đôi đầy đủ, thực hiện với mọi giá trị của BTĐK (một nhánh 
cho giá trị đúng, một nhánh cho giá trị sai). 
Dạng c) : Dạng phân nhánh lồng nhau: có thể đầy đủ hoặc không đầy đủ và mức độ lồng 
nhau tùy ý. 
Dạng d) : Dạng n nhánh. 
 Cách thực hiện nhánh đôi: - Tính toán và kiểm tra biểu thức điều kiện (BTĐK). 
- Nếu BTĐK có giá trị đúng thì nhóm lệnh 1 sẽ được thực hiện (bỏ qua nhóm lệnh 
2), ngược lại nhóm lệnh 2 được thực hiện. 
- Thực hiện các khối tiếp theo. 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
7 
 Cách thực hiện dạng n nhánh: - Dựa theo giá trị của biểu thức chọn (BTC) mà 
thực hiện một trong các nhánh tương ứng. Ví dụ giá trị BTC = N1 thực hiện Nhóm 
lệnh 1,giá trị là Nn, thực hiện nhóm lệnh n. 
- Mỗi lần chỉ thực hiện 1 nhánh, bỏ qua các nhánh kia và kết thúc lệnh. 
 Ví dụ số 2: Cho 3 số a,b,c . Viết thuật toán tìm số lớn nhất trong 3 số đó. 
 Ví dụ số 3: Viết thuật toán giải phương trình bậc 2: Ax2 + Bx + C = 0 (trang 19) 
 Ví dụ số 4: Viết sơ đồ thuật toán tính số lượng sinh viên có tuổi từ 18-20, 21-25, 
26-30 và trên 30. 
Ký hiệu số lượng sinh viên các nhóm là SL1, SL2, SL3, SL4. 
 Thuật toán ví dụ 3 Thuật toán ví dụ 4 
3. Dạng thuật toán chu trình – Chu trình lồng nhau 
3.1. Dạng thuật toán một chu trình 
 Khái niệm : Thuật toán lặp là cấu trúc trong đó một nhóm lệnh (miền tác động) 
được lặp đi lặp lại nhiều lần, có dạng tổng quát không thay đổi, có thể biến đổi 
một số tham số trong miền. 
Có 2 dạng lặp: lặp với số lần lặp đã xác định (dạng a) hoặc lặp với số lần không 
xác định (dạng b ). 
 Một số dạng tổng quát – cấu trúc: 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
8 
Dạng a) 
Dạng b) 
 Giải thích: BĐK - biến điều khiển hay biến đếm của chu trình; n1,n2,n3 – là các 
giá trị đầu, bước nhẩy và giá trị cuối của biến điều khiển. Các lệnh lặp: là các 
khối cần thực hiện trong miền tác dụng của chu trình. 
 Cách thực hiện: Dạng a) 
- Bước 1 : Gán giá trị đầu cho biến điều khiển - Khối 1 
- Bước 2 : Thực hiện các lệnh trong miền tác động của chu trình lặp – Khối 2 
- Bước 3 : Tăng giá trị của biến điều khiển – Khối 3 
- Bước 4 : Kiểm tra BĐK đã vượt qua giá trị cuối hay chưa, nếu chưa quay lại thực 
hiện từ bước 2, nếu đã vượt quá, kết thức quá trình lặp (thực hiện các bước tiếp theo)- 
Khối 4. 
 Cách thực hiện: Dạng b) 
- Bước 1 : Gán giá trị đầu cho biến điều khiển - Khối 1 
- Bước 2 : Kiểm tra BĐK, nếu thỏa mãn điều kiện lặp, thực hiện bước 2, nếu không 
thỏa mãn điều kiện, kết thức quá trình lặp (thực hiện các bước tiếp theo)- Khối 4. 
- Bước 3 : Thực hiện các lệnh trong miền tác động của chu trình lặp – Khối 2 
- Bước 4 : Tăng giá trị của biến điều khiển – Khối 3 
 Chú ý : - Với dạng a) chu trình luôn thực hiện ít nhất 1 lần, với dạng b) nếu biểu 
thức điểu kiện không thỏa mãn, có thể dừng ngay chu trình ( không thực hiện lần 
nào). 
- Thuật toán chu trình luôn tồn tại đủ 4 khối 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
9 
- Không được thay đổi các giá trị n1,n2,n3 trong miền tác dụng chu trình. 
- Có thể kết thức chu trình sớm ( trước khi lặp đủ số lần khai báo)- nhảy từ trong ra 
ngoài chu trình. 
- Không đượcnhẩy từ ngoài chu trình vào trong chu trình 
 Ví dụ số 5: Cho một véc tơ A có n phần tử. Viết sơ đồ thuật toán tính tổng các 
phần tử trong véc tơ. 
Phân tích: - Các biến cần nhập: n (biến đơn) ; véc tơ A (biến mảng), nhập từng phần tử 
Ai, bước này lặp n lần. 
- Tính toán: Tổng các phần tử: T (biến đơn). Để tính tổng : giả sử ban đầu T=0; sau đó 
cộng từng phần tử vào T , có dạng T ← T+ Ai ( với i chạy từ 1-n) : công thức này được 
lặp n lần. 
 Thuật toán Ví dụ 5 Thuật toán Ví dụ 6 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
10 
 Ví dụ số 6: Cho một véc tơ B có m phần tử. Viết sơ đồ thuật toán tìm giá trị lớn 
nhất của véc tơ. 
Phân tích: - Các biến cần nhập: m (biến đơn) ; véc tơ B (biến mảng), nhập từng phần tử 
Bi, bước này lặp m lần. 
- Tính toán: Giá trị lớn nhất ký hiệu Max (biến đơn). Để tìm giá trị lớn nhất: giả sử 
ban đầu Max = B1; sau đó lấy từng phần tử Bi kiểm tra với Max (với i chạy từ 1-
n), nếu phần tử nào lớn hơn gán lại Max ← Bi,: công thức này chỉ thực hiện khi 
điều kiện KT là đúng. 
3.2. Dạng Thuật toán chu trình lồng nhau: 
Về nguyên tắc thuật toán chu trình lồng nhau cũng giống như thuật toán 1 chu trình, 
mỗi chu trình cũng có đủ 4 khối và 4 bước thực hiện như thuật toán 1 chu trình. 
Chú ý : - Mỗi chu trình có một biến điều khiển riêng (thường ký hiệu i,j,k .) 
- Các giá trị n1,n2,n3 của biến điều khiển mỗi chu trình có thể giống hoặc khác 
nhau. 
- Toàn bộ chu trình trong là một phần của miền tác dụng chu trình ngoài (nằm trong 
khối 2). 
- Số lần thực hiện của chu trình trong nhiều hơn chu trình ngoài, biến điều khiển của 
chu trình trong sẽ tăng trước. 
- Dạng tổng quát : 
Chu trình có số lần lặp đã biết 
Chu trìnhcó số lần lặp chưa biết 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
11 
 Ví dụ số 7: Cho một lớp học có m người và điểm thi từng môn của n môn. Viết sơ 
đồ thuật toán : 
- Tìm điểm trung bình n môn của mỗi người 
- Tìm danh sách những người có điểm trung bình >8 . 
Phân tích: - Các biến cần nhập: số người m (biến đơn); véc tơ họ tên HT( mảng 1 chiều), 
nhập từng phần tử HTi, lặp m lần; Nhậpđiểm thi từng môn D (mảng 2 chiều, mỗi hàng là 
cho một người, mỗi cột là cho một môn), nhập từng phần tử Dij, bước này lặp mxn lần. 
- Tính toán: 
+ Điểm trung bình từng người ký hiệu TB (mảng 1 chiều, m phần tử): Tìm tổng điểm 
các môn của người thứ i: Tbi ←Tbi+Dij ( mỗi chu trình i lặp n lần chu trình j). Kết 
thúc chu trình j, tình trung bình: Tbi = Tbi /n 
+ Tìm danh sách: Có 2 cách: Kiểm tra điểm trung bình từng người, nếu ai có Tbi>8 in 
ngay tên của người tương ứng. Hoặc lập danh sách mới chỉ chứa tên những người có 
điểm TB >8 ( số lượng chưa biết) 
- Xuất kết quả : In ra màn hình véc tơ điểm trung bình – TB (m người); Danh sách 
những người có DTB lớn hơn 8 (In trực tiếp). 
Thuật toán Ví dụ 7 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
12 
 Ví dụ số 8: Cho ma trận A vuông có m hàng, m cột. Viết sơ đồ thuật toán tìm tích 
của các phần tử nằm trong khoảng [x , y] cho trước và tổng các phần tử dương 
nằm phía trên đường chéo chính. 
Thuật toán Ví dụ 8 
 Ví dụ 9: Cho một ma trận A có m hàng, m cột. Ma 
trận B có n hàng, n cột. 
Yêu cầu : 
Viết sơ đồ thuật toán ghép hai ma trận trên thành ma trận C 
có m+n hàng, m+n cột có dạng như hình bên. 
Trong đó viết 1 chương trình chính là chương trình điều 
khiển và 3 chương trình con, một chương trình con nhập dữ 
liệu, một chương trình con ghép 2 ma trận và một chương 
trình con In kết quả ra màn hình. 
Phân tích bài toán: 
- Các chương trình con nhập dữ liệu và xuất kết quả ta viết cho một ma trận X bất 
kỳ, có kích thước giả định n1,n2. Chương trình con ghép lấy đúng tên các ma trận 
A,B,C. Chương trình con xuất dữ liệu, về thuật toán sẽ giống nhập DL. 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
13 
- Chương trình điều khiển sẽ gọi 2 lần chương trình con Nhập dữ liệu (thay X bằng 
A,B, thay n1,n2 bằng m, n) để nhập cho A và B; và gọi chương trình con ghép 2 
ma trận. 
Thuật toán Ví dụ 9 
Chương trình con Nhập 
Dữ liệu cho một mảng 
 Chương trình con 
Ghép 2 ma trận A,B vào ma trận C 
Chương trình con xuất kết quả 
Chương trình chính 
Giáo trình Nhập môn Tin học: Phần II - Thuật toán GVC: Đào Tăng Kiệm 
Bộ môn Tin học Xây dựng 
14 
Ví dụ 10: Cho dữ liệu của một phường dân cư gồm m hộ, biết họ tên chủ hộ (HT), 
số điện tiêu thụ từng tháng (DTT) trong 12 tháng của năm. Viết thuật toán nhập dữ 
liệu cho cả phường với các yêu cầu sau: 
- Nhập các dữ liệu vào máy. 
- Tính tổng số điện tiêu thụ (TD) của mỗi hộ trong cả năm 
- Lập danh sách (DS) những hộ tiêu thu điện cả năm > X số. 
Thuật toán Ví dụ 10