Tin học đại cương - Phần 1 Đại cương về tin học - Chương 6

Tài liệu tham khảo giáo trình Tin học đại cương dùng cho khối A do Đỗ Thị Mơ chủ biên - Bộ môn công nghệ phần mềm gồm 2 phần chia làm 13 chương - Phần 1 Đại cương về tin học - Chương 6 Giải thuật
Nội dung trích xuất từ tài liệu:
Tin học đại cương - Phần 1 Đại cương về tin học - Chương 6 CHƯƠNG VI: GI I THU T1. Khái ni m gi i thu t (Algorithms) - Khi c n gi i quy t m t bài toán trong th c t v i s tr giúp c a máy tính ñi n t tathư ng ph i bi t d li u vào c a bài toán (Input) là gì? và bài toán yêu c u d li u ra (Output)là gì?. Bư c ti p theo ta ph i thi t l p ñư c các bư c thao tác c th ñ t Input ta có ñư cOutput. Công vi c ñó trong tin h c ñư c g i là xây d ng gi i thu t. - Gi i thu t c a 1 bài toán là m t dãy các câu l nh (Statements) ch t ch và rõ ràngxác ñ nh m t trình t các thao tác trên m t s ñ i tư ng nào ñó sao cho sau m t s bư ch u h n th c hi n ta thu ñư c k t qu mong mu n. - V i ñ nh nghĩa như v y ta th y r ng ñ i v i m t bài toán c th có th có nhi u gi ithu t khác nhau nhưng t t nhiên là các gi i thu t ñó ph i cho cùng m t k t qu theo ñúng yêuc u c a bài toán. - Khi nghiên c u v gi i thu t thư ng ta ph i bi t ñư c gi i thu t ñó tác ñ ng lên dli u nào. Vi c l a ch n c u trúc d li u (Data structures) phù h p và vi c thi t l p ñư c cácgi i thu t ñúng ñ n có c u trúc t t và hi u qu là nh ng v n ñ m u ch t c a công vi c thi tl p ph n m m. Chính vì v y mà Niklaus Wirth ngư i sáng l p ra ngôn ng l p trình Pascal ñãt ng k t: Gi i thu t+C u trúc d li u= Chương trình Ví d : Xây d ng gi i thu t tìm UCLN c a 2 s nguyên dương a và b, ký hi u (a,b) + ð i v i bài toán này ta có Input: 2 s nguyên dương a, b Output: (a,b) + Gi i thu t ñư c xây d ng d a trên tính ch t N u a=b thì (a,b)=a N u a>b thì (a,b)=(a-b,b) N u ab thì thay th a b i a-b, n u a2. Các yêu c u v i gi i thu tGi i thu t c a bài toán ph i tho mãn 3 yêu c u sau: Yêu c u 1: Tính d ng Gi i thu t ph i d ng sau m t s h u h n các thao tác, ñây là yêu c u h t s c quan tr ngv i m t gi i thu t Yêu c u 2: Tính ñúng ñ n Ta ph i ñ t câu h i Li u gi i thu t có th hi n ñúng l i gi i c a bài toán không? .Thông thư ng chúng ta cài ñ t gi i thu t dư i d ng chương trình và cho th c hi n trên máytính v i m t s b d li u nào ñó, sau ñó so sánh v i nh ng k t qu mà ta ñã bi t. Nhưngcách th này ch kh ng ñ nh ñư c tính sai ch chưa th kh ng ñ nh ñư c tính ñúng ñ n c agi i thu t. B ng cách s d ng các công c toán h c ta có th kh ng ñ nh ñư c tính ñúng ñ nc a 1 gi i thu t nhưng thư ng thì ñây là m t công vi c ph c t p. Yêu c u 3: Tính ñơn gi n và hi u qu Ta thư ng mong mu n xây d ng ñư c m t gi i thu t ñơn gi n, d hi u, d l p trình.Nhưng ñôi khi thu t gi i ñơn gi n l i gây ra s lãng phí th i gian và b nh . Do ñó m c tiêulà ph i xây d ng ñư c các gi i thu t có th i gian th c hi n nhanh, h n ch t i ña dung lư ngb nh dành cho vi c lưu tr nh ng k t qu trung gian.3. Các cách di n t gi i thu t3.1. Cách 1: Li t kê t ng bư c Ví d : Có 31 que diêm, ngư i và máy thay nhau b c. M i l n b c t 1 ñ n 4 que. Aiph i b c sau cùng là thua. Hãy xây d ng thu t gi i sao cho máy b c trư c bao gi cũng thua. Bư c 1: Máy b c ng u nhiên x que diêm (1≤x≤4) Bư c 2: Ngư i b c (5- x) que, t ng s que diêm gi m ñi 5 que. N u s que diêm còn l ilà 1 que thì chuy n sang bư c 3, n u không thì quay l i th c hi n bư c 1 Bư c 3: Tuyên b ngư i th ng cu c3.2. Cách 2: S d ng lưu ñ S d ng phương ti n hình h c cũng là m t cách t t ñ minh ho gi i thu t c a 1 bàitoán. Trong lưu ñ ngư i ta s d ng các hình sau, v i kí hi u + là ñúng, - là sai. - + Kh i l nh Kh i i u ki n Cung Kh i b t u và k t thúc 103Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 103 a. C u trúc r nhánh - R nhánh d ng khuy t: if then (hình 1) - R nhánh d ng ñ : if then else (hình 2) - + - + K K L nh L nh 2 L nh 1 - C u l nh l a ch n: case Giá tr 1: Th c hi n l nh 1 Giá tr ình 1 c hi n l nh 2 H 2: Th Hình 2 .......................................... Giá tr n: Th c hi n l nh n else Th c hi n l nh (n+1) end - - - L nh (n+1) gt1 ...