Baøi Toaùn
Tìm Kieám Nhò Phaân
KIỂM TRA BÀI CŨ
A. Kiểm Tra Bài Cũ

1/ Haõy trình baøy yù töôûng cuûa baøi toaùn tìm kieám tuaàn töï?
Trả lời :
Lần lượt so sánh từng số hạng trong dãy A với khóa cần tìm cho đến khi hoặc tìm thấy một số hạng bằng khóa hoặc dãy đã xét hết và không có giá trị nào bằng khóa.
2/ Cho daõy A = 3 6 7 9 11 14 18 20 vaø k = 18
Hãy cho biết dãy A có tính chất gì?
Trả lời :
Dãy A là một dãy có thứ tự không giảm
Máy tính sẽ thực hiện đến lần thứ mấy thì sẽ tìm thấy được k trong dãy A?
Trả lời :
Đến lần thứ 7 thì sẽ tìm được k trong dãy A
BÀI TOÁN TÌM KIẾM NHỊ PHÂN
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
MỤC ĐÍCH YÊU CẦU
- Bieát moät baøi toaùn coù theå ñöôïc giaûi baèng nhieàu thuaät toaùn khaùc nhau
- Hieåu ñöôïc yù töôûng cuûa baøi toaùn tìm kieám nhò phaân
- Bieát trình baøy thuaät toaùn theo hai caùch lieät keâ vaø sô ñoà khoái
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
C. Nội Dung
NỘI DUNG
1. Xét ví dụ :
1. Xét ví dụ :
- Giả sử, có một tấm bìa được kẽ các ô vuông bằng nhau trên cả hai mặt tấm bìa và được đánh số thứ tự trên một mặt. Mặt còn lại tiến hành điền vào các giá trị số khác nhau theo thứ tự từ nhỏ đến lớn,theo chiều từ trái sang phải.
- Có hai học sinh đố nhau. Làm cách nào để cắt ra được một ô vuông có giá trị bất kỳ, sao cho số lần cắt là ít nhất (với điều kiện là học sinh cắt bìa không được nhìn thấy giá trị các số ghi trên mỗi ô vuông)
Mặt 1 :
Mặt 2 :
BÀI TOÁN TÌM KIẾM NHỊ PHÂN
- Giả sử cần cắt ra ô vuông có giá trị là :
BÀI TOÁN TÌM KIẾM NHỊ PHÂN
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
C. Nội Dung
1. Xét ví dụ :

Học sinh 1 :
Học sinh 2 :
Kiểm tra ô vuông có giá trị cần cắt

Học sinh 1 :
Học sinh 2 :
Kiểm tra ô vuông có giá trị cần cắt

Học sinh 1 :
Học sinh 2 :
Đưa ra ô vuông có chứa giá trí cần cắt
BÀI TOÁN TÌM KIẾM NHỊ PHÂN
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
C. Nội Dung
2. Xác định bài toán :
Input :
Output :
2. Xác định bài toán :
Input
Output
Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, ... , aN và một số nguyên k
Chỉ số i mà ai = k hoặc thông báo không tìm thấy k trong dãy A
1. Xét ví dụ :
BÀI TOÁN TÌM KIẾM NHỊ PHÂN
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
C. Nội Dung
3. Ý tưởng :
Sử dụng tính chất dãy A là dãy tăng, ta chia đôi dãy thành hai dãy con, phạm vi tìm kiếm sẽ được thu hẹp sau mỗi lần so sánh khóa với số hạng được chọn.
Ta chọn số hạng aGiữa để so sánh với k, trong đó:
2. Xác định bài toán :
Input
Output
- Nếu aGiữa = k
3. Ý tưởng :
Giua = [(N + 1) / 2]
thì đưa ra Giua, rồi kết thúc
- Nếu aGiữa > k
- Nếu aGiữa > k thì phạm vi tìm kiếm được thu hẹp lại trên nữa dãy đầu so với dãy ban đầu
- Nếu aGiữa < k
- Nếu aGiữa < k thì phạm vi tìm kiếm được thu hẹp lại trên nữa dãy sau so với dãy ban đầu
1. Xét ví dụ :
BÀI TOÁN TÌM KIẾM NHỊ PHÂN
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
C. Nội Dung
2. Xác định bài toán :
Input
Output
3. Ý tưởng :
1. Xét ví dụ :
4. Thuật toán :
4. Thuật toán :
a) Liệt kê :
Liệt kê
Bước 1 :
Nhập N, các số hạng a1, a2, ... , aN và khóa k
Bước 2 :
Dau ? 1 , Cuoi ? N
Bước 3 :
Giua ? [(Dau+Cuoi)/2]
Bước 4 :
Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc.
Bước 5 :
Nếu aGiua > k thì Cuoi = Giua - 1, rồi chuyển đến bước 7
Bước 6 :
Dau ? Giua + 1
Bước 7 :
Nếu 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
Bước 8 :
Quay lại bước 3
A. Kiểm Tra Bài Cũ

