Tìm kiếm theo tiêu đề

Tìm kiếm Google

Quảng cáo

Quảng cáo

Hướng dẫn sử dụng thư viện

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (04) 66 745 632
  • 0166 286 0000
  • contact@bachkim.vn

Bài 9. Tin học và xã hội

Tham khảo cùng nội dung: Bài giảng, Giáo án, E-learning, Bài mẫu, Sách giáo khoa, ...
Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn:
Người gửi: Nguyễn Thanh Vũ
Ngày gửi: 18h:30' 12-10-2017
Dung lượng: 3.0 MB
Số lượt tải: 72
Số lượt thích: 0 người
1
Bài 4: Bài toán và Thuật toán(tt)
TIẾT 13+14: THUẬT TOÁN TÌM KIẾM TUẦN TỰ VÀ TÌM KIẾM NHỊ PHÂN
2
Tớ là một chú cá . Hãy tìm tớ trong đám bạn này nhé!!
1
2
3
4
5
Không phải rồi!
Ồ! Không phải nữa rồi!

Ồ! Lại sai nữa rồi!
Hi! Hi! Chưa đúng đâu nghen!
A! Ha! Tìm ra rồi!
3
XÁC ĐỊNH BÀI TOÁN
OUPUT
INPUT
Dãy A gồm N số nguyên khác nhau a1,a2,…,aN và số nguyên k
Chỉ số i mà ai=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
TÌM KIẾM TUẦN TỰ
(Sequential Search)
4
TÌM KIẾM TUẦN TỰ
(Sequential Search)
Ý tưởng:
Lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đó với khóa cho đến khi gặp một số hạng bằng khóa thì số hạng đó là số hạng cần tìm.
Trong trường hợp thứ hai, dãy không có số hạng nào bằng khóa.
5
TÌM KIẾM TUẦN TỰ
Ví dụ:
Dãy A gồm các số
1
4
2
9
8
11
5
7
a1 a2 a3 a4 a5 a6 a7 a8
N=8
K=9





||
Tìm thấy
, có a6=k, vậy chỉ số cần tìm là i=6
K=6
, không có giá trị nào



Không tìm thấy
6
Ví dụ thuật toán tìm kiếm tuần tự
2
3
4
5
6
SAI
ĐÚNG
VẬY i = 6
7
Thuật toán tìm kiếm tuần tự
SƠ ĐỒ KHỐI
B1. Nhập N, a1,a2,…aN, khóa k;
B2. i1;
B3. Nếu ai=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.
LIỆT KÊ
Nhập N, a1,a2….,aN,k
i1
ai=k
Đưa ra i rồi
kết thúc
ii+1
i>N?
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
Đúng
Sai
Đúng
Sai
8
Nhập N, a1,…,aN,k
ai = k
i > N
Đưa ra i rồi kềt thúc
SAI
ĐÚNG
i  i + 1
i  1
i = 2
i = 3
i = 4
i = 1
SAI
Với i = 4 thì a4 = 2
THUẬT TOÁN TÌM KIẾM TUẦN TỰ
(Sequentinal Search)
N = 6; k = 2
a1 = 5
i = 2 < N
a2 = 7
i = 3 < N
a3 = 1
i = 4 < N
a4 = 2
Ví dụ
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
9
Em có suy nhận xét gì sau khi xem xong?
Người đọc sách muốn tìm trang 30 của quyển sách.
Người ấy bắt đầu mở chính giữa quyển sách
Số trang vừa mở được là trang 44.(chưa tìm đúng số trang cần tìm)
Như vậy người ấy chỉ tìm trong phạm vi từ số trang từ đầu cho đến trang 44 (không cần tìm phần sau trang 44 )
Tiếp tục phân đôi số trang từ trang đầu cho đến trang 44. Trang tìm được là trang 22, cứ tiếp tục như vậy cho đến khi tìm được trang 30.
10
Thuật toán tìm kiếm nhị phân
(dãy A tăng)
OUPUT
INPUT
Dãy A tăng gồm N số nguyên khác nhau a1,a2,…,aN và số nguyên k
Chỉ số i mà ai=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
Xác định bài toán
11
Ý tưởng
aGiữa=k
aGiữaChọn aGiữa ở giữa dãy để so
sánh với k, trong đó Giữa=
Giữa là chỉ số cần
tìm. Kết thúc
Tìm kiến trên dãy
aGiữa+1,,,aN
aGiữa>k
Việc tìm kiếm
chỉ xét trên dãy
a1,…,aGiữa-1
Quá trình lặp lại cho đến khi hoặc tìm thấy k hoặc vi phạm tìm kiếm bằng rỗng
12
150
84
6
75
9
8
7
5
4
3
2
1
i
38
15
7
2
A
Biểu diễn thuật toán :
k = 150
Lượt thứ nhất: aGiữa là a5 = 75; 75 < 150
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a9
151
90
 vùng tìm kiếm thu hẹp trong phạm vi từ a8 a9
