Cấu trúc dữ liệu - Phần 1 pptx

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 (305.12 KB, 36 trang )

LOGO
GVGD: Trng Phc Hi
Tng quan gii thut
2
Ni dung
1. Bài toán và gii thut
2. Biu din gii thut
3. Gii toán trên máy tính
4. Thit k gii thut
3
Bài toán và gii thut
 Khái nim bài toán
 Là mt công vic mà ta mun máy tính thc hin thay cho
ta hoc h tr mt phn

4
Bài toán và gii thut
 Mô t bài toán

 Bài toán đc mô t thông qua các thành phn input và
output

 Input: d liu đu vào (nguyên liu) ti thiu đ gii đc
bài toán

 Output: d liu đu ra (thành phm) theo yêu cu ca bài
toán

 Input và output cn phi đc xác đnh đúng đn
5
Bài toán và gii thut

 Ví d bài toán

 Cho 2 s nguyên dng a, b. Hãy tìm UCLN ca a và b

 Input: a, b

 Output: c = UCLN(a, b)

 Cho 2 s nguyên a, b. Hãy tìm phân s ti gin ca phân
s a/b.

 Input: a, b

 Output: tu, mau
6
Bài toán và gii thut
 Ví d không phi bài toán

 Cho danh sách đim thi hc k môn gii thut ca sinh viên
khoa CNTT. Cho bit sinh viên có đim thi cao nht

 Hãy sp th t danh sách sinh viên khoa CNTT theo đim
thi môn gii thut
7
Bài toán và gii thut
 Khái nim gii thut (thut toán)

 Là dãy hu hn các thao tác đc sp xp theo mt trình
t xác đnh đ to ra output t input ca bài toán.

 Phân bit gii thut và thut gii:

 Gii thut: luôn cho kt qu đúng vi mi trng hp
ca input.

 Thut gii: cho kt qu ca bài toán là gn đúng, nhng
không luôn luôn đúng.
8
Bài toán và gii thut
 Ví d: gii phng trình bc 1: ax + b = 0

 Bc 1: Nhp a, b
 Bc 2: Kim tra a  0
 Nu đúng thì sang bc 3.
 Ngc li sang bc 4.
 Bc 3:
 Thông báo phng trình có nghim –b/a.
 n bc 5.
 Bc 4: Kim tra b  0
 Nu đúng thì phng trình vô nghim.
 Ngc li phng trình có vô s nghim.
 Bc 5: kt thúc
9
Bài toán và gii thut
 Các tính cht ca gii thut

 Tính dng: gii thut phi đi đn kt thúc sau mt s bc
hu hn các thao tác thi hành

 Tính xác đnh: các thao tác thi hành phi rõ ràng và ch có

mt cách hiu

 Tính đúng đn: gii thut phi cho output chính xác trong
mi trng hp ca input

 Tính hiu qu: gii thut phi có tc đ thi hành nhanh, s
dng ít b nh
10
Bài toán và gii thut
 Ví d ung thuc

 Bc 1: cho 1 mung caưé thuc vào ly
 Bc 2: pha 20ml nc và ung sau khi n
 Bc 3: ung đn khi nào ht bnh thì dng
11
Bài toán và gii thut
 Ví d nu cm

 Bc 1: đong 2 lon go
 Bc 2: vo sch và cho vào ni
 Bc 3: đ nc ngp 1 đt ngón tay
 Bc 4: cm đin nu đn khi đèn tt là chín

12
Bài toán và gii thut
 Ví d nu cm

 Bc 1: đong 2 lon go
 Bc 2: vo sch và cho vào ni
 Bc 3: đ nc ngp 1 đt ngón tay
 Bc 4: cm đin nu đn khi đèn tt là chín

13
Ni dung
1. Bài toán và gii thut
2. Biu din gii thut
3. Gii toán trên máy tính
4. Thit k gii thut
14

Biu din gii thut
 Lit kê các bc thi hành

 V s đ khi thi hành

 Mã gi điu khin

15
Biu din gii thut
 Lit kê các bc thi hành:

 Ch ra thao tác thc hin trong tng bc mt

 u đim: biu din đc các bài toán có s bc thc thi
nhiu

 Nhc đim: khó thy đc tng th trc quan v lung thi
hành  các bc ca bài toán
16
Biu din gii thut
 Gii pt bc 2: ax
2
+ bx + c = 0 (a  0)

 Bc 1: Nhn giá tr ca a, b, c
 Bc 2: tính d = b
2
– 4.a.c
 Bc 3: kim tra d ≥ 0
 Nu đúng: đn bc 4

 Ngc li: đn bc 5
 Bc 4:
 Kt lun nghim là x
1
= (-b - d)/(2.a) và x
2
= (-b +
d)/(2.a)
 n bc 6.
 Bc 5:
 Kt lun phng trình vô nghim. n bc 6.
 Bc 6: kt thúc
17
Biu din gii thut
 V s đ khi thi hành

 S dng các khi kí hiu đ mô t cho tng thao tác làm
vic

 u đim: trc quan, kim tra đc lung đng đi ca
thut toán

 Nhc đim: nu bài toán có quá nhiu thao tác s gây ri
do có quá nhiu kí hiu biu din. Do đó ch biu din các
bài toán  dnh nh
18
Biu din gii thut
 Các khi biu din thao tác thi hành
Bt đu gii thut
Kt thúc gii thut

Hng thi
hành
nhp/xut
x lý
tính toán
T F
kim tra
19
Biu din gii thut
 Gii phng trình bc 1: ax + b = 0
Bt đu
nhp a, b
a  0
F
b  0
Kt thúc
T
Phng trình
có nghim –b/a
F T
Phng trình
vô nghim
Phng trình
vô s nghim
20
Biu din gii thut
 Mã gi điu khin:

 S dng mã gi ta ngôn ng lp trình đ biu din thut
toán.

 vd: kim tra s nguyên n có phi là s nguyên t?

dem = 0
for i = 1 to n do
if (n % 2 = 0) then dem = dem + 1
if dem = 2 then printf(“là s nguyên t”)
else printf(“không phi là s nguyên t”)

21
Ni dung
1. Bài toán và gii thut
2. Biu din gii thut
3. Gii toán trên máy tính
4. Thit k gii thut
22
Gii toán trên máy tính
 Các bc gii mt bài toán trên máy tính:

 Xác đnh bài toán: xác đnh input, output

 La chn hoc thit k gii thut, biu din gii thut.

 Lp trình đa gii thut lên máy tính.

 Hiu chnh chng trình
23
Gii toán trên máy tính
 Xác đnh bài toán:

 Xác đnh danh sách input, output ca bài toán.

 Xác đnh các điu kin ràng buc hoc min giá tr đi vi
input và output.
24
Gii toán trên máy tính
 La chn hoc thit k gii thut

 Thit k gii thut

 La chn CTDL thích hp đ lu tr d liu ca bài
toán: bin, cu trúc, mng, DSLK, cây, bng bm…

 Tính toán kích thc vùng nh ca gii thut

 Tính toán s thao tác mà gii thut thc hin
25
Gii toán trên máy tính
 La chn hoc thit k gii thut:

 Mô t gii thut: s dng cách lit kê các bc thc thi, v

s đ khi hoc mã gi

 Kim tra tính đúng đn ca gii thut thông qua s đ mô
t

Cấu trúc dữ liệu - Phần 1 pptx

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về