Bài giảng Tin học 10 bài 6: Giải bài toán trên máy tính
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (379.91 KB, 25 trang )
BÀI GIẢNG ĐIỆN TỬ
MÔN: TIN HỌC 10
05/01/21
1
Bài tốn là gì?
Bài tốn là một cơng việc mà con người muốn
máy tính thực hiện.
Thuật tố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.
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
tốn?
Việc giải tốn
trên máy tính
được thực hiện
như thế nào?
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.
Để giải bài tốn trên
máy tính ta thường tiến
hành theo 5 bước.
§ 6 GIẢI BÀI TỐN TRÊN MÁY
TÍNH
Việc giải bài tố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 tố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.
1/ Xác định bài tốn :
?Với định
một bài
thìlàtrước
phải và
xácOutput
định hai
Xác
bàitốn
tốn
xác tiên
địnhcần
Input
yếubài
tố cần
thiết, đó là hai yếu tố nào?
của
tốn.
xácNhững
định input
output
bài số
tốn
• Phải
Input:
dữ và
kiện,
giảcủa
thiết,
liệu đã có.
• Output: Kết quả cần tìm, kết luận cần chỉ ra.
Ví dụ1 : Xét bài tố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.
BÀI TỐN
Có thể
có nhiều
cách giải
(thuật tốn)
Cách 1
Cách 2
Cách 3
...
KẾT QUẢ
2/ Lựa chọn hoặc thiết kế thuật toán
a/ Lựa chọn thuật tốn :
Một bài tốn có thể có nhiều thuật tóan để giải nhưng
mỗi thuật tốn chỉ giải được cho một bài tốn. Vì vậy ta
phải chọn thuật tốn tối ưu trong các thuật tốn đã có.
Một thuật tố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 tố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.
Ví dụ 1:Tìm ước chung lớn nhất của hai số ngun dương
M, N.
Ý tưởng: ta có 2 ý tưởng sau:
• 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
UCLN(M,N)=UCLN(M,N-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.
Thuật toán :
* Diễn tả thuật toán bằng cách liệt kê :
B1:Nhập M,N
B1: Nhập M, N
B2: Nếu M=N thì giá trị
chung là UCLN rồi kết thúc
B2: Chia M cho N lấy
dư là R
B3:Nếu M>N thì
B3: Nếu R=0 thì
UCLN(M,N)=N rồi kết
thúc
M M-N, chuyển sang B2
B4: N
B2
N-M, chuyển sang
B4: M N , N
chuyển sang B2
R,
* Diễn tả thuật toán bằng sơ đồ khối:
Nhập M,N
Nhập M,N
Đ
M=N
S
Đ
M>N
S
N
Đưa ra M và
KT
Chia M cho N
lấy dư R
Đ
R=0
M
M-N
S
M
N
N-M
1
Đưa ra N và
KT
N
R
2
Nên lựa chọn cách giải (thuật toán) nào để viết chương
trình?
Với M=3, N=100
Nhập M,N
Đ
M=N
S
M>N
S
N
N-M
Đ
Đưa ra M và
KT
M
M-N
Lần
M
N
1
3
100
2
3
97
3
3
…
…
94
…
34
3
1
35
2
1
36
1
1
KQ
UCLN(3,100)=1
Với M=3, N=100
Nhập M,N
Chia M cho N
lấy dư R
Đ
R=0
S
M
N
N
R
Đưa ra N và
KT
Lần
M
N
R
1
3
100
3
2
100
3
1
3
3
1
0
KQ
UCLN(3,100)=1
Số
lần
thực
hiện
Thuật toán 1 và
giá trị tương
ứng của (M,N)
Thuật toán 2 và
giá trị tương ứng
của (M,N)
1
2
3
4
3,100
3,97
3,94
3,91
3,100
100,3
3,1
Kết luận: ƯCLN =
1
…
34
35
36
…
3,1
2,1
1,1
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 tố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
tn theo những quy định đó.
Program TimUCLN;
Var M, N, R:integer;
Begin
Write(‘Nhap vao M,N’);
Read(M,N);
Program TimUCLN;
Var M, N, R:integer;
Begin
Write(‘Nhap vao M,N’);
Read(M,N);
While N<> 0 do
While M<>N do
Begin
IF M>N THEN
R:=M mod N;
M:=M-N
M:=N; N:=R;
ELSE
N:=N-M;
Write(‘ uoc chung lon nhat
la:’, M);
End.
end;
Write(‘ uoc chung lon nhat la:’, M);
End.
4/ Hiệu chỉnh :
?Khi ta giải một bài tốn có phải lúc nào kết quả cũng
đúngniệm:
khơng?
Tại saotrình
cần phải
bướctra
hiệu
chỉnh?
Khái
Chương
đượccókiểm
bằng
cáchThế
nàochạy
là hiệu
cho
thửchỉnh?
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.
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 tốn.
Bài tố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).
Bước hiệu chỉnh giúp cho người lập trình thấy những
sai sót để sửa sai, giúp cho kiểm tra tính đúng đắn của
chương trình để có được một chương trình hồn chỉnh.
5/ Viết tài liệu :
Mơ tả chi tiết tồn bộ bài tốn, thuật tốn, thiết kế
chương trình, kết quả thử nghiệm và hướng dẫn sử
dụng.
Ví dụ 3:
Bài tốn: viết thuật tốn giải pt bậc nhất ax+b=0 và sử dụng vài bộ
Input để kiểm chứng tính đúng đắn của chương trình.
Xác định bài tốn :
- Input : các hệ số a,b
- Output : các kết luận về nghiệm của pt.
Ý tưởng : nghiệm của bài toán phụ thuộc vào các số a và b như sau:
-Nếu a=0 :
+Nếu b=0 :kết luận pt có vơ số nghiệm;
+Nếu b≠ 0 : kết luận pt vô nghiệm;
-Nếu a ≠ 0 : kết luận pt có một nghiệm x = -b/a.
•Thuật toán :
- Sơ đồ khối
Nhập a và b
a=0?
Đ
b=0?
Đ
Pt vsn rồi
kết thúc
S
S
nghiệm x=-b/a
rồi kết thúc
Pt vn rồi
kết thúc
Giải pt: 8x+96=0
Pt có nghiệm :x=-12
CÂU HỎI TRẮC NGHIỆM
Câu 1: Các bước cần phải có khi giải bài tố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 tốn,viết
chương trình, viết tài liệu.
c. Xác định bài tốn,lựa chọn hoặc thiết kế thuật tố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 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 tốn.
d. Để tạo ra một chương trình mới.
Câu 3. Thuật tố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 tốn.. .
c) Sử dụng nhiều thời gian, nhiều bộ nhớ, ít phép
tốn.. .
d) Sử dụng ít thời gian, ít bộ nhớ, ít phép toán.. .
Về nhà học bài, trả lời các câu hỏi sau bài học.
Chuẩn bị bài phần mềm máy tính cho tiết sau.
