Chuyên đề Bài toán và thuật toán - Trường THPT Trần Hưng Đạo

 TRƯỜNG THPT TRẦN HƯNG ĐẠO 
 TỔ TOÁN - TIN 
 -------   ------- 
 CHUYÊN ĐỀ 
 BÀI TOÁN VÀ THUẬT TOÁN 
I. MỤC ĐÍCH – YÊU CẦU 
 - Giúp học sinh hiểu được 2 khái niệm then chốt là "bài toán" và "thuật toán", nắm được 
các tính chất của thuật toán và cách diễn tả thuật toán bằng 2 cách: liệt kê và sơ đồ khối. 
 - Giúp cho học sinh có cái nhìn trực quan sinh động hơn đối với môn Tin học. 
 - Rèn luyện cho học sinh có tư duy khoa học, logic, tác phong sáng tạo, say mê môn học. 
II. NỘI DUNG CHUYÊN ĐỀ 
1. Chuẩn bị 
- Về phương pháp: 
 + Giáo viên soạn trước bài giảng "Bài toán và thuật toán" trên máy tính bằng phần mềm 
 PowerPoint (Bài soạn này được dạy trong 4 tiết học). Sử dụng phương pháp thuyết trình 
 kết hợp vấn đáp và gọi 5-6 học sinh lên bảng đứng làm mẫu khi cần biểu diễn thuật toán 
 Tìm Max và thuật toán sắp xếp. 
 + Chuẩn bị một số bài tập áp dụng để rèn luyện kỹ năng biểu diễn thuật toán. 
- Về phương tiện: 
 + Giáo viên chuẩn bị một dàn máy tính (để bàn hoặc xách tay), một máy chiếu, một màn 
 chiếu. 
 + Học sinh cần có đầy đủ sách bút, vở ghi. 
2. Các bước thực hiện bài giảng "Bài toán và thuật toán" 
  Hoạt động 1: Giúp học sinh hiểu rõ khái niệm "Bài toán" trong Tin học: 
Giáo viên đặt vấn đề bằng cách đưa ra các ví dụ để học sinh quan sát: 
Ví dụ 1: Giải phương trình bậc 2 tổng quát: ax2+ bx+ c= 0 (a khác 0). 
Ví dụ 2: Giải bài toán "Trăm trâu trăm cỏ 
 Trâu đứng ăn năm 
 Trâu nằm ăn ba 
 Lụ khụ trâu già 
 Ba con một bó" 
 Hỏi có bao nhiêu trâu mỗi loại ? 
Ví dụ 3: Bài toán quản lý học sinh trong một kỳ thi tốt nghiệp bằng máy tính: 
 Điểm 
 Điểm Điểm Điểm Điểm Điểm Tổng Xếp 
 Ngoại 
 SBD Họ và tên toán văn lý sinh sử điểm loại 
 ngữ 
 410001 Phạm Ngọc Toàn 8 9 7 8 6 5 43 Khá 
 410002 Bùi Long Thể 2 3 4 4 5 3 21 Yếu 
 410003 Hà Nguyên Diệp 9 8 7 8 9 10 51 Giỏi 
 410004 Nguyễn Thị Thanh Bình 6 5 4 9 8 7 39 Khá 
 410005 Phan Thị Thanh 6 7 4 3 6 5 31 TB 
 Phát vấn học sinh: Em hãy xác định dữ kiện ban đầu và kết quả của mỗi bài toán sẽ có 
dạng gì ? (Dạng số, hình ảnh, hay văn bản ?) 
 Học sinh trả lời: Dữ kiện (Cho biết) Kết quả (cần tìm) 
 Các hệ số a, b, c bất kỳ Nghiệm của phương trình (nếu có) 
 ở ví dụ 1 
 có dạng số nguyên hoặc số thực. 
 Có 100 con trâu và 100 bó cỏ. Số lượng trâu đứng, trâu nằm và 
 Mỗi con trâu đứng ăn 5 bó. trâu già ( dạng số nguyên) 
 ở ví dụ 2 
 Mỗi con trâu nằm ăn 3 bó. 
 3 con trâu già ăn chung một bó 
 Số báo danh, họ tên, ngày sinh, Tổng điểm của mỗi học sinh, xếp 
 ở ví dụ 3 
 điểm toán, điểm văn, điểm lý. loại tốt nghiệp nào, đỗ hay trượt. 
 Phát vấn học sinh: Em hãy nhận xét sự giống và khác nhau giữa bài toán trong Tin học 
và bài toán trong Toán học? 
 Học sinh trả lời: Bài toán trong Toán học yêu cầu chúng ta giải cụ thể để tìm ra kết quả, 
