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.
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
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.

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
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
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

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
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
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

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ễ
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
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

-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.
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
-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

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à
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
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

-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.
GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt
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.

GV : Đào Minh Đạt
Trường THPT Lý Thường Kiệt

Họ tên và chữ ký
Đào Minh Đạt
GV : Đào Minh Đạt