Sáng kiến kinh nghiệm: Một số bước cơ bản giúp học sinh giải bài toán trên máy tính

ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY I. LÍ DO CHOÏN ÑEÀ TAØI: Dựa trên mục tiêu đổi mới chương trình giáo dục phổ thông của Bộ GD- ĐT ban hành nhằm góp phần năng cao chất lượng giáo dục toàn diện, tăng cường bồi dưỡng cho thế hệ trẻ lòng yêu nước, tinh thần tự tôn dân tộc, lòng nhân ái, ý thức tôn trọng pháp luật, tinh thần hiếu học, chí tiến thủ. Hỗ trợ tích cực việc đổi mới phương pháp dạy và học; Phát huy tư duy sáng tạo và năng lực tự học, khả năng ứng dụng kiến thức đã học của học sinh, quan tâm đúng mức tới các loại trình độ học tập. Tiếp cận trình độ giáo dục phổ thông của các nước tiên tiến trong khu vực và trên thế giới. Đảm bảo tính kế thừa, đảm bảo các tiêu chuẩn cơ bản, tinh giản, sát thực tiễn và điều kiện của nền giáo dục Việt Nam đã áp dụng cho tất cả các môn học nói chung và môn tin học nói riêng. Từ năm 2006 đến nay, môn tin học đã được áp dụng cho mọi đối tượng học sinh trung học phổ thông (THPT) không phân hóa theo chuyên ban và được dạy cho cả 3 khối lớp 10, 11, 12. Song môn tin học ở bậc Trung học cơ sở là một môn học tự chọn. Do vậy mà môn tin học ở bậc THPT được xây dựng trên giả thiết là một môn học mới nên học sinh phải học lại từ đầu. Vả lại môn tin học nhằm cung cấp cho học sinh những kiến thức phổ thông về ngành khoa học tin học, hình thành và phát triển khả năng tư duy thuật toán, năng lực sử dụng các thành tựu của ngành khoa học trong học tập và trong lĩnh vực hoạt động của mình sau này. Đặc biệt là về kiến thức sẽ trang bị cho học sinh một cách tương đối có hệ thống các khái niệm cơ bản nhất ở mức phổ thông về tin học, một ngành khoa học với những đặc thù riêng, các kiến thức về hệ thống, thuật toán, cấu trúc dữ liệu, lập trình, …. Về kỹ năng thì học sinh bước đầu biết được sử dụng máy tính, biết soạn thảo văn bản, biết GV: Nguyễn Huỳnh Thanh Trang 1 ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY sử dụng Internet, khai thác được các phần mềm thông dụng, giải được các bài toán đơn giản bằng máy tính. Còn về thái độ thì rèn luyện cho học sinh phong cách suy nghĩ và làm việc khoa học như sự ham hiểu biết, tìm tòi, sáng tạo, chuẩn mực chính xác trong suy nghĩ và hành động, say mê môn học, cẩn thận trong công việc, hợp tác tốt với bạn bè. Xuất phát từ thực tiễn giảng dạy tại trường THPT Sông Ray. Tôi thấy rằng, để đạt hiệu quả cao trong mỗi phần học, mỗi 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, mỗi 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 để đá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ó). Ngày nay, trong thời đại bùng nổ thông tin, việc lập được các chương trình tự hoạt động cho máy tính là rất cần thiết, và để làm được việc đó cần có một quá trình nghiên cứu, học tập về ngôn ngữ lập trình lâu dài, qua đó nhà lập trình có thể chọn một ngôn ngữ lập trình thích hợp. Tuy nhiên mọi thứ điều có điểm khởi đầu của nó, với học sinh bước đầu muốn giải một bài toán trên máy tính không phải là đơn giản. Do đó mà tôi đã chọn đề tài : “Một số bước cơ bản giúp học sinh giải bài toán trên máy tính” để các em thấy hứng thú, tích cực chủ động hơn đối với bộ môn tin học. Ii. toå chöùc thöïc hieän ÑEÀ TAØI : 1. Cơ sở lí luận : Trong quá trình nghiên cứu giải quyết các vấn đề về bài toán, người ta đã đưa ra những nhận xét như sau: o Có nhiều bài toán cho đến nay vẫn chưa tìm ra một cách giải theo kiểu thuật toán và cũng không biết là có tồn tại thuật toán hay không. o Có nhiều bài toán đã có thuật toán để giải nhưng không chấp nhận được vì thời gian giải theo thuật toán đó quá lớn hoặc các điều kiện cho thuật toán khó đáp ứng. GV: Nguyễn Huỳnh Thanh Trang 2 ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY o Có những bài toán được giải theo những cách giải vi phạm thuật toán nhưng vẫn chấp nhận được. Từ những nhận định trên, người ta thấy rằng cần phải có những đổi mới cho khái niệm thuật toán. Người ta đã mở rộng hai tiêu chuẩn của thuật toán: Tính xác định và tính đúng đắn. Việc mở rộng tính xác định đối với thuật toán đã được thể hiện qua các giải thuật đệ quy và ngẫu nhiên. Tính đúng của thuật toán bây giờ không còn bắt buộc đối với một số cách giải bài toán, nhất là các cách giải gần đúng. Trong thực tiễn có nhiều trường hợp người ta chấp nhận các cách giải thường cho kết quả tốt nhưng ít phức tạp và hiệu quả. Chẳng hạn nếu giải một bài toán bằng thuật toán tối ưu đòi hỏi máy tính thực hiện nhiều năm thì chúng ta có thể sẵn lòng chấp nhận một giải pháp gần tối ưu mà chỉ cần máy tính chạy trong vài ngày hoặc vài giờ. Các cách giải chấp nhận được nhưng không hoàn toàn đáp ứng đầy đủ các tiêu chuẩn của thuật toán thường được gọi là các thuật giải. Khái niệm mở rộng này của thuật toán đã mở cửa cho chúng ta trong việc tìm kiếm phương pháp để giải quyết các bài toán được đặt ra. Hạt nhân của chương trình máy tính là sự lưu trữ và xử lý thông tin. Việc tổ chức dữ liệu như thế nào có ảnh hưởng rất lớn đến cách thức xử lý dữ liệu đó, cũng như tốc độ thực thi và sự chiếm dụng bộ nhớ của chương trình. Do đó mục đích của đề tài này là cung cấp những hiểu biết nền tảng trong việc thiết kế một chương trình trên máy tính để thấy rõ được sự cần thiết của việc phân tích, lựa chọn cấu trúc dữ liệu phù hợp cho từng bài toán cụ thể. Trong phạm vi tin học, ta có thể quan niệm bài toán là một việc nào đó mà ta muốn máy tính thực hiện. Chẳng hạn như muốn đưa một dòng chữ ra màn hình, giải phương trình bậc hai, tìm ước chung lớn nhất của hai số nguyên dương, kiểm tra tính nguyên tố của một số nguyên dương hay xếp loại học tập của một lớp,… Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố đó là đưa vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output). Do đó để phát biểu một bài toán ta cần phải trình bày rõ Input và Output của bài toán đó và mối quan hệ giữa Input và Output. Việc cho một bài toán là mô tả rõ Input cho trước và Output cần tìm. Vấn đề là làm thế nào để tìm ra Output? Trước hết ta cần lưu ý rằng trong toán học có một GV: Nguyễn Huỳnh Thanh Trang 3 ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY xu hướng nghiên cứu định tính các bài toán có nghĩa là người ta có thể chỉ cần chứng minh sự tồn tại của lời giải và không cần chỉ ra một cách tường minh cách tìm lời giải đó. Đối với việc chỉ ra tường minh một cách tìm Output của bài toán được gọi là một thuật toán (Algorithm) giải bài toán đó. Có nhiều định nghĩa khác nhau về thuật toán và đây là một định nghĩa thường dùng. “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 ấy, từ Input của bài toán ta nhận được Output cần tìm”. Hiểu rõ khái niệm thuật toán là cách giải bài toán mà về nguyên tắc có thể giao cho máy tính thực hiện. Xây dựng thuật toán cho một số bài toán đơn giản. Qua đó hình thành một số kỹ năng chuẩn bị tiếp thu việc học ngôn ngữ lập trình, cách dùng biến, khởi tạo giá trị biến. Các kiến thức trên góp phần phát triển khả năng tư duy khi giải quyết các vấn đề trong khoa học cũng như trong cuộc sống. 2.Nội dung, biện pháp thực hiện các giải pháp của đề tài Học sử dụng máy tính thực chất là học cách giao cho máy tính việc mà ta muốn nó làm. Khả năng khai thác máy tính phụ thuộc rất nhiều vào sự hiểu biết của người dùng. Để giải bài toán trên máy tính thường được tiến hành qua các bước như sau: Bước 1: Xác định bài toán Việc xác định bài toán tức là xác định xem ta phải giải quyết vấn đề gì? Với giả thiết nào đã cho và lời giải cần đạt những yêu cầu gì? Khác với các bài toán thuần túy trong toán học là chỉ cần xác định rõ giả thiết và kết luận chứ không cần xác định yêu cầu về lời giải, đôi khi những bài toán tin học trong thực tế chỉ cần tìm lời giải tốt tới mức nào đó, thậm chí là chỉ ở mức chấp nhận được. Như đã trình bày ở mục cơ sở lí luận, mỗi bài toán được đặc tả bởi hai thành phần đó là Input và Output. Việc xác định bài toán chính là xác định rõ hai thành phần này và mối quan hệ giữa chúng. Các thông tin đó cần được nghiên cứu cẩn thận để có thể lựa chọn thuật toán, cách thể hiện các đại lượng đã cho, các đại lượng phát sinh trong quá trình giải bài toán và ngôn ngữ lập trình thích hợp. GV: Nguyễn Huỳnh Thanh Trang 4 ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY Ví dụ 1: Bài toán tìm ước chung lớn nhất của hai số nguyên dương a và b. - Xác định bài toán : o Input: Hai số nguyên dương a và b o Output: UCLN(a,b) Ví dụ 2: Bài toán tìm nghiệm của phương trình bậc hai: ax2 + bx + c = 0 (a ≠ 0) - Xác định bài toán : o Input: Các số thực a,b,c (a ≠ 0) o Output: Tất cả các nghiệm x thoả mãn phương trình: ax2 + bx + c = 0 Ví dụ 3: Bài toán xếp loại học tập của một lớp. - Xác định bài toán : o Input: bảng điểm của học sinh trong lớp o Output: bảng xếp loại học lực. Trong thực tế, ta nên xét một vài trường hợp cụ thể, thông qua đó hiểu được bài toán rõ hơn và thấy được các thao tác cần phải tiến hành. Đối với những bài toán đơn giản, đôi khi chỉ cần qua ví dụ là ta có thể đưa về một bài toán quen thuộc để giải. Bước 2: Lựa chọn hoặc thiết kế thuật toán Bước lựa chọn hoặc thiết kế thuật toán là bước quan trọng nhất để giải một bài toán. Mỗi thuật toán chỉ giải một bài toán nào đó nhưng có thể có nhiều thuật toán khác nhau cùng giải một bài toán. Nên ta cần thiết kế hoặc chọn một thuật toán phù hợp đã có để giải bài toán cho trước. Khi thiết kế hoặc lựa chọn thuật toán người ta thường quan tâm đến các tài nguyên như thời gian thực hiện, số lượng ô nhớ,… Trong các loại tài nguyên người ta quan tâm nhiều nhất đến thời gian vì đó là dạng tài nguyên không tái tạo được. Ví dụ: với bài toán tìm kiếm, nếu dãy đã cho là dãy đã sắp xếp thì dễ thấy thuật toán tìm kiếm nhị phân cần ít thao tác hơn nhiều so với thuật toán tìm kiếm tuần tự. Vì thế nó cần ít thời gian thực hiện hơn. GV: Nguyễn Huỳnh Thanh Trang 5 ... - tailieumienphi.vn