Giáo án môn Tin học 10 - Tiết 17: Giải bài toán trên máy tính

Tiết: 17
Đ6. giảI bàI toán trên máy tính
Ngày dạy: 05/ 10/ 2009
A - Mục đích, yêu cầu:
1. Về kiến thức
- Hiểu được cách tổ chức và giải bàI toán trên máy tính, tức là cách dùng máy tính thực hiện các công việc cần làm.
 - Hiểu rõ hơn các khái niệm: Bài toán, thuật toán, chương trình.
2. Kỹ năng
- Thực hiện một số bước để giải bàI toán đơn giản trên máy tính.
3. Về thái độ
 - Nhận thức được tầm quan trọng của một chương trình trong việc giải một bài toán tin học.
 - Rèn luyện ý thức học tập bộ môn, tính cần cù và ham thích tìm hiểu.
 - Rèn luyện ý thức suy luận khoa học sáng tạo. 
B – Chuẩn bị phương pháp và phương tiện : 
a) Chuẩn bị của giáo viên : 
Sách giáo khoa, projector và máy tính, ....
Chuẩn bị một số chương trình viết bằng ngôn ngữ Pascal.
Chuẩn bị các phiếu câu hỏi.
b) Chuẩn bị của học sinh : Sách giáo khoa, xem bài trước ở nhà, xem lại bàI cũ.
c) Chuẩn bị phương pháp dạy học : Gợi mở , vấn đáp, thảo luận nhóm,
C - Tiến trình tổ chức bài học:
ổn định lớp: 
 - Sỹ số lớp : 
 - Nắm tình hình sách gtáo khoa của học sinh.
Nội dung tiết dạy:
Hoạt động 1: (Giúp học sinh thấy được tính ưu việt của việc giải bài toán trên máy tính)
	Tìm ước chung lớn nhất UCLN của các cập số nguyên M và N sau: 
	a) M = 6, N = 54; 	b) M = 99, N = 121;	c) M = 29, N = 78,	d) M = 26, N = 169
Hoạt động Học Sinh
Hoạt động Giáo Viên
UCLN (M, N) là số lớn nhất mà M, N có thể chia hết.
Phân tích các số M, N thành tích các số nguyên tố, UCLN của M, N là tích các số nguyên tố chung đã được phân tích của hai số M, N.
UCLN(6, 54) = 6; 
UCLN(99, 121) = 11;
UCLN(29, 78) = 1;
UCLN(26, 169) = 13;
Bước 1: Xác định bàI toán.
Bước 2: Lựa chọn hoặc thiết thuật toán;
Bước 3: Viết chương trình;
Bước 4: Hiệu chỉnh;
Bước 5: Viết tàI liệu;
UCLN(M, N) được định nghĩa như thế nào?
Làm thế nào để tìm UCLN của hai số M, N ?
Hãy tìm UCLN của các cập số M, N nói trên.
ĐVĐ: Chúng ta thấy việc tìm UCLN của các cập số M, N như thế sẽ rất lâu khi M, N càng lớn có khi không tìm được. Hoặc công việc sẽ lâu nếu ta tìm một lúc nhiều ước chung của nhiều cập số. Nếu giả sử ta đã có một chương trình nào đó trên máy tính dùng để tìm UCLN(M, N) với M, N nhập bất kỳ từ bàn phím thì công việc sẽ trở nên nhanh hơn rất nhiều so với việc tính bằng tay. Và cách tìm như thế là ta đã thục hiện giải một bàI toán trên máy tính?
Theo các em việc giảI một bàI toán trên máy tính cần làm theo những bước nào?
Lắng nghe, điều chỉnh;
1) Xác định bàI toán
	Hoạt động 2: (Xây dựng kiến thức)
	Theo các em việc xác định bàI toán là chúng ta đi làm những công việc gì? vì sau phải có bước này trong việc giảI bàI toán trên máy tính. Cho ví dụ?
Hoạt động Học Sinh
Hoạt động Giáo Viên
 Là việc xác định giá trị Input, Output và mối quan hệ của chúng trong bàI toán.
Việc xác định bàI toán tốt sẽ giúp ta phân biệt dược loại thông tin cần xử lý là gì, thông tin cần xuất là gì, qua đó giúp ta xác định được thuật toán, các đại lượng phát sinh cho bài toán và để chọn ngôn ngữ lập trình thích hợp. 
Ví dụ: Đối với bài toán tìm UCLN của hai số M, N ta có:
Input: M, N là hai số nguyên dương.
Output: UCLN(M, N), là số nguyên dương nhận giá trị từ 1 và không vượt quá M, N
Hướng dẫn học sinh trả lời câu hỏi.
Gọi một vàI học sinh trả lời và nhận xét.
Nhận xét các ý kiến.
Chốt lại vấn đề cho học sinh.
2) lựa chọn hoặc thiết kế thuật toán
	a) Lựa chọn thuật toán
	Hoạt động 3: (Xây dụng kiến thức)
	a) Theo các em tại sao phải có bước này? 
	b) Có ý kiến cho rằng “việc lập trình giải bài toán là của con người, còn việc giải bài toán là của máy tính không có việc gì khác khi ta sử dụng các thuật toán khác nhau để giải cùng một bài toán trên máy tính”, điều này đúng hay sai? Vì sao?
