Bài 5. Gi i thu t x lý thông tin và ả ậ ử
ngôn ng l p trình ữ ậ
KHOA CÔNG NGH THÔNG TIN Ệ
B MÔN CÔNG NGH PH N M MỘ Ệ Ầ Ề
Bài giảng: LẬP TRÌNH CƠ BẢN
Tài liệu tham khảo
Gi i thu t x lý thông tin và ngôn ng l p trìnhả ậ ử ữ ậ2
Giáo trình tin h c c s , H S Đàm, Đào Ki n Qu c, ọ ơ ở ồ ỹ ế ố
H Đ c Ph ng. Đ i h c S ph m, 2004 – Ch ng 7, 9.ồ ắ ươ ạ ọ ư ạ ươ
NỘI DUNG
Khái ni m bài toán gi i thu t ệ ả ậ
Đ c tr ng c a gi i thu tặ ư ủ ả ậ
Các ph ng pháp di n đ t gi i thu tươ ễ ạ ả ậ
S l c v đánh giá gi i thu tơ ượ ề ả ậ
Ngôn ng l p trình và các m c khác nhau c a ngôn ng ữ ậ ứ ủ ữ
l p trìnhậ
Quá trình th c hi n ch ng trình trên ngôn ng b c caoự ệ ươ ữ ậ
3 Gi i thu t x lý thông tin và ngôn ng l p trìnhả ậ ử ữ ậ
KHÁI NIỆM BÀI TOÁN
Cho s t ố ự
nhiên n
n có ph i s ả ố
nguyên t hay ố
không
“có” hay
“không”
Cho h s ồ ơ
đi m sinh viênểTìm t t c các sinh ấ ả
viên có đi m trung ể
bình trên 8
Danh sách sv
tho mãnả
Thi t k hình ế ế
h c, t i tr ngọ ả ọ Tính s c b n ứ ề Đ b n ộ ề
Input Yêu c uầOutput
Cho m t bài toán nghĩa là cho input, ộ
và yêu c u đ tìm (tính) ra output ầ ể
4 Gi i thu t x lý thông tin và ngôn ng l p trìnhả ậ ử ữ ậ
KHÁI NIỆM THUẬT TOÁN
Thu t toán (algorithm) là m t quá trình g m m t dãy h u h n các ậ ộ ồ ộ ữ ạ
thao tác có th th c hi n đ c s p x p theo m t trình t xác đ nh ể ự ệ ượ ắ ế ộ ự ị
dùng đ gi i m t bài toán ể ả ộ
Ví d : thu t toán Euclid tìm c s chung l n nh t c a hai s t ụ ậ ướ ố ớ ấ ủ ố ự
nhiên. Thay vì ph i tính toán theo đ nh nghĩa ch làm rõ c u trúc c a ả ị ỉ ấ ủ
USCLN (tích c a các c s chung v i s mũ nh nh t) thu t toán ủ ướ ố ớ ố ỏ ấ ậ
Euclid d a trên các tính ch t sau:ự ấ
USCLN(a,b) = USCLN (b,a))
N u a> b, USCLN(a,b) = USCLN (a-b,b)ế
USCLN(a,a)= a
5 Gi i thu t x lý thông tin và ngôn ng l p trìnhả ậ ử ữ ậ