Trừong THPT Tập SƠN
BÀI GIẢNG ỨNG DỤNG
CÔNG NGHỆ THÔNG TIN
GV: TÔ MINH DƯƠNG
NĂM HỌC 2009 - 2010
KIỂM TRA BÀI CỦ:
INPUT, OUTPUT của bài toán là gì?
Thế nào là ngôn ngữ lập trình?
Input: là thông tin đã biết của bài tóan
Output: là thông tin cần tìm từ Input đã có
Là ngôn ngữ dùng để diễn tả thuật tóan mà máy tính có thể hiểu và thực hiện được
Làm thế nào để máy tính có thể thực hiện đựơc yêu cầu của bài toán trên?
Bài toán: Cho 2 số nguyên dương M và N.
Hãy tìm uớc chung lớn nhất (UCLN) của M và N.
Link
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Để giải bài toán trên máy tính, ta phải tiến hành qua mấy bước, đó là những bước nào?
Để giải bài toán trên máy tính, ta thường tiến hành qua các bước:
Bước 1: Xác định bài toán;
Bước 2: Lựa chọn và 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.
Bước 1: Xác định bài toán
Input : ???
Output : ???
Ý nghĩa: Xác định rõ mối quan hệ giữa 2 yếu tố trên giúp chúng ta xác định hướng giải quyết bài toán, từ đó xây dựng được thuật toán và lựa chọn cách thể hiện các đại lượng đã cho, các đại lượng phát sinh và giúp quyết định lựa chọn ngôn ngữ lập trình thích hợp với bài toán.
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Xác định bài toán là xác định những yếu tố nào?
Bước 1: Xác định bài toán
Là xác định Input và Output của bài toán
VD: bài toán tìm UCLN của 2 số nguyên dương M và N
Input: 2 số nguyên dương M và N
Output: UCLN của M và N
Input : ???
Output : ???
Ý nghĩa: Xác định rõ mối quan hệ giữa 2 yếu tố trên giúp chúng ta xác định hướng giải quyết bài toán, từ đó xây dựng được thuật toán và lựa chọn cách thể hiện các đại lượng đã cho, các đại lượng phát sinh và giúp quyết định lựa chọn ngôn ngữ lập trình thích hợp với bài toán.
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Xác định bài toán là xác định những yếu tố nào?
a) Lựa chọn thuật toán:
Bước 2: Lựa chọn và thiết kế thuật toán;
Với bài toán tìm kiếm chúng ta có những thuật toán nào?
Với dãy đã sắp xếp thì thuật toán tìm kiếm nhị phân sẽ tối ưu hơn.
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
+ Tìm kiếm tuần tự
+ Tìm kiếm nhị phân (Đối với dãy đã sắp xếp tăng hoặc giảm)
a) Lựa chọn thuật toán:
Bước 2: Lựa chọn và thiết kế thuật toán;
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Tại sao phải lựa chọn thuật toán
Ta lựa chọn thuật toán tối ưu dựa vào những tiên chuẩn nào?
a) Lựa chọn thuật toán:
Bước 2: Lựa chọn và thiết kế thuật toán;
Mỗi thuật toán chỉ giải một bài toán, nhưng một bài toán có thể có nhiều thuật toán để giải. Do đó chúng ta phải thiết kế và lựa chọn thuật toán tốt nhất để giải bài toán (thuật toán tối ưu)
Tiêu chuẩn lựa chọn thuật toán tối ưu:
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Thời gian thực hiện nhanh;
Thuật toán đơn giản, dễ nhìn, dễ hiểu;
Tốn ít tài nguyên bộ nhớ.
Ta có những cách nào để diễn tả thuật toán
b) Diễn tả thuật toán:
Bước 2: Lựa chọn và thiết kế thuật toán;
GẢI BÀI TOÁN TRÊN MÁY TÍNH
Diễn tả thuật toán bằng cách liệt kê
Diễn tả thuật toán bằng sơ đồ khối
b) Diễn tả thuật toán:
Bước 2: lựa chọn và thiết kế thuật toán;
Bài toán:Tìm uớc chung lớn nhất (UCLN) của 2 số nguyên duơng M và N.
Xác định bài toán:
GẢI BÀI TOÁN TRÊN MÁY TÍNH
Ý 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,N);
- Nếu Mb) Diễn tả thuật toán:
Mô phỏng:
M=18
N=24
M
N
M=18
N=24
M<>N
M=18
N=6
M<>N
M=12
N=6
M<>N
M=6
N=6
M=N
MM>N
M>N
UCLN=6
M=6
N=5
M
N
M=6
N=5
M<>N
M=1
N=5
M<>N
M=1
N=4
M<>N
M=1
N=3
M<>N
M=1
N=2
M<>N
M>N
MMMMM=1
N=1
M=N
UCLN=1
b) Diễn tả thuật toán:
Thuật toán liệt kê:
Bước 1: Nhập M và N;
Bước 2: Nếu M=N thì thông báo UCLN=M hoặc UCLN=N rồi kết thúc;
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;
Dựa vào các bước liệt kê, hãy vẽ sơ đồ khối của bài tóan
b) Diễn tả thuật toán:
Sơ đồ khối:
Nhập M và N
Đưa ra UCLN=M
rồi kết thức
M=N
M>N
N ? N-M
M ? M-N
Đúng
Đúng
Sai
Sai
Bước 3: Viết chương trình;
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Tại sao phải viết chương trình mà không sử dụng thuật tóan liệt kê hoặc sơ đồ khối??
program ucln;
uses crt;
var m,n:integer;
begin
clrscr;
write(`Nhap gia tri M: `); readln(m);
writeln;
write(`Nhap gia tri N: `); readln(n);
writeln;
while m<>n do
begin
if m>n then m:=m-n
else n:=n-m;
end;
writeln;
write(`UCLN(M,N) = `,m);
readln
end.
VD: Thuật toán tìm UCLN(M,N) được viết bằng ngôn ngữ lập trình PasCal
Bước 3: Viết chương trình;
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Chương trình đuợc viết bằng gì?
Tại sao phải viết chương trình mà không sử dụng thuật tóan liệt kê hoặc sơ đồ khối??
Việc lựa chọn cách tổ chức dữ liệu;
Sử dụng ngôn ngữ lập trình để diễn đạt đúng thuật toán;
Một số lưu ý:
Nên lựa chọn ngôn ngữ lập trình hoặc phần mềm chuyên dụng thích hợp
Sử dụng ngôn ngữ lập trình nào cần tuân thủ đúng quy định ngữ pháp ngôn ngữ đó.
Chương trình dịch chỉ phát hiện những lỗi ngữ pháp, do đó cần lưu ý về lỗi ngữ nghĩa
Bước 3: Viết chương trình;
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Viết chương trình là kết hợp giữa:
Nếu phát hiện chương trình còn sai sót ta phải tiến hành sửa lỗi chương trình rồi thử lại nhiều lần cho đến khi chương trình không còn lỗi. Quá trình này gọi là hiệu chỉnh.
Bước 4: Hiệu chỉnh;
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Tại sao phải hiệu chỉnh? Hiệu chỉnh là chúng ta làm gì?
Link
Sử dụng các bộ Input đặc trưng cho bài toán để thử tính đúng đắn của chương trình
VD: chương trình giải phương trình bậc 2 ax2+bx+c=0, ta có thể thử với ba bộ Input với các trường hợp sao:
Cho a, b, c sao cho ?>0: kq chương trình đưa ra 2nghiệm
Cho a, b, c sao cho ?=0: kq chương trình đưa ra nghiệm kép
Cho a, b, c sao cho ?<0: kq chương trình thông báo pt vô nghiệm
Nếu phát hiện chương trình còn sai sót ta phải tiến hành sửa lỗi chương trình rồi thử lại nhiều lần cho đến khi chương trình không còn lỗi. Quá trình này gọi là hiệu chỉnh.
Bước 4: Hiệu chỉnh;
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Tại sao phải hiệu chỉnh? Hiệu chỉnh là chúng ta làm gì?
Link
Mục đích:
Tài liệu phải mô tả bài toán, thuật toán, chương trình thiết kế, kết quả thử nghiệm và hướng dẫn sử dụng;
Giúp ích cho người sử dụng trong quá trình sử dụng chương trình
Giúp ích cho việc nghiên cứu và đề xuất khả năng hoàn thiện chương trình
Bước 5: Viết tài liệu.
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Mục đích của việc viết tài liệu là gì?
Cũng cố
Các bước giải bài toán trên máy tính:
Bước 1: Xác định bài toán;
là xác định Intput, Output và mối liên hệ giữa chúng
Bước 2: Lựa chọn và thiết kế thuật toán;
Lựa chọn thuật toán tối ưu, diễn tả thuật tóan bằng liệt kê hoặc SĐK
Bước 3: Viết chương trình;
Sử dụng ngôn ngữ lập trình diễn tả đúng thuật toán
Bước 4: Hiệu chỉnh;
Thử chương trình với các bộ Input đặc trưng cho các trường hợp, phát hiện lỗi và chỉnh sửa lỗi cho chương trình
Bước 5: Viết tài liệu.
Tài liệu lưu lại những gì liên quan bài toán và hướng dẫn sử dụng chương trình
Link
Cũng cố
Các bước giải bài toán trên máy tính:
Bước 1: Xác định bài toán;
là xác định Intput, Output và mối liên hệ giữa chúng
Bước 2: Lựa chọn và thiết kế thuật toán;
Lựa chọn thuật toán tối ưu, diễn tả thuật tóan bằng liệt kê hoặc SĐK
Bước 3: Viết chương trình;
Sử dụng ngôn ngữ lập trình diễn tả đúng thuật toán
Bước 4: Hiệu chỉnh;
Thử chương trình với các bộ Input đặc trưng cho các trường hợp, phát hiện lỗi và chỉnh sửa lỗi cho chương trình
Bước 5: Viết tài liệu.
Tài liệu lưu lại những gì liên quan bài toán và hướng dẫn sử dụng chương trình
Bước nào là bước
quan trọng nhất
Link
BÀI GIẢNG ĐẾN ĐÂY
KẾT THÚC
XIN CHÂN THÀNH CẢM ƠN