BÀI 6. GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Các bước để giải một bài toán trên máy tính
- Xác định bài toán
- Lựa chọn hoặc thiết kế thuật toán
- Viết chương trình
- Hiệu chỉnh
- Viết tài liệu.
1. Xác định bài toán
- Là xác định rõ 2 thành phần Input và Output và mối quan hệ giữa chúng để có thể lựa chọn thuật toán và ngôn ngữ lập trình thích hợp.
2. Lựa chọn hoặc thiết kế thuật toán
a. Lựa chọn thuật toán:
- Là bước quan trọng nhất để giải bài toán.
- Có thể có nhiều thuật toán để giải một bài toán, cần thiết kế hoặc chọn 1 thuật toán phù hợp để giải bài toán cho trước.
b. Diễn tả thuật toán
VD: Tìm UCLN [M,N]
- Xác định bài toán
- Input: cho M, N
- Output: UCLN [M,N]
- Ý tưởng:
- Nếu M=N thì UCLN [M]
- Nếu M>N thì M\[\leftarrow\]M-N
- Nếu MN thì M \[\leftarrow\] M - N rồi quay lại B2;
- B4: N \[\leftarrow\] N – M rồi quay lại B2;
- B5: Đưa ra kết quả UCLN rồi kết thúc.
3. Viết chương trình
- Là việc lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán.
- Khi chọn ngôn ngữ lập trình nào phải tuân theo quy định ngữ pháp của ngôn ngữ đó.
4. Hiệu chỉnh
- Sau khi viết xong, chương trình cần phải được thử bằng một số Input tiêu biểu. Nếu phát hiện sai sót thì phải sửa chương trình rồi thử lại.
5. Viết tài liệu
- Tài liệu phải mô tả chi tiế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. Từ tài liệu này, người sử dụng đề xuất các khả năng hoàn thiện thêm.
* Các bước để giải một bài toán trên máy tính:
+ Xác định bài toán
+ Lựa chọn hoặc thiết kế thuật toán
+ Viết chương trình
+ Hiệu chỉnh
+ Viết tài liệu.
1. Xác định bài toán :
- Là xác định rõ 2 thành phần Input và Output và mối quan hệ giữa chúng để có thể lựa chọn thuật toán và ngôn ngữ lập trình thích hợp.
2. Lựa chọn hoặc thiết kế thuật toán:
a. Lựa chọn thuật toán:
- Là bước quan trọng nhất để giải bài toán.
- Có thể có nhiều thuật toán để giải một bài toán, cần thiết kế hoặc chọn 1 thuật toán phù hợp để giải bài toán cho trước.
b. Diễn tả thuật toán :
VD: Tìm UCLN [M,N]
- Xác định bài toán
+ Input: cho M,N
+ Output: UCLN [M,N]
- Ý tưởng:
+ Nếu M=N thì UCLN [M]
+ Nếu M>N thì M!M-N
+ Nếu M4->1>2->5
B.5->4->1->3>2
C.1->4->3->2->5
D.2->3->4->1->5
Trả lời :
Đáp án đúng: B
Việc giải toán trên máy tính thường được tiến qua 5 bước:
- Xác định bài toán
- Lựa chọn hoặc thiết kế thuật toán
- Viết chương trình
- Hiệu chỉnh
- Viết tài liệu
Cùng Top lời giải tìm hiểu kĩ hơn về 5 bước giải bài toán trên máy tính nhé.
Kiến thức tham khảo về 5 bước giải bài toán trên máy tính
1. Khái niệm bài toán
- Bài toán trong tin học được hiểu là một việc gì đó mà ta muốn máy tính thực hiện nhằm cho ra kết quả.
- Ví dụ như là tính diện tích hình chữ nhật, tìm ước chung lớn nhất của hai số nguyên dương, giải phương trình bậc nhất, quản lý nhân sự, quản lý tiền lương của nhân viên…
- Muốn giải một bài toán nào đó trên máy tính, trước tiên ta cần xác định được hai yếu tố cơ bản:
+ Đầu vào [Input]: đưa vào máy thông tin gì [các thông tin đã có]
+ Đầu ra [Output]: cần lấy ra thông tin gì [các thông tin cần tìm]
- Hay ta có thể hiểu một cách đơn giản những thông tin mà chúng ta đã biết thì gọi là input, còn những thông tin chúng ta cần tìm là output.
Ví dụ 1: Biết chiều rộng và chiều dài của hình chữ nhật. Tính diện tích hình chữ nhật
+ Input: chiều rộng, chiều dài
+ Output: diện tích
Ví dụ 2: Giải phương trình bậc nhất ax+b = 0
+ Input: Hệ số a, b [a khác 0]
+ Output: Nghiệm của phương trình
Ví dụ 3: Tìm ước chung lớn nhất của hai số nguyên dương
+ Input: a, b nguyên dương
+ Output: UCLN của a,b
Ví dụ 4: Xếp loại kết quả học tập của học sinh
+ Input: Bảng điểm của học sinh trong lớp
+ Output: Bảng xếp loại học lực
- Như vậy, khi muốn giải quết một bài toán thì điều đầu tiên chúng ta cần phải xác định được đầu vào [input] và đầu ra [output] của bài toán. Ta gọi chung việc xác định bài toán là xác định input và xác định output.
2. Các bướcgiải bài toán trên máy tính
a. Xác định bài toán
Ví dụ 1:Tìm ước chung lớn nhất [UCLN] của hai số nguyên dương M và N
- Input: M,N
- Output: UCLN[M,N]
Xác định bài toán là xác định rõ hai thành phần: Input ; Output;
b. Lựa chọn hoặc thiết kế thuật toán
Lựa chọn thuật toán
- Một bài toán có nhiều cách giải, do đó người ta lựa chọn thuật toán phù hợp nhất dựa trên các tiêu chí:
+ Thời gian thực hiện ngắn
+ Sử dụng ít ô nhớ
+ Thuật toán dễ hiểu, ít phức tạp
+ Tốn ít tài nguyên nhất có thể.
Diễn tả thuật toán
Ví dụ:Tìm ước chung lớn nhất [ƯCLN] của hai số nguyên dương M và N.
Xác định bài toán:
- Input: Nhập M, N
- Output: ƯCLN[M, N]
Ý tưởng:Sử dụng những điều đã biết sau:
- Nếu M = N thì giá trị chung đó là ƯCLN của M và N
- Nếu M > N thì ƯCLN[M, N] = ƯCLN[M – N,N]
- Nếu M < N thì ƯCLN[M, N] = ƯCLN[M,N- M]
Thuật toán
- Thuật toán diễn tả bằng cách liệt kê
+ Bước 1: Nhập M, N;
+ Bước 2: Nếu M = N đưa ra ƯCLN[M,N]=M; Kết thúc
+ Bước 3: Nếu M > N thì M ←M - N rồi quay lại bước 2;
+ Bước 4: N ←N - M rồi quay lại bước 2
- Thuật toán diễn tả bằng sơ đồ khối
Sau đây là hai ví dụ mô phỏng các bước thực hiện thuật toán trên:
c. Viết chương trình:
-Là việc lựa chọn cách tổ chức dữ liệu và sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán.
- Khi chọn ngôn ngữ lập trình nào phải tuân theo quy định ngữ pháp của ngôn ngữ đó.
d. Hiệu chỉnh
- Khái niệm: là việc thử chương trình với 1 số bộ Input tương ứng với Output đã biết trước, từ đó ta xác định được các lỗi của chương trình.
- Mỗi bộ Input – Output được gọi là các Test.
- Sau khi viết xong, chương trình cần phải được thử bằng một số Input tiêu biểu. Nếu phát hiện sai sót thì phải sửa chương trình rồi thử lại.
e. Viết tài liệu
- Tài liệu phải mô tả chi tiế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. Từ tài liệu này, người sử dụng đề xuất các khả năng hoàn thiện thêm.
Ví Dụ :Hãy viết thuật toán giải phương trình ax + b =0 và đề xuất các Test tiêu biểu
Lời giải:
- Bước 1: Nhập a,b và khởi tạo biến x.
- Bước 2: Nếu a # 0 thì thực hiện bước 3, nếu không quay về bước 1.
- Bước 3: x ← -b/a
- Bước 4: Thông báo x.
Input |
Output |
| 3 6 | -2 |
| 3 0 | 0 |
| 0 2 | |
| 3/4 3 | -4 |