Quy trình giải quyết một bài toán tin học

QUY TRÌNH GIẢI QUYẾT MỘT BÀI TOÁN TIN HỌC

Quy trình giải một bài toán tin học
Giải quyết một bài toán tin học thường được tiến hành theo các bước sau:

1. Đọc hiểu bài toán
2. Thiết kế thuật toán
3. Viết chương trình
4. Kiểm tra chương trình
5. Rà soát lại trước khi submit bài

1. Đọc hiểu bài toán
Giai đoạn đầu tiên là cần phải hiểu đúng yêu cầu bài toán. Chỉ cần hiểu sai, hiểu lầm một khái niệm trong bài toán có thể dẫn đến lời giải hoàn toàn sai. Đã hiểu sai bài toán rồi thì dù chúng ta bỏ công sức thiết kế thuật toán tối ưu cở nào, cẩn thận code từng dòng lệnh ra sao thì công sức ấy cũng là công "giã tràng xe cát biển đông"!

Ví dụ: Đề cho đường thẳng đi qua 2 điểm, nhưng khi đọc vì quá chú tâm đến 2 điểm nên có thể chúng ta lại nghĩ là đoạn thẳng.

Cho nên chúng ta nên cẩn trọng khi đọc đề bài toán. Giành thời gian để đọc hiểu từng đoạn văn yêu cần của bài toán. Cần suy ngẫm từ từ cho đến khi hiểu rõ các ngõ ngách của đề bài.

Một số bước để đọc hiểu đề bài toán có thể tóm tắt như sau:

1. Đọc từng câu, từng đoạn, để hiểu cơ bản bài toán
2. Đọc input và output của bài toán
3. Đọc lại từng câu, từng đoạn, hiểu rõ từng câu, từng đoạn của bài toán
4. Đọc input và output của bài toán, chú ý kích thước dữ liệu của bài toán
5. Giải các ví dụ trong đề bài để hiểu rõ thêm bài toán
6. Lấy thêm các ví dụ để hiểu rõ thêm bài toán

- Nếu vẫn chưa hiểu bài toán, thì đọc đi đọc lại để tìm những chổ chưa hiểu. Nếu vẫn chưa hiểu bài toán thì nên nghĩ ngơi một chút, rồi sau đó cứ đọc đi đọc lại cho đến khi nào hiểu bài toán.

Bài toán cần đọc lại nhiều lần để:
(1) Cảm giác thân thuộc với bài toán
(2) Mỗi lần đọc là một lần nghĩ khác đi một chút bài toán
(3) Phát hiện ra một số điều trước đây chưa nhìn ra


Tóm lại, đọc đề bài toán cần hết sức cẩn trọng, chưa hiểu đề, hiểu đề lơ mờ thì nhất quyết không giải bài toán đó.

2. Thiết kết thuật toán

Để thiết kế ra được thuật toán giải quyết bài toán, chúng ta cần phải tự mình giải trước các ví dụ của bài toán. Trong quá trình tự giải quyết các ví dụ, chúng ta sẽ dần dần hình thành hướng giải quyết bài toán. Từ đó đưa ra quy tắc từng bước giải quyết bài toán. Sau đó chúng ta cần kiểm nghiệm quy tắc này bằng cách áp dụng quy tắc đưa ra xem có thể giải các ví dụ được không.

Như vậy, chúng ta có thể đưa ra một số bước gợi ý để tìm lời giải của bài toán

1. Lấy từng ví dụ, từ nhỏ đến lớn. Giải các ví dụ bài toán theo như cách bài toán muốn định hướng chúng ta làm (không quan tâm có hiệu quả hay không mà chỉ quan tâm giải được)
2. Quan sát các nghiệm của bài toán: Bằng cách quan sát các nghiệm của bài toán, chúng ta có thể phát hiện ra quy luật của nghiệm, từ đó dẫn đến lời giải bài toán
3. Quan sát quá trình tự giải bài toán, có thể hình thành nên bộ quy tắc từng bước để giải bài toán
4. Tối ưu bộ quy tắc để có thể giải nhanh hơn
5. Thử sắp xếp dữ liệu xem có lợi thế gì không
6. Chú ý kích thước dữ liệu của bài toán để từ đó tinh chỉnh quy tắc giải bài toán
7. Thử phân loại bài toán này thuộc dạng phương pháp nào: chia để trị, tham lam, quy hoạch động, vét, sắp xếp, tìm kiếm nhị phân, tìm kiếm 2 con trỏ, tìm kiếm tam phân, BFS, Lý thuyết đồ thị, ...