B. Mục Đích Yêu Cầu
C. Nội Dung
2. Xác định bài toán :
Input
Output
3. Ý tưởng :
1. Xét ví dụ :
4. Thuật toán :
Liệt kê
Đưa ra vị trí Giua, rồi kết thúc
Nhập N; dãy a1,. . . ,aN ; K
Dau  1 ; Cuoi  N
Giua ? [ (Dau + Cuoi)/2 ]
AGiua = K?
AGiua >K?

Dau ? Giua + 1
Cuoi ? Giua -1
Thông báo K không có trong dãy số A , rồi kết thúc
Dau > Cuoi?
Bước 1 :
Nhập N, các số hạng a1, a2, ... , aN và khóa k
Bước 2 :
Dau ? 1 , Cuoi ? N
Bước 3 :
Giua ? [(Dau+Cuoi)/2]
Bước 4 :
Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc.
Đ
S
Bước 5 :
Nếu aGiua > k thì Cuoi = Giua-1, rồi chuyển đến bước 7
Đ
S
Bước 6 :
Dau ?Giua + 1
Bước 7 :
Nếu 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
Đ
S
Bước 8 :
Quay lại bước 3
b) Sơ đồ khối :
Sơ đồ khối
Mô phỏng
Đưa ra vị trí Giua rồi kết thúc
Nhập N; dãy a1,. . . ,aN ; K
Dau  1 ; Cuoi  N
Giua ? [ (Dau + Cuoi)/2 ]
AGiua = K?
AGiua >K?

Dau ? Giua + 1
Cuoi ? Giua -1
Thông báo K không có trong dãy số A , rồi kết thúc
Dau > Cuoi?
Đ
S
Đ
S
S
N = 10
K = 21
Giua
Nhập N; dãy a1,. . . ,aN ; K
Dau  1 ; Cuoi  N
Giua ? [ (Dau + Cuoi)/2 ]
AGiua = K?
K = 21
AGiua >K?

Dau ? Giua + 1
Dau > Cuoi?
Giua ? [ (Dau + Cuoi)/2 ]
AGiua = K?
S
AGiua >K?

Cuoi ? Giua -1
S
Dau > Cuoi?
Giua ? [ (Dau + Cuoi)/2 ]
AGiua = K?
Đưa ra vị trí Giua rồi kết thúc
Giua = 6
21
CỦNG CỐ

1/ Haõy cho bieát ñieàu kieän caàn phaûi coù ñeå coù theå söû duïng thuaät toaùn tìm kieám nhò phaân ?
Trả lời :
Dãy đã cho phải là một dãy có thứ tự.
2/ Haõy so saùnh thôøi gian thöïc hieän giöõa thuaät toaùn tìm kieám tuaàn töï vaø tìm kieám nhò phaân
Hãy mô phỏng việc thực hiện tìm kiếm nhị phân, với khóa cần tìm k = 6 ?
Hãy mô phỏng việc thực hiện tìm kiếm nhị phân, với khóa cần tìm k = 15 ?
A. Kiểm Tra Bài Cũ
B. Mục Đích Yêu Cầu
C. Nội Dung
2. Xác định bài toán :
Input
Output
3. Ý tưởng :
1. Xét ví dụ :
4. Thuật toán :
Liệt kê
Sơ đồ khối
D. Củng Cố
Mô phỏng
Trả lời :
Thời gian thực hiện tìm kiếm của thuật toán nhị phân nhanh hơn thuật toán tuần tự, hạn chế đáng kể số lượng phép toán so sánh trong thuật toán.
3/ Cho daõy A = 3 6 7 9 11 14 18 20
Kính chúc sức khỏe quí thầy cô
Các em học sinh học tập tiến bộ