Sáng kiến kinh nghiệm Phương pháp tổng quát để giải một bài toán bằng máy tính

 Trường THPT Lý Thường Kiệt
 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
 1. 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.
 2. 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. 
 3. 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.
 4. 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.
GV : Đào Minh Đạt Trường THPT Lý Thường Kiệt
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ử
GV : Đào Minh Đạt Trường THPT Lý Thường Kiệt
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
GV : Đào Minh Đạt Trường THPT Lý Thường Kiệ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])
GV : Đào Minh Đạt Trường THPT Lý Thường Kiệt
-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ư 
GV : Đào Minh Đạt