Chương 1 - Tổng quan về giải thuật ppt
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.89 MB, 26 trang )
(6 ti t)ế
1
2
Giải thuật
Ngôn ngữ
Lập trình
*
Đúng đ n, chính xác (ắ correctness).
*
Ch c ch n (ắ ắ robustness).
*
Thân thi n (ệ user friendliness).
*
Kh năng thích nghi (ả adapability): Ch ng trình ươ
có kh năng đ phát tri n ti n hóa theo yêu c u.ả ể ể ế ầ
*
Tính tái s d ng (ử ụ reuseability): Ch ng trình có ươ
th dùng đ làm m t ph n trong m t ch ng ể ể ộ ầ ộ ươ
trình l n khác.ớ
3
*
Tính hi u qu (ệ ả efficiency).
*
Tính kh chuy n (ả ể porability): Kh ả
năng chuy n đ i gi a các môi ể ổ ữ
tr ng.ườ
*
Tính an toàn (security).
*
Tính d ng (ừ halt).
4
*
Fortran
*
Pascal
*
Java
*
C
5
*
*
*
*
*
*
Borland C++
*
Microsoft Visual Basic
*
Microsoft Visual C++
*
Jbuider
*
Eclipse SDK
*
Visual .Net
*
…
6
7
Input -> Process -> Output
*
Gi i quy t v n đ gì?ả ế ấ ề
*
Gi thi t, thông tin đ c cung c pả ế ượ ấ
*
Đ t đ c nh ng yêu c u nào?ạ ượ ữ ầ
8
*
Ph i bi u di n đ y đ đ c thông tin nh p và ả ể ễ ầ ủ ượ ậ
xu t c a bài toánấ ủ
*
Phù h p v i gi i thu t đ c ch nợ ớ ả ậ ượ ọ
*
Cài đ t đ c trên ngôn ng l p trình c thặ ượ ữ ậ ụ ể
9
*
Gi i thu tả ậ là m t ộ
t p h p h u h nậ ợ ữ ạ c a các ch th ủ ỉ ị
hay ph ng cách đ c đ nh nghĩa ươ ượ ị
rõ ràng cho vi c hoàn t t m t s ệ ấ ộ ố
s vi c t m t tr ng thái ban ự ệ ừ ộ ạ
đ u cho tr c; khi các ch th này ầ ướ ỉ ị
đ c áp d ng tri t đ thì s d n ượ ụ ệ ể ẽ ẫ
đ n k t qu sau cùng nh đã d ế ế ả ư ự
đoán.
10
*
Tính chính xác: đ đ 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. ự ệ ượ
*
Tính rõ ràng: gi i thu t ph i đ c th hi n b ng các ả ậ ả ượ ể ệ ằ
câu l nh minh b ch; các câu l nh đ c s p x p theo ệ ạ ệ ượ ắ ế
th t nh t đ nh. ứ ự ấ ị
*
Tính khách quan: M t gi i thu t dù đ c vi t b i ộ ả ậ ượ ế ở
nhi u ng i trên nhi u máy tính v n ph i cho k t qu ề ườ ề ẫ ả ế ả
nh nhau. ư
*
Tính ph d ng: ổ ụ gi i thu t không ch áp d ng cho m t ả ậ ỉ ụ ộ
bài toán nh t đ nh mà có th áp d ng cho m t l p các ấ ị ể ụ ộ ớ
bài toán có đ u vào t ng t nhau. ầ ươ ự
*
Tính k t thúc: ế gi i thu t ph i g m m t s h u h n ả ậ ả ồ ộ ố ữ ạ
các b c tính toán. ướ
*
X lý file.ữ
*
Đ h a.ồ ọ
*
Đ th .ồ ị
*
V. v…
11
*
ế
*
ắ ế
*
ệ
*
ữ ỗ ự
•
Mã t nhiênự
•
Pseudocode (mã gi )ả
•
Flowchart (l u đ )ư ồ
Khi thi t k gi i thu t ph i mô t rõ:ế ế ả ậ ả ả
•
Input - Đ u vàoầ
•
Output - Đ u ra (k t qu )ầ ế ả
•
Process - Mô t gi i thu tả ả ậ
12
13
Ví d : Tìm c s chung l n nh t c a 2 s ụ ướ ố ớ ấ ủ ố
nguyên d ng a và bươ
*
Đ u vàoầ : 2 s nguyên d ng a và bố ươ
*
Đ u raầ : c s chung l n nh t c a a và bướ ố ớ ấ ủ
*
Gi i thu tả ậ :
Cách 1: Dùng mã t nhiênự
B c 1: N u a = b thì k t lu n a là c s chung ướ ế ế ậ ướ ố
l n nh t, k t thúcớ ấ ế
B c 2: N u a > b thì a = a – b;ướ ế
Ng c l i thì b = b – a;ượ ạ
B c 3: Quay tr l i B c 1ướ ở ạ ướ
14
Cách 2: Dùng mã gi (Pseudocode)ả
WHILE a ≠ b DO
IF a>b THEN
a=a-b
ELSE
b=b-a
ENDIF
ENDWHILE
15
Cách 3: Dùng l u đ (flowchart)ư ồ
16
*
D hi u, không chi ti t đ n các k thu t l p trìnhễ ể ế ế ỹ ậ ậ
*
c p đ h t s c t ng quát: g n ngôn ng t nhiênỞ ấ ộ ế ứ ổ ầ ữ ự
*
Ho c r t chi ti t: nh dùng ngôn ng t a Pascal, C++, …ặ ấ ế ư ữ ự
*
Các t khóaừ
*
IF <Đi u ki n> THEN …ENDIFề ệ
*
IF <Đi u ki n> THEN ELSE ENDIFề ệ
*
WHILE <Đi u ki n> DO … ENDWHILEề ệ
*
DO … UNTIL <Đi u ki n>ề ệ
*
WRITE …
*
RETURN …
17
*
L u đ thu t toán là công c dùng đ ư ồ ậ ụ ể
bi u di n thu t toánể ễ ậ , vi c mô t ệ ả nh pậ
(input), d li u ữ ệ xu t ấ (output) và lu ng x ồ ữ
lý thông qua các ký hi u hình h cệ ọ
*
Ph ngươ pháp duy t l u đệ ư ồ
*
! !"ệ ư ô
*
#$%!" ệ ư a
B t đ u/ k t thúcắ ầ ế
R nhánhẽ
Lu ng x lýồ ử
Kh i x lýố ử
Nh p/ Xu tậ ấ
ề
!ệ
Giá trị trả về
Điểm nối
18
19
1.Cho s nguyên n. Tính tr tuy t đ i c a n ố ị ệ ố ủ
2.Gi i và bi n lu n ph ng trình b c I: ax+b=0ả ệ ậ ươ ậ
3.Nh p và s nguyên k (k>0), Xu t ra màn hình ậ ố ấ
k dòng ch “Xin chào”ữ
4.Tính t ng: ổ ,v i n>0ớ
5.Tính t ng: ổ ,v i n>0ớ
6.Nh p vào ba c nh a, b, c c a tam giác. Xu t ậ ạ ủ ấ
ra màn hình tam giác đó thu c lo i tam giác ộ ạ
gì? (Th ng, cân, vuông, đ u hay vuông cânươ ê ).
nS ++++= 321
n
n
nS
1
)1(4321)(
+
−++−+−=
20
Cho s nguyên n. Tính tr tuy t đ i c a n ố ị ệ ố ủ
*
Đ u vào: S nguyên nầ ố
*
Đ u ra: |n|ầ
*
Gi i thu t (Pseudocode):ả ậ
IF n<0 THEN
n=n*(-1)
ENDIF
WRITE n
*
Gi i thu t (Flowchart):ả ậ
21
22
Gi i và bi n lu n ph ng trình b c I: ax+b=0ả ệ ậ ươ ậ
*
Đ u vào: Hai s nguyên a và bầ ố
*
Đ u ra: Nghi m c a ptầ ệ ủ
*
Gi i thu t (Pseudocode):ả ậ
IF a=0 THEN
IF b=0 THEN
WRITE “PT VSN”
ELSE
WRITE “PT VN”
ENDIF
ELSE
x = -b:a
WRITE “Nghi m :”+xệ
ENDIF
23
24
*
Microsoft Visio
*
Crocodile Clips 6.05
*
Cách s d ng các ký hi uử ụ ệ
*
Ch y t ng b c và ki m tra k t quạ ừ ướ ể ế ả
25
