Phương pháp tổng quát để giải bài toán bằng máy tính

PHƯƠNG PHÁP TỔNG QUÁT ĐỂ GIẢI BÀI TOÁN BẰNG MÁY TÍNH PHẦN I: MỞ ĐẦU Bối cảnh của đề tài : Tin học là một môn khoa học mới, muốn học giỏi tin học đòi hỏi phải học giỏi các bộ môn khoa học khác như: toán, lý, hoá, anh văn.... Tin học sử dụng kiến thức của các bộ môn khoa học đó làm công cụ để nghiên cứu. Muốn giải quyết được các bài tập tin học không chỉ có những kiến thức đó mà còn phải có kiến thức về tin học. Đặc biệt đối với các bài tập khó cần phải có một phương pháp tổng quát để giải. Phương pháp tổng quát để giải bài toán tin học là một hệ thống các bước có tính ổn định nhằm giúp người học có thể tìm ra thuật giải, biễu diễn được dữ liệu và từ đó viết được chương trình. Lý do chọn đề tài : Qua thực tế công việc giảng dạy tin học ở trường THPT Lý Thường Kiệt, tôi thấy học sinh học tin học còn yếu, chưa biết cách học viết chương trình, thậm chí có em còn tìm cách học thuộc lòng các chương trình mẫu của giáo viên. Nguyên nhân chính dẫn đến điều đó là do các em đều chưa ý thức được thứ tự các bước để hình thành nên chương trình. Từ những thực tế trên, kết hợp với quá trình giảng dạy và nghiên cứu một số sách tham khảo, bản thân tôi xin trình bày một số kinh nghiệm về phương pháp giải các bài toán trong tin học ở phổ thông. Phạm vi và đối tượng nghiên cứu : Học sinh lớp 10 bắt đầu làm quen với giải thuật, thuật toán, và học cách tìm ra phương pháp giải bài toán trên máy tính. Mục đích nghiên cứu : Giúp cho học sinh hiểu và xác định được thứ tự để giải bài toán trên máy tính và thực hiện qua những bước sau : Bước 1: Xác định bài toán Bước 2: Lựa chọn hoặc thiết kế thuật toán. Bước 3: Viết chương trình Bước 4: Hiệu chỉnh CT Bước 5: Viết tài liệu. Với khuôn khổ của đề tài, thời gian và kiến thức của bản thân còn hạn chế đề tài sẽ không tránh khỏi những thiếu sót. Bản thân tôi rất mong được các ý kiến đóng góp xây dựng quý báu của đồng nghiệp để đề tài không ngừng được hoàn thiện, từ đó có thể áp dụng và phổ biến rộng rãi. Tôi xin chân thành cảm ơn. PHẦN II: NỘI DUNG Phương pháp tổng quát để giải bài toán tin học bao gồm các bước sau: I/ XÁC ĐỊNH BÀI TOÁN 1/Khái niệm bài toán Trong quá trình tồn tại và phát triển, mọi cá nhân luôn phải giải quyết các bài toán. Cuộc sống là một chuổi các bài toán mà ta phải đối đầu để giải quyết. Theo nhiều nhà nghiên cứu thì mọi bài toán đều có thể diễn đạt theo một sơ đồ chung A B Trong đó: A là giả thiết, điều kiện ban đầu hoặc là cái đã cho, đã có khi bắt đầu giải bài toán. B là kết luận, mục tiêu cần đạt hoặc là cái phải tìm, phải làm ra khi kết thúc bài toán Là suy luận, giải pháp cần xác định hoặc là một chuỗi các thao tác cần thực hiện, cần thi hành để có được cái phải tìm B từ cái đã có A 2/Xác định bài toán Theo sơ đồ trên thì xác định bài toán có nghĩa là xác định A, B và nếu có thể được thì xác định luôn các thao tác được phép sử dụng để đi từ A đến B (Điều này rất quan trọng nhưng thường lại được hiểu ngầm). 3/Bài toán trên máy tính Một bài toán trên máy tính cũng mang đầy đủ các tính chất của một bài toán tổng quát nhưng được diễn đạt theo một cách khác A: gọi là INPUT (thông tin vào) B: gọi là OUTPUT (thông tin ra) : gọi là chương trình được tạo từ các câu lệnh cơ bản của máy cho phép biến A thành B. 4/Các khó khăn thường gặp Để xác định một bài toán trên máy tính ta thường gặp hai khó khăn: +Thông tin về A, B không đầy đủ rõ ràng. +Thông báo về các điều kiện đặt ra cho cách giải thường không được nêu ra một cách minh bạch. 5/Ví dụ minh hoạ a/Bài toán 1: tám quân hậu Hãy tìm cách đặt 8 quân hậu trên một bàn cờ vua sao cho không có quân hậu nào có thể ăn quân hậu khác. Xác định thông tin vào: -Bàn cờ vua là bảng hình vuông gồm 8 hàng 8 cột -Quân hậu có thể ăn được bất kỳ quân nào nằm trên cùng một hàng, cùng một cột, hay cùng một đường chéo. -Có tất cả 8 quân hậu Xác định thông tin ra: -Các bảng hình vuông trên đó có đánh dấu vị trí của 8 quân hậu sao cho không có quân hậu nào có thể ăn quân hậu khác. Nghĩa là trên mỗi hàng, mỗi cột, mỗi đường chéo chỉ có thể có một quân hậu. -Chỉ ra tất cả các bảng vuông khác nhau thoả mãn điều kiện của bài ra. Xác định các thao tác -Lần lượt xác định vị trí của một trong 8 quân hậu trên bàn cờ. -Đặt đủ 8 quân. -Tất cả các quân hậu đều phải thoả mãn đIũu kiện đã nêu b/Bài toán 2: (Mã đi tuần) Cho một bàn cờ kích thước n*n (n>3). Một quân mã di chuyển theo luật cờ vua được đặt tại một ô có toạ độ (x,y). Hãy tìm một đường đi sao cho mọi ô trên bàn cờ đều được mã nhảy đến đúng một lần. Xác định thông tin vào -Một bảng vuông kích thước n*n -Toạ độ vị trí thứ nhất của quân mã. -Tám nước đi có thể của quân mã Xác định thông tin ra -Một bảng hình vuông trên đó có đánh dấu vị trí theo thứ tự từ 1 đến n*n của quân mã. -Từ vị trí K đến vị trí K+1 phải theo đúng luật đi của quân mã Xác định các thao tác chế biến thông tin: -Lần lượt xác định các vị trí của quân mã từ 2 đến n*n sao cho quân mã di chuyển đúng luật và mỗi ô chỉ đi đúng một lần. c/Bài toán 3: Cho một dãy số nguyên dương a1,a2,...,an. Hãy tìm từ dãy trên một dãy con (không nhất thiết liên tục) tăng và có độ dài là dài nhất. Xác định thông tin vào -Một dãy số nguyên dương a1, a2, a3, ..., an -Mỗi số được xác định bởi hai yếu tố: Giá trị và chỉ số. Xác định thông tin ra: -Một dãy con lấy từ dãy đã cho -Dãy con phải có hai tính chất: Tăng và dài nhất Xác định các thao tác -Lần lượt duyệt các phần tử -Quyết định loại bỏ phần tử nào để dãy còn lại là tăng và dài nhất d/ Bài toán 4: Cho hai số tự nhiên a,b. Tìm USCLN của chúng Xác định thông tin vào -Hai số tự nhiên a, b Xác định thông tin ra Số tự nhiên d thoả mãn d là ước của a và d là ước của b và d là lớn nhất trong tập ước chung đó. Xác định các thao tác chế biến thông tin -Xây dựng một tập hữu hạn các phép tính cho phép tính được d từ a và b 6/Một số nhận xét quan trọng -Việc xác định bài toán rất quan trọng, ảnh hưởng đến cách thức và chất lượng của việc giải quyết bài toán. -Một bài toán cho dù được diễn đạt bằng thông báo chính xác đến đâu đi chăng nữa cũng phải giả định là phần lớn thông tin về A, B đều tiềm ẩn trong đầu người giải. Thông báo về A hoặc B chỉ là biểu tượng gợi nhớ đến các thông tin tiềm ẩn đó. -Bước đầu tiên để xác định một bài toán là phải phát biểu lại bài toán một cách chính xác theo ngôn ngữ riêng mình vì đó là cách ta tiếp cận bài toán, hiểu bài toán. -Bước kế tiếp là tìm hiểu các thông tin input và output và mối liên hệ giữa chúng. -Nên xét một vài trường hợp cụ thể, từ đó hiểu được bài toán. Qua đó thấy rõ được các thao tác cần phải tiến hành. II/TÌM CẤU TRÚC DỮ LIỆU BIỄU DIỄN BÀI TOÁN 1/Khái niệm ban đầu Máy tính điện tử được phát minh như một thiết bị nhằm làm dễ dàng và tiến hành nhanh các tính toán phức tạp và lớn. Trong nhiều ứng dụng, khả năng lưu trữ và truy cập lượng thông tin lớn giữ vai trò quan trọng và được xem như là đặc trưng chính của nó, và khả năng tính toán trở thành ít quan trọng trong nhiều trường hợp. Trong thực tế, thông tin cần xữ lý là trừu tượng. Thông tin cung cấp cho máy gồm một tập hợp dữ liệu về bối cảnh thực đã được mã hoá. Nói rõ hơn tập hợp này được xem như thích đáng cho vấn đề định sẵn. Từ đó có thể đưa và máy tính và tính ra kết quả cần tìm. -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 chon này tuỳ thuộc vào vấn đề phải giải quyết. Sau đó là chọn cách biểu diễn thông tin. Việc này tuỳ thuộc vào các thao tác thực hiện trên kiểu dữ liệu. Ví dụ: -Nếu chỉ cần thao tác cộng thì cách tốt nhất để biểu diễn một số nguyên là n que hoặc dùng số La mã. Quy tắc cộng với sự biểu diễn này là khá đơn giản và tự nhiên trong khi đó phép biểu diễn dùng số ả rập đòi hỏi các quy tắc ít hiển nhiên hơn. -Tuy nhiên, trường hợp trên bị đảo ngược khi ta xét đến việc công các số lớn hoặc chỉ xét đến phép nhân hoặc phép chia. Việc phân tích các thao tác trên thành các thao tác đơn giản được thực hiện dễ dàng trong phép biểu diễn bằng số ả rập mà nguyên tắc dựa trên vị trí chữ số. -Mọi người đều biết là máy tính điện tử biểu diễn các dữ liệu bằng các chữ số nhị phân. Phép biểu diễn này ít thích hợp cho con người vì cần khá nhiều bít song nó lại thích hợp cho các loại mạch điện tử vì hai giá trị 0 và 1 có thể được biểu diễn một cách dễ dàng và tin cậy được với sự có hay vắng mặt của dòng điện, từ trường hoặc điện tích. 2/Cấu trúc dữ liệu thường dùng a/Kiểu đơn giản -Kiểu cơ bản: +BOOLEAN +INTEGER +REAL +CHAR -Kiểu người sử dụng định nghĩa +SUB RANGE +ENUMERATED b/Kiểu có cấu trúc +ARRAY +SET +RECORD +STRING +FILE Trong đó: -BOOLEAN: Là kiểu logic, là tập hợp có hai giá trị là TRUE hoặc FALSE -INTEGER: Kiểu số nguyên, là tập hpựo các giá rị nguyên từ -32768 đến 32767 -REAL: Kiểu số thực, là tập hợp các giá trị từ –2.9*10(39) đến 1.7*10(38) -CHAR: Kiểu ký tự, là tập hợp các ký tự ‘a’-‘z’,’0’-‘9’ và các ký tự đặc biệt khác -SUB RANGE: Kiểu miền con của một kiểu sơ cấp. Ví dụ: TYPE Tuoi=0..120 -ENUMERATED: Kiểu liệt kê được định nghiã bằng cách liệt kê tất cả các phần tử có thể có Ví dụ: TYPE thu=(Chủ nhật, hai, ba, tư, năm, sáu, bảy) -ARRAY: Kiểu mảng gồm một tập hợp các phần tử cùng thuộc một kiểu dữ liệu cơ sở được xác định bởi chỉ số Ví dụ: TYPE MMC=array[1..100] of integer; -RECORD: Kiểu bản ghi, gồm một tập hợp các phần tử thuộc các kiểu dữ liệu khác nhau. Vídụ: TYPE Hocsinh=record Hoten:string; Lop:1..12; Truong: string; DTB: real; END; -SET: Kiểu tập hợp gồm một số các đối tượng có cùng kiểu cơ sở. Ví dụ: TYPE Chucai=set of char; Chuso=set of 0..9; -STRING: Kiểu chuổi, gồm một dãy các ký tự. -FILE: Kiểu tệp, gồm một tập hợp các dữ liệu có liên quan với nhau và có cùng kiểu được nhóm lại thành một dãy và đưọc lưu trữ trên đĩa. Ví dụ TYPE Tep=file of integer; Bai=text; 3/Các lưu ý khi chọn cấu trúc dữ liệu Khi lựa chọn cấu trúc dữ liệu để biểu diễn một bài toán ta nên dựa vào các tiêu chuẩn sau đây: -Cấu trúc dữ liệu 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 phù hợp với điều kiện cho phép của ngôn ngữ lập trình mà MTĐT đang sử dụng. 4/Các ví dụ a/Bài toán 1: (Bài toán tám con hậu) -Bàn cờ là một bảng vuông 8*8, nên rõ ràng cấu trúc mảng là thích hợp để biểu diễn. -Theo luật cờ vua, một quân hậu ăn được mọi quân khác nằm cùng hàng, hoặc cùng cột hoặc cùng đường chéo trên bàn cờ. Vậy ta suy ra mỗi cột có thể chứa một và chỉ một quân hậu. Do đó, để đơn giản ta ký hiệu quân hậu ở cột i là i. Như vậy tham biến i trở thành chỉ số cột và việc lựa chọn được tiến hành trên tám giá trị của chỉ số hàng j. -Để tìm dữ liệu biểu diễn tám quân hậu trên bàn cờ, cách chọn thoạt tiên là dùng mảng vuông để biểu diễn bàn cờ, nhưng xem kỹ thấy cách biểu diễn đó dẫn tới thao tác cồng kềnh trong việc thử quyền sử dụng các quân hậu ở các vị trí. Điều đó hết sức không hay vì thao tác trên lại phải thực hiện nhiều lần. Do đó ta sẽ chọn cách biểu diễn sao cho thao tác trên dễ bao nhiêu hay bấy nhiêu. Cách tốt nhất là biểu diễn các thông tin thực sự nổi bật và được sử dụng một cách càng trực tiếp càng tốt. Trong trường hợp cả bài toán này thì đó không phải là vị trí các quân hậu mà là phải chăng đã có một quân hậu trên mỗi hàng và các đường chéo (Ta đã biết rằng đúng một quân hậu đã được đặt trên mỗi cột k với 1<=k<=I). Điều đó dẫn tới cách chọn các biến như sau: Var X:array[1..8] of integer; A: array[1..8] of boolean; B: array[b1..b2] of boolean; C: array[c1..c2] of boolean; Trong đó: X[I] biểu diễn vị trí quân hậu trong cột thứ i. a[j]=true có nghĩa là không có quân hậu nào nằm trên hàng j. b[k]=true có nghĩa là không có quân hậu nào nằm trên đường chéo c[k]=true có nghĩa là không có quân hậu nào nằm trên đường chéo Các chỉ số của b và c đều tính được, do đó việc chọn các giới hạn chỉ số b1, b2, c1, c2 cũng được quyết định theo. Ta lưu ý rằng trên một đường chéo thì mọi ô đều có cùng tổng số các toạ độ i+j và trên một đường chéo thì hiệu số toạ độ i-j là không đổi. Với cách chọn cấu trúc dữ liệu biểu diễn bài toán như trên thì: Câu lệnh đặt quân hậu sẽ như sau: X[i]:=j; A[j]:=false; B[i+j]:=false; C[i-j]:=false; Câu lệnh cất quan hậu sẽ là A[j]:=true; B[i+j]:=true; C[i-j]:=true; Điều kiện an toàn của ô (i,j) có thể đặt quân hậu được biểu diễn bởi biểu thức logic (A[j]) and (B[i+j]) and (c[i-j]) III/TÌM THUẬT TOÁN 1/Khái niệm thuật toán 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 các thao tác trên một dãy các đối tượng sao cho sau một hữu hạn các bước thực hiện các thao tác, ta đạt được mục tiêu định trước. 2/Các đặc trưng của thuật toán -Tính xác định. -Tính hữu hạn dừng. -Tính đúng đắn. -Tính phổ dụng. -Tính hiệu quả. -Có đại lượng vào ra. 3/Mở rộng khái niệm thuật toán Để có thể giải các bài toán bằng máy tính, ta phải có một quan niệm rộng hơn về thuật toán. Cụ thể là cần lưu ý đến các đặc điểm sau: -Không cần xác định toàn bộ lời giải, các thao tác theo từng bước một cách chính xác và rõ ràng. -Có nhiều bài toán không có cách giải đúng, hoặc không thể chấp nhận được do hạn chế về thời gian. Nhưng nếu chấp nhận kết quả gần đúng thì có thể tồn tại nhiều cách giải hiệu quả hơn. IV/ LẬP TRÌNH 1/Khái niệm: Lập trình là dùng một ngôn ngữ cụ thể nào đó để diễn tả thuật toán, cấu trúc dữ liệu thành các câu lệnh để máy tính có thể thực hiện được và giải quyết đúng bài toán mà người lập trình mong muốn. 2/Kỷ năng lập trình: Là kỷ năng cài đặt thành công các thuật toán bằng một ngôn ngữ lập trình. Kỷ năng này chỉ có thể có được thông qua rèn luyện tích cực. Kinh nghiệm cho thấy, một thuật toán hay nhưng cài đặt vụng về khi chạy máy có thể cho kết quả rất tồi tệ. 3/Phát triển chương trình bằng cách tinh chế từng bước: Tinh chế từng bước là phương pháp khoa học có hệ thống giúp ta phân tích các thuật toán, cấu trúc dữ liệu từ đó viết thành chương trình. -Bước 1: Chương trình được viết bằng lời tự nhiên. -ở các bước sau: Mỗi câu được phân tích chi tiết hơn. -Ta nói ở mỗi bước ta đã tinh chế những ý đó. Sự tinh chế luôn hướng về ngôn ngữ lập trình. -Mỗi câu lời tự nhiên nếu đơn giản thì thay bằng một vài câu lệnh, nếu phức tạp thì coi là một chương trình con. -Trong quá trình tinh chế, ta phải đưa ra biễu diễn dữ liệu. Như vậy cùng với tinh chế cộng việc, dữ liệu cũng được tinh chế -Hiểu được tinh chế từng bước sẽ giúp người lập trình có được định hướng, tránh được sự mò mẫm. V/CHẠY THỬ, THAY ĐỔI KIỂM TRA CHƯƠNG TRÌNH . 1/Chạy thử: Một chương trình đã viết chưa chắc đã chạy được trên máy để cho kết quả mong muốn vì vậy đòi hỏi phải chạy thử chương trình. Kỷ năng tìm lỗi, sửa lỗi, điều chỉnh cũng là một kỷ năng của người lập trình. 2/Phân loại lỗi và cách sửa chữa: Có ba loại lỗi -Lỗi về thuật toán -Lỗi về trình tự -Lỗi về cú pháp. 3/Xây dựng các bộ test Hầu hết các chương trình rất khó kiểm tra tính đúng đắn. Để khắc phục ta nên xây dựng nhiều bộ test để thử. Khi xây dựng bộ test cần lưu ý: -Nên khởi đầu bằng các bộ test nhỏ nhưng chứa các giá trị đặc biệt -Làm nhiều bộ test nhưng đa dạng. -Phải có các bộ test có kích thước lớn. Lưu ý: Chương trình chạy qua một số bộ test chưa hẳn là chương trình đúng. Nếu được, nên tìm cách chứng minh tính đúng đắn của chương trình. 4/Thay đổi chương trình Một chương trình đã viết xong, đã chạy tốt chưa hẳn là quá trình lập trình đã kết thúc. Ta phải sửa đổi nó theo một hướng nào đó để đáp ứng yêu cầu mới. Phương pháp tinh chế từng bước giúp ta thuận lợi trong việc sửa đổi chương trình. PHẦN III: KẾT LUẬN Trong hầu hết các sách tin học đều có bài tập rèn luyên kỷ năng lập trình. Đối với các bài tập dễ ta có thể viết nhanh được chương trình đúng nhưng đối với các bài tập khó cần phải có một phương pháp tổng quát, bắt buộc người học phải theo các bước trong phương pháp mới có thể giải nhanh giải đúng các bài toán đó. Vì vây, giáo viên khi dạy lập trình cho học sinh cần phải trang bị cho học sinh phương pháp tổng quát này và xem đây là điều kiện tất yếu để hoàn thành nhanh và đúng cho mọi chương trình. Trong quá trình giảng dạy , đối với những học sinh chịu khó vận dụng phương pháp học tập mà tôi đã hướng dẫn , các em có tiến bộ rõ rệt. Các em đã có chuyển biến trong học tập, các em đã hiểu và vận dụng được các bài tập vào các tình huống thực tế mà các em gặp, ngoài ra các em còn nâng cao đươc khả năng sử dụng máy tính, ứng dụng được công cụ máy tính vào thực tế, các em không còn cảm thấy e ngại khi sử dụng máy tính mà xem máy tính như một công cụ hỗ trợ học tập. Từ đó kết quả ở học kỳ II có tiến bộ rất nhiều so với học kỳ I Cụ thể * Lớp 10C1 : Học kỳ I : có 20 hs có điểm bình quân dưới 6 Học kỳ II : chỉ còn 10 hs có điểm bình quân dưới 6, Cả năm : còn 5 hs có điểm bình quân dưới 6 * Lớp 10C4 : Học kỳ I : có 16 hs có điểm bình quân dưới 7 Học kỳ II : chỉ còn 5 hs có điểm bình quân dưới 7 Cả năm : còn 2 hs có điểm bình quân dưới 5 Ngày Tháng Năm Họ tên và chữ ký Đào Minh Đạt