Tin học đại cương - Chương 3: Giải bài toán trên máy tính

Nội dung text: Tin học đại cương - Chương 3: Giải bài toán trên máy tính

1. ChChɉɇɉɇngng 33 GiGiɠɠii BBàài Toánn TrênTrên MMááyy TTíínhnh Trɤn Phɉ͛c Tuɢn tranphuoctuan.khoatoan.dhsp@gmail.com 1͙i dung bài h͍c 1. 9ɢn ÿɾ - bài toán 2. Thuɪt toán - thuɪt giɠi 3. Các phɉɇng pháp biʀu diʂn thuɪt toán 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính 5. 7͕ng quan vɾ ngôn ngͯ Oɪp trình Page 2 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
2. 1. Vɢn ÿɾ - bài toán Khái niʄm • 9ɢn ÿɾ thɉ͝ng ÿɉͣc dùng v͛i nghśa r͙ng hɇn bài toán, bài toán là vɢn ÿɾ mà ÿʀ giɠi quyɼt nó phɠi liên quan ít nhiɾu ÿɼn tính toán • Pitago chia m͍i vɢn ÿɾ mà con ngɉ͝i cɤn giɠi quyɼt thành hai loɞi: – Theorema: vɢn ÿɾ Fɤn khɰng ÿʈnh tính ÿúng – sai – Problema: vɢn ÿɾ Fɤn tìm giɠi pháp ÿʀ ÿʀ ÿɞt ÿɉͣc mͥc tiêu tͫ nhͯng ÿLɾu kiʄn ban ÿɤu nào ÿó Page 3 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 1. Vɢn ÿɾ - bài toán Khái niʄm • Theo nhiɾu kɼt quɠ nghiên cͩu: viʄc giɠi quyɼt Yɢn ÿɾ - bài toán mà Pitago nêu ra ÿɾu có thʀ diʂn ra theo m͙t sɇÿ͓ chung: A Æ B • ͞ ÿây: – A có thʀ là giɠ thiɼt, ÿiɾu kiʄn ban ÿɤu – B có thʀ là kɼt luɪn, mͥc tiêu cɤn ÿɞt – Æ là suy luɪn, giɠi pháp cɤn xác ÿʈnh Page 4 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
3. 1. Vɢn ÿɾ - bài toán Khái niʄm • Ví dͥ 1: Bài toán kiʀm tra tính nguyên t͑ – Cho: S͑ nguyên dɉɇng N – &ɤn biɼt: N có là s͑ nguyên t͑ hay không? • Ví dͥ 2: Bài toán quɠn lý h͓ Vɇ sinh viên – Cho: H͓ Vɇ g͑c cͧa các sinh viên trong trɉ͝ng – &ɤn biɼt: Bɠng th͑ng kê, phân loɞi sinh viên theo kɼt quɠ K͍c tɪp Page 5 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 1. Vɢn ÿɾ - bài toán Khái niʄm • &ɢu trúc m͙t bài toán: – Thông tin ÿɤu vào (input): cái cho trɉ͛c – Thông tin ÿɤu ra (output): cái cɤn tìm • Giɠi bài toán: là viʄc xác ÿʈnh tɉ͝ng minh output theo input bɮng m͙t quá trình có thʀ thͱc hiʄn m͙t cách hiʄu quɠ Page 6 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
4. 2. Thuɪt toán – thuɪt giɠi Thuɪt toán – khái niʄm • Thuɪt toán là khái niʄm cɇ s͟ Fͧa toán h͍c và tin h͍c • Thuɪt toán là m͙t dãy các chʆ thʈ rõ ràng và có thʀ thi hành ÿɉͣc ÿʀ Kɉ͛ng dɨn thͱc hiʄn hành ÿ͙ng nhɮm ÿɞt ÿɉͣc mͥc tiêu ÿɴt ra • Thuɪt toán là sͱ thʀ hiʄn cͧa m͙t phɉɇng pháp ÿʀ giɠi quyɼt vɢn ÿɾ Page 7 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 2. Thuɪt toán – thuɪt giɠi Thuɪt toán – ÿɴc trɉng • Nhɪp (input). Các thuɪt toán thɉ͝ng có giá trʈ ÿɤu vào • Xuɢt (output). Tͫ giá trʈ vào thuɪt toán cho ra kɼt quɠ. • Tính xác ÿʈnh (definiteness). Các bɉ͛c trong thuɪt toán phɠi chính xác rõ ràng. • Tính hͯu hɞn (finiteness). Thuɪt toán phɠi cho ra l͝i giɠi (hay kɼt quɠ) sau m͙t s͑ Eɉ͛c hͯu hɞn. • Tính hiʄu quɠ. Tính hiʄu quɠ ÿɉͣc ÿánh giá dͱa trên m͙t s͑ tiêu chuɦn nhɉ kh͑i lɉͣng tính toán, không gian và th͝i gian sͭ Gͥng (khi thͱc hiʄn thuɪt toán trên máy tính). • Tính t͕ng quát. Thuɪt toán phɠi áp dͥng ÿɉͣc cho tɢt cɠ các bài toán cùng dɞng, chͩ không chʆ áp dͥng ÿɉͣc cho m͙t s͑ trɉ͝ng Kͣp riêng lɸ nào ÿó. Page 8 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
5. 2. Thuɪt toán – thuɪt giɠi Thuɪt toán – ví dͥ Thuұt toán giҧi phѭѫng trình bұc hai: AX2 + BX + C = 0 (A z 0) -Bѭӟc 1 : Tính DELTA = B*B-4*A*C -Bѭӟc 2 : So sánh DELTA vӟi sӕ 0 -Bѭӟc 3 : RӁ làm 3 trѭӡng hӧp : . -Trɉ͝ng hͣp DELTA 0 : rb b2 4 ac X 1,2 2a Page 9 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 2. Thuɪt toán – thuɪt giɠi Thuɪt toán – các cɢu trúc cɇ bɠn 1. Tuɤn tͱ: thͱc hiʄn hɼt lʄnh này ÿɼn Oʄnh khác 2. 5ɺ nhánh: tùy theo dͯ liʄu ÿɤu vào mà ta quyɼt ÿʈnh thͱc hiʄn câu lʄnh gì tiɼp theo 3. /ɴp: thͱc hiʄn lɞi nhiɾu lɤn m͙t s͑ câu Oʄnh nào ÿó cho ÿɼn khi ÿLɾu kiʄn không còn th͏a mãn nͯa Page 10 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
6. 2. Thuɪt toán – thuɪt giɠi Thuɪt giɠi • Khái niʄm thuɪt toán ÿã trình bày chính là cánh Fͭa khép kín cho viʄc giɠi 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 Fͧa thuɪt toán. – Có nhiɾu bài toán chɉa tìm 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 Page 11 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 2. Thuɪt toán – thuɪt giɠi Thuɪt giɠi • 7ͫ nhͯng nhɪn ÿʈnh trên ngɉ͝i ta thɢy rɮng: Fɤn phɠi có nhͯng ÿ͕i m͛i cho khái niʄm thuɪt toán Æ “Thuɪt giɠi” Page 12 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
7. 2. Thuɪt toán – thuɪt giɠi Thuɪt giɠi – m͟ U͙ng tính xác ÿʈnh • Tính xác ÿʈnh thͱc chɢt là tính ÿɇn trʈ Fͧa cách giɠi Fͧ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 Gͱng toàn b͙ quá trình giɠi chʆ Fɤn chʆ ra cách chuyʀn tͫ Eɉ͛c i sang bɉ͛c i+1. • Cách gʆai ngɨu nhiên, ÿʄ quy là m͟ U͙ng tính xác ÿʈnh Page 13 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 2. Thuɪt toán – thuɪt giɠi Thuɪt giɠi – m͟ U͙ng tính ÿúng ÿɬn • Tính ÿúng ÿɬn ÿɉͣc hiʀu là cho kɼt quɠ ÿúng. • Trong thͱc tɼ thì s͑ Jɤn ÿúng là có thʀ chɢp nhɪn ÿɉͣc • Ngoài ra dùng cách giɠi heuristic ÿɇn giɠn, ÿ͙c ÿáo vɨn có thʀ cho kɼt qͧa m͙t cách sáng tɞo Page 14 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
8. 3. Các phɉɇng pháp biʀu diʂn thuɪt toán • Ngôn ngͯ Wͱ nhiên • /ɉu ÿ͓ - Vɇÿ͓ kh͑i • Mã giɠ Page 15 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 3. Các phɉɇng pháp biʀu diʂn thuɪt toán Ngôn ngͯ Wͱ nhiên • Liʄt kê các thao tác, các chʆ thʈ Eɮng ngôn ngͯ Wͱ nhiên • Ví dͥ: Có 43 que diêm. Hai ngɉ͝i chɇi luân phiên b͑c diêm. M͗i lɉͣt, m͗i ngɉ͝i b͑c tͫ 1 ÿɼn 3 que diêm. Ngɉ͝i nào b͑c cu͑i cùng Vɺ thɬng cu͙c Page 16 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
9. 3. Các phɉɇng pháp biʀu diʂn thuɪt toán Ngôn ngͯ Wͱ nhiên • Giɠi thuɪt ÿʀ ngɉ͝i ÿi trɉ͛c luôn thɬng cu͙c ÿɉͣc diʂn tɠ Eɮng cách liʄt kê tͫng bɉ͛c nhɉ sau: – %ɉ͛c 1: %͑c 3 que r͓i ÿͣi ÿ͑i phɉɇng ÿi – %ɉ͛c 2: Ĉ͑i phɉɇng b͑c (giɠ Vͭ x que, 0<x<4) – %ɉ͛c 3: Ĉɼn lɉͣt ngɉ͝i ÿi trɉ͛c b͑c a = (4-x) que. Nɼu còn diêm thì quay lɞi %ɉ͛c 2 – Tuyên b͑ thɬng cu͙c. Kɼt thúc Page 17 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 3. Các phɉɇng pháp biʀu diʂn thuɪt toán 6ɇÿ͓ kh͑i • Là m͙t phɉɇng tiʄn hình h͍c giúp ta diʂn tɠ giɠi thuɪt m͙t cách trͱc quan • Ĉɉͣc tɞo b͟i các kiʀu kh͑i cɇ bɠn, n͑i v͛i nhau bɮng các ÿɉ͝ng có Kɉ͛ng • Thuɪt ngͯ tiɼng Anh là Flow Chart Page 18 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
10. 3. Các phɉɇng pháp biʀu diʂn thuɪt toán 6ɇÿ͓ kh͑i Eҳt ÿҫu ÿLӅu kiӋn NӃt thúc thao tác input Chѭѫng trình con output +ѭӟng xӱ lý Page 19 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 3. Các phɉɇng pháp biʀu diʂn thuɪt toán 6ɇÿ͓ kh͑i – ví dͥ %ҳt ÿҫu %ҳt ÿҫu %ҳt ÿҫu Thùng = 0 Lon 6ӕa, Sӕb a, b 1 Lon Không Thêm 1 Lon vào thùng c = a + b 6ӕ a có bҵng 6ӕ b không? Chѭa Thùng = 24 Lon? c Có %ɮng 6ӕ a bҵng Sӕ b 6ӕ a không bҵng Sӕ b .Ӄt thúc .ɼt thúc .Ӄt thúc Page 20 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
11. 3. Các phɉɇng pháp biʀu diʂn thuɪt toán Mã giɠ • Ngoài viʄc sͭ Gͥng ngôn ngͯ Wͱ nhiên và Oɉu ÿ͓ ÿʀ biʀu diʂn thuɪt toán, ngɉ͝i ta còn Vͭ Gͥng ngôn ngͯ Wͱa pascal, c, ÿɉͣc g͍i là mã giɠ • Trong mã giɠ ta sͭ Gͥng cɠ Fɢu trúc cͧa ngôn ngͯ Oɪp trình và ngôn ngͯ Wͱ nhiên Page 21 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 3. Các phɉɇng pháp biʀu diʂn thuɪt toán Mã giɠ-vídͥ BiӃn A,B,C,DELTA,X1,X2 : SӕThӵc ; %ҳWĈҫu Nhұp A,B,C; DELTA:=B*B-4*A*C; 1Ӄu DELTA <0 Thi Xuҩt 'Phѭѫng trinh vô nghiӋm '; 'ӯng; 1Ӄu DELTA =0 Thi X1:=(-B/2/A); X2:=X1; Xuҩt 'NghiӋm kép X1,X2 '; 'ӯng; 1Ӄ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 '; 'ӯng; .ӃtThúc. Page 22 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
12. 3. Các phɉɇng pháp biʀu diʂn thuɪt toán Bài tɪp 1. Tính ÿLʀm trung bình cͧa h͍c sinh g͓m các môn Toán, Lý, Hóa. 2. Kiʀm tra 2 s͑ a, b gi͑ng nhau hay khác nhau. 3. Kiʀm tra 1 s͑ a chɲn hay lɸ 4. Giɠi pt: ax+b=0 5. Giɠi phɉɇng trình bɪc 2: ax2 + bx + c = 0 Page 23 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính • %ɉ͛c 1: Xác ÿʈnh vɢn ÿɾ - bài toán • %ɉ͛c 2: Lͱa ch͍n phɉɇng pháp giɠi • %ɉ͛c 3: Xây dͱng thuɪt toán hoɴc thuɪt giɠi • %ɉ͛c 4: Cài ÿɴt chɉɇng trình • %ɉ͛c 5: Hiʄu chʆnh chɉɇng trình • %ɉ͛c 6: Thͱc hiʄn chɉɇng trình Page 24 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
13. 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính %ɉ͛c 1: Xác ÿʈnh vɢn ÿɾ - bài toán • Phân tích hʄ th͑ng nhɮm phát biʀu chính xác vɢn ÿɾ, làm rõ yêu cɤu cͧa ngɉ͝i sͭ Gͥng • Ĉánh giá, nhɪn ÿʈnh tính khɠ thi cͧa vɢn ÿɾ Page 25 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính %ɉ͛c 2: Lͱa ch͍n phɉɇng pháp giɠi • Có nhiɾu cách khác nhau ÿʀ giɠi quyɼt vɢn ÿɾ, tùy theo nhu cɤu cͥ thʀ mà ta lͱa ch͍n phɉɇng pháp thích hͣp • Viʄc lͱa ch͍n phɉɇng pháp cŸng cɤn căn cͩ vào khɠ Qăng xͭ lý tͱ ÿ͙ng mà ta cɤn sͭ Gͥng Page 26 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
14. 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính %ɉ͛c 3: Xây dͱng thuɪt toán hoɴc thuɪt giɠi • Xác ÿʈnh input, output • Xác ÿʈnh các bɉ͛c thͱc hiʄn cɇ bɠn cho dͯ liʄu ÿɤu vào và ÿɤu ra • Nên áp dͥng phɉɇng pháp thiɼt kɼ có cɢu trúc, tͫ thiɼt kɼ W͕ng thʀ tiɼn hành làm mʈn Gɤn các bɉ͛c Page 27 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính %ɉ͛c 4: Cài ÿɴt chɉɇng trình • Mô tɠ thuɪt giɠi thành chɉɇng trình • &ɤn nɬm vͯng ngôn ngͯ Oɪp trình và thʀ hiʄn m͙t cách chính xác thuɪt toán ÿã ÿɉͣc ÿɉa ra. Page 28 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
15. 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính %ɉ͛c 5: Hiʄu chʆnh chɉɇng trình • Cho chɉɇng trình chɞy thͭ và hiʄu chʆnh nhͯng sai sót • Trong bɉ͛c này ta cɤn khɬc phͥc hai loɞi l͗i: – /͗i cú pháp (có sͱ K͗ trͣ Fͧa IDE) – /͗i ngͯ nghśa (thɉ͝ng khó phát hiʄn hɇn l͗i cú pháp) Page 29 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009 4. Các bɉ͛c ÿʀ giɠi m͙t bài toán trên máy tính %ɉ͛c 6: Thͱc hiʄn chɉɇng trình • Cho chɉɇng trình chɞy v͛i nhͯng b͙ Gͯ liʄu khác nhau ÿʀ kiʀm tra • /ɉu ý các trɉ͝ng hͣp ÿɴc biʄt • /ɉu ý các trɉ͝ng hͣp ngɉ͝i dùng nhɪp dͯ liʄu có kiʀu không phù hͣp v͛i kiʀu dͯ liʄu Vͭ Gͥng trong chɉɇng trình Page 30 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009
16. 5. T͕ng quan vɾ ngôn ngͯ Oɪp trình 6ͱ K͗ trͣ Fͧa máy tính Giҧi bài toán này thӃ nào ÿây? Chѭѫng trình biên dӏch File Ngôn (Bӝ máy cӫa NNLT) ngӳ máy (exe, dll, com, ) Source code Cách giҧi ÿѭӧc KiӃn thӭc KiӃn thӭc diӉn ÿҥt bҵng Chuyên môn YӅ NNLT ngôn ngӳ Wӵ nhiên Page 31 T.P.Tuҩn-NHҰP MÔN TIN HӐC 12/12/2009