›
›

Bài giảng Tin học căn bản - Chương III: Giải quyết bài toán bằng máy tính

ppt 42 trang ngocly 1690
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học căn bản - Chương III: Giải quyết bài toán bằng máy tính", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_tin_hoc_can_ban_chuong_iii_giai_quyet_bai_toan_ban.ppt

Nội dung text: Bài giảng Tin học căn bản - Chương III: Giải quyết bài toán bằng máy tính

  1. CHƯƠNG III GIAÛI QUYEÁT BAØI TOAÙN BAÈNG MAÙY TÍNH 133
  2. CHƯƠNG III GIAÛI QUYEÁT BAØI TOAÙN BAÈNG MAÙY TÍNH 3.1 Kyõ thuaät laäp trình 3.2 Thuaät toaùn vaø Thuaät giaûi 3.3 Bieåu dieãn thuaät toaùn 3.4 Caùc böôùc giaûi quyeát baøi toaùn treân maùy 134
  3. 3.1 Kyõ thuaät laäp trình 135
  4. Khaùi quaùt • Kyõ thuaät xaây döïng phaàn meàm chính laø kyõ thuaät laäp trình. Laäp trình vöøa laø moät kyõ thuaät vöøa laø moät ngheä thuaät. • Laäp trình (Programming) thöïc chaát laø ñieàu khieån - baèng moät ngoân ngöõ laäp trình cuï theå - caùch xöû lyù thoâng tin treân maùy theo yeâu caàu cuûa baøi toaùn ñaët ra. • Ñeå laäp trình, phaûi bieát caùch toå chöùc döõ lieäu (nguyeân lieäu ñeå maùy xöû lyù) vaø caùch thöùc xöû lí döõ lieäu (thuaät giaûi) ñeå cho ra keát quaû mong muoán. 136
  5. PROGRAMMING = ALGORITHMS + DATA STRUCTURE 137
  6. • PHAÛI TOÅ CHÖÙC DÖÕ LIEÄU THEO CAÙCH TOÁT NHAÁT : Döõ lieäu trong tin hoïc phaûi ñöôïc phaân loaïi, xaùc ñònh moät caùch raïch roøi theo nhöõng quy ñònh chaët cheõ, chính xaùc ñeå maùy coù theå phaân bieät, nhaän bieát, löu tröõ vaø xöû lyù • PHAÛI TÌM ÑÖÔÏC THUAÄT TOAÙN TOÁT NHAÁT, TOÁI ÖU NHAÁT 138
  7. • 4 TIEÂU CHUAÅN ÑAÙNH GIAÙ MOÄT CHÖÔNG TRÌNH : ü Tính tin caäy ü Tính uyeån chuyeån ü Tính trong saùng ü Tính höõu hieäu 139
  8. LAÄP TRÌNH CAÁU TRUÙC ü Caáu truùc veà maët döõ lieäu ü Töø nhöõng leänh ñôn giaûn ñaõ coù hoaëc nhöõng leänh ñaõ coù caáu truùc, coù theå xaây döïng nhöõng leänh coù caáu truùc phöùc taïp hôn ü Caáu truùc veà maët chöông trình : Moät chöông trình lôùn coù theå chia thaønh nhieàu modun chöông trình con ñoäc laäp • Moãi chöông trình con laïi coù theå phaân chia thaønh caùc chöông trình con khaùc. PASCAL laø moät trong caùc ngoân ngöõ tieâu bieåu veà coù caáu truùc 140
  9. 3.2 Thuaät toaùn vaø Giaûi thuaät 141
  10. KHAÙI NIEÂM THUAÄT TOAÙN Lµ kh¸i niÖm c¬ së cña To¸n häc vµ Tin häc ThuËt to¸n (Algorithm) lµ mét hÖ thèng chÆt chÏ vµ râ rµng c¸c quy t¾c nh»m x¸c ®Þnh mét d·y c¸c thao t¸c trªn những ®èi t­îng, sao cho sau mét sè hữu h¹n b­ícthùc hiÖn c¸c thao t¸c ta ®¹t ®­îc môc tiªu ®Þnh tr­íc. 142
  11. Ng­êi hoÆc m¸y thùc hiÖn mét thuËt to¸n ®­îcgäi lµ mét bé xö lý. Nh­ vËy mét bé xö lý cña mét thuËt to¸n T nµo ®ã lµ mét c¬ chÕ cã khả năng thùc hiÖn c¸c thao t¸c trªn c¸c ®èi t­îng theo mét trình tù do T quy ®Þnh. 143
  12. Cïng mét bµi to¸n cã thÓ cã nhiÒu thuËt to¸n kh¸c nhau. ThuËt to¸n ®¬n giaûn, dÔ hiÓu, cã ®é chÝnh x¸c cao, ®­îc baûo ®aûm vÒ mÆt to¸n häc, dÔ triÓn khai trªn m¸y, thêi gian thao t¸c ng¾n, ®­îcgäi lµ thuËt to¸n tèi ­u. 144
  13. Nghiªn cøu thuËt to¸n lµ mét trong nhöõng vÊn ®Ò quan träng nhÊt cña Tin häc. Lý thuyÕt vÒ thuËt to¸n phaûi giaûi quyÕt c¸c vÊn ®Ò sau : -Nhöõng bµi to¸n nµo giaûi ®­îcb»ng thuËt to¸n; bµi to¸n nµo kh«ng giaûi ®­îc b»ng thuËt to¸n -Tìm thuËt to¸n tèt nhÊt, tèi ­ucña mét bµi to¸n -TriÓn khai thuËt to¸n trªn m¸y tÝnh 145
  14. Vaøi ví duï ThuËt to¸n giaûi ph­¬ng trình bËc hai : A X2 + BX + C = 0 (A 0) -B­íc 1 : TÝnhDELTA = B*B-4*A*C -B­íc 2 : So s¸nhDELTA víi sè 0 -B­íc 3 : RÏ lµm 3 tr­êng hîp : -Tr­êng hîpDELTA 0 :tÝnh hai nghiÖm ph©n biÖt: X1, X2 th«ng b¸o nghiÖm ; kÕt thóc thuËt to¸n. 146
  15. ThuËt to¸n Hoocne tÝnh gi¸ trÞ cña ®a thøc : n n-1 1 Cho Pn(X)=AnX + An-1X + +A1X +A0 TÝnh Pn(c) ? Pn(c)=( ((An.c +An-1).c + An-2 ) ).c + A0 - B­íc 1 : Cho i = n ; Q = An - B­íc 2 : Cho i nhËn gi¸ trÞ cò cña i trõ 1 : i = i - 1 So s¸nh i víi 0. - B­íc 3 : RÏ lµm 2 tr­êng hîp : 1-Tr­êng hîp i >= 0 : tÝnh Q b»ng gi¸ trÞ cò cña Q nh©n víi c céng víi Ai ; Quay trë l¹i b­íc 2. 2-Tr­êng hîp i < 0 : th«ng b¸o kÕt quaû Q; KÕt thóc thuËt to¸n. 147
  16. ý nghÜa cña thuËt to¸n hoocne n n-1 1 Cho Pn(X)=AnX + An-1X + +A1X +A0 ViÕt ®a thøc d­íi d¹ng : Pn(c)=( ((An.c +An-1).c + An-2 ) ).c + A0 ChØ bao gåm c¸c phÐp nh©n, céng liªn tiÕp P2(c)=(A2.c +A1).c + A0 P3(c)=((A3.c +A2).c + A1).c + A0 148
  17. 6 TÍNH CHAÁT CUÛA THUAÄT TOAÙN 1-tÝnh dõng - kÕt thóc 2-tÝnh x¸c ®Þnh 3-tÝnh hµng lo¹t 4-tÝnh KHẢ THI 5-tÝnh ®Çy ®ñ-vÐt c¹n 6-tÝnh ®óng ®¾n 149
  18. TÍNH DÖØNG ThuËt to¸n phaûi kÕt thóc sau mét sè höõu haïn b­íc. VÝ dô : ThuËt to¸n kh«ng dõng 1) Xo¸ bảng 2) ViÕt sè 9 3) Thùc hiÖn b­íc 1 VÝ dô 7 : ThuËt to¸n kh«ng dõng Đäc c¸c sè tù nhiªn liªn tiÕp, b¾t ®Çu tõ 1 150
  19. TÍNH XAÙC ÑÒNH C¸c thao t¸c ë mçi b­ícph ải hÕt søc râ rµng vµ chØ ®­îc hiÓu theo mét nghÜa duy nhÊt. Trong cïng mét ®iÒu kiÖn, hai bé xö lý kh¸c nhau hoÆc hai lÇn thao t¸c kh¸c nhau phải cho cïng mét kÕt quả khi thùc hiÖn cïng mét thuËt to¸n. C¸c ng­êikh¸c nhau cïng sö dông mét thuËt to¸n, sÏ hµnh ®éng gièng nhau cho dï hä kh«ng hiÓu gì vÒ bản chÊt vµ ý nghÜa cña vÊn ®Ò. 151
  20. TÍNH HAØNG LOAÏT ThuËt to¸n cã hiÖu lùc nh­nhau ®èi víi c¸c bµi to¸n cïng lo¹i, cã cïng miÒn ¸p dông thuËt to¸n. ThuËt to¸n Hooc-ne cã tÝnh hµng lo¹t trªn tËp số thực R v￿ bÊt kì ®a thøc ®¹i sè bËc nµo. ThuËt to¸n Giải phương trình bậc 2 không cã tÝnh hµng lo¹t nÕu sè liÖu g¸n cho a, b,c nhËp tõ bµn phÝm. Ch¼ng h¹n khi nhËp a=0 hoÆc a kh«ng phải lµ sè ￿. 152
  21. TÍNH KHAÛ THI ThuËt to¸n phải bao gåm những thao t¸c mµ m¸y cã thÓ thùc hiÖn ®­îc. Máy tính chØ cã thÓ thùc hiÖn ®­îc những phÐp to¸n sè häc, c¸c phÐp so s¸nh, c¸c phÐp logic, c¸c phÐp nhËp xuÊt th«ng tin tiªu chuÈn. ThuËt to¸n Hooc-ne cã tÝnh khả thi. ThuËt to¸n Giải phương trình bậc 2 kh«ng cã tÝnh khả thi trong tr­ênghîp DELTA > 0 vì m¸y kh«ng thÓ thùc hiÖn phÐp tÝnh khai căn DELTA. 153
  22. TÍNH ÑAÀY ÑUÛ-VEÙT CAÏN ThuËt to¸n phải vÐt ®­îchÕt c¸c tình huèng, c¸c khả năng cã thÓ xẩy ra, kh«ng bá sãt bÊt kỳ mét tr­ênghîp nµo trong miÒn ¸p dông. ThuËt to¸n Hooc-ne v￿ Giải phương trình bậc 2 kh«ng cã tÝnh ®Çy ®ñ nÕu dữ liÖu nhËp tõ bµn phÝm 154
  23. TÍNH ÑUÙNG ÑAÉN ThuËt to¸n phải cho kÕt quả ®óng cña bµi to¸n nghÜa lµ phải ®­îc chøng minh vÒ mÆt to¸n häc . ThuËt to¸n tìm béi sè chung nhá nhÊt cña hai sè nguyªn d­¬ng a,b ký hiÖu c=BSCNN(a,b) : -B1 : NÕu a = 1 thì c = b , dõng NÕu b = 1 thì c = a , dõng -B2 : NÕu a >1 vµ b >1 thì c = a*b , dõng Cã thÓ kiÓm tra 100 tr­ênghîp cña a, b ®Òu cho kÕt qủa ®óng, nh­ng víi a = 4, b = 2 thì sai. ThuËt to¸n này kh«ng cã tÝnh ®óng ®¾n trªn N 155
  24. MOÄT THUAÄT TOAÙN PHAÛI THOAÛ MAÕN ÑOÀNG THÔØI CAÙC TÍNH CHAÁT TREÂN 156
  25. CAÁU TRUÙC CÔ BAÛN CUÛA THUAÄT TOAÙN 157
  26. CAÁU TRUÙC TUAÀN TÖÏ THAO TÁC 1 THAO TÁC 2 THAO TÁC 3 158
  27. CAÁU TRUÙC REÕ NHAÙNH ĐIỀU KIỆN THAO TÁC 1 THAO TÁC 2 159
  28. CAÁU TRUÙC VOØNG LAËP THAO TÁC ĐIỀU KIỆN THAO TÁC 160
  29. CAÙC PHÖÔNG PHAÙP BIEÅU DIEÃN THUAÄT TOAÙN 161
  30. 1) Dïng ng«n ngữ mẹ đẻ hoặc ngôn ngữ mã giả 2) Ng«n ngữ l­u ®å 3) Ng«n ngữ lËp trình BiÓu diÔn thuËt to¸n b»ng ng«n ngữ lËp trình chÝnh lµ thảo ch­¬ng, môc tiªu quan träng trong Tin häc. 162
  31. Ngoân ngöõ maõ giaû ThuËtTo¸nPh­¬ngTrinhBËcHai; BiÕn A,B,C,DELTA,X1,X2 : SèThùc ; B¾tĐÇu NhËp A,B,C; DELTA:=B*B-4*A*C; NÕu DELTA <0 Thi XuÊt 'Ph­¬ng trinh v« nghiÖm '; Dõng; NÕu DELTA =0 Thi X1:=(-B/2/A); X2:=X1; XuÊt 'NghiÖm kÐp X1,X2 '; Dõng; NÕu DELTA =0 Thi X1:=(-B-CanBËcHai(DELTA))/2/A; X2:=(-B+CanBËchH(DELTA))/2/A; XuÊt 'NghiÖm ph©n biÖt X1,X2 '; Dõng; KÕtThóc. 163
  32. BEGIN Löu ñoà NhËp A,B,C DELTA =B*B-4*A*C X1=X2=-B/2/A V¤ NGHI£M DELTA THùC ? X1= X2= IN KÕt QUa END 164
  33. Ngoân ngöõ laäp trình PASCAL PROGRAM Phuongtrinh BacHai; USES Crt; LABEL 20; VAR a, b, c : Real; Delta, X1, X2: Real; BEGIN 20 : Clrscr; GoTOXY(10,4); Writeln(' Giai phuong trinh bac hai'); GoTOXY(10,5); Writeln(' '); Write('Ban hay nhap vao gia tri cua A : '); Readln(a); IF a = 999999999 THEN Halt; IF a = 0 THEN BEGIN Writeln(' a khong hop le !'); Delay(500); GOTO 20; END; 165
  34. Write('Ban hay nhap vao gia tri cua B: '); Readln(b); Write('Ban hay nhap vao gia tri cua C: '); Readln(c); Delta := spr(b)- 4*a*c; IF Delta 0 THEN BEGIN Writeln('Phuong trinh coù 2 nghiem : '); X1 := (-b+sqrt(delta))/(2*a); X2 := (-b-sqrt(delta))/(2*a); Writeln(' X1 = ', X1: 9 : 2); Writeln(' X2 = ', X2: 9 : 2); END; Readln; END. 166
  35. THUËT GI¶I Kh¸i niÖm thuËt to¸n đã trình bày chÝnh lµ c¸nh cöa khÐp kÝn cho viÖc gỉai c¸c bµi to¸n vì: -NhiÒu bµi to¸n kh«ng tháa c¸c ®Æc tr­ng c¬ bản cña thuËt to¸n. -Cã nhiều bµi to¸n ch­a ìmt ra thuËt to¸n hoÆc ch­a chøng minh ®­îc lµ cã thuËt to¸n hay kh«ng. Cã những bµi to¸n cã thuËt to¸n nh­ng khã thùc hiÖn hoÆc kh«ng thùc hiÖn ®­îc 167
  36. · Cã những bµi to¸n ®­îcgi ải tuy vi ph¹m c¸c quy ®Þnh cña thuËt to¸n nh­ng lêi giải vÉn ®­îc thùc tiÔn chÊp nhËn THUẬT GIẢI CŨNG LÀ THUẬT TOÁN NHƯNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN 168
  37. NHỮNG MỞ RỘNG CHO CÁC ĐIỀU KIỆN · Më réng tÝnh x¸c ®Þnh TÝnh x¸c ®Þnh thùc chÊt lµ tÝnh ®¬n trÞ cña c¸ch giải cña mét thuËt to¸n vµ sù râ rµng tèi ®a. Trong thùc tÕ cã nhiÒu bµi to¸n vi ph¹m tÝnh x¸c ®Þnh mµ vÉn cho kÕt qủa. Nh­ vËy thay cho viÖc x©y dùng toµn bé qu¸ trình giải chØ cÇn chØ ra c¸ch chuyÓn tõ b­íc i sang b­íc i+1. C¸ch gỉai ngÉu nhiªn, ®Ö quy lµ më réng tÝnh x¸c ®Þnh 169
  38. Më réng tÝnh ®óng ®¾n TÝnh ®óng ®¾n ®­îchiÓu lµ cho kÕt quả ®óng. Nh­ngtrong thùc tÕ thì sè gÇn ®óng lµ cã thÓ chÊp nhËn. Ngoµi ra dïng c¸ch gỉai heuristic ®¬n giản, ®éc ®¸o vÉn cã thÓ cho kÕt qủa mét c¸ch s¸ng t¹o. 170
  39. NAÊM BÖÔÙC GIAÛI BAØI TOAÙN TREÂN MAÙY TÍNH a) B­íc 1 Nghiªn cøu kÜ néi dung, yªu cÇu cña bµi to¸n vµ tìm ph­¬ngph¸p, thuËt to¸n giải bµi to¸n Víi bµi to¸n lín, phøc t¹p viÖc tìm ph­¬ng ph¸p vµ thuËt to¸n rÊt khã khăn. NhiÒu tr­ênghîp phải cã sù céng t¸c, gióp ®ì cña c¸c chuyªn gia vÒ ph­¬ng ph¸p tÝnh to¸n vµ thuËt to¸n . b) B­íc 2 DiÔn tả thuËt to¸n b»ng l­u®å hoÆc b»ng ng«n ngữ Mô tả thuật toán. 171
  40. c) B­íc 3 DiÔn tả thuËt to¸n b»ng b»ng ng«n ngữ LËp trình Đ©y lµ c«ng viÖc chuyÓn l­u®å hoÆc ng«n ngữ Mô tả thuật toán thµnh ng«n ngữ lËp trình. Qu¸ trình nµy gäi lµ thảo ch­¬ng . d) B­íc 4 Ch¹y thö vµ söa lçi. B­ícnµy cã thÓ thùc hiÖn xen kÏ trong b­íc3 vµ thùc hiÖn nhiÒu lÇn víi nhiÒu ng­êikh¸c nhau nh»m ph¸t hiÖn tèi ®a c¸c sai sãt . Phải söa hÕt tÊt cả c¸c lçi dï nhá nhÊt. 172
  41. e) B­íc 5 иnh gi¸ sù ®óng ®¾n vµ ®é tin cËy cña kÕt qña.ViÖc ®¸nh gi¸ nµy th­êng dùa trªn : - ý nghÜa thùc tiÔn cña bµi to¸n - Kinh nghiÖm dù ®ãan kÕt qña cña ng­êi giải - So s¸nh kÕt qña víi kÕt qña cña bµi to¸n ®· cã lêi giai ®óng - Giải bµi to¸n trong những tr­êng hîp ®Æc biÖt, tr­êng hîp thu gän dÔ thÊy kÕt qña lµ ®óng hay sai. NÕu kÕt quả sai phải rµ so¸t l¹i tõ b­íc1 và cã thÓ sai tõ thuËt to¸n. C«ng viÖc tìm lçi sai vµ söa lçi cña thuËt to¸n rÊt khã NÕu kÕt qủa tìm ®­îclµ ®óng ®¾n vµ tin cËy, ghi ch­¬ngtrì nh lªn ®Üa ®Ó l­u . 173
  42. CAÙC PHÖÔNG PHAÙP THOÂNG DUÏNG • PH¦¬ng ph¸p ®óng • Ph­¬ng ph¸p gÇn ®óng - ph­¬ng ph¸p tÝnh • Ph­¬ng ph¸p ngÉu nhiªn • Ph­¬ng ph¸p kinh nghiÖm HEURISTIC 174