13
50
39
75
11
30
6
9
10
9
8
7
5
4
3
2
1
i
8
6
5
1
A
k = 14
Lượt thứ nhất: agiữa là a5 = 9; 9 < 14
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a10
Lượt thứ hai: agiữa là a8 = 39; 39 > 14
 vùng tìm kiếm thu hẹp trong phạm vi từ a6 a7;
Lượt thứ ba: agiữa là a6 = 11; 11 < 14
 vùng tìm kiếm thu hẹp chỉ còn a7;
Lượt thứ tư: agiữa là a 7 = 30 > 14
 Cuối=Giửa - 1 = 6 > đầu = 7
 Thông báo không tìm thấy số hạng có giá trị bằng 14.
14
Thuật toán liệt kê
B1. Nhập N, a1,a2,…aN, khóa k;
B2. Dau1, CuoiN;

B3. Giữa 

B4. Nếu aGiữa=k thì thông báo chỉ số Giữa rồi kết thúc;
B5.Nếu aGiữa>k thì đặt Cuoi=Giua-1, rồi chuyển đến bước 7
B6. DauGiua+1;
B7. Nếu Dau>Cuoi thì thông báo dãy A không có số hạng có gíá trị bằng k rồi kết thúc
B8. Quay lại B3
LIỆT KÊ
Chọn aGiữa ở giữa dãy để so
sánh với k, trong đó Giữa=
aGiữa=k
Giữa là chỉ số cần
tìm. Kết thúc
aGiữa>k
Việc tìm kiếm
chỉ xét trên dãy
a1,a2,…,aGiữa-1
aGiữaTìm kiến trên dãy
aGiữa+1,aGiữa+2,
…,aN
Quá trình lặp lại cho đến khi hoặc tìm thấy
k hoặc vi phạm tìm kiếm bằng rỗng
15
SƠ ĐỒ KHỐI
Nhập N và a1,a2,..,aN;k
Dau1;Cuoi1
Giua[(Dau+Cuoi)]/2
aGiua=k?
Dua ra Giua roi
ket thuc
aGiua>k
CuoiGiua-1
DauGiua+1
Dau>Cuoi?
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
Đúng
Đúng
Đúng
Sai
Sai
Sai
B1. Nhập N, a1,a2,…aN, khóa k;
B2. Dau1, CuoiN;
B3. Giữa [(Dau+Cuoi)]/2
B4. Nếu aGiữa=k thì thông báo chỉ số Giữa rồi kết thúc;
B5.Nếu aGiữa>k thì đặt Cuoi=Giua-1, rồi chuyển đến bước 7
B6. DauGiua+1;
B7. Nếu Dau>Cuoi thì thông báo dãy A không có số hạng có gíá trị bằng k rồi kết thúc
B8. Quay lại B3
16
Nhập N và a1,a2,..,aN;k
Dau1;CuoiN
Giua[(Dau+Cuoi)]/2
aGiua=k?
Dua ra Giua roi
ket thuc
aGiua>k
CuoiGiua-1
DauGiua+1
Dau>Cuoi?
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
Đúng
Đúng
Đúng
Sai
Sai
Sai
SƠ ĐỒ KHỐI
K=21, N=9
1
9
5
9
6
7
9
22
6
6
6
21
Chỉ số cần tìm i=Giua=6
1
2
3
Avatar

FAKE

 
Gửi ý kiến