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

Ngày soạn: 28 / 10 / 2006 ;	 ngày giảng: 30 / 10 / 2006 ; Lớp: 10
Bài: 	§6. GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Tiết PPCT 18
I. MỤC TIÊU BÀI HỌC:
	1. Kiến thức: Biết các bước cơ bản khi tiến hành giải toán trên máy tính: xác định bài toán; xây dựng và 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.
2. Kỹ năng	
3. Thái độ
II. CHUẨN BỊ:
	1. Tài liệu, bài tập:
	2. Dụng cụ, thiết bị:
III. TIẾN TRÌNH LÊN LỚP:
	1. Oån định, tổ chức lớp:
	2. Kiểm tra bài cũ:
	3. Bài giảng:
Hoạt động của Thầy và Trò
Nội dung ghi bảng
GV: ĐVĐ Máy tính là công cụ hỗ trợ con người rất nhiều trong cuộc sống, con người muốn máy tính thì phải đưa lời giải bài toán đó vào máy dưới dạng các lệnh. Như vậy các bước để xây dựng một bài toán là gì?
 GV: Chúng ta tìm hiểu từng bước giải bài toán.
Bước 1: X¸c ®Þnh bµi to¸n:
 GV: Xác định bài toán là ta xác định các thành phần nào?
HS: Trà lời: Xác định Input, Output
 GV: Đúng rồi. ViƯc x¸c ®Þnh bµi to¸n chÝnh lµ x¸c ®Þnh râ hai thµnh phÇn nµy vµ mèi quan hƯ gi÷a chĩng.
 *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:
 Bước 1: X¸c ®Þnh bµi to¸n;
 Bước 2: Lùa chän hoỈc thiÕt kÕ thuËt to¸n;
 Bước 3: ViÕt ch­¬ng tr×nh;
 Bước 4: HiƯu chØnh;
Bước Bước 5: ViÕt tµi liƯu.
1. X¸c ®Þnh bµi to¸n
Xác định hai thµnh phÇn: Input vµ Output. Từ đó xác định ngôn ngữ lập trình và cấu trúc dữ liệu một cách thích hợp.
GV: Sau khi xác định xong Input và Output của bài toán ta sang bước tiếp theo:
Bước 2: Lùa chän hoỈc thiÕt kÕ thuËt to¸n:
GV: Em nào nhắc lại thuật toán là gì?
HS: Trả lời câu hỏi.
GV: Bài toán tìm kiếm có bao nhiêu thuật toán?
HS: Có 2 thuật toán:
 -TT Tìm kiế tuần tự 
 -TT tìm kiếm Nhị phân
GV: Theo các em Thuật toán Tìm kiếm tuần tự có giải được bài toán Sắp xếp ( hay bài toán khác)?
HS: Trả lời. (không giải được).
GV: Vậy Thuật toán Tìm kiếm tuần tự dùng để giải bài toán nào?
HS: Trả lời: Dùng để giải bài toán Tìm kiếm
GV: Giải thích rõ hơn về các tiêu chí của Thuật toán tối ưu.
 -Dễ hiểu; (Đọc vào ta có thể hiểu được ngay)
-Trình bày dễ nhìn; ( Rõ ràng)
-Thời gian chạy nhanh; (TT Tìm kiế tuần tự > TT tìm kiếm Nhị phân).
-Tốn ít bộ nhớ. ( Không dùng nhiều biến (ô nhớ)).
VD: Bài toán: Tìm ƯCLN của 2 số nguyên dương a và b.
*XĐBT:
-Input: Hai số nguyên dương M và N.
-Output: ƯCLN của 2 số M và N.
 Ta có: M và N thuộc số nguyên dương (kiểu dữ liệu)
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 nµo ®ã, nh­ng mét bµi to¸n cã thĨ cã nhiỊu thuËt to¸n kh¸c nhau để gi¶i. Vậy ta phải chọn thuật toán tối ưu nhất trong những 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;
-Trình bày dễ nhìn;
-Thời gian chạy nhanh;
-Tốn ít bộ nhớ.
GV: Sau khi ta chọn được thuật toán thích hợp, ta tìm cách diễn tả thuật toán.
GV: Lấy lại VÝ dơ (T×m ­íc chung lín nhÊt (¦CLN) cđa hai sè nguyªn d­¬ng M vµ N).
GV: Hướng dẫn cách nêu ý tưởng của bài toán:
 Ta xét VD: Tìm ƯCLN(M = 15,N = 6)
Lượt 1: 
Cách mô tả:
ƯCLN(15, 6 )
-Vị trí số nhỏ ghi lại
ƯCLN( ? , 6)
-Vị trí còn lại lấy số lớn-số nhỏ 
ƯCLN ( 9, 6 )
 Ta lập lại lượt 1 cho đến khi M = N thì đưa ra KQ rồ kết thúc.
