1
Chào mừng quí thầy cô cùng tất cả các em đến với tiết học hôm nay
GV Nguyễn Thanh Phong
Lớp dạy10A3
Trường THPT Nguyễn Văn Cừ Tổ Toán - Tin
10/27/2011 2:28:48 PM


Bài toán trong tin học là gì?
Bài toán là một công việc mà con người muốn máy tính thực hiện.
 Thuật toán là gì?
Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.
Kiểm tra bài cũ
10/27/2011 2:28:48 PM
2
Có phải máy tính thông minh và làm được mọi công việc kể cả việc giải toán?
Máy tính làm một công việc hay giải một bài toán là do con người đã đưa vào trong máy các cách thức làm việc để hướng dẫn cho máy thực hiện công việc.
Việc giải toán trên máy tính được thực hiện như thế nào?
Để giải bài toán trên máy tính ta thường tiến hành theo 5 bước.
10/27/2011 2:28:48 PM
3
Qui ước slide nào có hình thì ghi vào vở
§ 6 GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Việc giải bài toán trên máy tính thường có 5 bước :
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 5: Viết tài liệu.
10/27/2011 2:28:48 PM
4
1/ Xác định bài toán :

?Với một bài toán thì trước tiên cần phải xác định hai yếu tố cần thiết, đó là hai yếu tố nào?
Phải xác định input và output của bài toán

Xác định bài toán là xác định Input và Output
của bài toán.
Input: Những dữ kiện, giả thiết, số liệu đã có.
Output: Kết quả cần tìm, kết luận cần chỉ ra.
10/27/2011 2:28:48 PM
5
Ví dụ1 : Xét bài toán sau

Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N
? Hãy xác định Input và Output của bài toán trên?
Input : Hai số nguyên dương M và N;
Output: ƯCLN(M, N).
Khi đã xác định được input và output ta sẽ lựa chọn hoặc thiết kế thuật toán cho bài toán.

10/27/2011 2:28:48 PM
6

2/ Lựa chọn hoặc thiết kế thuật toán

Một bài toán có thể có nhiều thuật tóan để giải nhưng mỗi thuật toán chỉ giải được cho một bài toán. Vì vậy ta phải chọn thuật toán tối ưu trong các thuật toán đã có.
Một thuật toán tối ưu phải có các tiêu chuẩn sau :
Thời gian thực hiện nhanh.
Ít tốn bộ nhớ.
Trình bày dễ hiểu, dễ nhìn.
b/ Diễn tả thuật toán :
Có 2 cách diễn tả một thuật toán
Diễn tả bằng cách liệt kê.
Diễn tả bằng sơ đồ khối.


a/ Lựa chọn thuật toán :
10/27/2011 2:28:48 PM
7
Có thể
có nhiều
cách giải
(thuật toán)
BÀI TOÁN
Cách 1
Cách 2
Cách 3
. . .
KẾT QUẢ
Ví dụ 1:Tìm ước chung lớn nhất của hai số nguyên dương M, N.
Nếu M=N thì giá trị chung là UCLN
Nếu M>N thì UCLN(M,N)=UCLN(M-N,N)
Nếu M Chia M cho N lấy dư là R
Nếu R=0 thì UCLN(M,N)=N
Nếu R khác 0 thì gán N cho M, gán R cho N
Tiếp tục chia M cho N.
C1:
C2:
Ý tưởng: ta có 2 ý tưởng sau:
10/27/2011 2:28:48 PM
8
B1: Nhập M, N
B2: Chia M cho N lấy dư là R
B3: Nếu R=0 thì UCLN(M,N)=N rồi kết thúc
B4: M N , N R, chuyển sang B2
B1:Nhập M,N
B2: Nếu M=N thì giá trị chung là UCLN rồi kết thúc
B3:Nếu M>N thì
M M-N, chuyển sang B2
B4: N N-M, chuyển sang B2
C1:
C2:
Thuật toán :
* Diễn tả thuật toán bằng cách liệt kê :
10/27/2011 2:28:48 PM
9
Nhập M,N
N N-M
M=N
Đưa ra M và
KT
M>N
S
Đ
S
M M-N
Đ
Nhập M,N
Chia M cho N
lấy dư R
R=0
M N
N R
Đưa ra N và
KT
?
Nên lựa chọn cách giải (thuật toán) nào để viết chương trình?
Đ
S
2
1
* Diễn tả thuật toán bằng sơ đồ khối:
10/27/2011 2:28:48 PM
10
Nhập M,N
N N-M
M=N
Đưa ra M và
KT
M>N
S
Đ
S
M M-N
Đ
2
3
97
3
3
94
1
3
100
35
2
1
36
1
1
34
3
1
…
…
…
KQ
UCLN(3,100)=1
Áp dụng thuật toán 1 Với M=3, N=100
10/27/2011 2:28:48 PM
11
Nhập M,N
Chia M cho N
lấy dư R
R=0
M N
N R
Đưa ra N và
KT
Đ
S
1
3
100
3
2
100
3
1
3
3
1
0
KQ
UCLN(3,100)=1
Áp dụng thuật toán 2 với M=3, N=100
10/27/2011 2:28:48 PM
12
Khi có thuật toán rồi thì máy tính có thể hiểu và thực hiện theo được hay chưa?
10/27/2011 2:28:49 PM
13
3/ Viết chương trình :
Là lựa chọn cách tổ chức dữ liệu và lựa chọn ngôn ngữ lập trình (NNLT) phù hợp với thuật toán.
Có nhiều loại NNLT, vì vậy khi viết chương trình trong ngôn ngữ nào thì phải tuân theo những quy định đó.