Hoạt động Học Sinh
Hoạt động Giáo Viên
- Một thuật toán chỉ có thể giải được một bàI toán tổng thể nào đó.
- Một bài toán có thể có nhiều thuật toán khác nhau để giải.
- Các thuật toán khác nhau có ảnh hưởng đến việc lập trình giải bài toán trên máy tính, vì thuật toán càng đơn giản, càng dể hiểu thì sẽ giúp cho người lập trình dể dàng khai thác được tính tối ưu của thuật toán, có thể dể dàng kiểm tra được Output cần tìm là đúng hay chưa để có thể hiệu chỉnh.
 Đối với máy chương trình càng ngắn gọn dể hiểu thì máy sẽ làm việc nhanh hơn, ít thực hiện các lệnh hơn, ít tốn dung lượng bộ nhớ hơn.
 - Công việc này rất cần.
- Hướng dẫn các em bằng các câu hỏi:
Câu hỏi 1: Một thuật toán có thể giải được bao nhiêu bài toán?
Câu hỏi 2: Một bài toán có thể có bao nhiêu thuật toán?
Câu hỏi 3: Các thuật toán khác nhau có ảnh hưởng gì không đối với việc lập trình và giải bài toán trên máy tính? Vì sao?
- Vậy bước này có cần trong việc lập trình để giải một bàI toán trên máy tính không?
Chốt lại.
- Một bàI toán có thể có nhiều thuật toán khác nhau, nhưng cần lựa chọn thuật toán tối ưu theo một tiêu chí nào đó, chẳng hạn dùng ít tàI nguyên máy tính hoặc có thời gian tực hiện ngắn.
b) Diễn tả thuật toán
	Hoạt động 4: (Xây dựng kiến thức)
	Hãy tìm thuật toán cho bàI toán tìm UCLN của hai số nguyên dương m và n.
Hoạt động Học Sinh
Hoạt động Giáo Viên
- Xác định bài toán:
Input: m, n là hai số nguyên dương.
Output: UCLN(m, n).
- ý tưởng:
 - Nếu m = n thì UCLN(m, n) = m 
	 hoặc UCLN(m, n) = n;
 - Nếu m < n thì UCLN(m, n) = UCLN(m, n - m) ;
 - Nếu m > n thì UCLN(m, n) = UCLN(m - n, n) ;
- Thuật toán:
 - Bước 1: Nhập m, n;
 - Bước 2: Nếu m = n thì UCLN(m, n) =m rồi chuyển đến bước 5;
 - Bước 3: Nếu m > n thì m Đ m – n rồi quay lạ bước 2;
 - Bước 4: n Đ n – m rồi quay lại bước 2;
 - Bước 5: Đưa ra kết quả UCLN rồi kết thúc;
- Xác định bài toán trên.
- Hãy cho ý tưởng giải bài toán trên.
- Hãy diễn tả thuật toán của bài toán bằng phương pháp liệt kê.
Trình bày sơ đồ khối của thuật toán (vẽ sẳn bảng phụ)
Mô phỏng thuật toán với m = 10, n = 25 và cập số m = 17, n =13
- Có thuật toán nào khác để giải bàI toán trên không?
Giới thiệu tuật toán cho bàI toán bằng sơ đồ khối (vẽ sẳn) yêu cầu học sinh về nhà diễn tả bằng cách liệt kê.
3) viết chương trình
Hoạt động Học Sinh
Hoạt động Giáo Viên
Học sinh lắng nghe ghi chép
- 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 phù hợp để diễn đạt đúng thuật toán.
- Thông qua một chương trình viết bằng ngôn ngữ Pascal, chỉ rõ cho học sinh phần tổ chức dữ liệu, phần diễn đạt thuật toán và mối quan hệ của chúng tring chương trình. (Trình chiếu một chương trình viết bằng Pascal)
- Chương trình dịch chỉ có thể phát hiện lỗi ngữ pháp 
4) hiệu chỉnh
Hoạt động Học Sinh
Hoạt động Giáo Viên
Học sinh lắng nghe và ghi chép.
Ta có tfheer sủa dụng các bộ test sau:
M chia hết cho N;
M = N;
M, N nguyên tố cùng nhau.
Giảng cho học sinh:
Bước này nhằm phát hiện lỗi của chương trình và sửa lỗi. 
- Cách làm: Chạy thử chương trình với một số bộ Input tiêu biểu phụ thuộc vào đặc thù của bàI toán để kiểm tra kết quả, từ đó phát hiện lỗi và sửa chữa.
- Mỗi bộ input và Output tương úng gọi là một Test
- Hướng dẫn học sinh tìm ra một test của một số bàI toán: giảI phương trình bậc hai, bàI toán tìm kiếm,
Theo các em trong trường hợp của bàI toán tìm UCLN trên nên cho chạy các bộ test nào để dễ dàng phát hiện lỗi?
5) Viết tàI liệu
Hoạt động Học Sinh
Hoạt động Giáo Viên
Viết tàI liệu là mô tả chi tiết bàI toán, tổ chức dữ liệu, thuật toán và hướng dẫn sử dụng.
TàI liệu rất có ích cho người sử dụng chương trình và cả cho việc đề xuát những khả năng hoàn thiện.
Củng cố bài giảng, dặn dò:
Cần nhấn mạnh cho học sinh là: trong các bước trên thì quan trọng nhất là bước 2 nhằm mục đích lựa chọn được thuật toán tối ưu xét theo niều mặt:
Về tàI nguyên: Thuật toán lựa chọn có thời gian thục hiện nhanh, tiết kiệm boojo nhớ,
Việc viết chương trình ít phức tạp
Học sinh về làm các câu hỏi và bàI tập trong SGK trang 51.
Rút kinh nghiệm từng lớp: (Nếu có)