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

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

97
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 T 1. 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 ta thư 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ó ñư c Output. 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àng xá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ư c h 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 i thu 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êu c 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 d li 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ác gi 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 t l 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 a
2. Các yêu c u v i gi i thu t Gi 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 ng v 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áy tí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ưng cá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 a gi 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 ñ n c 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êu là 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ư ng b 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 t 3.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. Ai ph 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 i là 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 c 3.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ài toá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 103 Trư 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 gt2 gtn + + + L nh 1 L nh 1 L nh n Hình 3 b. C u thúc l p + L p m t s l n ñ nh trư c: D ng 1: for i:=m to n do Th c hi n l nh v i i nh n các giá tr nguyên tăng t m t i n v i bư c nh y b ng 1 D ng 2: for i:=n downto m do Tương t như d ng 1 nhưng bư c nh y gi m b ng 1 + L p v i ñi u ki n trư c: while do < l nh> Khi ñi u ki n còn ñúng thì còn th c hi n l nh, quá trình l p k t thúc khi ñi u ki n sai (hình 1) + L p v i ñi u ki n sau: repeat until Khi ñi u ki n còn sai thì còn th c hi n l nh, quá trình l p k t thúc khi ñi u ki n ñúng (hình 2) - + K L nh LLnh L nh nh K - + 104 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 104
3.3 Cách 3: S d ng gi ngôn ng có c u trúc t a ngôn ng l p trình b c cao Là phương pháp di n t gi i thu t d a vào các c u trúc ñi u khi n, cùng v i các t khoá c a m t ngôn ng l p trình b c cao nào ñó. Trong giáo trình này ta s s d ng ngôn ng t a Pascal ñ di n t gi i thu t. Cách di n ñ t này ñã ti p c n g n hơn v i ngôn ng l p trình. Ví d : V i thu t gi i tìm UCLN trên ta có th di n ñ t như sau while a≠b begin if a>b then thay a b i a-b else thay b b i b-a end write ư c chung l n nh t là a 4. Thi t k gi i thu t 4.1. Mô-ñun hoá và vi c gi i quy t bài toán Nh ng bài toán ta g p trong th c t thư ng là ph c t p, trong trư ng h p ñó ngư i ta thư ng chia bài toán thành nh ng bài toán nh và d gi i quy t hơn. Nghĩa là coi bài toán ban ñ u là Mô- ñun chính, ta chia nó thành các Mô- ñun con, và m i Mô- ñun con này có th l i ñư c chia thành các Mô- ñun nh hơn... Cách gi i quy t bài toán như v y ngư i ta thư ng g i là chi n thu t "Chia ñ tr "(divide and conquer). Trong khi l p trình vi c chia chương trình chính thành các chương trình con th hi n tính có c u trúc c a ngôn ng l p trình v m t chương trình 4.2. Tinh ch nh t ng bư c gi i thu t Tinh ch nh t ng bư c là phương pháp thi t k gi i thu t g n li n v i l p trình. Bư c ñ u gi i thu t ñư c minh ho b ng ngôn ng t nhiên, càng các bư c sau ngôn ng t nhiên ñư c thay th b i ngôn ng t nhiên pha l n ngôn ng l p trình mà ta g i là gi ngôn ng . Ta có sơ ñ sau: Ngôn ng t nhiên→ Gi ngôn ng → Ngôn ng l p trình 4.3. Phân tích thu t gi i Phân tích gi i thu t ph i căn c vào 3 tiêu chu n ñ i v i m t gi i thu t: Tính d ng, tính ñúng ñ n, tính ñơn gi n và hi u qu . Vi c ki m tra gi i thu t là m t ph n h t s c quan tr ng, lý tư ng là khi có th kh ng ñ nh m t cách hình th c tính ñúng ñ n c a gi i thu t. Tuy nhiên trong th c t th i gian và công s c ñ vi t ra m t cách c n th n và ñ y ñ t t c nh ng chi ti t ch ng minh tính ñúng ñ n c a m t gi i thu t ph c t p thư ng là không cho phép. Ngư i l p trình thư ng áp d ng các bi n pháp sau: - Ch ng minh m t cách suy di n r ng nh ng bư c trong gi i thu t là ñúng ñ n. Nghĩa là gi i thu t b t ñ u b ng m t kh ng ñ nh (gi thi t) v d li u vào và dùng phương pháp suy lu n lôgic ñ ch ra r ng vi c th c hi n gi i thu t s cho m t kh ng ñ nh (k t lu n) v ñ u ra. - Th h ên gi i thu t b ng m t ngôn ng l p trình và th th c hi n chương trình v i các b d li u vào mà k t qu ta ñã bi t trư c. Thư ng thì các l i v cú pháp và l i lúc th c hi n chương trình thư ng d tìm và s a ch a còn các l i lôgic thư ng khó phát hi n hơn nhi u. 105 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 105
- Có ñôi lúc viêc ki m tra chương trình ph i th c hi n th công, ki m tra t ng bư c, t ng th t c c a chương trình chính. K thu t này ñư c g i là “ñi b qua chương trình”(Walking through the program) - Quan tâm ñ c bi t t i th i gian th c hi n chương trình, th i gian th c hi n ph thu c r t nhi u vào vi c t ch c d li u ñưa vào (kích thư c d li u). 5. Gi i thu t s p x p (Sorting) S p x p là m t trong s yêu c u thư ng xuyên xu t hi n trong quá trình x lý s li u. B n ch t c a thu t gi i s p x p là b trí l i v trí c a s li u theo th t tăng d n ho c gi m d n. Có nhi u gi i thu t s p x p trong tin h c, trong giáo trình này chúng ta s ñ c p ñ n m t s thu t gi i ñơn gi n ñó là s p x p l a ch n (selection sort), s p x p chèn (insertion sort) và s p x p n i b t (bubble sort). ð ñơn gi n gi s yêu c u c a bài toán là: S p x p m t dãy s cho trư c a1, a2, ......, an theo th t tăng d n. 5.1 S p x p l a ch n (selection sort) Thu t gi i ch n ñư c di n t như sau: Tìm ph n t nh nh t trong dãy s và hoán v nó v i ph n t ñ u tiên, tìm ph n t nh nh t k ti p và hoán v nó v i ph n t th hai. Ti p t c quá trình này ñ n khi toàn b dãy s ñư c s p x p. procedure Selection_Sort; begin for i:=1 to n-1 do begin m:=i for j:=i+1 to n do if aj
procedure Insertion_Sort begin for i:=2 to n do begin k:=ai j:=i while aj-1>k do begin aj:=aj-1, j:=j-1 end aj:=k end end Ví d Dãy s ban ñ u : 3 6 -2 7 5 i=2 3 6 -2 7 5 i=3 -2 3 6 7 5 i=4 -2 3 6 7 5 i=5 -2 3 5 6 7 5.3 S p x p n i b t (bubble sort) Thu t gi i này còn có tên g i khác là s p x p b ng cách ñ i ch tr c ti p (exchange sort), thu t gi i n i b t ñư c di n t như sau: Duy t dãy s theo th t t ph i sang trái n u hai ph n t k c n ngư c th t thì ñ i ch cho nhau. Như v y sau lư t duy t ñ u tiên ph n t ñ u tiên s là ph n t nh nh t, sau lư t th hai ph n t nh th hai ñư c chuy n lên v trí th hai...c như v y dãy s s ñư c s p x p tăng d n. procedure Bubble_Sort begin for i:=1 to n-1 do for j:=n downto i+1 do if aj
6.1 Tìm ki m tu n t (sequential searching) ðây là thu t gi i tìm ki m ñơn gi n nh t, ta s duy t tu n t dãy s , thu t gi i s k t thúc khi tìm th y ph n t b ng giá tr X ho c khi duy t h t dãy s nhưng không có ph n t nào có giá tr là X procedure Sequential_Searching begin i:=1 while ai≠ X do i:=i+1 if i=n+1 then không có ph n t c n tìm else v trí ph n t c n tìm là i end 6.2 Tìm ki m nh phân (binary searching) Gi s dãy s ñã ñư c s p x p tăng d n a1≤a2≤.....≤an (trư ng h p s p x p gi m d n thì tương t ), thu t gi i nh phân g n gi ng như khi ta tìm m t t trong t ñi n. ð tìm ph n t b ng X trư c tiên ta so sánh nó v i ph n t v trí gi a c a dãy s n u X nh hơn thì X ch có th trong m t n a trư c c a dãy n u ngư c l i thì X ch có th trong n a sau c a dãy. L p l i quá trình tìm ki m ñó ñ n khi tìm th y ho c dãy s tr nên r ng (không tìm th y). procedure Binary_Searching begin left:=1 right:=n repeat mid:=[(left+right)/2] (*Kí hi u [a] nghĩa là l y ph n nguyên c a s th c a*) if Xright) if X=amid then v trí c n tìm là mid else không có ph n t c n tìm end Ví d : Tìm ph n t 28 trong dãy s sau [4 15 28 33 67 99 103] L pl n1 [4 15 28] L pl n2 [28] 7. Gi i thu t ñ quy 7.1. Khái ni m ñ qui M t ñ i tư ng ñư c g i là ñ qui n u nó bao g m m t ph n c a chính nó hay ñư c ñ nh nghĩa b i chính nó. Trong khi thi t k gi i thu t ta thư ng thi t k dư i d ng các mô- ñun. Khi gi i thu t ñư c cài ñ t thành chương trình thí các mô- ñun s tương ng v i các chương trình con (hàm- function và th t c- procedure), Chương trình con ñư c g i là ñ qui n u trong thân c a nó có l i g i tr c ti p ho c gián ti p ñ n chính b n thân nó. ð qui có ý nghĩa ñ c bi t quan tr ng trong các ñ nh nghĩa toán h c 108 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 108
Ví d 1: ð nh nghĩa s t nhiên + 0 là s t nhiên + S ti p theo c a m t s t nhiên là m t s t nhiên Ví d 2: ð nh nghĩa n! + 0!=1 + n!=n*(n-1)! n u n>0 - ð nh nghĩa m t phép ñ qui g m có 2 ph n + Trư ng h p suy bi n: Giúp cho quá trình ñ qui k t thúc + Ph n ñ qui (hay ph n qui n p): Trong ñó tác ñ ng c n ñư c th c hi n cho giá tr hi n th i c a các tham s ñư c ñ nh nghĩa b ng các tác ñ ng hay giá tr ñư c ñ nh nghĩa trư c ñây Trong ví d ñ nh nghĩa n! thì trư ng h p suy bi n ñ nh nghĩa 0!, ph n qui n p ñ nh nghĩa n! qua các giá tr c a n và giá tr c a (n-1)! D nh n xét, n u (n-1)! ñã tính ñư c thì n! s d dàng tính ñư c. V i cách suy di n tương t , (n-1)! s tính ñư c n u như (n-2)! ñã tính ñư c... cu i cùng 1! s tính ñư c n u 0! ñã tính ñư c. Ta th y r ng 0! ñã cho trong ñ nh nghĩa. Do v y ñi ngư c t cu i, vì 0! ñã tính ñư c nên 1! cũng tính ñư c,....,sau khi (n-1)! ñã có ta s nh n ñư c n! Minh ho : Tính 3! 3!=3*2!=3*2=6 2!=2*1!=2*1=2 1!=1*0!=1*1=1 0!=1 Gi i thu t ñư c vi t dư i d ng th t c hàm (t a Pascal) như sau: function giaithua(n) begin if n=0 then giaithua:=1 (* trư ng h p suy bi n*) else giaithua:=n*giaithua(n-1) (* ph n ñ qui*) end Chú ý: Không ph i lúc nào tính ñ qui trong cách gi i bài toán cũng th hi n rõ nét và d phát hi n như ví d trên. Do ñó mu n bi t gi i thu t c a m t bài toán có th thi t k dư i d ng gi i thu t ñ qui ñư c hay không? Có th th y câu tr l i qua vi c tr l i các câu h i sau : + Có th ñ nh nghĩa ñư c bài toán dư i d ng m t bài toán cùng lo i nhưng “nh ” hơn không? + Kích thư c c a bài toán s gi m ñi m i bư c g i ñ qui như th nào? + Trư ng h p nào c a bài toán ñư c coi là trư ng h p suy bi n? 7. 2. Ví d v gi i thu t ñ qui : Bài toán tháp Hà N i Bài toán Tháp Hà N i là m t ví d c ñi n cho th y thu t toán ñ qui là ñ c bi t thích h p. Có th gi i quy t bài toán m t cách d dàng n u dùng ñ qui, nhưng cách gi i không ñ qui là tương ñ i khó. N i dung bài toán: T i c c A có n chi c ñĩa, ñĩa to dư i, ñĩa nh trên. Chuy n các ñĩa t c c A sang c c C có th nh c c B làm v trí trung chuy n theo các quy t c sau: - M i l n ch ñư c chuy n m t ñĩa và ph i là ñĩa trên cùng - ðĩa l n không bao gi ñư c phép n m trên ñĩa nh 109 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 109
- Khi chuy n m t ñĩa, nó ph i ñư c ñ t vào m t trong 3 c c trên Hãy ch ra th t các bư c chuy n. A B C M t truy n thuy t cho r ng các th y tu ði n Bramah ñư c cho m t bài toán ñ v i m t n n vàng có 3 kim vàng trên 1 c c có 64 ñĩa vàng. Khi h chuy n các ñĩa vàng theo các lu t c a bài toán trên, n u m i giây chuy n ñư c m t ñĩa và h b t ñ u công vi c t năm 0, ñ n khi hoàn thành công vi c thì s là ngày t n th . Nh ng ngư i m i b t ñ u có th gi i bài toán m t cách d dàng v i s các ñĩa là bé, nhưng h s r t khó khăn khi s ñĩa tăng lên 7,8 và l n hơn. Tuy nhiên v i m t nhà l p trình thì có th gi i bài toán m t cách không m y khó khăn. Cách gi i: N u có m t ñĩa, chuy n nó t c c A sang c c C. Bài toán gi i ñư c v i n=1 Gi s r ng bài toán có nghi m v i n-1 ñĩa , nghi m v i n ñĩa có th nh n ñư c m t cách d dàng nh dùng phép ñ quy: + Chuy n n-1 ñĩa trên cùng c c A sang c c B, dùng c c C làm trung chuy n + Chuy n ñĩa còn l i c c A sang c c C + Chuy n n-1 t c c B sang c c C, dùng c c A làm trung chuy n Ta có th vi t gi i thu t c a bài toán Tháp Hà N i như sau: procedure Move(n,A,B,C) (* Chuy n n ñĩa t c c A sang c c C, dùng c c B làm trung chuy n*) begin if n=1 then chuy n ñĩa t A sang C else begin Move(n-1,A,C,B) (* Chuy n n-1 ñĩa t A sang B, dùng C làm trung chuy n*) Move(1,A,’ ‘,C) (* Chuy n 1 ñĩa t c c A sang c c C*) Move(n-1,B,A,C) (* Chuy n n-1 ñĩa t B sang C, dùng A làm trung chuy n*) end end 110 Trư ng ð i h c Nông nghi p 1 - Giáo trình Tin h c ñ i cương --------------------------------------------- 110
Bài t p chương VI: Thu t gi i Vi t gi i thu t cho các bài toán sau: 1. Tính n giai th a: n! =1.2...n v i n>1 2. Tính các t ng: S=1/2 + 1/4 +...+ 1/(2k) Q=1.1!+2.2!+...+n.n! 3. Tìm và in ra t t c các s chính phương nh hơn m t s cho trư c, cho bi t có bao nhiêu s chính phương như v y. 4. Vi t chương trình gi i bài toán c : " V a gà v a chó, bó l i cho tròn, ba mươi sáu con, m t trăm chân ch n. H i có bao nhiêu gà, bao nhiêu chó?" 5. Vi t chương trình tìm ư c s chung l n nh t c a 2 s nguyên dương cho trư c. x x2 xn + ... v i ñ chính xác ε=10-4 ( ABS(xn/n!) < ε ), giá tr x 6. Tính Ex= 1 + + + ...+ 1! 2 ! n! ñư c nh p vào t bàn phím khi ch y chương trình. 7. C n có 50000 ñ t các lo i gi y b c 1000ñ, 2000ñ và 5000ñ. Tìm t t c các phương án có th . 8. Chuy n m t s th p phân nguyên dương thành m t s nh phân, in ra màn hình d ng X10 = Y2 9. Tính tích phân xác ñ nh c a m t hàm s trên m t ño n cho trư c 10. Vi t chương trình tìm và in ra màn hình các s nguyên t nh hơn m t s cho trư c. 11. Cho dãy s sau: a1,a2,....,an . Vi t chương trình tìm ph n t l n nh t, ph n t nh nh t c a dãy s ñó. 12. Cho dãy s sau: a1,a2,....,an . Vi t chương trình s p x p dãy theo th t tăng d n . 13. Cho dãy s sau: a1,a2,....,an . Vi t chương trình ñ m s ph n t dương và xoá ñi ph n t th m trong dãy (m