Thuật toán + Ngôn ngữ lập trình = chương trình
10/27/2011 2:28:49 PM
14
Program TimUCLN;
Var M, N, R:integer;
Begin
Write(‘Nhap vao M,N’); Read(M,N);
While N<> 0 do
Begin
R:=M mod N;
M:=N; N:=R;
end;
Write(‘ uoc chung lon nhat la:’, M);
End.
Program TimUCLN;
Var M, N, R:integer;
Begin
Write(‘Nhap vao M,N’);
Read(M,N);
While M<>N do
IF M>N THEN
M:=M-N
ELSE
N:=N-M;
Write(‘ uoc chung lon nhat la:’, M);
End.
10/27/2011 2:28:49 PM
15
4/ Hiệu chỉnh :
Khái niệm: Chương trình được kiểm tra bằng cách cho chạy thử trên những bộ Input mà người ta đã biết trước Output.
Các bộ Input-Output này gọi là các Test.
Nếu có sai sót người lập trình phải sửa chương trình rồi thử lại.
Quá trình này được gọi là hiệu chỉnh.
Khi ta giải một bài toán có phải lúc nào kết quả cũng đúng không? Tại sao cần phải có bước hiệu chỉnh? Thế nào là hiệu chỉnh?
10/27/2011 2:28:49 PM
16
Ví dụ 2: Để kiểm chứng tính đúng đắn của chương trình giải pt bậc hai ax2 +bx +c =0, ta sử dụng vài bộ số Input để thấy rõ bước hiệu chỉnh của bài toán.
Bài toán này có Input là gì?
Input là bộ ba số a,b,c.
a=1,b= -3,c=2 ; ∆ =1>0(chương trình đưa ra hai nghiệm).
a=1,b= -4,c=4; ∆ =0 (chương trình đưa ra một nghiệm).
a=1,b=3,c=4; ∆= -7 <0 (chương trình thông báo pt vô nghiệm).

10/27/2011 2:28:49 PM
17
5/ Viết tài liệu :
Mô tả chi tiết toàn bộ 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.
Việc giải bài toán trên máy tính thường có 5 bước :
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 5: Viết tài liệu.
Củng cố
10/27/2011 2:28:49 PM
18



Câu 1: 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.

CÂU HỎI TRẮC NGHIỆM
10/27/2011 2:28:49 PM
19


Câu 2: Mục đích của việc hiệu chỉnh là :
a. Xác định lại Input và Output của bài toán.
b. Phát hiện và sửa sai sót.
c. Mô tả chi tiết bài toán.
d. Để tạo ra một chương trình mới.
10/27/2011 2:28:49 PM
20
Câu 3. Thuật toán tốt 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.. .
10/27/2011 2:28:49 PM
21



Về nhà học bài, làm bài tập 1, 2, 3 trang 51.
Chuẩn bị bài phần mềm máy tính cho tiết sau.
10/27/2011 2:28:49 PM
22