còn bài toán trong Tin học yêu cầu máy tính giải và đưa ra kết quả cho chúng ta. 
 Từ đây Giáo viên trình chiếu khái niệm Bài toán trong Tin học : Là một việc nào đó mà 
ta muốn máy tính thực hiện để từ thông tin đầu vào (dữ kiện) máy tính cho ta kết quả mong 
muốn. 
 - Những dữ kiện của bài toán được gọi là Input. 
 - Kết quả máy tính trả ra được gọi là Output của bài toán. 
Sau đó giáo viên yêu cầu học sinh tìm lại Input và Output của 3 ví dụ trên. 
 Như vậy, khái niệm bài toán không chỉ bó hẹp trong phạm vi môn toán, mà phải được hiểu 
như là một vấn đề cần giải quyết trong thực tế, để từ những dữ kiện đã cho máy tính tìm ra kết 
quả cho chúng ta. 
  Hoạt động 2: Giúp học sinh hiểu rõ khái niệm "Thuật toán" trong Tin học: 
+Bước 1: Giáo viên nêu tình huống gợi động cơ: 
 Làm thế nào để từ Input của bài toán, máy tính tìm cho ta Output ? 
Học sinh trả lời: Ta cần tìm cách giải bài toán và làm cho máy tính hiểu được cách giải đó. 
 Đến đây sẽ có em thắc mắc: Như vậy chúng ta vẫn phải giải bài toán mà có khi còn 
phức tạp hơn trong Toán học ? 
 Giáo viên giải thích: Nếu như trong Toán học chúng ta phải giải trực tiếp từng bài để 
lấy kết quả, thì ở đây, chúng ta chỉ cần tìm cách giải bài toán tổng quát và máy tính sẽ giải cho 
ta một lớp các bài toán đồng dạng. 
 Ví dụ: Bài toán giải phương trình bậc 2 với các hệ số a,b,c bất kỳ, bài toán tìm diện tích 
tam giác với độ dài 3 cạnh được nhập bất kỳ, bài toán tìm UCLN của 2 số nguyên bất kỳ, bài 
toán quản lý học sinh ,v.v 
+Bước 2: Giáo viên đưa ra khái niệm thuật toán và các tính chất của một thuật toán: 
 Khái niệm: “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 các thao tác ấy, từ thông tin đầu 
vào (Input) của bài toán ta nhận được kết quả (Output) cần tìm”. 
  Các tính chất của một thuật toán: 
 - Tính dừng 
 - Tính xác định 
 - Tính đúng đắn 
+ Bước 3: Giới thiệu cho học sinh 2 cách biểu diễn một thuật toán 
- Cách l: Liệt kê các bước: Chính là dùng ngôn ngữ tự nhiên để diễn tả các bước cần làm khi 
giải một bài toán bằng máy tính. 
- Cách 2: Dùng sơ đồ khối. 
Một số quy ước khi biểu diễn thuật toán bằng sơ đồ khối: 
 Khối hình oval: mô tả thao tác nhập xuất dữ liệu 
 - 2 - 
 Khối hình chữ nhật: mô tả các thao tác tính toán 
 Khối hình thoi: mô tả các thao tác so sánh 
 Hình mũi tên : Chỉ sự truyền thông 
 Giáo viên nhắc học sinh phải nhớ các quy ước trên để biểu diễn thuật toán được chính xác. 
*Hoạt động 3: Giới thiệu và hướng dẫn học sinh mô tả, biểu diễn thuật toán của một số 
bài toán điển hình.(Trọng tâm) 
Bài toán 1: Giải phương trình bậc 2 tổng quát : ax2+bx+c = 0 ( a ≠ 0). 
Trước tiên giáo viên yêu cầu học sinh xác định Input và Output của bài toán: 
 - Input: 3 hệ số a,b,c. 
 - Output: Nghiệm của phương trình . 
Sau đó gọi một học sinh đứng lên nhắc lại cách giải một phương trình bậc 2 đầy đủ, rồi từng 
bước hướng dẫn học sinh viết thuật toán theo 2 cách. 
Lưu ý rằng giáo viên vừa trình chiếu từng bước của thuật toán vừa vấn đáp học sinh ( dùng 
hiệu ứng xuất hiện phù hợp) 
Cách 1: Liệt kê từng bước 
 - Bước 1: Bắt đầu 
 - Bước 2: Nhập 3 hệ số a,b,c. 
 - Bước 3: Tính biệt số Error! Objects cannot be created from editing field codes. = b2- 
 4ac 
 - Bước 4: Nếu Error! Objects cannot be created from editing field codes. < 0 thông 
 báo phương trình vô nghiệm rồi kết thúc. 
 - Bước 5: Nếu Error! Objects cannot be created from editing field codes. = 0 thông 
 báo phương trình có nghiệm kép Error! Objects cannot be created from editing field 
 codes. rồi kết thúc. 
 - Bước 6: Nếu Error! Objects cannot be created from editing field codes. > 0 thông 
 báo phương trình có 2 nghiệm x1,x2=Error! Objects cannot be created from editing 
 field codes., rồi kết thúc. 
 - Bước 7: Kết thúc. 
