CHÀO QUÝ THẦY CÔ VÀ CÁC EM HỌC SINH
LỚP 10C3
GV:Hoa Oải Hương
KIỂM TRA BÀI CŨ
Ngôn ngữ lập trình là gì? Nêu các loại ngôn ngữ lập trình mà em đã học? Trong các ngôn ngữ lập trình đó thì ngôn ngữ nào được phát triển nhất? Vì sao?
?
Ngôn ngữ lập trình: là ngôn ngữ dùng để viết chương trình
Các loại: Ngôn ngữ máy, Hợp ngữ, ngôn ngữ bậc cao.
Ngôn ngữ lập trình được phát triển nhất: Là ngôn ngữ bậc cao. Vì đây là ngôn ngữ gần gũi với tự nhiên hơn, tạo môi trường làm việc dễ dàng hơn cho con người.
3
CHỦ ĐỀ: BÀI TOÁN VÀ THUẬT TOÁN
BÀI TOÁN VÀ THUẬT TOÁN
NGÔN NGỮ LẬP TRÌNH
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Ngôn ngữ máy
BÀI TOÁN
THUẬT TOÁN
Liệt kê hoặc sơ đồ khối
Input
Output
Hợp ngữ
Ngôn ngữ bậc cao
Khi giải bài toán bằng tay chúng ta cần thực hiện theo những bước nào?
?
Giải bài toán trên máy tính thông qua 5 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 5: Viết tài liệu
B1: Tìm hiểu đề
B2: Xác định dạng bài toán và chọn cách giải
B3: Giải bài toán
B4: Kiểm tra lại kết quả
B5:Trình bày lời giải cho bài toán
Để giải được bài toán trên máy tính ta phải tiến hành mấy bước, đó là những bước nào?
?
Xác định bài toán
Xác định bài toán là cần phải xác định cái gì? Và xác định nhằm mục đích gì?
?
Xác định rõ 2 thành phần:
- INPUT
- OUTPUT
Từ đó, xác định NNLT và lựa chọn thuật toán thích hợp
VD: Giải phương trình bậc hai:
ax2 + bx + c = 0 (a# 0)
Hãy xác định Input và Output của bài toán?
+Input: Nhập hệ số a, b, c (a#0)
+Output: Kết luận nghiệm của phương trình
-Pt VN
-Pt có nghiệm kép
-Pt có 2 nghiệm phân biệt x1 và x2
Cho a=1, b=-3, c=2 thì ta có pt x2 – 3x + 2 = 0.
Theo em, pt này có mấy cách giải?
?
Xác định bài toán
2. Lựa chọn hoặc thiết kế thuật toán:
Xác định rõ 2 thành phần: INPUT và OUTPUT
- Là bước quan trọng nhất để giải một bài toán.
- Mỗi thuật toán chỉ giải 1 bài toán, nhưng một bài toán có thể có nhiều thuật toán để giải. Chọn thuật toán tối ưu nhất.
Cho a=1, b=-3, c=2 thì ta có pt x2 – 3x+2 = 0.
?
- 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 ngắn gọn
* Thời gian thực hiện nhanh
* Tốn ít bộ nhớ
a. Lựa chọn thuật toán:
b. Diễn tả thuật toán:
VD: Giải phương trình bậc hai:
ax2 + bx + c = 0 (a# 0)
* Xác định bài toán:
* Ý tưởng:
- Tính Delta (D)
- Nếu D<0 pt VN
- Nếu D=0 pt có nghiệm kép x=-b/2a
- Nếu D>0 pt có 2 nghiệm phân biệt x1 và x2
* Thuật toán:
Chọn thuật toán tối ưu nhất
C1: Tính Delta và áp dụng công thức nghiệm
C2: Nhẩm nghiệm: Lấy giá trị bất kỳ đưa vào pt xem có phải là nghiệm hay không?
b. Diễn tả thuật toán:
2. Lựa chọn hoặc thiết kế thuật toán:
B1: Nhập a, b, c (a#0)
B2: D b2 – 4ac
B3: Nếu D<0 thì kl pt VN, rồi kết thúc. (ngược lại sang b4)
B4: Nếu D=0 thì kl pt có nghiệm kép x = - b/2a, rồi kết thúc
B5: Nếu D>0 thì kl pt có 2 nghiệm phân biệt x1, x2, rồi kết thúc.
Liệt Kê
b. Diễn tả thuật toán:
2. Lựa chọn hoặc thiết kế thuật toán:
Sơ đồ khối
Nhập a,b,c
D b2 – 4ac
D < 0
PT vô nghiệm
rồi kt
D = 0
PT có nghiệm kép
rồi kt
PT có 2 nghiệm pb
rồi kt
B1
B2
B3
B4
B5
Đ
Đ
S
S
b. Diễn tả thuật toán:
2. Lựa chọn hoặc thiết kế thuật toán:
Mô phỏng thuật toán giải phương trình bậc hai
a,b,c= 1 3 5
D = 3*3 - 4*5 = - 11
D=-11 < 0
PT vô nghiệm
D
= 0
S
PT có 2 nghiệm pb
Đ
S
D b2 - 4ac
Nhập vào a,b,c
D < 0
Đ
b. Diễn tả thuật toán:
2. Lựa chọn hoặc thiết kế thuật toán:
Mô phỏng thuật toán giải phương trình bậc hai
a,b,c= 1 3 -4
D = 9 + 16 = 25
PT vô nghiệm
PT có nghiệm kép
S
PT có nghiệm pb
đ
S
D b2 - 4ac
Nhập vào a,b,c
D < 0
đ
D = 0
PT có nghiệm x1 = 1
x2 = -4
b. Diễn tả thuật toán:
2. Lựa chọn hoặc thiết kế thuật toán:
Mô phỏng thuật toán giải phương trình bậc hai
a,b,c= 1 2 1
D = 2*2 - 4*1*1 = 0
D=0
PT vô nghiệm
S
PT có 2 nghiệm pb
Đ
S
D b2 - 4ac
Nhập vào a,b,c
D < 0
Đ
D = 0
PT có nghiệm kép
x=-1
Xác định bài toán
2. Lựa chọn hoặc thiết kế thuật toán:
Xác định rõ 2 thành phần: INPUT và OUTPUT
a. Lựa chọn thuật toán: Chọn tt tối ưu nhất
b. Diễn tả thuật toán:
Bằng cách nào để máy tính hiểu được thuật toán?
?
3. 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 NNLT để diễn đạt đúng thuật toán.
Dùng NNLT
diễn đạt đúng thuật toán
Xác định bài toán
2. Lựa chọn hoặc thiết kế thuật toán:
Xác định rõ 2 thành phần: INPUT và OUTPUT
a. Lựa chọn thuật toán: Chọn thuật toán tối ưu nhất
b. Diễn tả thuật toán:
Chương trình khi viết xong thì có đảm bảo rằng là hoàn toàn đúng không?
?
3. 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 NNLT để diễn đạt đúng thuật toán.
4. Hiệu chỉnh:
Là quá trình thử lại chương trình với nhiều bộ Input khác nhau cho ra output tương ứng. Nếu có sai sót, ta sửa chương trình rồi thử lại.
VD: Kiểm chứng nghiệm của pt bậc hai:
ax2 + bx + c = 0 (a# 0)
Với các bộ input sau:
a=1; b= -5; c=6
a=1; b= -4; c=4
a=1; b=4; c=8
Xác định bài toán
2. Lựa chọn hoặc thiết kế thuật toán:
Xác định rõ 2 thành phần: INPUT và OUTPUT
a. Lựa chọn thuật toán: Chọn thuật toán tối ưu nhất
b. Diễn tả thuật toán:
3. Viết chương trình: Lựa chọn cách tổ chức dữ liệu và sử dụng NNLT để diễn đạt đúng thuật toán.
4. Hiệu chỉnh: Thử lại chương trình
Là tổng hợp lại từ việc mô tả 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 chương trình.
5. Viết tài liệu:
Mục đích của việc viết tài liệu là gì?
?
Chú ý: các bước trên có thể lặp đi lặp lại nhiều lần cho đến khi ta cho rằng chương trình đã làm việc đúng đắn và hiệu quả.
Câu hỏi trắc nghiệm
Câu 1: Giải bài toán trên máy tính được tiến hành qua mấy bước?
A. 2 bước B. 3 bước C. 4 bước D. 5 bước
Câu 2: Tiêu chí lựa chọn hoặc thiết kế thuật toán là?
Hiệu quả về thời gian B. Hiệu quả về không gian
C. Khả thi khi cài đặt D. Tất cả đều đúng
Câu 3: Viết chương trình là?
A. Biểu diễn thuật toán
B. Dùng NNLT để diễn đạt bài toán
C. Dùng NNLT và cấu trúc dữ liệu thích hợp để diễn tả thuật toán
D. Tất cả đều đúng
D. 5 bước
D. Tất cả đều đúng
C. Dùng ngôn ngữ lập trình và cấu trúc dữ liệu thích hợp để diễn tả thuật toán
16
Lựa chọn thuật toán
Lựa chọn hoặc thiết kế thuật toán
GIẢI BÀI TOÁN TRÊN MÁY TÍNH
Xác định bài toán
Viết chương trình
Hiệu chỉnh
Viết tài liệu
Input
Output
Chọn ngôn ngữ lập trình phù hợp.
Tổ chức dữ liệu
Test và sửa sai sót.
Mô tả chương trình
Hướng dẫn sử dụng
CỦNG CỐ
BÀI TẬP VỀ NHÀ
Hãy viết thuật toán giải phương trình bậc nhất ax + b = 0 và đề xuất các bộ Test tiêu biểu
Chúc các em học tốt!
GV:Hoa Oải Hương
nguon VI OLET
