bài toán và thuật toán

Bài soạn:


BÀI TỐN VÀ THUẬT TỐN
 Home
 Mục tiêu
 Chuẩn bò của
GV & HS
 Tiến trình
lên lớp
n đònh lớp
 kiểm tra bài cũ
 bài mới
Tiết 14:



BÀI TỐN VÀ THUẬT TỐN
✓Mục tiêu:
1)Kiến thức:

Biết khái niệm bài toán và thuật toán, các tính chất của thuật
toán.
•
Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và bằng các
bước liệt kê.Hiểu một số thuật toán bằng các bước thông dung.
2)Kỹ năng: Xây dựng được thuật toán giải một số bài toán đơn
giản bằng sơ đồ khối hoặc bằng các bước liệt kê.

 Home
 Mục tiêu
 Chuẩn bò của
GV & HS
 Tiến trình
Lên lớp
n đònh lớp
 kiểm tra bài cũ
 bài mới
 Home
 Mục tiêu
 Chuẩn bò của
GV & HS
 Tiến trình
lên lớp
n đònh lớp
 kiểm tra bài cũ
 bài mới
Tiết 14:



BÀI TỐN VÀ THUẬT TỐN
✓Chuẩn bò của GV và HS:
*GV:Máy chiếu
* HS: Chuẩn bò trước sơ đồ khối ở nhà
✓Tiến trình lên lớp:
* nỔ đònh lớp.
*GV:Bài mới.
 Home
 Mục tiêu
 Chuẩn bò của
GV & HS
 Tiến trình
lên lớp
n đònh lớp
 kiểm tra bài cũ
 bài mới
Tiết 14:



BÀI TỐN VÀ THUẬT TỐN
*Kiểm tra bài cũ:
Câu hỏi: Hãy mô tả thuật toán tìm kiếm
tuần tự bằng phương pháp liệt kê (hay sơ
đồ khối). Cho dãy số A gồm: 5, 7, 1, 4, 2,
9, 8, 11, 25, 51.
Với k =1 xét xem trong dãy có số hạng
nào bằng k, nếu có hãy cho biết chỉ số
đó?
TRẢ LỜI
 Home
 Mục tiêu
 Chuẩn bò của
GV & HS
 Tiến trình
lên lớp
n đònh lớp
 kiểm tra bài cũ
 bài mới
Tiết 14:



Tập soạn giáo án
Mơn:
Phương pháp dạy học
Phương pháp dạy học



BÀI TỐN VÀ THUẬT TỐN
Thuật toán tìm kiếm tuần tự bằng phương pháp liệt kê:
B1: Nhập N, các số hạng a
1
, a
2
, a
3
, …, a
N
và khoá k
B2: i←1;
B3:Nếu a
i
=k thì thông báo chỉ số i, rồi kết thúc;
B4: i←i+1;
B5: Nếu i>N thì thông báo dãy A không có số hạng nào có giá trò bằng k, rồi kết thúc
B6: Quay lại bước 3.
 Home
 Mục tiêu
 Chuẩn bò của
GV & HS
 Tiến trình
lên lớp
n đònh lớp
 kiểm tra bài cũ
 bài mới
với k=1 thì a
3
=1
*Mô phỏng việc thực hiện thuật toán trên là:
Theo đề ta có k=1 và N=10
A 5 7 1 4 2 9 8 11 25 51
i 1 2 3 - - - - - - -
Tiết 14:



Tập soạn giáo án
Mơn:
Phương pháp dạy học
Phương pháp dạy học

Nội dung


Tiết 5:

Tiết 14:



Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán
Tiết 14:



Tiết 14:
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán
Ví dụ 4: Bài toán tìm kiếm
Cho dãy A được sắp xếp theo thứ tự tăng
dần gồm N số nguyên khác nhau : a
1
, a
2
, a
3
,
… , a
N
và một số nguyên k. Cần biết có hay
không chỉ số i (1≤i ≤N) mà a
i
=k. Nếu có
hãy cho biết chỉ số đó?

Bài tốn
cho biết
cái gì?
Và cần
tìm cái gì?

Input: Dãy A là dãy
tăng gồm N số nguyên
khác nhau a
1
, a
2
, a
3
,…,
a
N
và một số nguyên k
 Output: Chỉ số i mà
a
i
=k hoặc thông báo
không có số hạng nào
của dãy A có giá trò
bằng k.


Tiết 14:
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán



Tiết 14:
 Ví dụ
Nội dung
Đối với thuật toán tìm kiếm nhò phân nó hàm
chứa một ý tưởng và cách tư duy (“chia để trò”và
đệ quy) có thể dùng khi giải nhiều bài toán trong
tin học.
Tại mỗi bước, phạm vi tìm kiếm được thu hẹp chỉ
còn một nửa ta chia đôi dãy thành hai dãy con,
hơn kém nhau không quá một phần tử ) do đó sẽ
tăng nhanh tốc độ tìm kiếm
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán



Tiết 14:
Hãy suy nghó và cho biết ý tưởng xây dựng
thuật toán này như thế nào?
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán

Ý tưởng:


Tiết 14:
Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh
phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được
chọn. Ta chọn số hạng a
giua
ở “giữa dãy” để so sánh với k,
trong đó
Ta có ba trường hợp xãy ra như sau:
-Nếu a
giua
=k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
-Nếu a
giua
>k thì do dãy A là dãy đã được sắp xếp nên việc tìm
kiếm tiếp theo chỉ xét trên dãy a
1
, a
2
, a
3
, …, a
giua – 1
.
-Nếu a
giua
< k thì thực hiện tìm kiếm trên dãy a
Giua +1
, a
giua+2
, …,
a
N
.






+
=
2
1N
Giua
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán



Tiết 14:
Nội dung
B1: Nhập N, các số hạng a
1
, a
2
, a
3
, … , a
N
và khoá k.
B2: Dau ← 1, Cuoi ← N;
B3:
B4: Nếu a
giua
=k thì thông báo chỉ số Giua, rồi kết thúc;
B5: Nếu a
giua
>k thì đặt Cuoi = Giua -1, rồi chuyển đến bước 7;
B6: Dau = Giua + 1;
B7: Dau > Cuoi thì thông báo dãy A không có số hạng có giá trò bằng k, rồi kết
thúc;
B8: Quay lại bước 3;
THUẬT TOÁN:
a)Cách liệt kê:
;
2






+
←
CuoiDau
Giua
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán



Tiết 14:
Nội dung
Thông báo dãy A không
có số hạng có giá trò
bằng k rồi kết thúc
Nhập N và a
1
, a
2
, a
3
, … , a
N
; k
Dau 1; Cuoi N
Giua ←[(Dau+Cuoi)/2]
A
giua
=k?
Đưa ra Giua
rồi kết thúc
A
giua
> k?
Cuoi←Giua - 1
Dau←Giua +1
Dau > Cuoi ?
sai
Đúng
sai
Đúng
sai
Đúng
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán



Tiết 14:
Nội dung
Bài toán tìm kiếm
Nội dung
tưởng
Xác đònh bài toán
Xây dựngThuật toán
Mô phỏng thuật toán
Mô phỏng thuật toán
K=21, N=10
i 1 2 3 4 5 6 7 8 9
A 2 4 5 6 9 21 22 30 31 33
Dau 1 6 6
cuối
10 10 7
Giau
5 8 6
a
giua
9 30 21
Lần duyệt
1 2 3
Ở lần duyệt thứ ba thì a
giua
=k. vậy chỉ số cần tìm là:
i=Giua=6

Xem chi tiết: bài toán và thuật toán