Bài giảng Lập trình C - Chương 1: Giải quyết vấn đề, bài toán bằng máy tính

án
9/16/2008T.P.Tuấn-Lập Trình CPage 17
Thuật toán giải phương trình bậc hai:
AX2 + BX + C = 0 (A  0)
 -Bước 1 : Tính DELTA = B*B-4*A*C
 -Bước 2 : So sánh DELTA với số 0
 -Bước 3 : Rẽ làm 3 trường hợp : 
-Trường hợp DELTA < 0 : 
vô nghiệm;
-Trường hợp DELTA = 0 : 
-Trường hợp DELTA > 0 :
.
2. Thuật toán – thuật giải
Thuật toán – ví dụ
1 2 2*
B
X X
A
  
2
1,2
4
2
b b ac
X
a
  
9/16/2008T.P.Tuấn-Lập Trình CPage 18
2. Thuật toán – thuật giải
Thuật toán – các cấu trúc cơ bản
1. Tuần tự: thực hiện hết lệnh này đến 
lệnh khác
2. Rẽ nhánh: tùy theo dữ liệu đầu vào mà
ta quyết định thực hiện câu lệnh gì tiếp 
theo
3. Lặp: thực hiện lại nhiều lần một số câu 
lệnh nào đó cho đến khi điều kiện không 
còn thỏa mãn nữa
9/16/2008T.P.Tuấn-Lập Trình CPage 19
• Khái niệm thuật toán đã trình bày chính là cánh 
cửa khép kín cho việc giải các bài toán vì:
– Nhiều bài toán không thỏa các đặc trưng cơ bản 
của thuật toán.
– Có nhiều bài toán chưa tìm ra thuật toán hoặc 
chưa chứng minh được là có thuật toán hay 
không. 
– Có những bài toán có thuật toán nhưng khó thực 
hiện hoặc không thực hiện được
2. Thuật toán – thuật giải
Thuật giải
9/16/2008T.P.Tuấn-Lập Trình CPage 20
• Từ những nhận định trên người ta thấy rằng: 
cần phải có những đổi mới cho khái niệm thuật 
toán  “Thuật giải”
– Tính xác định
– Tính đúng đắn
2. Thuật toán – thuật giải
Thuật giải
THUẬT GIẢI CŨNG LÀ THUẬT TOÁN 
NHƯNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN
9/16/2008T.P.Tuấn-Lập Trình CPage 21
• Tính xác định thực chất là tính đơn trị của cách giải 
của một thuật toán và sự rõ ràng tối đa. 
• Trong thực tế có nhiều bài toán vi phạm tính xác 
định mà vẫn cho kết qủa. Như vậy thay cho việc xây 
dựng toàn bộ quá trình giải chỉ cần chỉ ra cách 
chuyển từ bước i sang bước i+1. 
• Cách gỉai ngẫu nhiên, đệ quy là mở rộng tính xác 
định
2. Thuật toán – thuật giải
Thuật giải – mở rộng tính xác định
9/16/2008T.P.Tuấn-Lập Trình CPage 22
• Tính đúng đắn được hiểu là cho kết quả 
đúng. 
• Trong thực tế thì số gần đúng là có thể chấp 
nhận được
• Ngoài ra dùng cách giải heuristic đơn giản, 
độc đáo vẫn có thể cho kết qủa một cách 
sáng tạo
2. Thuật toán – thuật giải
Thuật giải – mở rộng tính đúng đắn
9/16/2008T.P.Tuấn-Lập Trình CPage 23
• Ngôn ngữ tự nhiên
• Lưu đồ - sơ đồ khối
• Mã giả
3. Các phương pháp biểu diễn thuật toán
9/16/2008T.P.Tuấn-Lập Trình CPage 24
• Liệt kê các thao tác, các chỉ thị bằng ngôn 
ngữ tự nhiên
• Ví dụ: Có 43 que diêm. Hai người chơi luân 
phiên bốc diêm. Mỗi lượt, mỗi người bốc từ 
1 đến 3 que diêm. Người nào bốc cuối cùng 
sẽ thắng cuộc
3. Các phương pháp biểu diễn thuật toán
Ngôn ngữ tự nhiên
9/16/2008T.P.Tuấn-Lập Trình CPage 25
• Giải thuật để người đi trước luôn thắng cuộc 
được diễn tả bằng cách liệt kê từng bước như 
sau:
– Bước 1: Bốc 3 que rồi đợi đối phương đi
– Bước 2: Đối phương bốc (giả sử x que, 0<x<4)
– Bước 3: Đến lượt người đi trước bốc a = (4-x) 
que. Nếu còn diêm thì quay lại Bước 2
– Tuyên bố thắng cuộc. Kết thúc
3. Các phương pháp biểu diễn thuật toán
Ngôn ngữ tự nhiên
9/16/2008T.P.Tuấn-Lập Trình CPage 26
1. Tính điểm trung bình của học sinh gồm các 
môn Toán, Lý, Hóa.
2. Kiểm tra 2 số a, b giống nhau hay khác 
nhau.
3. Kiểm tra 1 số a chẵn hay lẻ
4. Giải pt: ax+b=0
5. Giải phương trình bậc 2: ax2 + bx + c = 0
3. Các phương pháp biểu diễn thuật toán
Ngôn ngữ tự nhiên – Bài tập
9/16/2008T.P.Tuấn-Lập Trình CPage 27
• Là một phương tiện hình học giúp ta diễn tả
giải thuật một cách trực quan
• Được tạo bởi các kiểu khối cơ bản, nối với 
nhau bằng các đường có hướng
• Thuật ngữ tiếng Anh là Flow Chart
3. Các phương pháp biểu diễn thuật toán
Sơ đồ khối
9/16/2008T.P.Tuấn-Lập Trình CPage 28
3. Các phương pháp biểu diễn thuật toán
Sơ đồ khối
bắt đầu
kết thúc
Chương 
trình con
Hướng xử lý
điều kiện
input
output
thao tác
9/16/2008T.P.Tuấn-Lập Trình CPage 29
3. Các phương pháp biểu diễn thuật toán
Sơ đồ khối – ví dụ
Bắt đầu
Kết thúc
a, b
c = a + b
c
Bắt đầu
Kết thúc
Số a, Số b
Số a bằng Số b
Số a có bằng
Số b không?
Số a không bằng Số b
Có
Không
Bắt đầu
Kết thúc
Thùng = 24 Lon?Chưa
Thùng = 0 Lon
1 Lon
Thêm 1 Lon vào thùng
Bằng
9/16/2008T.P.Tuấn-Lập Trình CPage 30
1. Tính điểm trung bình của học sinh gồm các 
môn Toán, Lý, Hóa.
2. Kiểm tra 2 số a, b giống nhau hay khác 
nhau.
3. Kiểm tra 1 số a chẵn hay lẻ
4. Giải pt: ax+b=0
5. Giải phương trình bậc 2: ax2 + bx + c = 0
3. Các phương pháp biểu diễn thuật toán
Sơ đồ khối – Bài tập
9/16/2008T.P.Tuấn-Lập Trình CPage 31
3. Các phương pháp biểu diễn thuật toán
Mã giả
• Ngoài việc sử dụng ngôn ngữ tự nhiên và 
lưu đồ để biểu diễn thuật toán, người ta còn 
sử dụng ngôn ngữ tựa pascal, c, … được gọi 
là mã giả
• Trong mã giả ta sử dụng cả cấu trúc của 
ngôn ngữ lập trình và ngôn ngữ tự nhiên
9/16/2008T.P.Tuấn-Lập Trình CPage 32
3. Các phương pháp biểu diễn thuật toán
Mã giả - ví dụ
Biến
A,B,C,DELTA,X1,X2 : SốThực ;
BắtĐầu
Nhập A,B,C;
DELTA:=B*B-4*A*C;
Nếu DELTA <0 Thi
Xuất 'Phương trinh vô nghiệm ';
Dừng;
Nếu DELTA =0 Thi
X1:=(-B/2/A);
X2:=X1;
Xuất 'Nghiệm kép X1,X2 ';
Dừng;
Nếu DELTA =0 Thi
X1:=(-B-CanBậcHai(DELTA))/2/A;
X2:=(-B+CanBậchH(DELTA))/2/A;
Xuất 'Nghiệm phân biệt X1,X2 ';
Dừng;
KếtThúc.
9/16/2008T.P.Tuấn-Lập Trình CPage 33
1. Tính điểm trung bình của học sinh gồm các 
môn Toán, Lý, Hóa.
2. Kiểm tra 2 số a, b giống nhau hay khác 
nhau.
3. Kiểm tra 1 số a chẵn hay lẻ
4. Giải pt: ax+b=0
5. Giải phương trình bậc 2: ax2 + bx + c = 0
3. Các phương pháp biểu diễn thuật toán
Mã giả – Bài tập
Sử dụng ngôn ngữ tựa pascal
9/16/2008T.P.Tuấn-Lập Trình CPage 34
4. Các bước để giải một bài toán trên máy tính
• Bước 1: Xác định vấn đề - bài toán
• Bước 2: Lựa chọn phương pháp giải
• Bước 3: Xây dựng thuật toán hoặc thuật giải
• Bước 4: Cài đặt chương trình
• Bước 5: Hiệu chỉnh chương trình
• Bước 6: Thực hiện chương trình
9/16/2008T.P.Tuấn-Lập Trình CPage 35
4. Các bước để giải một bài toán trên máy tính
• Phân tích hệ thống nhằm phát biểu chính 
xác vấn đề, làm rõ yêu cầu của người sử
dụng
• Đánh giá, nhận định tính khả thi của vấn đề
Bước 1: Xác định vấn đề - bài toán
9/16/2008T.P.Tuấn-Lập Trình CPage 36
4. Các bước để giải một bài toán trên máy tính
• Có nhiều cách khác nhau để giải quyết vấn 
đề, tùy theo nhu cầu cụ thể mà ta lựa chọn 
phương pháp thích hợp
• Việc lựa chọn phương pháp cũng cần căn cứ
vào khả năng xử lý tự động mà ta cần sử
dụng
Bước 2: Lựa chọn phương pháp giải
9/16/2008T.P.Tuấn-Lập Trình CPage 37
4. Các bước để giải một bài toán trên máy tính
• Xác định input, output
• Xác định các bước thực hiện cơ bản cho dữ
liệu đầu vào và đầu ra
• Nên áp dụng phương pháp thiết kế có cấu 
trúc, từ thiết kế tổng thể tiến hành làm mịn 
dần các bước
Bước 3: Xây dựng thuật toán hoặc thuật giải
9/16/2008T.P.Tuấn-Lập Trình CPage 38
4. Các bước để giải một bài toán trên máy tính
• Mô tả thuật giải thành chương trình
• Cần nắm vững ngôn ngữ lập trình và thể
hiện một cách chính xác thuật toán đã được 
đưa ra.
Bước 4: Cài đặt chương trình
9/16/2008T.P.Tuấn-Lập Trình CPage 39
4. Các bước để giải một bài toán trên máy tính
• Cho chương trình chạy thử và hiệu chỉnh 
những sai sót
• Trong bước này ta cần khắc phục hai loại lỗi:
– Lỗi cú pháp (có sự hỗ trợ của IDE)
– Lỗi ngữ nghĩa (thường khó phát hiện hơn lỗi cú
pháp)
Bước 5: Hiệu chỉnh chương trình
9/16/2008T.P.Tuấn-Lập Trình CPage 40
4. Các bước để giải một bài toán trên máy tính
• Cho chương trình chạy với những bộ dữ liệu 
khác nhau để kiểm tra
• Lưu ý các trường hợp đặc biệt
• Lưu ý các trường hợp người dùng nhập dữ
liệu có kiểu không phù hợp với kiểu dữ liệu 
sử dụng trong chương trình
Bước 6: Thực hiện chương trình
9/16/2008T.P.Tuấn-Lập Trình CPage 41
5. Tổng quan về ngôn ngữ lập trình
VẤN ĐỀ
NAN GIẢI
PP giải
(giải thuật)
VẤN ĐỀ 
TƯƠNG TỰ KẾT QUẢ
Ôi nhiều 
việc quá
Con người làm việc
9/16/2008T.P.Tuấn-Lập Trình CPage 42
VẤN ĐỀ
NAN GIẢI
PP giải
(giải thuật)
VẤN ĐỀ 
TƯƠNG TỰ
KẾT QUẢ
Có máy tính Sướng 
thật, đi làm việc 
khác thôi!
5. Tổng quan về ngôn ngữ lập trình
Sự hỗ trợ của máy tính
9/16/2008T.P.Tuấn-Lập Trình CPage 43
Giải bài toán này 
thế nào đây?
Cách giải được 
diễn đạt bằng 
ngôn ngữ tự nhiên
Source code
Kiến thức
về NNLT
Kiến thức
Chuyên môn
Chương trình 
biên dịch
(Bộ máy của NNLT)
File Ngôn
ngữ máy
(exe, dll, com, ...)
5. Tổng quan về ngôn ngữ lập trình
Sự hỗ trợ của máy tính
9/16/2008T.P.Tuấn-Lập Trình CPage 44
6. Thể hiện thuật toán bằng ngôn ngữ lập trình
1. Tuần tự
2. Rẽ nhánh
3. Lặp
1. Dấu ;
2. If, 
switch … case …
3. While, 
do … while, 
for(…,…,…)
Các cấu trúc của thuật toán Các cấu trúc của ngôn ngữ C
9/16/2008T.P.Tuấn-Lập Trình CPage 45
Thành phần 
tương ứng 
(nhập xuất)
-Màn hình
-Máy in
-File (tập tin)
-Cơ sở dữ liệu
-Loa
-…
-Bàn phím:dữ liệu vào thông 
qua
-Màn hình Console
-Windows (các điều khiển: nút 
lệnh, textbox,…)
-Chuột: các điều khiển 
-File (tập tin)
-Cơ sở dữ liệu
-Micro
-Máy scan
-Máy nhận dạng mã vạch
-…
Thông tin đầu ra
(output)
Thông tin đầu vào
(input)
7. Mối liên hệ giữa các thành phần trong cấu trúc của bài 
toán và các thành phần nhập xuất trong máy tính
9/16/2008T.P.Tuấn-Lập Trình CPage 46
8. Hãy tìm thuật toán?
1. Cho a,b,c tìm max, min (phát 
triển cho 4 số, 5 số, …)
2. ax+b=0;
3. ax2+bx+c=0; 
4. Tháng  Quý.
5. Tiền điện.
6. Dạng tam giác(nhập a,b,c): 
Cân, Vuông, Đều, Vuông cân. 
7. S=1+2+…+n
8. Số hạng thứ n của dãy fibonaci
9. UCLN, BCNN của 2 số. 
10. Rút gọn phân số (nhập tử số, 
mẫu số). 
11. Cơ số 10  2. (10  k)
12. Cơ số 2  10. (k  10) 
13. Nhập giờ, phút, giây, nhập số
giây thêm, xuất ra giờ, phút 
giây. 
14. Số nguyên tố
15. Số chính phương
16. Phân tích Thừa số nguyên tố. 
17. Tổng các ước số của 1 số. 
18. Tổng các số nguyên tố < n
19. Tổng các số chính phương < n 
9/16/2008T.P.Tuấn-Lập Trình CPage 47