Bài giảng Tin học 8: Bài toán và thuật toán

BAØI TOAÙN VAØ THUAÄT TOAÙNXét các yêu cầu sau :Giải phương trình bậc hai ax2+bx+c=0Viết một dòng chữ ra màn hình máy tính.Quản lý các cán bộ trong một cơ quan.Tìm ước chung lớn nhất của hai số nguyên dương a và b. Xếp loại học tập các học sinh trong lớp.I. KHÁI NiỆM BÀI TOÁNTrong TIN HỌCTrong TOÁN HỌCYêu cầu 1 và 4 được xem là bài toánTất cả các yêu cầu trên đều được xem là bài toánTrong các yêu cầu trên, yêu cầu nào được xem như là một bài toán?Khái niệm bài toán trong Tin học?	Bài toán là việc nào đó ta muốn máy tính thực hiện.TIN HỌCĐưa vào máy thông tin gìCần lấy ra thông tin gì TOÁN HỌC?Các yếu tố cần quan tâm khi giải một bài toán Trong Tin học, để phát biểu một bài toán, ta cần trình bày rõ Input và Output của bài toán đó.TOÁN HỌC Giả thiết Kết luậnTHUẬT NGỮ Input OutputCAÙC THAØNH PHAÀN CÔ BAÛN CUÛA BAØI TOAÙNINPUTCaùc thoâng tin ñaõ coùOUTPUTCaùc thoâng tin caàn tìm töø InputCÁC VÍ DỤ	VD1 : Giải phương trình bậc hai ax2 + bx + c = 0 (a ≠ 0).Input : Các số thực a,b,c (a ≠ 0)Output : Số thực x thỏa : ax2+bx+ c = 0 	VD2 : Tìm giá trị nhỏ nhất của các số trong một dãy số.Input : Các số trong dãy số.Output : Giá trị nhỏ nhất trong dãy số. VD3 : Tìm ước chung lớn nhất của hai số nguyên dương a và b.Input : Output : 	 VD4 : Xếp loại học tập các học sinh trong lớp. Input :Output :UCLN của a và b.Hai số nguyên dương a và b.CÁC VÍ DỤ (tt)	????Bảng điểm của học sinh.Bảng xếp loại học tập.Nêu một bài toán và chỉ rõ Input, Output của bài toán đó?Xem thêm các ví dụ trong SGK/24, 25TÓM LẠI	Một bài toán được cấu tạo bởi 2 thành phần cơ bản :Input (Các thông tin đã có)Output (Các thông tin cần tìm từ Input)II. KHÁI NiỆM THUẬT TOÁNHướng dẫn các thao tác cho máy thực hiện để tìm ra lời giảiBài toánInputOutputBằng cách nào?Giải bài toánThuật toánInputOutputTHUẬT TOÁN(Thao tác 1Thao tác 2...Thao tác n)Thuật toán để giải một bài toán là một 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 sao cho sau khi thực hiện dãy thao tác đó, từ Input của bài toán này, ta nhận được Output cần tìm.BÀI TOÁNThuật toán để giải một bài toán là : Một dãy hữu hạn các thao tác. Các thao tác được sắp xếp theo một trình tự xác định. Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.MÔ TẢ CÁC THAO TÁC TRONG THUẬT TOÁNCó 2 cách mô tảLiệt kêDùng sơ đồ khốiNêu ra tuần tự các thao tác cần tiến hànhDùng một số biểu tượng thể hiện các thao tácGiải toán thông thường:Nếu a = 0 thì () không phải là pt bậc nhất. + Neáu b = 0 thì () voâ số nghieäm. + Neáu b ≠ 0 thì () voâ nghieäm.Nếu a ≠ 0 thì () có 	nghiệm x = -b/a.a) LIỆT KÊ 	LIỆT KÊ : Bước 1 : Nhập a, b. Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3. Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4. Bước 4 : Đưa ra kết quả x và kết thúc.VD : Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 (): Thể hiện các thao tác so sánhb) DÙNG SƠ ĐỒ KHỐITrong sơ đồ khối, người ta dùng một số biểu tượng thể hiện các thao tác như :: Thể hiện các phép tính toán: Quy định trình tự thực hiện các 	thao tác: Thể hiện các thao tác nhập, xuất 	dữ liệuVD: Tìm nghiệm phương trình bậc nhất tổng quát : ax + b = 0 Nhaäp a, b a = 0 x -b/aSaiÑuùngÑöa ra x vaø keát thuùc Bước 1 : Nhập a, b. Bước 2 : Nếu a = 0 thì quay lại bước 1, ngược lại thì qua bước 3. Bước 3 : Gán cho x giá trị -b/a, rồi qua bước 4. Bước 4 : Đưa ra kết quả x và kết thúc.SƠ ĐỒ KHỐILIỆT KÊIII. VÍ DỤ VỀ THUẬT TOÁN1.Bài toán 1 : Cho dãy số gồm N số sau (N = 5):	11 6 20 4 8 Tìm giá trị NHỎ NHẤT của dãy số trên ?a) XÁC ĐỊNH BÀI TOÁNInput : Số nguyên dương N và dãy N số nguyên a1,.,aN.Output: Giá trị bé nhất (Min) của dãy sốb) Ý TƯỞNGKhởi tạo giá trị Min = a1Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Min, nếu Min>ai thì Min nhận giá trị mới là aiHÖÔÙNG DAÃN: Goïi Min laø giaù trò nhoû nhaát caàn tìm. Gaùn Min baèng giaù trò phaàn töû ñaàu tieân cuûa daõy. Laàn löôït so saùnh Min vôùi caùc phaàn töû tieáp theo trong daõy. Taïi moãi vò trí so saùnh : + Neáu Min lôùn hôn giaù trò phaàn töû caàn so saùnh trong daõy thì laáy giaù trò cuûa phaàn töû ñoù gaùn laïi cho Min.- Khi so saùnh ñeán phaàn töû cuoái cuøng trong daõy soá thì Min seõ mang giaù trò nhoû nhaát cuûa daõy.Gán i = 2 11 6 20 4 8MinMin=11Min=6Min=4Giaù trò nhoû nhaát: 4Biến i lưu trữ vị trí tiếp theo mà Min sẽ so sánh+ Tăng i lên 1 đơn vịLIỆT KÊBöôùc 1 : Nhaäp N vaø daõy a1,, aN.Böôùc 2 : Ñaët Min  a1, i  2;Böôùc 3 : Neáu i ai thì ñaët Min  ai.	4.2. Taêng i moät ñôn vò roài quay veà böôùc 3Böôùc 5 : Ñöa ra Min roài keát thuùc.SƠ ĐỒ KHỐI :Nhaäp N vaø daõy a1,, aN Min  a1 ,i  2i aiMin  ai i  i+1Ñöa ra Min roài keát thuùcSaiÑuùngÑuùngSaiMô phỏng thuật toán MinDãy số51076-315842-9imin52130568911121047-3-3-3-3-3-9002.Bài toán 2 : 	Tìm giá trị LỚN NHẤT của một dãy số với Input và Output như sau:Input : Số nguyên dương N và dãy N số 	a1,...,aN.Output : Giá trị lớn nhất (Max) của dãy số.	Mô tả thuật toán để giải bài toán này theo cả 2 cách liệt kê và dùng sơ đồ khối.III. VÍ DỤ VỀ THUẬT TOÁN(tt)a) XÁC ĐỊNH BÀI TOÁNInput : Số nguyên dương N và dãy N số nguyên a1,.,aN.Output: Giá trị lớn nhất (Max) của dãy sốb) Ý TƯỞNGKhởi tạo giá trị Max = a1Lần lượt với i từ 2 đến N, so sánh giá trị số hạng ai với giá trị Max, nếu ai>Max thì Max nhận giá trị mới là aiVÍ DỤ ÁP DỤNGCho dãy số gồm N số sau (N = 5):	11 6 20 4 8 Tìm giá trị LỚN NHẤT của dãy số trên ?HÖÔÙNG DAÃN: Goïi Max laø giaù trò lớn nhaát caàn tìm. Gaùn Max baèng giaù trò phaàn töû ñaàu tieân cuûa daõy. Laàn löôït so saùnh Max vôùi caùc phaàn töû tieáp theo trong daõy. Taïi moãi vò trí so saùnh : + Neáu Max nhỏ hôn giaù trò phaàn töû caàn so saùnh trong daõy thì laáy giaù trò cuûa phaàn töû ñoù gaùn laïi cho Max.- Khi so saùnh ñeán phaàn töû cuoái cuøng trong daõy soá thì Max seõ mang giaù trò lớn nhaát cuûa daõy.Gán i = 2 11 6 20 4 8MaxMax=11Max=11Giaù trò lớn nhaát: 20Biến i lưu trữ vị trí tiếp theo mà Max sẽ so sánh+ Tăng i lên 1 đơn vịMax=20Max=20LIỆT KÊBöôùc 1 : Nhaäp N vaø daõy a1,, aN.Böôùc 2 : Ñaët Max  a1, i  2;Böôùc 3 : Neáu i >N thì chuyeån ñeán böôùc 5.Böôùc 4 : 	4.1. Neáu ai > Max thì ñaët Max  ai.	4.2. i  i + 1 roài quay veà böôùc 3Böôùc 5 : Ñöa ra Max roài keát thuùc.SƠ ĐỒ KHỐI :Nhaäp N vaø daõy a1,, aN Max a1 ,i  2i >N?ai >Max?Max  ai i  i+1Ñöa ra Max roài keát thuùcÑuùngSaiÑuùngSaiMô phỏng thuật toán MaxDãy số5147631584912imax525354757677158915151115121015III. VÍ DỤ VỀ THUẬT TOÁN(tt)3.Bài toán 3 : 	Mô tả thuật toán để giải bài toán này theo cả 2 cách liệt kê và dùng sơ đồ khối.Kiểm tra tính nguyên tố của một số nguyên dương:Input : ?Output : ?a) XÁC ĐỊNH BÀI TOÁNInput :?Output:?N là một số nguyên dươngN là nguyên tố hay không nguyên tốb) Ý TƯỞNGNếu N = 1 thì N không là số nguyên tốNếu 1=4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tốVậy nếu có bất kỳ một ước số khác 1 và chính nó thì kết luận N không là nguyên tố.LIỆT KÊBöôùc 1 : Nhaäp số nguyeân döông N ;Böôùc 2 : Neáu N = 1 thì thoâng baùo N khoâng laø nguyeân toá roài keát thuùc;Böôùc 3 : Neáu N [ ] thì thoâng baùo N laø nguyeân toá roài keát thuùc;Böôùc 6: Neáu N chia heát cho i thì thoâng baùo N khoâng laø nguyeân toá roài keát thuùc;Böôùc 7: i  i + 1 roài quay laïi böôùc 5.SƠ ĐỒ KHỐI :Nhập NN=1?N[ ]?NThông báo N là nguyên tố rồi kết thúcThông báo N không là nguyên tố rồi kết thúcii + 1ĐúngĐúngSaiSaiĐúngSaiĐúngSaiMô phỏng thuật toán kiểm tra tính nguyên tối23456N/iChia hết không?Với N = 29 ([ ] = 5)29 là số nguyên tố29/229/329/429/5KhôngKhôngKhôngKhôngMô phỏng thuật toán kiểm tra tính nguyên tối23N/iChia hết không?45/245/3KhôngChia hết45 không là số nguyên tốVới N = 45 ( [ ] = 6)CÁC TÍNH CHẤT CỦA THUẬT TOÁNTính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác CÁC TÍNH CHẤT CỦA THUẬT TOÁN (tt)Tính xác định: Sau khi thực hiện một thao tác thì:Hoặc thuật toán kết thúcHoặc có đúng một thao tác xác định để được thực hiện tiếp theoCÁC TÍNH CHẤT CỦA THUẬT TOÁN (tt)Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.CÁC THUẬT NGỮ CHÍNH Là việc nào đó ta muốn máy tính thực hiệnCác thông tin đã có (các giả thiết)Các thông tin cần tìm từ Input (kết luận)*Một dãy hữu hạn các thao tác.*Các thao tác được sắp xếp theo một trình tự xác định.*Sau khi thực hiện dãy thao tác đó, từ Input ta tìm được Output của bài toán.Dùng các biểu tượng qui ước để thể hiện các thao tác trong thuật toán Bài toán Input Output Thuật toán Sơ đồ khốiGhi nhớ Xuất MinNhập dãy NThực hiện lệnh(Phép gán, phép tính)Điều KiệnĐúngSai	Ta cần diễn tả thuật toán bằng một ngôn ngữ sao cho máy tính có thể hiểu và thực hiện được, ngôn ngữ đó gọi là ngôn ngữ lập trình. Kết quả diễn tả thuật toán như vậy gọi là chương trình.LƯU ÝTÌM MAX TRONG N SỐ514763158MAX 12345678i55771515iADauCuoiGiuaaGiuaLaàn duyeät12345678910926452122303133110596106830676211 a­giua 9 K 30 > 21Cuoi=Giua-13615378107124615378107124615378107124615378107124615378107124615378107124MOÂ PHOÛNG THUAÄT TOAÙN TRAÙO ÑOÅI (Exchange Sort)6153781071241537810712471210816537646 1 5 3 7 8 10 7 12 41 6 5 3 7 8 10 7 12 41 5 6 3 7 8 10 7 12 41 5 3 6 7 8 10 7 12 41 5 3 6 7 8 7 10 12 41 5 3 6 7 8 7 10 4 12 Ví duïCho daõy A goàm caùc soá: 3, 5, 23, 8, 2, 9, 4, 6, 11, 98, 7.Vôùi khoaù k= 4.k35238294611987i1243444546474 Vaäy chæ soá caàn tìm laø i= 7. Ví duïCho daõy A goàm caùc soá: 3, 5, 23, 8, 2, 9, 4, 16, 11, 98, 7.Vôùi khoaù k= 6.k352382941611987i16236465666768696106116 Vaäy khoâng coù haïn naøo cuûa daõy ACoù giaù trò baèng k.154212332484578IAiK=4554 12 32 84 78 45 25 34 49XUAÁT i=6645!154212332484578IAiK=1354 12 32 84 78 45 25 34 49XUAÁT THOÂNG BAÙO DAÕY A KHOÂNG COÙ PHAÀN TÖÛ NAØO BAÈNG K645725834949?!K = 2 vaø N = 10 A 5 7 1 4 2 9 8112551 1 5 _ 2 _ 3 _ 4 _Vôùi i = 5 thì a5 = 2K = 6 vaø N = 10AI57142981125511231045678911Vôùi moïi i töø 1 ñeán 10 khoâng coù ai coù giaù trò baèng 6