Cách 2: Biểu diễn thuật toán bằng sơ đồ khối 
 Bắt đầu 
 Nhập a,b,c 
 2
 Tính = b - 4ac 
 Đúng 
 Phương trình vô 
 < 0 
 nghiệm 
 Sai 
 Đúng 
 = 0 Phương trình có nghiệm Kết thúc 
 kép 
 x= -b/2a 
 Sai 
 Phương trình có 2 nghiệm 
 - 3 - 
 x1,x2=(-b )/2a 
  Sau khi đã hướng dẫn xong các cách biểu diễn thuật toán để giải bài toán trên, giáo 
 viên nêu ra các ứng dụng của bài toán này trong thực tế: dùng để giải các phương trình bậc 2 
 trên máy tính cá nhân, tích hợp vào máy tính bỏ túi như: Casio FX 500A, Casio FX 
 500MS,.....mà học sinh chỉ cần nhập 3 hệ số a,b,c vào máy là ngay lập tức máy tính sẽ cho 
 nghiệm chính xác. 
 Bài toán 2: Kiểm tra tính nguyên tố của một số tự nhiên N 
 Phát vấn học sinh: Một số được coi là nguyên tố khi nào? Số 223 có là số nguyên tố 
 không? 
 Học sinh trả lời: Một số là số nguyên tố khi nó chỉ chia hết cho 1 và chính nó.Ví dụ : 
 2,3,5,7,11,13,17 
 Số 223 là số nguyên tố vì nó thỏa mãn tính chất trên. 
 Giáo viên lưu ý phân tích cho học sinh hiểu: Muốn kiểm tra tính nguyên tố của một số 
 nguyên dương N, ta chỉ cần xét xem nó có các ước trong khoảng từ 2 đến phần nguyên căn bậc 
 2 của nó là đủ( kí hiệu làError! Objects cannot be created from editing field codes.). Nếu N 
 không chia hết cho số nào trong khoảng này chứng tỏ N không nguyên tố. 
 Giáo viên bắt đầu trình chiếu 2 cách biểu diễn thuật toán và giải thích ý nghĩa từng biến 
 dùng trong thuật toán: 
 Cách 1: Liệt kê các bước 
 - Bước 1: Nhập số tự nhiên N. 
 - Bước 2: Nếu N=1 thì N không là số nguyên tố . 
 - Bước 3: Nếu 1<N< 4 thông báo N là số nguyên tố 
 - Bước 4: i2. 
 - Bước 5: Nếu Error! Objects cannot be created from editing field codes. thì thông 
 báo N là số nguyên tố rồi kết thúc 
 - Bước 6: Nếu N chia hết cho i thì thông báo N không là số nguyên tố rồi kết thúc. 
 - Bước 7: i i+1 rồi quay lại bước 5. 
 Cách 2: Biểu diễn bằng sơ đồ khối 
 Nhập N 
 Đ 
 N=1 ? 
 S 
 Đ 
 N<4 ? 
 S 
 i2 
 Đ 
 iN Thông báo N là số nguyên tố 
 rồi kết thúc 
 S 
 S 
 N có chia hết cho i 
 ii+1 không? 
 Đ 
Thông báo N không là số 
 nguyên tố rồi kết thúc 
 - 4 - 
 * Chú ý: Giáo viên nên chọn hiệu ứng xuất hiện từng bước để học sinh tiện theo dõi. 
Bài toán 3: Tìm Max của một dãy số gồm N số nguyên a1, a2, a3, , an. 
Trước tiên giáo viên phát vấn học sinh nêu ý tưởng để giải bài toán này. 
 Ý tưởng: 
 - Ban đầu coi max là a1. 
 - Duyệt từ đầu dãy đến cuối dãy, nếu gặp một số ai >Max thì gán Max bằng ai, cuối 
cùng sẽ tìm được Max. 
 Trình chiếu thuật toán: 
Cách 1: Liệt kê các bước 
 - Bước 1: Nhập N và N số nguyên a1, a2, a3, , an. 
 - Bước 2: Max  a1, i 2. 
 - Bước 3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc. 
 - Bước 4: 
 4.1: Nếu ai > Max thì Max ai 
 4.2: i i+1 rồi quay lại bước 3 
