Tài liệu Skkn một số phương pháp tìm hiểu về bài toán và thuật toán

Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán MỘT SỐ PHƯƠNG PHÁP TÌM HIỂU VỀ BÀI TOÁN VÀ THUẬT TOÁN I/ LÍ DO CHỌN ĐỀ TÀI Ngày nay, trên thế giới nói chung và Việt Nam nói riêng đang diễn ra quá trình tin học hoá trên nhiều lĩnh vực hoạt động của xã hội loài người và đem lại nhiều hiệu quả to lớn. Việc sử dụng máy tính không còn chỉ bó hẹp trong viện nghiên cứu, các trường đại học, các trung tâm máy tính mà còn mở rộng ra mọi cơ quan, tổ chức kinh tế,.. và trong các gia đình. Song song với quá trình trên, việc giảng dạy Tin học trong các trường đại học, THPT cũng được đẩy mạnh đi đôi với việc tăng cường trang bị máy vi tính. Đảng và Nhà nước ta đã nhận thấy được tầm quan trọng của ngành Tin học và đã đưa môn học này vào trường phổ thông như những môn học khác bắt đầu từ năm học 2006-2007. Chính vì vậy, đối với mỗi giáo viên giảng dạy môn Tin học ở các trường phổ thông, việc tìm hiểu, nghiên cứu các vấn đề về Tin học, cùng với việc tìm các biện pháp giảng dạy Tin học trong các trường phổ thông là một công việc cần phải làm thường xuyên, nhằm đáp ứng với sự đòi hỏi ngày càng cao của xã hội. Trong nghiệp vụ của người thầy (cô) giáo có hai vấn đề quan trọng: thứ nhất là thực tiễn về tiềm năng - những kiến thức lý thuyết mà họ được học rất cơ bản. Thứ hai là thực tiễn về nghiệp vụ - thầy (cô) giáo phải biết cách truyền thụ kiến thức phù hợp với trình độ của học sinh. Trong đó, thực tiễn thứ hai là điều quyết định trong nghiệp vụ của thầy (cô) giáo, nó đánh giá chất lượng giảng dạy của thầy (cô) giáo. Hai thực tiễn trên vừa mâu thuẫn với nhau, lại vừa thống nhất với nhau. Thầy (cô) giáo không thể mang hết các kiến thức lý thuyết cao xa và trừu tượng dạy cho học sinh, nhưng cũng không thể dạy tốt cho học sinh nếu thầy (cô) giáo hiểu biết quá ít. Trong bối cảnh toàn ngành Giáo dục và Đào tạo đang nỗ lực đổi mới phương pháp dạy học theo hướng phát huy tính tích cực chủ động của học sinh trong hoạt động học tập. Điều 24.2 của Luật giáo dục đã nêu rõ: “Phương pháp giáo dục phổ thông phải phát huy tính tích cực, tự giác, chủ động, sáng tạo của Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 1 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán học sinh, phù hợp với đặc điểm của từng khu vực, lớp học và môn học; bồi dưỡng phương pháp tự học, rèn luyện kỹ năng vận dụng kiến thức vào thực tiễn, tác động đến tình cảm, đem lại niềm vui, hứng thú học tập cho học sinh”. Như vậy, chúng ta có thể thấy định hướng đổi mới phương pháp dạy học đã được khẳng định, không còn là vấn đề tranh luận. Cốt lõi của việc đổi mới phương pháp dạy học ở trường phổ thông là giúp học sinh hướng tới việc học tập chủ động, chống lại thói quen học tập thụ động. Đổi mới phương pháp dạy học theo hướng tích cực hóa hoạt động của học sinh là một quá trình lâu dài; không thể ngày một ngày hai mà đông đảo giáo viên từ bỏ được kiểu dạy học truyền thụ kiến thức, tiếp thu thụ động đã quen thuộc từ lâu. Việc phát triển các phương pháp tích cực đòi hỏi một số điều kiện, trong đó quan trọng nhất là bản thân mỗi giáo viên cần có một sự nỗ lực để tìm tòi, sáng tạo trong công tác giảng dạy của mình. Đổi mới phương pháp dạy học là một vấn đề hết sức quan trọng, nhất là với bộ môn Tin học hiện đang được đưa vào giảng dạy ở các trường phổ thông. Là một giáo viên giảng dạy bộ môn này, theo tôi không phải cứ tìm được nhiều bài toán khó, bài toán hay để giảng dạy cho học sinh. Mà vấn đề đặt ra là chúng ta cần phải tích cực tìm tòi, sáng tạo trong việc đưa ra những bài toán đó như thế nào để giúp cho học sinh có sự hứng thú, tìm tòi sáng tạo trong quá trình học tập, từ đó biết vận dụng linh hoạt trong các tình huống cụ thể ngoài thực tế. Trong việc giảng dạy cho học sinh, ngoài việc giúp học sinh lĩnh hội những kiến thức cơ bản. Người thầy còn phải biết kích thích tính tích cực, sự sáng tạo say mê học hỏi của học sinh trong việc học tập của các em. Bởi vì, việc học tập tự giác, tích cực, chủ động và sáng tạo đòi hỏi học sinh phải có ý thức về những mục tiêu đặt ra và tạo được động lực bên trong thúc đẩy bản thân họ hoạt động để đạt các mục tiêu đó. Các cách thiết kế bài giảng hiện nay nhằm mục đích áp dụng phương pháp hiện đại để bồi dưỡng cho học sinh năng lực ham muốn học hỏi, tư duy sáng tạo, năng lực tự giải quyết vấn đề, rèn luyện và phát triển năng lực tự học sáng tạo, nghiên cứu, nghĩ và làm việc một cách tự chủ… Đồng thời để thích Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 2 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán ứng với sự phát triển tư duy của học sinh trong xã hội mới và tiếp cận với các công nghệ tiên tiến trên thế giới. Bên cạnh đó, trong các kỹ thuật dạy học mới, vai trò của người thầy có sự thay đổi là: “hướng dẫn học sinh biết tự mình tìm ra hướng giải quyết những vấn đề nảy sinh trong quá trình học tập, biết cách làm việc độc lập, làm việc tập thể. Thầy là người định hướng, là người cố vấn giúp học sinh tự đánh giá, cũng như giúp học sinh luôn đi đúng con đường tìm hiểu, lĩnh hội kiến thức…”. Xuất phát từ thực tiễn giảng dạy tại trường THPT Thanh Bình tôi thấy rằng, để đạt hiệu quả cao trong mỗi phần học, tiết học cần có cách thiết kế bài giảng cho phù hợp với nội dung kiến thức, phương pháp, phương tiện dạy học phải phù hợp với từng đối tượng học sinh. Để qua mỗi phần học, tiết học học sinh thích thú với kiến thức mới, qua đó hiểu được kiến thức đã học trên lớp, đồng thời học sinh thấy được tầm quan trọng của vấn đề và việc ứng dụng của kiến thức trước hết để đáp ứng những yêu cầu của môn học, sau đó là việc ứng dụng của nó vào các công việc thực tiển trong đời sống xã hội (nếu có). Tuy nhiên, với các em học sinh nói chung và đặc biệt ở vùng nông thôn nói riêng, việc tiếp cận với bộ môn Tin học còn nhiều hạn chế. Một lẽ dễ hiểu đó là vì hầu hết các em ít có điều kiện tiếp xúc, nguyên nhân chính là điều kiện kinh tế cũng như cơ sở vật chất chưa đáp ứng đầy đủ, vì thế lĩnh vực công nghệ thông tin vấn còn khá mới mẻ! Vì vậy quá trình dạy và học bộ môn Tin học trong nhà trường phổ thông còn gặp rất nhiều khó khăn. Từ thực tế này tôi muốn chia sẻ một kinh nghiệm nho nhỏ để chúng ta cùng tham khảo trong quá trình dạy học, đó là kinh nghiệm về việc phối hợp một số phương pháp trong giờ dạy- học để giúp học sinh có cái nhìn trực quan, giúp các em nắm được bài tốt hơn. Cụ thể tôi muốn nói ở đây là dùng "giáo án điện tử" do giáo viên tự biên soạn để trình chiếu bài giảng, kết hợp thuyết trình, vấn đáp và mô phỏng bằng các ví dụ thực tế cho học sinh. Trước đây chúng ta thường sử dụng phương pháp thuyết trình, vấn đáp đơn thuần trên lớp do chưa đủ phương tiện. Nhưng những năm gần đây, được sự Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 3 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán quan tâm của Bộ Giáo dục _ Sở Giáo dục và Đào tạo đã trang bị cho các trường phổ thông một số máy tính (Computer) và máy chiếu (Projector), vì vậy chúng ta có nhiều điều kiện dùng "giáo án điện tử" để trình chiếu bài giảng cho học sinh. Tôi xin trình bày phương pháp giảng dạy của mình thông qua một ví dụ về một bài giảng cụ thể trong chương trình Tin học lớp 10, đó là bài "Tìm hiểu bài toán và thuật toán". Đây được coi là bài học khó trong chương trình giáo khoa lớp 10 và có liên quan chặt chẽ đến kiến thức lớp 11 sau này. 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/ CƠ SỞ LÍ LUẬN VÀ THỰC TIỄN 1/ Cơ sở lí luận - Nhiều gia đình và học sinh chưa có điều kiện trang bị máy tính cho học sinh vì đời sống gia đình còn gặp nhiều khó khăn. - Nhiều gia đình còn ngại cho học sinh sử dụng máy tính vì sợ con em mình ham mê các trò chơi điện tử . . . - Một số học sinh chưa thực sự số gắng tự học, tự nâng cao khả năng tư duy về toán học cũng như các thuật toán. - Một số học sinh chưa hiểu hết tầm quan trong của thuật toán và chưa ứng dụng môn học này vào quá trình giải quyết một số bài toán đại số và vật lý bằng máy tính điện tử. - Tình hình ứng dụng tin học nói chung và ngôn ngữ lập trình đã góp phần không nhỏ trong việc học tập của học sinh trong một vài năm gần đây cùng với Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 4 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán xu hướng đổi mới phương pháp giảng dạy, học sinh đã không ngừng ứng dụng thành quả của lập trình vào học tập. - Trong giáo dục phổ thông cần phải phát huy tính tích cực, tự giác, chủ động sáng tạo của học sinh phù hợp với từng lớp học, môn học, tác động đến tình cảm đem lại niềm vui, hứng thú trong khi học môn tin học. - Phương pháp tích cực là phương pháp giáo dục, dạy học theo hướng phát huy tính tích cực, chủ động sáng tạo của người học thông qua việc tổ chức hiệu quả các hoạt động của học sinh. 2/ Thực tiễn của vấn đề a /Tình trạng thực tiễn khi chưa thực hiện đề tài Trước đây khi chưa áp dụng phương pháp giảng dạy bằng giáo án điện tử, lấy ví dụ từ thực tế… học sinh luôn phản ánh với giáo viên rằng: “Bài toán và thuật toán” này khó hiểu và trừu tượng. Khi kiểm tra với mức độ đề tương đương với một vài ví dụ trong sách giáo khoa, các em vẫn mơ hồ và đạt kết quả chưa cao. b/ Khảo sát thực tế Giáo viên đưa ra đề kiểm tra 1 tiết đối với lớp 10A3 có 38 học sinh như sau: Bài 1: Xác định Input và Output của bài toán sau: “Tính tổng các bình phương các chữ số của 1 số tự nhiên bất kỳ có 4 chữ số ” Bài 2: Liệt kê các bước của thuật toán để giải bài toán sau : a Rút gọn phân số b với a, b bất kỳ, b  0 . Kết quả kiểm tra như sau: Điểm 2.5 đến 3 4 5 6 7 8 9 Số học sinh 10 7 8 6 4 3 0 Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình Tỉ lệ 29% 18% 21% 15% 10% 8% 0% 5 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán 10 0 0% Đối với Bài 1: Hầu như học sinh chỉ tìm được Input và Output của bài toán mà chưa viết được đầy đủ thuật toán để giải. Đối với Bài 2: Học sinh chưa mô phỏng được thuật toán bằng cách liệt kê hoặc sơ đồ khối III/ TỔ CHỨC THỰC HIỆN CÁC GIẢI PHÁP 1/ Chuẩn bị a/ Về phương pháp: - Giáo viên soạn trước bài giảng "Tìm hiểu 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 5 tiết học”. Sử dụng phương pháp thuyết trình kết hợp pháp vấn. - Chuẩn bị một số bài tập áp dụng để rèn luỵên kỹ năng biểu diễn thuật toán. b/ Về phương tiện: - Giáo viên chuẩn bị máy tính “để bàn hoặc xách tay”, một máy chiếu, một màn chiếu, bút chỉ laze, bảng phụ … - 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 "Tìm hiểu 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  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 ? Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 6 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán 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: SBD Điểm Điểm Điểm Điểm Điểm Điểm Tổng Xếp Họ và tên Ngoại toán văn lý sinh sử điểm loại ngữ Đào T Hoa 8 9 7 8 6 5 43 Khá 51012 3 51012 Mai T Hà 2 3 4 4 5 3 21 Yếu 4 51012 Đỗ T Nga 9 8 7 8 9 10 51 Giỏi 5 51012 Lê T Nhàn 6 5 4 9 8 7 45 Khá 6 51012 Mai V Sơn 6 7 4 3 6 5 31 TB 7 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 Ví dụ 1 Ví dụ 2 Ví dụ 3 Các hệ số a, b, c bất kỳ Có 100 con trâu và 100 bó cỏ. Mỗi con trâu đứng ăn 5 bó. 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, điểm toán, điểm văn, điểm lý… Kết quả Nghiệm của phương trình (nếu có) có dạng số nguyên hoặc số thực. Số lượng trâu đứng, trâu nằm và trâu già (dạng số nguyên) Tổng điểm của mỗi học sinh, xếp loại tốt nghiệp nào, đỗ hay trượt… Phát vấn học sinh: Một bài toán trong “toán học” gồm mấy phần? đó là những phần nào? Học sinh trả lời: Một bài toán trong “toán học” gồm hai phần: - Giả thiết - Kết luận 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. Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 7 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán 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. Toán học Giả thiết Kết luận Tin học Thông tin đưa vào máy Thông tin muốn lấy tứ máy Thuật ngữ Input Output - 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: Bài toán Input Output - 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? Bài toán Input Bước 1, Bước 2 . . . . . . . . . . . . . . .Bước n Output Thuật toán Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 8 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán 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 3 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  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  Mũi tên: mô tả trình tự thực hiện các bước  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. Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 9 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán * 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 đủ hoặc có thể một em lên bảng giải bài toán phương trình bậc 2 dạng tổng quát, rồi từ đó 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ố  = b2- 4ac - Bước 4: Nếu  < 0 thông báo phương trình vô nghiệm rồi kết thúc. - Bước 5: Nếu  = 0 thông báo phương trình có nghiệm kép x b 2a rồi kết thúc. - Bước 6: Nếu  b   > 0 thông báo phương trình có 2 nghiệm x1,x2= 2a , rồi kết thúc. - Bước 7: Kết thúc. Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 10 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán Cách 2: Biểu diễn thuật toán bằng sơ đồ khối Bắt đầu Nhập a,b,c Tính  = b2- 4ac Đúng  <0  =0 Phương trình vô nghiệm Sai Phương trình có nghiệm kép x= -b/2a Đúng Sai Kết thúc Phương trình có 2 nghiệm 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: Giải phương trình bậc nhất ax +b = 0 - Phát vấn học sinh: Khác với phương trình bậc 2 dạng tổng quát theo em để giải phương trình bậc nhất ta có các cách nào? - Học sinh lên bảng trình bày? Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 11 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán  Giáo viên lưu ý phân tích cho học sinh hiểu: Để trình bày thuật toán này bằng cách liệt kê có rất nhiều lựa chọn và từ đó đưa ra lựa chọn ngắn gọn, đơn giản, dễ hiểu và dễ trình bày nhất. Giáo viên bắt đầu trình chiếu các cách liệt kê 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 a, b - Bước 2: Nếu a = b thì - Bước 2.1: Nếu Nếu b= 0 Xuất phương trình vô số nghiệm rồi kết thúc - Bước 2.2: Nếu b<>0 Xuất phương trình vô nghiệm rồi kết thúc - Bước 3: Nếu a<> 0 thì x = -b/a Xuất giá trị x rồi kết thúc. Cách 2: - Bước 1: Nhập a, b - Bước 2: NẾU a= 0 thì Nếu b = 0 Xuất phương trình vô số nghiệm rồi kết thúc Ngược lại thì Xuất phương trình vô nghiệm rồi kết thúc NGƯỢC LẠI thì x = -b/a Xuất giá trị x rối kết thúc * Thuật toán sơ đồ khối: Nhập a, b Đúng Xuất pt vô số nghiệm rồi (kết thúc) Đúng a = 0? b = 0? Sai Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình Sai Xuất pt vô nghiệm rồi (kết thúc) 12 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán x = -b/a Xuất x rồi (kết thúc) * 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 hai số nguyên dương A và B 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: - Trước tiên ta có thể mời hai hoc sinh lên bảng sau dó so sanh chiều cao của hai bạn. - Nếu bạn A cao hơn bạn B thì Max là bạn A ngược lại Max là bạn B - Trình chiếu thuật toán: Cách 1: Liệt kê các bước - Bước 1: Hai số nguyên dương A và B - Bước 2: Nếu A> B thì Max là A rồi chuyển đền bước 4 - Bước 3: Nếu A< B thì Max là b rồi chuyển đền bước 4 - Bước 4 : Đưa ra Max của A và B rồi kết thúc Cách 2: Biểu diễn bằng sơ đồ khối Nhập A, B A>B Đ Max A S Max B Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình Đưa ra Max rồi Kết thúc 13 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán Bài toán 4: Tìm UCLN của hai số nguyên dương A và B - Pháp vấn học sinh: Thế nào là UCLN của hai số nguyên dương? - Học sinh trả lời : UCLN của một số nguyên dương là hai số đó chia hết cho một số lớn nhất. Cách 1: Thuật toán liết kê. Bước 1: Nhập hai số nguyên dương A và B Bước 2: Nếu A = B thì UCLN của A và B là A or là B rồi kết thúc. Bước 3: Nếu A > B thì A = A – B rồi quay lại Bước 2 Bước 4: Nếu B > A thì B = B – A rối quay lại Bước 2 Bước 5: Xuất UCLN của A và B rồi kết thúc Cách 2: Thuật toán sơ đồ khối - Ở bài toán này giáo viên cho học sinh thảo luận nhóm để từ đó học sinh có thể hình dung và trình bày thuật toán này bằng sơ đồ khối. - Sau mười phút giáo viên gọi học sinh lên bảng trình bày thuật toán, các nhóm khác đưa ra những nhận xét góp ý. - Các nhóm đã nhận xét góp ý xong, giáo viên củng cố lại và trình chiếu thuật toán: Nhập A,B A=B Đúng Đưa ra UCLN của A, B rồi (kết thúc) Sai A>B Đúng A= A- B Sai Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 14 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán B=B-A Bài toán 5 : Tìm UCLN của hai số nguyên dương A = 25 và B= 15. * Ý tưởng: Duyệt lần lượt cho đến khi hai số đó chia cho một số lớn nhất - 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 hai số nguyên dương A = 25 và B = 15 Bước 2: Nếu A = B thì UCLN của A và B là A or là B rồi kết thúc. Bước 3: Nếu A > B thì A = 25 – 15 rồi quay lại Bước 2 (A = 10) Bước 4: Nếu B > A thi B = 15 – 10 rồi quay lại Bước 2 (B = 5) Bước 4: Nếu A > B thi B = 10 – 5 rồi quay lại Bước 2 (A =5) Bước 5: Xuất UCLN của A=25 và B=15 là 5 rồi kết thúc Cách 2: Biểu diễn bằng sơ đồ khối Nhập A= 25,B=15 Đúng A=B Đưa ra UCLN của A, B rồi (kết thúc) Sai Đúng A>B Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình A = 25 - 15 15 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán Sai B=B-A Duyệt lần thứ nhất: A = 25 và B =15  A > B; A = A – B (25 -15)  A = 10 - Lần duyệt thứ nhất ta thấy A =10 và B = 15 nên A < B vì thế ta chuyển sang lần duyệt thứ hai Lần duyệt thứ hai Nhập A= 25, B=15 Đúng A=B Đưa ra UCLN của A, B rồi (kết thúc) Sai Sai AB A = 10 - 5 Sai B=B-A Duyệt lần thứ ba: A = 10 và B =5  A > B; A = A – B (10 -5)  A = 5 - Lần duyệt thứ ba ta thấy A =5 và B = 5 nên A = B vậy UCLN của A = 25 và B = 15 là 5 * Sau ba lần duyệt ta tìm ra được UCLN của hai số nguyên dương A = 25 và B = 15 là 5 rồi kết thúc. Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 17 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán Bài toán 6: Tính tổng của 100 số tự nhiên đầu tiên: - Trước tiên giáo viên cần yêu cầu học sinh xác định hai yêu tố Input và Output. + Input: Dãy 100 số tự nhiên đầu tiên: 1, 2, 3, . . ., 100. + Output: Giá trị tổng 1 + 2 + 3 + . . . + 100. * Ý tưởng: Để giải bài toán này là dùng một biến Sum để lưu giá trị của tổng. Việc tìm Sum có thể được thực hiện như sau: Đầu tiên gán cho Sum giá trị bằng 0. Tiếp theo lần lượt thêm các giá trị 1, 2, 3, 4, ….., 100 vào Sum. Vấn đề là ở chỗ tổ chức việc “lần lượt thêm vào” như thế nào? Cách dễ nhận thấy nhất là thực hiện liên tiếp 100 phép cộng: Bước 1: Sum  0. Bước 2: Sum  Sum + 1. ... Bước 101: Sum  Sum + 100. Tuy nhiên việc mô tả thuật toán như trên là quá dài dòng (nhất là khi không chỉ tính tổng của 100 số mà các số cần tính tổng lớn hơn nhiều). Để ý một chút ta có thể thấy trong tất cả các bước nêu trên đều chỉ có một phép toán để thực hiện: cộng thêm vào Sum lần lượt các giá trị 1, 2, 3, …, 100. Tức là chỉ có một thao tác “cộng” được lặp đi lặp lại 100 lần. Mặt khác, việc cộng thêm số i vào Sum chỉ được thực hiện khi i không vượt quá 100. Vì vậy, thuật toán tìm Sum có thể được mô tả ngắn gọn hơn như sau: Bước 1: Sum  0; i  0. Bước 2: i  i + 1. Bước 3: Nếu i <= 100, thì Sum  Sum + i và quay lại bước 2. Bước 4: Thông báo kết quả rồi kết thúc. Giáo viên có thể mô ta bằng hình vẽ 8 7 để học sinh nắm bắt dễ hơn. 6 . . . . . . 5 4 3 2 3 2 1 1 Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 18 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán Bài toán 7: Tìm số lớn nhất trong dãy A các số a1, a2, …, an cho trước. * Ý tưởng: Ta sẽ dùng biến Max để lưu giá trị phần tử lớn nhất của dãy A. Việc xác định Max có thể được thực hiện như sau: Đầu tiên ta gán giá trị a1 cho biến Max, tiếp theo ta lần lượt so sánh các số a2, …, an của dãy A với Max. Nếu ai > Max, ta gán ai cho Max. Từ đó ta có thuật toán như sau: + Input: Dãy A các số a1, a2, …, an (n>=1). + Output: Giá trị Max = max a1, a2, …, an Bước 1: Max  a1; i  1. Bước 2: i  i + 1. Bước 3: Nếu i > n, chuyển đến bước 5. Bước 4: Nếu ai > Max, Max  ai. Quay lại bước 2. Bước 5: Kết thúc thuật toán. * Ta có thể minh họa thuật toán trên với một trường hợp chọn Thỏ lớn nhất trong bốn chú Thỏ như sau: Max 1 2 1 3 4 - Duyệt lần 1: Trước hết, ta giả sử thỏ lớn nhất là thỏ số 1, tức là Max  1. Max  1 Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 19 Sáng kiến kinh nghiệm: Một số phương pháp tìm hiểu vế Bài toán và Thuật toán 1 2 3 4 - Duyệt lần 2: So sánh Max (thỏ số 1) với thỏ số 2. Vì thỏ số 2 nhỏ hơn thỏ số 1, do đó Max vẫn bằng 1. Max  3 1 2 3 4 - Duyệt lần 3: So sánh Max (thỏ số 1) với thỏ số 3. Vì thỏ số 3 lớn hơn thỏ số 1, do đó Max được đặt lại bằng 3 (thỏ số 3) Max  3 Gv:Nguyễn Quang Hưng – Trường THPT Thanh Bình 20