Trong các bước giải bài toán trên máy tính những bước nào có thể lặp lại nhiều lần
|
Việc giải bài toán trên máy tính thường được tiến hành qua các bước sau: • Giải bài toán trên máy tính thường được tiến hành qua 5 bước - B1: xác định bài toán; - B2: lựa chọn hoặc thiết kế thuật toán; - B3: viết chương trình; - B4: hiệu chỉnh; - B5: viết tài liệu; 1. Xác định bài toán - Là quá trình xác định 2 thành phần: Input và Output và mối quan hệ giữa chúng. - Ví dụ: Tìm bội chung lớn nhất (BCNN) của hai số nguyên dương A và B + Input: A, B + Output: BCNN(A,B) 2. Lựa chọn hoặc thiết kế thuật toán a) 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ể. b) 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: 3. Viết chương trình - Viết chương trình là việc tổng hợp giữa 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. Ngôn ngữ lập trình + Thuật toán = Chương trình - Khi viết chương trình ta nên chọn một ngôn ngữ lập trình hoặc một phần mềm chuyên dụng thích hợp với thuật toán. - Viết chương trình trong ngôn ngữ nào thì phải tuân theo ngôn ngữ đó. - Chương trình dịch chỉ có thể phát hiện và thông báo về mặt ngữ pháp. 4. 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. 5. Viết tài liệu - Tài liệu dùng để: + mô tả bài toán, thuật toán; + thiết kế chương trình; + kết quả thử nghiệm; + hướng dẫn sử dụng. - Tài liệu này rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm. - Các bước có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả. Loigiaihay.com * 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 M - Xây dựng thuật toán + Liệt kê (sgk trang 48) + Sơ đồ khối (sgk trang 49) 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ả 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. Củng cố, dặn dò: - Các bước giải một bài toán trên máy tính. - Đặc điểm của mỗi bước giải bài toán trên máy tính. 
A. Lý thuyết • Giải bài toán trên máy tính trải qua 5 bước - B1: xác định bài toán - B2: lựa chọn hoặc thiết kế thuật toán - B3: viết chương trình - B4: hiệu chỉnh - B5: viết tài liệu 1. Xác định bài toán - Là quá trình xác định 2 thành phần: Input và Output và mối quan hệ giữa chúng. - Ví dụ: Tìm bội chung lớn nhất (BCNN) của hai số nguyên dương A và B + Input: A, B + Output: BCNN(A,B) 2. Lựa chọn hoặc thiết kế thuật toán a. 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ể. b. 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: 3. Viết chương trình - Viết chương trình là việc tổng hợp giữa 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. Ngôn ngữ lập trình + Thuật toán = Chương trình - Khi viết chương trình ta nên chọn một ngôn ngữ lập trình hoặc một phần mềm chuyên dụng thích hợp vơi thuật toán. - Viết chương trình trong ngôn ngữ nào thì phải tuân theo ngôn ngữ đó. - Chương trình dịch chỉ có thể phát hiện và thông báo về mặt ngữ pháp. 4. 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. 5. Viết tài liệu - Tài liệu dùng để: + mô tả bài toán, thuật toán + thiết kế chương trình + kết quả thử nghiệm + hướng dẫn sử dụng - Tài liệu này rất có ích cho người sử dụng chương trình và cho việc đề xuất những khả năng hoàn thiện thêm - Các bước có thể lập đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả B. Bài tập trắc nghiệm Câu 1: Các bước giải bài toán trên máy tính được tiến hành theo thứ tự nào sau đây: A. Xác định bài toán – Lựa chọn thuật toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu B. Xác định bài toán – Viết chương trình – Lựa chọn thuật toán – Viết tài liệu C. Lựa chọn thuật toán – Xác định bài toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu D. Viết chương trình – Hiệu chỉnh – Viết tài liệu Đáp án
Đáp án : A Giải thích : Các bước giải bài toán trên máy tính được tiến hành theo thứ tự: Xác định bài toán – Lựa chọn thuật toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu. Câu 2: Mỗi bài toán được đặc tả bởi mấy thành phần: A. 4 B. 3 C. 2 D. 1 Đáp án
Đáp án : C Giải thích : Mỗi bài toán được đặc tả bởi 2 thành phần là Input và Output. Câu 3: Viết chương trình là? A. Biểu diễn thuật toán B. Dùng ngôn ngữ lập trình để diễn đạt bài toán C. Dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả thuật toán D. Tất cả đều đúng Đáp án
Đáp án : C Giải thích : Viết chương trình là tổng hợp giữa việc dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả đúng thuật toán. Câu 4: Tiêu chuẩn lựa chọn thuật toán: A. Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép B. Độ phức tạp của thuật toán C. Các tài nguyên như thời gian thực hiện, số lượng ô nhớ... D. Cả 3 ý trên đều đúng Đáp án
Đáp án : D Giải thích : Khi lựa chọn thuật toán để giải một bài toán cụ thể cần căn cứ vào các tiêu chí sau: + Lượng tài nguyên thuật toán đòi hỏi và lượng tài nguyên cho phép + Độ phức tạp của thuật toán + Các tài nguyên như thời gian thực hiện, số lượng ô nhớ... Câu 5: Giải bài toán trên máy tính được tiến hành qua mấy bước? A. 3 B. 4 C. 5 D. 6 Đáp án
Đáp án : C Giải thích : Giải bài toán trên máy tính được tiến hành qua 5 bước: Xác định bài toán – Lựa chọn thuật toán – Viết chương trình – Hiệu chỉnh – Viết tài liệu. Câu 6: Tiêu chí lựa chọn hoặc thiết kế thuật toán là? A. Hiệu quả về thời gian B. Hiệu quả về không gian C. Khả thi khi cài đặt D. Tất cả đều đúng Đáp án
Đáp án : D Giải thích : Tiêu chí lựa chọn hoặc thiết kế thuật toán là nhanh, tốn ít bộ nhớ, chạy được khi cài đặt. Câu 7: Thuật toán tối ưu là? A. Sử dụng ít thời gian, ít bộ nhớ... B. Sử dụng ít thời gian, nhiều bộ nhớ, ít phép toán... C. Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép toán... D. Sử dụng ít thời gian, ít bộ nhớ, ít phép toán... Đáp án
Đáp án : D Giải thích : Thuật toán tối ưu là sử dụng ít thời gian, ít bộ nhớ, ít phép toán, ít phức tạp... Câu 8: Các bước cần phải có khi giải bài toán trên máy tính là: A. Xác định bài toán, lựa chọn hoặc thiết kế thuật toán, diễn tả thuật toán, hiệu chỉnh, viết tài liệu B. 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, viết tài liệu 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 D. Xác định bài toán, viết thuật chọn, viết chương trình, viết tài liệu Đáp án
Đáp án : C Giải thích : Các bước cần phải có khi giải bài toán trên máy tính là: 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. |
