Giáo án: Tin học 10
Chơng i
Một số khái niệm cơ bản của tin học
Ngày soạn: 14/08/2008
Tiết CT : 01
Đ1 tin học là một ngành khoa học
I . muc tiêu:
a. Kiến thức:
-Biết tin học là một ngành khoa học.
-Biết đợc sự phát triển của tin học trong xã hội.
-Biết một số ứng dụng tin học và máy tính điện tử trong các hoạt động đời
sống.
b. Giáo dục t tởng:
- Có t tởng và thái độ đúng đắn khi học môn tin học, có ý thức học tập môn
này.
II. đồ dùng dạy học:
1. Chuẩn bị của giáo viên:
- Máy chiếu và các đoạn phim có sử dụng CNTT
2. Chuẩn bị của học sinh
- SGK
III. Kiểm tra bài cũ:
- Kiểm tra tình hình tiếp cận tin học của hs.
IV. Hoạt động dạy - học:
* Đặt vấn đề: Chúng ta nhắc đến Tin học nhng nó thực chất là gì thi ta cha đợc
biết và những hiểu biết về nó là rất ít. Vậy ta sẽ tìm hiểu về nó thông qua bài
Tin học là một ngành khoa học
1. Hoạt động 1: Tìm hiểu sự hình thành và phát triển của tin học
a. Mục tiêu: Học sinh biết đợc sự hình thành và phát triển trong xã hội hiện nay.
b. Nội dung
- Sự hình thành: Xuất hiện nhân tố mới đó là thông tin, Sự hình thành và phát
triển của nền văn minh gắn lền với công cụ lao động mới:
Đặc tính:
- Máy tính có thể làm việc đợc 24/24 giờ.
- Tốc độ xử lý thông tin nhanh, độ chính xác cao.
- MT lu trữ đợc một lợng TT lớn.
- MT liên kết thành mạng và có thể chia sẽ TT với nhau.
- Máy tính ngày càng gọn nhẹ và phỗ biến.
c. Các bớc tiến hành
* Vai trò.
- Ban đầu máy tính ra đời chỉ với mục
đích cho tính toán đơn thuần, dần dần
nó không ngừng đợc cải tiến và hỗ trợ
cho rất nhiều lĩnh vực khác nhau.
- Ngày nay máy tính đã xuất hiện khắp
nơi, chúng hỗ trợ hoặc thay thế hoàn
toàn con ngời.
- Đọc SGK và nêu lên đợc vai trò của
tin học trong cuộc sống hàng ngày.
* Một số đặc tính.
- Chia thành 4 nhóm, mỗi nhóm đa ra
một đặc tính và lấy ví dụ cụ thể cho đặc
tính đó.
- Máy tính có thể làm việc đợc 24/24
giờ.
Vd: Các máy chữ chạy 24/24
- Tốc độ xử lý thông tin nhanh, độ
Giáo viên: Nguyễn Đức Kỳ
Trang
2
Giáo án: Tin học 10
- Khẳng định lại.
* Khái niệm về Tin học
- Tin học là một ngành khoa học dựa
HS: trả lời câu hỏi.
(Tin học là một ngành khoa học có
mục tiêu là phát triển và sử dụng máy
tính điện tử để nghiên cứu cấu trúc,
tính chất TT, phơng pháp thu thập, lu
trữ, tìm kiếm, biến đổi, truyền TT và
Giáo viên: Nguyễn Đức Kỳ
Trang
3
Giáo án: Tin học 10
trên máy tính điện tử.
- Nó nghiên cứu cấu trúc, tính chất
chung của thông tin.
- Nghiên cứu quy luật phơng pháp thu
thập, biến đổi truyền thông tin và ứng
dụng của nó trong đời sống XH.
ứng dụng vào lĩnh vực khác nhau của
đời sống XH)
V. đánh giá cuối bài:
- Thông qua bài trên các em phải nắm đợc sự phát triển của Tin học
- Tầm quan trọng của nó trong đời sống
- Biết đợc tin học là gì.
Vi. Câu hỏi trắc nghiệm:
Câu 1: Thuật ngữ tin học là
a. Informatique. b. Informatics
c. Computer Science. d. Cả 3 ý trên
2. Chuẩn bị của học sinh:
- SGK
III. Kiểm tra bài cũ:
- Hãy cho biết một số thuật ngữ Tin học đợc sử dụng?
- Nêu một số đặc tính của MTĐT?
IV. Hoạt động dạy - học:
* Đặt vấn đề: Để biết về một đối tợng nào đó ta cần phải tìm hiểu các thông tin về nó.
Vậy để biết đợc Thông tin là gì, dữ liệu là gì, ta sẽ học bài Thông tin và dữ liệu
1. Hoạt động 1: Tìm hiểu k/n thông tin và dữ liệu, đơn vị đo và các dạng thông
tin.
a. Mục tiêu:
- Biết đợc TT là gì
- Phân biệt đợc các dạng thông tin
b. Nội dung
- Thông tin và dữ liệu
- Đơn vị đo thông tin
- Dạng thông tin
c. các bớc tiến hành
Nội dung Hoạt động của GV và HS TG
1. Khái niệm thông tin và dữ liệu
* Thông tin: Thông tin là sự phản ánh
các hiện tợng, sự vật của thế giới khách
quan và các hoạt động của con ngời
trong đời sống XH.
Đặt vấn đề: Trong cuộc sống XH, sự
hiểu biết về một thực thể nào đó càng
nhiều thì những suy đoán về thực thể
đó càng chính xác.
VD: Mỗi học sinh chúng ta sẽ có
Giáo viên: Nguyễn Đức Kỳ
trong 2 trạng thái hoặc đúng hoặc sai.
Do vậy ngời ta nghĩ ra đơn vị Bit để
biểu diễn TT trong máy tính.
GV: Bit là lợng TT vừa đủ để xác định
chắc chắn một sự kiện có 2 trạng thái
và khả năng xuất hiện của 2 trạng thái
đó nh nhau. Ngời ta sử dụng 2 con số
1 và 0 trng hệ nhị phân để quy ớc.
GV: Nếu 8 bóng đèn đó có bóng 3,5,7
sáng còn lại tối thì các em biểu diễn
nh thế nào.
HS: Đứng tại chỗ trả lời.
Giáo viên: Nguyễn Đức Kỳ
Trang
6
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
11001001
- Ngoài ra ngời ta còn sử dụng các đơn
vị cơ bản khác để đo TT.
1B (byte)= 8 bit
1KB=1024B
1MB=1024KB
1GB=1024MB
1TB=1024GB
1PB=1024TB
GV: 1GB bằng bao nhiêu Kb
1MB=?Byte
1GB=?KB
Trang
7
Giáo án: Tin học 10
gồm 256 ký tự đợc đánh số từ 0-255, số
hiệu này đợc gọi là mã ASCII thập phân
của kí tự. Nếu dùng 8 bit để biểu diễn
thì gọi là mã ASCII nhị phân của kí tự.
VD: Kí tự A
- Mã thập phân là 65.
- Mã nhị phân là 01000001
5. Biểu diễn thông tin trong máy tính.
a. Thông tin loại số:
- Hệ đếm và các hệ đếm dùng trong Tin
học.
Hệ đếm là tập hợp các ký hiệu và quy
tắc sử dụng tập ký hiệu đó để biểu diễn
và xác định giá trị các số.
* Có hệ đếm không phụ thuộc vào vị trí
và hệ đếm phụ thuộc vào vị trí.
- Hệ chữ cái La Mã không phụ thuộc
vào vị trí.
VD: X ở trong IX hay XI đều có nghĩa
là 10.
- Hệ đếm cơ số thập phân, nhị phân,
hexa là hệ đếm phụ thuộc vào vị trí.
VD: Số 1 trong 10 khác với số 1 trong
01.
* Nếu một số N trong hệ số đếm cơ số
b có biểu diễn là:
-m
b
-m
VD: 43,3=4.10
1
+3.10
0
+3.10
-1
Mỗi văn bản bảo gồm các kí tự thờng
và hoa và các chữ số, các dấu phép
toán. Để mã hoá thông tin dạng văn
bản ngời ta dùng mã ASCII.
GV: Biểu diễn thông tin trong máy
tính qui về 2 loại chính đó là số và phi
số, ta sẽ lần lợt tìm hiểu về nó.
Hệ đếm không phụ thuộc vào vị trí là
nó năm ở vị trí nào cũng đều mang
một giá trị, Hệ đếm phụ thuộc vào vị
trí là nó nằm ở vị trí khác nhau thì có
giá trị khác nhau.
GV: Có nhiều hệ đếm khác nhau nên
muốn phân biệt số đợc biểu diễn ở hệ
nào ngời ta viết cơ số làm chỉ số dới
của số đó.
T2
Giáo viên: Nguyễn Đức Kỳ
Trang
8
+3.16
0
=256+160+3=419
* Biểu diễn số nguyên:
- Biểu diễn số nguyên với 1 byte nh sau:
Bit 7
Bit 6
Bit 5
Bit 4
Bit 3
Bit 2
Bit 1
Bit 0
Bit 7 dùng để xác định dấu nếu 1 là số
âm, 0 là số dơng.
* Biểu diễn số thực:
- Mọi số thực đều có thể biểu diễn dới
dạng
K
Mx
10
(đợc gọi là dạng dấu
phẩy động), trong đó 0,1<=M<1, M đợc
gọi là phần định trị và K là số nguyên
không âm gọi là phần bậc.
VD: 222
7
9
01010100 01001001 01001110 biểu
diễn xâu TIN
* Các dạng khác:
- Nh âm thanh, hình ảnh...
dấu (.) và không dùng dấu nào để
ngăn cách nhóm 3 chữ số đứng liền
nhau.
VD: 67 234,23 -> 67234.23
GV: Hãy biểu diễn xâu: HOC
HS: Trả lời (dò vào bảng mã)
01001000 01001111 01000011
GV: Tại sao gọi là ảnh kỹ thuật số?
HS: Trả lời.
V. Củng cố
-Thông tin và đơn vị đo thông tin
-Cách biểu diễn thông tin
-Loại thông tin số và phi số.
VI. Câu hỏi trắc nghiệm
- Các bài tập cuối bài học.
Câu 1: Chọn phơng án ghép đúng: 1MB=
a.1024Kb b.1240byte c.1204 byte d.1402Kb
Câu 2: Biểu diễn số (010
2
) nào sau đây là đúng?
a. 0x2
3
+1x2
2
+0x2
1
+0x2
0
=5/8
10
Câu 3: Số 30
10
đợc biểu diễn ở hệ cơ số 2 là:
a. 11011 b. 10110 c. 11110 d. 10011
-----------------------------------
Ngày soạn: 27/08/2008
Tiết CT : 04
Bài tập và thực hành 1
I Mục đích, yêu cầu:
a. Kiến thức:
Giáo viên: Nguyễn Đức Kỳ
Trang
10
Giáo án: Tin học 10
- Củng cố hiểu biết ban đầu về tin học, máy tính.
- Sử dụng bộ mã ASCII để mã hoá kí tự, số nguyên
- Viết đợc số thực dới dạng dấu phẩy động.
b. Kĩ năng:
- Biết đợc cách mã hoá của máy tính
- Biết biểu diễn các hệ đếm cơ số 10,2,16
c. Giáo dục t tởng:
- Giúp cho học sinh có tính sáng tạo, tìm tòi nghiên cứu
- Hứng thú học tập hơn.
II. ổn định tổ chức lớp:
- Nắm sĩ số:
mã hoá nh thế nào.
HS: Trả lời tạ chỗ.
Giáo viên: Nguyễn Đức Kỳ
Trang
11
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
GV: ở phía sau sách có bảng mã
ASCII ta dựa vào đó để mã hoá và giãi
mã.
GV: Cho 2 hs lên giải 2 bài b1 và b2
trang 16 SGK. Sau đó đa ra các vd
khác để các em thực hiện giải mã.
3. Biểu diễn thông tin trong máy.
B1: Chuyễn 111 ở hệ cơ số 2 sang hệ cơ
số 10
B2: Chuyễn 1AE ở hệ cơ số 16 sang hệ
cơ số 10
GV:Gọi 2 hs lên bảng làm
Hd:
111
2
=1*2
2
+1*2
1
+1*2
0
=7
a. Kiến thức:
- Biết đợc chức năng các thiết bị chính của máy tính
- Biết máy tính làm việc theo nguyên lí J. Von Neumann.
b. Kĩ năng:
- Nhận biết đợc các bộ phận của máy tính.
c. Giáo dục t tởng:
- Giúp cho học sinh có tính sáng tạo, tìm tòi nghiên cứu
- Hứng thú học tập hơn.
II. ổn định tổ chức lớp:
- Nắm sĩ số:
- ổn định trật tự, tạo tâm lý tốt để bắt đầu tiết học.
III. Kiểm tra bài cũ:
- Thông tin là gì? Kể tên các đơn vị đo thông tin.
- Nêu khái niệm mã hoá thông tin, hãy biến đổi:
- 23
10
-> Cơ số 2
- 1101001
2
-> Cơ số 10.
IV. Nội dung bài mới:
* Đặt vấn đề: Tiến trớc ta đã học về thông tin và mã hoá thông tin. Hôm nay tã sẽ tiếp
tục tìm hiểu về các thành phần của máy tính qua bài Giới thiệu về máy tính
Nội dung Hoạt động của GV và HS TG
Đ3 giới thiệu về máy tính
1. Khái niệm về hệ thông tin học
-Hệ thống tin học gồm 3 thành phần:
-Phần cứng
-Phần mềm
-Sự quản lý điều khiển của con ngời.
Processing Unit)
-Bộ nhớ trong (Main Memory)
-Bộ nhớ ngoài (Sencondary Memory)
-Thiết bị vào (Input Divice)
-Thiết bị ra (Output Divice)
GV: Theo các em máy tính gồm bao
bộ phận.
HS: Trả lời.
GV: gọi hs bổ sung và ghi lại những
bộ phận đó. Nhận xét và đa ra 4 bộ
phận chính. (Bộ xử lí trung tâm, bộ
nhớ trong, bộ nhớ ngoài, thiết bị vào,
ra)
GV: Vẽ sơ đồ cấu trúc máy tính
HS: Thảo luận về các chức năng của
từng bộ phận.
GV: Gọi một số em đa ra ý kiến của
mình.
- Nhận xét, để biết rõ hơn ta se lần l-
ợt tìm hiểu từng bộ phận của nó.
3. Bộ xử lý trung tâm (CPU):
(Central Processing Unit)
-Là phần quan trọng trong máy tính, đó
là thiết bị thực hiện chơng trình. Vùng
nhớ đặc biệt của CPU sử dụng để lu trữ
tạm thời các lệnh và dữ liệu đang đợc xử
lý.
GV: CPU gồm 2 bộ phận chính
-Bộ điều khiển CU (Control Unit) điều
khiển các thiết bị khác làm việc.
diện ban đầu của máy với các CT.
-RAM (Random Acess Memory) Bộ
nhớ truy cập ngẫu nhiên, dùng để nhớ
các thông tin trong quá trình máy làm
việc, khi mất điện dl sể mất.
5. Bộ nhớ ngoài
-Bộ nhớ ngoài dùng để lu trữ thông tin
lâu dài.
-Bộ nhớ ngoài của máy tính thờng là đĩa
cứng, đĩa mềm, đĩa CD, thiết bị Flash.
GV: Đa ra các loại bộ nhớ ngoài để
học sinh quan sát,
-Các thông số về dung lợng của bộ
nhớ ngoài. Nói rõ cấu tạo của nó.GV: Hãy so sánh bộ nhớ trong và bộ
nhớ ngoài.
HS: Trả lời.
6. Thiết bị vào:
-Thiết bị vào dùng để đa thông tin vào
máy tính.
-Có nhiều loại thiết bị vào nh bản phím,
chuột, máy quét, micro webcam...
a. Bàn phím (Keyboard):
-Các phím đợc chia làm 2 nhom cơ bản.
b. Chuột (Mouse)
-Chuột có 3 nút: Nút trái, nút phải và nút
giữa.
c. Máy quét: (Scanner)
c. Máy chiếu (Projector)
-Đa nội dung màn hình ra màn ảnh
rộng.
d. Loa và tai nghe (Speaker and
Headphone)
e. Môđem (Modem):
-Dùng để truyền thông giữa các hệ
thống máy tính.
GV: Tại sao ngời ta nói màn hình có
độ phân giải là 640 x 480.
HS: Trả lời
GV: Giải thích: có 480 dòng và mỗi
dòng có 640 điểm ảnh.
GV: Em hãy kể một số loại máy in mà
em biết.
HS: Trả lời.
GV: Nói rõ hơn về chức năng của nó.
8. Hoạt động của máy tính.
-Chơng trình là một dãy lệnh, thông tin
của mỗi lệnh gốm:
- Địa chỉ của lệnh trong bộ nhớ.
-Mã của lệnh thao tác cần thực hiện.
-Địa chỉ các ô nhớ liên quan.
GV: Các em xem các nguyên lý lu trữ
chơng trình, truy cập theo địa chỉ,
phôn Nôi-man ở cuối bài.
* Ta xây dựng chơng trình sử dụng các
tấm bảng tơng tự nh ô nhớ, để thực hiện
các phép tính toán.
1
Đọc 8
Cộng 9
Ghi 12
Đọc 10
Cộng 11
Ghi 12
26
4
-10
5
Nhân 12
Dừng
12
1
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
trình)
- Tám bớc trên là một chơng trình. Vậy
ta nạp chơng trình đó vào bộ nhớ.
- Mỗi bảng ở trên tơng đơng với một ô
nhớ
-Mỗi lệnh chiếm 1 ô nhớ, có 8 lệnh
chiếm các ô nhớ từ 0-7
-Mỗi giá trị chiếm 1 ô nhớ, a,b,c,d
chiếm các ô nhớ từ 8-11
-Kết quả sẽ lu vào ô nhớ thứ 12
Nguyên lý Phôn Nây-Man:
Mã hoá nhị phân, điều khiển bằng ch-
ơng trình, lu trữ chơng trình và truy
- Xem bài cũ.
- Làm các câu hỏi cuối bài.
-------------------------------------------
Giáo viên: Nguyễn Đức Kỳ
Trang
17
Giáo án: Tin học 10
Ngày soạn: 10/9/2008
Tiết CT : 08-09
bài tập và thực hành 2
I Mục đích, yêu cầu:
a. Kiến thức:
- Làm quen với máy tính
- Sử dụng bàn phím.
- Sử dụng chuột.
b. Kĩ năng:
- Quan sát và nhận biết đợc các bộ phận chính của máy tính.
- Thao tác với chuột và bàn phím.
- Nhận thức đợc máy tính thiết kế thân thiện với con ngời.
c. Giáo dục t tởng:
- Giúp cho học sinh khái niệm về máy tính.
- Giúp cho các em tìm tòi khám phá, hứng thú học tập hơn.
II. ổn định tổ chức lớp:
- Nắm sĩ số:
- ổn định trật tự, tạo tâm lý tốt để bắt đầu tiết học.
III. Kiểm tra bài cũ:
- Vẽ sơ đồ máy tính.
- So sánh bộ nhớ trong và bộ nhớ ngoài.
- So sánh thiết bị vào và thiết bị ra, lấy một số ví dụ.
Nội dung Hoạt động của GV và HS TG
nhấn giữ phím.
- Gõ một dòng kí tự tuỳ chọn.
3.Sử dụng chuột
- Di chuyển chuột: Thay đổi vị
trí của chuột trên mặt phẳng.
- Nháy chuột: Nhấn chuột trái
rồi thả ngón tay.
- Nháy đúp chuột: Nháy chuột
nhanh 2 lần liên tiếp.
- Kéo thả chuột: Nhấn và giữ
nút trái của chuột, di chuyển
con trỏ chuột đến vị trí cần
thiết.
GV: Chuột có mấy nút.
HS: Trả lời.
V. Củng cố:
- Nhận xét buổi thực hành.
VI. Dặn dò:
- Trả lời các câu hỏi trang 28
- Đọc bài đọc thêm.
-------------------------------------------
Giáo viên: Nguyễn Đức Kỳ
Trang
19
Giáo án: Tin học 10
Ngày soạn: 18/09/2008
Tiết CT :10-11-12-13-14
Đ4 bài toán và thuật toán
HS: Trả lời tại chỗ.
GV: Trong toán học ta nhắc nhiều đến
k/n bài toán và ta hiểu đó là những
việc mã con ngời cần phải thực hiện
sau cho từ những dữ kiện đã có phải
tìm ra hay chứng minh 1 kết quả nào
đó. Vậy k/n bài toán trong tin học có
gì khác không?
GV: Trong nhà trờng có chơng trình
quản lý HS, nếu ta yêu cầu đa ra các
học sinh có điểm TBM là 9 đó là bài
toán. Hay đa ra danh sách của những
học sinh là con thơng binh đó cũng là
Giáo viên: Nguyễn Đức Kỳ
Trang
20
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
-Các yếu tố: Khi máy tính giải 1 bài
toán cần quan tâm 2 yếu tố:
+Input: (Thông tin đa vào máy tính)
+Output (Thông tin muốn lấy từ máy)
bài toán.
GV: hãy đa ra vd về bài toán trong tin
học.
HS Trả lời tại chỗ
GV: Để giải một bài toán việc đầu tiên
là gì?
HS: Trả lời: Xác định dữ kiện đã cho
-Khái niệm thuật toán: Là một dãy hữu
hạn các thao tác đợc sắp xếp theo một
trình tự xác định sao cho sau khi thực
hiện dãy thao tác đó, từ Input của bài
toán này ta nhận đợc Output cần tìm.
-Tác dụng của thuật toán: Dùng để giải
một bài toán.
VD: Thuật toán tìm UCLN của 2 số
M,N
+Input: M,N
GV: (Đặt vấn đề) Muốn cho cho máy
tính đa ra đợc Output từ Input đã cho
thì cần phải có chơng trình, mà muốn
viết đợc chơng trình thì cần phải có
thuật toán.
- Vậy thuật toán là gì?
HS: Suy nghĩ và trả lời.
GV: Đa ra k/n thuật toán. Giải thích
thêm k/n nh: Dãy hữu hạn các lệnh,
sắp xếp theo một trình tự nhất định.
GV: Đa ra vd tìm UCLN của 2 số
M,N. Xác định Input và Output của
bài toán.
Giáo viên: Nguyễn Đức Kỳ
Trang
21
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
+Output: UCLN(M,N)
GV: Vẽ sơ đồ thuật toán hoặc điều
chỉnh sửa chữa.
GV: Xoá các ghi chú Đ, S
HS: Lên bảng ghi lại những ghi chú
đó. Trình bài lại thuật toán bằng lời.
GV: Đa ra ví dụ tìm Min hoặc Max để
cho học sinh tự làm.
3. Một số ví dụ về thuật toán.
VD1: Kiểm tra tính nguyên tố của một
số nguyên dơng.
* Xác định bài toán:
-Input: N là một số nguyên dơng
b.Sơ đồ khối
Giáo viên: Nguyễn Đức Kỳ
Trang
22
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
-Output: N là số nguyên tố hoặc không
nguyên tố
* ý tởng: Một số nguyên dơng N là số
nguyên tố nếu nó có đúng 2 ớc số khác
nhau là 1 và chính nó.
-Nếu N=1 thì N Không là số nguyên tố.
-Nếu 1<N<4 thì N là số nguyên tố.
-Nếu N>=4 và không có ớc số trong
phạm vi từ 2 đến phần nguyên của căn
bậc 2 của N thì N là số nguyên tố.
-Từ đó ta có thuật toán nh sau.
,...,
a
N
. Cần sắp xếp các hạng số để dãy A
trở thành dãy không giảm.
* Xác định bài toán:
-Input: Dãy A gồm N số nguyên a
1
,a
2
,...,
a
N
.
-Output: Là dãy A đợc sắp tăng dần.
* ý tởng:Với mỗi cặp số hạng đứng liền
kề trong dãy, nếu số đứng trớc lớn hơn
số sau ta đổi chỗ chúng cho nhau. Việc
đó đợc lặp lại, cho đến khi mỗi số đứng
trớc nhỏ hơn số đứng sau.
b. Sơ đồ khối
Ghi chú: M=N, giảm M cho đến khi
M<2. i chạy từ 0 đến M+1
Giáo viên: Nguyễn Đức Kỳ
Trang
23
Giáo án: Tin học 10
Nội dung Hoạt động của GV và HS TG
*Thuật toán:
2
,..., a
N
.và 1 số 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ố đó.
*Thuật toán tìm kiếm tuần tự
(Sequential seasch)
*Xác định bài toán:
-Input: Dãy A gồm N số nguyên khác
nhau a
1
,a
2
,..., a
N
.và 1 số k.
-Output: Chỉ số i (1<=i<=N) 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.
*ý tởng: Tìm kiếm tuần tự đợc thực hiện
một cách tự nhiên. Lần lợt từ số hạng
thứ nhất, ta so sánh giá trị số hạng đang
xét với khoá cho đến khi hoặc gặp 1 số
hạng bằng khoá hoặc dãy đang xét hết.
Và không có gí trị nào bằng khoá.
(Binary Search)
*Xác định bài toán:
-Input: Dãy A là dãy tăng gồm N số
nguyên khác nhau a
1
,a
2
,..., 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ó
gí trị bằng k.
* ý tởng: Sử dụng tính chất dãy A là dãy
tăng, ta cần 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. Để làm điều đó, ta chọn
số hạng a
giữa
ở giữa dãy để so sánh với k,
trong đó giữa=
2
1
+
N
;
Khi đó, chỉ xảy ra 1 trong 3 trờng hợp
a. Cách liệt kê:
B1: Nhập N, các số hạng a
1
,a
2
,..., a
N
và
khoá k;
B2: Đầu1, Cuối N;
B3: Giữa
+
2
CuoiDau
;
Giáo viên: Nguyễn Đức Kỳ
Trang
25
Copyright: Tài liệu đại học ©