Cách 2: Biểu diễn bằng sơ đồ khối 
 Nhập n và dãy 
 a1,a2, ,an 
 Maxa1 , i 2 
 Đưa ra Max và kết 
 i >N? Đ 
 thúc 
 S 
 S 
 ai >Max? 
 Đ 
 Maxai 
 i i + 1 
Bài toán 4: Dùng thuật toán sắp xếp bằng tráo đổi để sắp xếp dãy số a1,a2, ,an theo thứ 
tự không giảm. 
 - 5 - 
  Ý tưởng: - Duyệt từ đầu dãy đến cuối dãy, nếu gặp một số ai >ai+1 thì đổi chỗ 2 số cho 
nhau.Tức là số đứng sau phải luôn lớn hơn hay bằng số đứng trước,giống như học sinh xếp 
hàng phảI tuân theo quy tắc bé đứng trước lớn đứng sau. 
 Như vậy ta phải duyệt dãy số nhiều lần, mỗi lần sẽ đưa được ít nhất một số về đúng vị 
trí của nó. 
 Giáo viên lại tiếp tục trình chiếu và hướng dẫn học sinh 2 cách biểu diễn thuật toán. 
Cách 1: Liệt kê các bước 
 Bước 1: Nhập số lượng các số hạng trong dãy (N) và các số cụ thể a1,a2, ,an. 
 Bước 2: MN . 
 Bước 3: Nếu M< 2 đưa ra dãy số đã sắp xếp. 
 Bước 4: MM-1, i0 
 Bước 5: ii+1 
 Bước 6: Nếu i>M quay lại bước 2 
 Bước 7: Nếu ai >ai+1 thì đổi chỗ 2 số cho nhau rồi quay lại bước 5. 
Cách 2: Biểu diễn bằng sơ đồ khối 
 Nhập n và dãy 
 a1,a2, ,an 
 MN 
 Đ Đưa ra dãy số đã 
 M<2? sắp xếp và kết thúc 
 S 
 MM-1, i 0 
 ii+1 
 Đ i >M ? 
 S 
 Tráo đổi ai và Đ ai >ai+1 
 ai+1 ? 
 Sau khi trình chiếu 2 cách biểu diễn thuật toán sắp xếp, giáo viên gọi 6 em học sinh lên 
đứng trước lớp theo thứ tự ngẫu nhiên để mô phỏng trực tiếp thuật toán sắp xếp. Cần sắp xếp 
lại sao cho 6 em này đứng theo đúng thứ tự bé đứng trước, lớn đứng sau đúng theo các bước 
trong thuật toán . 
Mô phỏng: 
Lúc đầu 6 em đứng như sau: ( Ta coi mỗi em là một số để tiện theo dõi) 
 - 6 - 
 2 5 4 1 6 3 
 Lần duyệt thứ nhất (tính từ phải sang trái): 
 Bạn số 6 cao hơn bạn 
 số 1 nên đổi chỗ 
 2 5 4 1 6 3 
 Bạn số 6 cao hơn bạn 
 số 4 nên đổi chỗ 
 2 5 4 6 1 3 
 - 7 - 
 Bạn số 6 cao hơn bạn 
 số 5 nên đổi chỗ 
 2 5 6 4 1 3 
 Bạn số 6 cao hơn bạn 
 số 2 nên đổi chỗ 
 2 6 5 4 1 3 
 Sau lần duyệt thứ nhất được 
 bạn số 6 về đúng vị trí. 
 6 2 5 4 1 3 
Lần duyệt thứ 2: 
 Bạn số 3 cao hơn bạn 
 số 1 nên đổi chỗ 
 6 2 5 4 1 3 
 - 8 - 
 6 2 5 4 3 1 
 Sau lần duyệt thứ 2 được 
 bạn số 1 và số 5 về đúng 
 vị trí. 
 6 5 2 4 3 1 
Lần duyệt 3: 
 Bạn số 4 cao hơn bạn số 2 
 nên đổi chỗ, sau lần này ta 
 được 4 bạn đúng vị trí: số 
 1,4,5,6. 
 6 5 2 4 3 1 
Lần duyệt 4 
 Bạn số 3 cao hơn bạn số 2 
 nên đổi chỗ,còn lại đã đúng 
 vị trí. 
 6 5 4 2 3 1 
Sau 4 vòng duyệt ta được một hàng theo đúng thứ tự như sau: 
 - 9 - 
6 5 4 3 2 1 
 - 10 -