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

Chia sẻ: Thanhbinh225p Thanhbinh225p | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

163
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Xuất phát từ thực tế đó mà đề tài "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" đã được nghiên cứu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY Một tiêu chí khác được rất nhiều người quan tâm là cần thiết kế hoặc lựa chọn thuật toán sao cho việc viết chương trình cho thuật toán đó ít phức tạp. Do vậy khi thiết kế hoặc lựa chọn thuật toán để giải một bài toán cụ thể cần căn cứ vào lượng tài nguyên mà thuật toán đòi hỏi và lượng tài nguyên thực tế cho phép. Ngoài ra khi giải một bài toán, ta cần phải định nghĩa tập hợp dữ liệu để biểu diễn tình trạng cụ thể. Việc lựa chọn này tùy thuộc vào vấn đề cần giải quyết và những thao tác sẽ tiến hành trên dữ liệu vào. Có những thuật toán chỉ thích ứng với một cách tổ chức dữ liệu nhất định, đối với những cách tổ chức dữ liệu khác thì sẽ kém hiệu quả hoặc không thể thực hiện được. Chính vì vậy nên bước xây dựng cấu trúc dữ liệu không thể tách rời bước tìm kiếm thuật toán giải quyết vấn đề. Các tiêu chuẩn khi lựa chọn cấu trúc dữ liệu:  Cấu trúc dữ liệu trước hết phải biểu diễn được đầy đủ các thông tin nhập và xuất của bài toán.  Cấu trúc dữ liệu phải phù hợp với các thao tác của thuật toán mà ta lựa chọn để giải quyết bài toán.  Cấu trúc dữ liệu phải cài đặt được trên máy tính với ngôn ngữ lập trình đang sử dụng. Đối với một số bài toán, trước khi tổ chức dữ liệu ta phải viết một đoạn chương trình nhỏ để khảo sát xem dữ liệu cần lưu trữ lớn tới mức độ nào. Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy thao tác trên cấu trúc dữ liệu sao cho: với một bộ dữ liệu vào, sau số hữu hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định. Thuật toán thông thường có 5 đặc trưng sau: o Tính đơn nghĩa. Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lộn xộn, tùy tiện, đa nghĩa. o Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng lại và cho kết quả sau một số hữu hạn bước. GV: Nguyễn Huỳnh Thanh Trang 6
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY o Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng quá trình đã định, ta phải được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó được kiểm chứng bằng yêu cầu bài toán. o Tính khả dụng Thuật toán phải dễ sửa lỗi để thích ứng được với bất kỳ bài toán nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau. o Tính khả thi Kích thước phải đủ nhỏ: Ví dụ: một thuật toán sẽ có tính hiệu quả bằng 0 nếu lượng bộ nhớ mà nó yêu cầu vượt quá khả năng lưu trữ của hệ thống máy tính. Thuật toán phải chuyển được thành chương trình: Ví dụ thuật toán yêu cầu phải biểu diễn được số vô tỷ với độ chính xác tuyệt đối là không thể thực hiện được với các hệ thống máy tính hiện nay. Thuật toán phải được máy tính thực hiện trong thời gian cho phép, điều này khác với lời giải toán(chỉ cần chứng minh và kết thúc sau một số hữu hạn bước). Ví dụ: chương trình sắp xếp thời khóa biểu cho một học kỳ thì không thể cho máy tính chạy tới học kỳ sau mới có kết quả được. Ví dụ: Bài toán tìm ước chung lớn nhất của hai số nguyên dương a và b. Thuật toán sẽ được tiến hành mô tả như sau: (có 2 cách) Cách 1: Diễn tả thuật toán B1: Nhập 2 số nguyên dương a,b B2: Nếu a = b thì lấy giá trị chung này làm UCLN rồi chuyển đến B5. B3: Nếu a>b thì a  a – b; rồi quay lại B2. B4: Nếu b>a thì b  b – a; rồi quay lại B2. B5: Đưa ra kết quả UCLN rồi kết thúc. Ngoài cách liệt kê dãy các thao tác như trên, thuật toán còn có thể được diễn tả bằng sơ đồ khối. Trong sơ đồ khối, người ta dùng một số khối, đường có mũi tên với: GV: Nguyễn Huỳnh Thanh Trang 7
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY o Hình thoi ◊ : Thể hiện thao tác so sánh. o Hình chữ nhật : Thể hiện các phép tính toán o Hình Ô van ○ : Thể hiện thao tác nhập, xuất dữ liệu. o Các mũi tên  : Qui định trình tự thực hiện các thao tác. Cách 2: Vẽ sơ đồ khối Nhập a,b Đ a=b S Lấy giá trị chung làm aa-b UCLN, rồi két thúc. Đ a>b S bb-a GV: Nguyễn Huỳnh Thanh Trang 8
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY Bước 3: Viết chương trình Sau khi đã có thuật toán ta phải lập trình để thực hiện thuật toán đó. Muốn lập trình đạt hiệu quả cao, cần phải có kỹ thuật lập trình tốt. Kỹ thuật lập trình tốt thể hiện ở kỹ năng viết chương trình, khả năng gỡ rối và thao tác nhanh. Lập trình tốt không chỉ nắm vững ngôn ngữ lập trình là đủ, mà phải biết cách viết chương trình một cách uyển chuyển, khôn khéo và phát triển dần dần để chuyển các ý tưởng ra thành chương trình hoàn chỉnh. Kinh nghiệm cho thấy một thuật toán hay nhưng do cài đặt vụng về nên khi chạy lại cho kết quả sai hoặc tốc độ chậm. Thông thường, ta không nên cụ thể hóa ngay toàn bộ chương trình mà nên tiến hành theo phương pháp tinh chế từng bước. Ban đầu chương trình được thể hiện bằng ngôn ngữ tự nhiên, thể hiện thuật toán với các bước tổng thể, mỗi bước nêu lên một công việc phải thực hiện. Một công việc đơn giản, hoặc một đoạn chương trình đã được học thuộc thì ta tiến hành viết mã lệnh ngay bằng ngôn ngữ lập trình. Một công việc phức tạp thì phải chia ra thành những công việc nhỏ hơn để tiếp tục với những công việc nhỏ hơn đó. Trong quá trình tinh chế từng bước ta phải đưa ra những biểu diễn dữ liệu, như vậy cùng với sự tinh chế các công việc, dữ liệu cũng được tinh chế dần, có cấu trúc hơn, thể hiện rõ hơn mối liên hệ giữa các dữ liệu. Phương pháp tinh chế từng bước là một thể hiện của tư duy giải quyết vấn đề từ trên xuống, giúp cho người lập trình có một định hướng thể hiện phong cách viết chương trình. Tránh việc mò mẫm, xóa đi viết lại nhiều lần, biến chương trình thành tờ giấy nháp. Do vậy khi viết chương trình ta nên chọn một ngôn ngữ lập trình hoặc một phần mềm chuyên dụng thích hợp với thuật toán. Viết chương trình trong ngôn ngữ nào thì cần phải tuân theo đúng qui định ngữ pháp của ngôn ngữ đó. Ví dụ: Viết chương trình tìm ước chung lớn nhất của hai số nguyên dương a và b. GV: Nguyễn Huỳnh Thanh Trang 9
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY Để kế thừa cho chương trình lớp 11, tôi chọn ngôn ngữ lập trình bậc cao Turbo Pascal một phần mềm chuyên dụng thích hợp với thuật toán để viết chương trình trên. Program UCLN; Uses crt; Var a,b : Integer; Begin Clrscr; Write (‘nhap 2 so nguyen duong a, b:’); readln(a,b); While a< > b do Begin If a > b then a:= a - b Else b: = b - a; End; Writeln(‘UCLN cua 2 so nguyen duong la:’,a); Readln End. Bước 4: Hiệu chỉnh Chương trình là do con người viết ra, cho nên khó có thể tránh khỏi sự nhầm lẫn. Một chương trình viết xong chưa chắc đã chạy được ngay trên máy tính để cho ra kết quả mong muốn. Kỹ năng tìm lỗi, sửa lỗi, điều chỉnh lại chương trình cũng là một kỹ năng quan trọng của người lập trình. Kỹ năng này có được bằng kinh nghiệm tìm và sửa lỗi của chính mình. Có 3 loại lỗi thường gặp khi lập trình:  Lỗi cú pháp: lỗi này hay gặp nhưng cũng là lỗi dễ sửa nhất. Chỉ cần nắm vững ngôn ngữ lập trình là đủ. Một người được coi là không biết lập trình nếu không biết sửa lỗi cú pháp. GV: Nguyễn Huỳnh Thanh Trang 10
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY  Lỗi cài đặt: Việc cài đặt thể hiện không đúng thuật toán đã định, đối với mỗi lỗi này thì phải xem lại tổng thể chương trình. Kết hợp với các chức năng gỡ rối để sửa lại cho đúng.  Lỗi thuật toán: Lỗi này ít gặp nhất nhưng nguy hiểm nhất. Nếu nhẹ thì phải điều chỉnh lại thuật toán, nếu nặng thì có khi phải viết lại một thuật toán mới từ đầu. - Có nhiều chương trình rất khó kiểm tra tính đúng đắn. Nhất là khi ta không biết kết quả đúng là thế nào? Vì vậy, nếu như chương trình vẫn chạy ra kết quả (không biết đúng sai thế nào) thì việc tìm lỗi rất khó khăn. Khi đó ta nên làm các bộ test để thử chương trình của mình. - Các bộ test nên đặt trong các file văn bản, bởi việc tạo một file văn bản (txt) rất nhanh, và mỗi lần chạy thử thì chỉ cần thay tên file dữ liệu vào là xong, không cần gõ lại bộ test từ bàn phím. Kinh nghiệm làm các bộ test là:  Bắt đầu với một bộ test nhỏ, đơn giản, làm bằng tay, cũng có được đáp số để so sánh với kết quả chương trình chạy ra.  Tiếp theo vẫn là các bộ test nhỏ nhưng chứa các giá trị đặc biệt hoặc tầm thường. Theo kinh nghiệm cho thấy thì đây là những bài test dễ sai nhất.  Các bộ test phải đa dạng, tránh sự lặp đi lặp lại các bộ test tương tự.  Nên có một vài bộ test lớn để kiểm tra tính chịu đựng của chương trình. Kết quả đó đúng hay không thì trong đa số trường hợp, ta không thể kiểm chứng được với test này. Lưu ý rằng, chương trình của bạn chạy qua được hết các bài test có nghĩa là chương trình đã đúng. Bởi vì có thể bạn chưa xây dựng được bộ test làm cho chương trình bị sai. Vì vậy, nếu có thể, ta nên tìm cách chứng minh tính đúng đắn của thuật toán và chương trình. Điều này thường rất khó.  Một chương trình chạy đúng không có nghĩa là việc lập trình đã xong. Ta phải sửa đổi lại một vài chi tiết để chương trình có thể chạy nhanh hơn, hiệu quả hơn. GV: Nguyễn Huỳnh Thanh Trang 11
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY  Thông thường trước khi kiểm thừ thì ta nên đặt mục tiêu viết chương trình sao cho đơn giản (miễn chạy ra kết quả đúng là được), sau đó khi tối ưu chương trình, ta xem lại những chỗ nào viết chưa tốt thì tối ưu lại những mã lệnh để chương trình ngắn gọn hơn, chạy nhanh hơn.  Không nên viết tới đâu tối ưu mã đến đó (bởi chương trình có mã tối ưu thường phức tạp và khó kiểm soát). - Việc tối ưu chương trình nên dựa theo 4 tiêu chuẩn chính sau:  Tính tin cậy Chương trình phải chạy đúng như dự định, mô tả đúng một giải thuật đúng. Thông thường khi viết chương trình, ta luôn có thói quen kiểm tra tính đúng đắn của các bước mỗi khi có thể.  Tính uyển chuyển Chương trình phải dễ sửa lỗi. Vì ít chương trình nào viết ra mà hoàn hảo ngay được mà vẫn cần phải sửa đổi lại. Chương trình viết dễ sửa đổi sẽ làm giảm bớt công sức của lập trình viên khi phát triển chương trình.  Tính trong sáng Chương trình viết ra đễ đọc, dễ hiểu. Để sau một thời gian dài khi đọc lại còn hiểu mình làm cái gì? . Để nếu có điều kiện thì còn có thể sửa sai (nếu phát hiện lỗi mới), cải tiến hay biến đổi để được chương trình giải quyết bài toán khác. Tính trong sáng của chương trình phụ thuộc rất nhiều vào công cụ lập trình và phong cách lập trình.  Tính hữu hiệu Chương trình phải chạy nhanh và ít tốn bộ nhớ (tiết kiệm được cả không gian và thời gian). Để có một chương trình hữu hiệu, cần phải có một giải thuật tốt và những tiểu xảo khi lập trình. Tuy nhiên, việc áp dụng quá nhiều tiểu xảo có thể khiến chương trình trở nên rối rắm, khó hiểu khi sửa đổi. Tiêu chuẩn hữu hiệu nên dừng ở mức chấp nhận được, không quan trọng bằng 3 tiêu chuẩn trên. Vì phần cứng phát triển rất nhanh, yêu cầu hữu hiệu không phải đặt ra gánh nặng. GV: Nguyễn Huỳnh Thanh Trang 12
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY => Từ những phân tích trên, chúng ta thấy rằng việc làm ra một chương trình phải trải qua rất nhiều công đoạn và tiêu tốn khá nhiều công sức. Chỉ một công đoạn không hợp lý sẽ tăng chi phí viết chương trình. Tóm lại: Sau khi viết xong chương trình thì chương trình vẫn còn có thể có nhiều lỗi khác chưa phát hiện được nên có thể không cho kết quả đúng. Vì vậy cần phải thử chương trình bằng cách thực hiện nó với một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bài toán và bằng cách nào đó ta đã biết trước Output. Các bộ Input và Output tương ứng này được gọi là các test. Nếu có sai sót ta phải sửa chương trình rồi thử lại. Quá trình này được gọi là hiệu chỉnh. Nếu kết quả hiệu chỉnh cho thấy ngôn ngữ lập trình hoặc thuật toán không phù hợp, thậm chí ta phải quay lại lựa chọn hay thiết kế thuật toán. Ví dụ: Để kiểm chứng tính đúng đắn của chương trình giải phương trình bậc hai: ax2 + bx + c = 0 (a ≠ 0) ; Ta có thể sử dụng ba bộ Input khác nhau:  Biệt số ∆ > 0 : a = 1, b = - 5, c = 6 (chương trình đưa ra hai nghiệm)  Biệt số ∆ = 0 : a = 1, b = - 4, c = 4 (chương trình đưa ra một nghiệm)  Biệt số ∆ < 0 : a = 1, b = 4, c = 8 (chương trình đưa ra thông báo phương trình vô nghiệm) Bước 5: Viết tài liệu Viết tài liệu là bước cuối cùng của quá trình triển khai, thực hiện kết quả đạt được của bài toán giải trên máy tính. Ở thời điểm hiện nay máy tính đã trở thành công cụ không thể thiếu để phục vụ công việc viết tài liệu. Với các ý tưởng, dữ liệu, thông tin đã tích lũy được và sắp xếp, phát triển đầy đủ trong bài viết. Tài liệu phải mô tả bài toán, thuật toán, thiết kế chương trình, kết quả thử nghiệm và hướng dẫn sử dụng. Khi viết một tài liệu hay thì sẽ rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm. Các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả. GV: Nguyễn Huỳnh Thanh Trang 13
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY iii.hieäu quaû cuûa ñeà taøi Lời đầu tiên tôi xin chân thành cám ơn các cấp lảnh đạo, đặc biệt là Ban giám hiệu nhà truờng cùng các thầy cô trong hội đồng sư phạm đã tận tình giúp đỡ, hướng dẫn, góp ý chân tình để cho tôi hoàn thành đề 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”. Sau khi thực hiện đề tài này tại trường trung học phổ thông Sông Ray . Qua từng tiết học tôi đã vận dụng các bước trên, kết hợp cả lý thuyết lẫn thực hành cho học sinh thực hiện và thấy rất khả quan và từ những bước trên dần hình thành giúp cho học sinh có khả năng tự mình giải một bài toán trên máy tính. Từ đó giúp học sinh tích cực hơn trong học tập, tự làm chủ lấy bản thân đồng thời cũng có thể tự mình lên kế hoạch để định hướng ngành nghề của mình sau này. Từ năm học 2006 bộ môn tin học mới bắt đầu chính thức đưa vào bậc trung học phổ thông và cũng từ đó tôi đã thực hiện phương pháp này và thấy có những hiệu quả rõ rệt. Để minh chứng tôi đưa ra số liệu thống kê của những lớp tôi dạy trong những năm qua như sau: Năm học Lớp Sĩ số Giỏi Khá Trung bình Yếu 10A 2 50 15(30%) 26(18%) 9(18%) 0(0%) 10A 5 49 11(22.4%) 30(61.2%) 8(16.4%) 0(0%) 10A 6 51 21(41.2%) 23(45.1%) 7(13.7%) 0(0%) 2006 – 2007 10B 1 48 4(8.3%) 12(25%) 27(56.3%) 5(0.4%) 10B 3 47 2(4.3%) 19(40.3%) 24(51.1%) 2(4.3%) 10B 4 47 0(0%) 27(57.4%) 18(38.3%) 2(7.3%) 10C 1 52 4(7.7%) 36(69.2%) 11(21.1%) 1(2%) 10A 1 44 5(11.4%) 29(66%) 10(22.6%) 0(0%) 10A 2 46 8(17%) 29(63%) 9(20%) 0(0%) 2007 – 2008 10A 3 47 7(15%) 30(64%) 10(21%) 0(0%) 11B 3 42 1(2%) 14(33%) 27(65%) 0(0%) 11B 4 43 0(0%) 9(21%) 31(72%) 3(7%) GV: Nguyễn Huỳnh Thanh Trang 14
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY 10A 1 46 8(17%) 29(63%) 9(20%) 0(0%) 10A 2 48 4(8.3%) 12(25%) 27(56.3%) 5(0.4%) 11A 1 51 21(41.2%) 23(45.1%) 7(13.7%) 0(0%) 2008 – 2009 11A 2 50 15(30%) 26(18%) 9(18%) 0(0%) 12A 1 47 7(15%) 30(64%) 10(21%) 0(0%) 12A 2 49 11(22.4%) 30(61.2%) 8(16.4%) 0(0%) 11B 6 43 0(0%) 9(21%) 31(72%) 3(7%) 11B 7 42 1(2%) 14(33%) 27(65%) 0(0%) 12A 1 44 5(11.4%) 29(66%) 10(22.6%) 0(0%) 12A 2 47 7(15%) 30(64%)2 10(21%) 0(0%) 12A 3 46 8(17%) 9(63%) 9(20%) 0(0%) 2009 – 2010 12A 4 47 2(4.3%) 19(40.3%) 24(51.1%) 2(4.3% 12A 5 44 5(11.4%) 29(66%) 10(22.6%) 0(0%) 12B 8 43 0(0%) 9(21%) 31(72%) 3(7%) 12B 9 44 2(4.5%) 23(52.3%) 19(43.2%) 0(0%) 12B 10 44 0(0%) 7(16%) 37(84%) 0(0%) 10c13 43 0(0%) 9(21%) 31(72%) 3(7%) 10c14 46 8(17%) 9(63%) 9(20%) 0(0%) 10c15 44 5(11.4%) 29(66%) 10(22.6%) 0(0%) 10c16 33 0(0%) 7(21.2%) 25(75.8%) 1(3%) 12a 4 41 8(19.5%) 19(46.3%) 14(34.2) 0(0%) 2010- 2011 12a 5 42 1(2%) 14(33%) 27(65%) 0(0%) 12a 13 47 0(0%) 27(57.4%) 18(38.3%) 2(7.3%) 12a 14 44 0(0%) 7(16%) 37(84%) 0(0%) 12a 15 44 2(4.5%) 23(52.3%) 19(43.2%) 0(0%) iv. ñeà xuaát , khuyeán nghò khaû naêng aùp duïng GV: Nguyễn Huỳnh Thanh Trang 15
ĐƠN VỊ: TRƯỜNG THPT SÔNG RAY Để góp phần tích cực, quan trọng trong việc nâng cao chất lượng giáo dục bộ môn tin học và được sự chỉ đạo hỗ trợ tích cực của Ban giám hiệu và của tổ chuyên môn nên sau khi thực hiện nghiên cứu đề 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” và bước đầu ứng dụng như đã trình bày ở trên nên tôi có một số đề xuất và khuyến nghị các cấp lảnh đạo tiếp tục mở rộng việc phổ biến và hướng dẫn thực hiện. v. taøi lieäu tham khaûo 1. Hồ Sĩ Đàm- Sách giáo viên tin học 10, 11,12 NXB Giáo Dục 2. Hồ Sĩ Đàm - Sách giáo khoa tin học 10,11,12 . NXB Giáo Dục 3. Hồ Sĩ Đàm - Sách bài tập tin học 11 . NXB Giáo Dục . 4. Hướng dẫn thực hiện chuẩn kiến thức, kỹ năng môn tin học THPT. NXB Giáo Dục. 5. Nguyễn Xuân Huy – Thuật toán. NXB thống kê, Hà Nội 1988 6. Bồi dưỡng giáo viên : Giáo dục tin học – NXB Hà Nội 1993 Đồng Nai, ngày 15 tháng 05 năm 2012 Người Thực Hiện Nguyễn Huỳnh Thanh Trang GV: Nguyễn Huỳnh Thanh Trang 16