CHÀO MỪNG QUÝ THẦY -
CÔ GIÁO
VỀ DỰ GIỜ THĂM LỚP
Sốp Cộp, ngày 28 tháng 10 năm 2014
LỚP 10B3
Cho bài toán:
Hãy tìm ước số chung lớn nhất (ƯSCLN) của hai số nguyên dương M và N?
Với:
1) M=5; N=10; (Nhóm 1)

2) M=15; N= 20; (Nhóm 2)

3) M=97; N=65; (Nhóm 3)

4) M=240; N=450; (Nhóm 4)


Các nhóm ghi kết quả vào phiếu!

Em có nhận xét gì về cách sử dụng máy tính để giải bài toán?
Đứng trước một bài toán ta cần làm gì (hay quan tâm đến các yếu tố (thành phần) nào)?

Bài toán: Cho dãy A gồm N số nguyên khác nhau: a1,a2,…,aN và một số nguyên k. Cần biết có hay không chỉ số i (1≤ i ≤N) mà ai=k. Nếu có hãy cho biết chỉ số đó.
(Ví dụ 3. Bài toán tìm kiếm- SGK trang40)
Hãy xác định bài toán trên?

Xác định bài toán:

- Input: Dãy A gồm N số nguyên khác nhau: a1,a2,…,aN và một số nguyên k;

- Output: Chỉ số i mà ai=k hoặc thông báo dãy A không có số hạng nào có giá trị bằng k.


Mô phỏng thuật toán: Với N=8 và k=19
Với i=6 thì ai=19.
Ở lần duyệt thứ 2 thì aGiua =k=19.
Vậy chỉ số cần tìm là i = Giua = 6
Tìm kiếm nhị phân
Tìm kiếm tuần tự
Mô phỏng thuật toán: Với N=8 và k=10
Với mọi i từ 1 đến 8 không có giá trị bằng 10.
Ở lần duyệt thứ 4 thì Dau> Cuoi nên kết luận trong dãy A không có số hạng nào có giá trị là 10.
Tìm kiếm nhị phân
Tìm kiếm tuần tự
Ví dụ (SGK Trang 48): Tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương M và N.
*) Thuật toán bằng cách liệt kê các bước:


Bước 1: Nhập M, N;

Bước 2: Nếu M = N thì đưa ra ƯCLN(M,N) = M 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.

Mô phỏng việc thực hiện thuật toán: Tìm ƯSCLN(M,N)=?

Với: M=10; N=25:
M=10
N=25
N←N-M
M=10
N=15
Lần duyệt thứ 1
N←N-M
Lần duyệt thứ 2
M=10
N=5
M←M-N
Lần duyệt thứ 3
M=5
N=5
=>ƯSCLN(10,25)= 5
Kết quả
Nhập M và N
Sơ đồ khối
M=N?
M>N?
N←N-M
M←M-N
Đưa ra M rồi kết thúc
Sai
Sai
Đúng
Đúng
Thuật toán: Tìm ước số chung lớn nhất của hai số nguyên dương M,N.
Tài liệu phải mô tả đầy đủ và giải thích chi tiết về:

Bài toán: Input và Output là gì?

Thuật toán:
+) Có những thuật toán nào khả thi?
+) cuối cùng thuật toán được chọn là gì?
+) Vì sao chọn thuật toán đó?
+) Các bước thực hiện nó ra sao?
…

Thiết kế chương trình: Sử dụng ngôn ngữ lập trình nào?

Kết quả thử nghiệm?

- Hướng dẫn sử dụng.
Câu hỏi củng cố
Hãy ghép các đặc điểm tương ứng ở cột bên phải với các bước thực hiện giải bài toán trên máy tính ở cột bên trái?
Đáp án đúng:

Trân trọng cảm ơn.