Lượt 2: 
Vị trí số nhỏ ghi lại
ƯCLN( ? , 6)
Vị trí còn lại lấy số lớn-số nhỏ 
ƯCLN ( 3, 6 )
Lượt 3: 
Vị trí số nhỏ ghi lại
ƯCLN( 3 , ?)
Vị trí còn lại lấy số lớn-số nhỏ 
ƯCLN ( 3, 3 )
è M = N = 3 = ƯCLN(15, 6).
 Từ ý tưởng ở trên GV hướng dẫn mô tả thuật toán bằng cách liệt kê. 
GV: M« pháng c¸c b­íc thùc hiƯn thuËt to¸n trªn
Lượt
1
2
3
M
15
9
3
3
N
6
6
6
3
ƯCLN(15, 6) = 3
HS: Lên bảng mô tả TT bằng sơ đồ khối
b) DiƠn t¶ thuËt to¸n:
VD: Tìm ¦CLN(M, N)?
· X¸c ®Þnh bµi to¸n
- Input: NhËp M, N;
- Output: ¦CLN(M, N).
· ý t­ëng: 
- 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 dùng hiệu của 2 số)
* DiƠn t¶ b»ng c¸ch liƯt kª:
Bước 1: NhËp M, N;
Bước 2: NÕu M = N th× lÊy gi¸ trÞ chung nµy lµm ¦CLN råi chuyĨn ®Õn b­íc 5;
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;
Bước 5: §­a ra kÕt qu¶ ¦CLN rồi KÕt thĩc.
.
b) ThuËt to¸n diƠn t¶ b»ng s¬ ®å khèi
NhËp M vµ N
M ¬ M - N 
N ¬ N - M 
§ĩng
M = N ?
Sai
M > N ?
Sai
§ĩng
§­a ra M; KÕt thĩc
GV: Bài toán tìm ƯCLN(M,N) trên có thể giải bằng thuật toán khác. Đó là Thuật toán dùng thương của 2 số hay còn gọi là Thuật toán Euclide (Ơ-clit)
 Ý tưởng của thuật toán Euclide:
 Tìm ƯCLN(M,N):
 - M ß N;
 - N ß M mod N;
 Lặp lại quá trình này cho đến khi N = 0 thì đưa ra kết quả ƯCLN của 2 số là M, rồi kết thúc.
Thuật toán: Euclide (Ơ-clit) 
(Thuật toán dùng thương của 2 số) 
Bước 1: NhËp M, N;
Bước 2: Số dư ß 0;
Bước 3: NÕu N = 0 thì đưa ra kết quả ƯCLN(M,N) là M, råi KÕt thĩc;
Bước 4: Nếu N khác 0 thì
 Số dư ß M mod N;
 M ß N;
 N ß Số dư;
Bước 5: Quay lại Bước 3.
GV: Đến đây ta đã có được thuật toán của bài toán, công việc tiếp theo là phải chuyển thuật toán thành chương trình, ta sang bước tiếp theo:
Bước 3: Viết chương trình
GV: Em nào cho biết có mấy loại NNLT?
HS: Trả lời: Có 3 loại: (Ngôn ngữ máy; Hợp ngữ; Ngôn ngữ bậc cao).
GV: Do NNLT có nhiều loại nên công việc trước tiên ta phải chọn NNLT thích hợp.
GV: Chương trình được viết không phải lúc nào cũng đảm bảo là hoàn toàn đúng đắn, do đó phải thử chương trình bằng các bộ input đặc trưng để kiểm tra sai sót.
GV: Sau khi chương trình đã hoàn thiện, công việc còn lại là viết tài liệu mô tả thuật toán, chương trình và hướng dẫn sử dụng chương trình.
3/ Viết chương trình:
 Là việc lựa chọn CTDL và NNLT để diễn đạt thuật toan trên máy tính.
 Khi viết chương trình cần chọn ngôn ngữ thích hợp, viết chương trình bằng ngôn ngữ nào thì phải tuân theo qui đị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 thử chương trình bằng một số INPUT đặc trưng. Trong quá trình thử nếu phát hiện ra sai sót thì phải sửa lại chương trình. Quá trình này gọi là hiệu chỉnh.
5/ Viết tài liệu:
 Viết mô tả chi tiết bài toán, thuật toán, chương trình và hướng dẫn chương trình.
4.Tổng kết nội dung, đánh giá cuối bài:
5.Dặn dò, kế hoạch học tập tiết sau: Học bài cũ, Xem trước bài mới (Bài 7, 8 và 9).
IV. NHỮNG VẤN ĐỀ CẦN RÚT KINH NGHIỆM: