§6. GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Ngày soạn : 27/10/2007
Tiết : 18
Lớp : 10
I. MỤC ĐÍCH - YÊU CẦU
* Kiến thức:
+ Biết các bước cơ bản khi tiến hành giải bài toán trên máy tính: Xác định bài toán, xây dựng và lựa chọn thuật toán, lựa chọn cấu trúc dữ liệu, viết chương trình, hiệu chỉnh, đưa ra kết quả và hướng dẫn sử dụng.
+ Cúng cố và làm rõ hơn các khái niệm như bài toán, thuật toán, dữ liệu, lệnh, ngôn ngữ lập trình và chương trình.
* Kĩ năng:
+ Giúp HS nắm được các bước cụ thể cần thực hiện khi giải một bài toán.
* Tư duy:
+ Rèn luyện tư duy lôgic và sáng tạo.
+ HS thấy rõ hơn muốn sử dụng máy tính, ngoài việc hiểu biết sơ lược về cấu trúc máy tính (phần cứng), còn cần hiểu biết về phần mềm ở mức độ có thể làm một số việc thiết thực.
II. CHUẨN BỊ
Thầy:
- Soạn giáo án, nghiên cứu sách giáo khoa, sách bài tập, tài liệu tham khảo.
- Máy tính cá nhân và máy chiếu ( nếu có).
Trò: Đọc trước ở nhà Sách giáo khoa.
III.TIẾN TRÌNH LÊN LỚP.
1. Ổn định tổ chức, kiểm tra sĩ số (1’).
2. Kiểm tra bài cũ. (5’)
Câu hỏi:
Em hiểu như thế nào về ngôn ngữ máy?
Chương trình dịch dùng để là gì?
Đáp án:
1. - Là ngôn ngữ duy nhất để viết chương trình mà máy tính trực tiếp hiểu và thực hiện được.
- Ưu điểm: Viết chương trình bằng ngôn ngữ máy, hiệu quả của chương trình sẽ là rất cao.
- Nhược điểm: Để viết hoặc hiểu chương trình bằng ngôn ngữ máy, người ta phải nhớ rất máy móc các dòng số không gợi ý nghĩa của các lệnh đồng thời phải dùng nhiều câu lệnh để diễn tả chi tiết các thao tác của thuật toán.
2. Chương trình dịch là chương trình có chức năng dịch những chương trình viết bằng ngôn ngữ bậc cao sang ngôn ngữ máy.
Đối tượng kiểm tra: HS trung bình.
3. Nội dung bài học mới.
Nội dung
Hoạt động của GV
Hoạt động của HS

* Các bước giải bài toán trên máy tính:
- Xác định bài toán.
- Lựa chọn và xây dựng 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 hai thành phần INPUT và OUTPUT của bài toán và mối quan hệ giữa chúng.
- Từ đó để có thể lựa chọn thuật toán, cách thể hiện các đại lường đã cho, các đại lượng phát sinh trong quá trình giải bài 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.

- Mỗi thuật toán chỉ giải một bài toán, song một bài toán có thể có nhiều thuật toán để giải. Vậy phải chọn thuật toán tối ưu nhất trong các thuật toán đưa ra.
- Thuật toán tối ưu là thuật toán có các tiêu chí sau:
+ Dễ hiểu, ít phức tạp.
+ Trình bày dễ nhìn.
+ Thời gian chạy nhanh.
+ Tốn ít bộ nhớ.

b) Diễn tả thuật toán
VD: Tìm UCLN (M, N) với M, N nguyên dương.
* Xác định bài toán
* Ý tưởng:
- Nếu M=N thì UCLN(M,N)=M.
- Nếu M> N thì UCLN (M,N) = UCLN (M -N, N).
- Nếu M< N thì UCLN(M,N) = UCLN(M, N- M).
* Thuật toán:
a) Cách liệt kê:
-B1: Nhập N;
-B2: Nếu M=N thì giá trị chung đó là UCLN rồi chuyển đến B5.
-B3: Nếu M >N thì M ←M - N rồi quay lại B2;
-B4: N ← N-M rồi quay lại B2;
-B5: Đưa ra UCLN rồi kết thúc

b) Sơ đồ khối




















3. Viết chương trình
- Là 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.







4. Hiệu chỉnh
- Sau khi viết xong chương trình cần phải thử chương trình bằng một số bộ Test đặc trưng . Nếu có sai sót, phải sửa lại chương trình rồi thử lại