Giáo án bài Thuật toán và bài toán - Tin học 10 - GV.Lê T.Giang

Chia sẻ: Lê Trúc Giang | Ngày: | Loại File: DOC | Số trang:27

Thêm vào BST

Báo xấu

768
lượt xem 43
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Với nội dung của bài Thuật toán và bài toán học sinh 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 liệt kê các bước, hiểu một số thuật toán thông dụ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 liệt kê các bước. Quý thầy cô cũng có thể tham khảo để có thêm tài liệu soạn giáo án.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo án bài Thuật toán và bài toán - Tin học 10 - GV.Lê T.Giang

GIÁO ÁN TIN HỌC 10 Tuần……. Tiết ……. § 4. BÀI TOÁN VÀ THUẬT TOÁN  I. Mục tiêu 1. Về 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 liệt kê các bước; Hiểu một số thuật toán thông dụng. 2. Về 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 liệt kê các bước. 3. Về tư duy và thái độ: Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn học trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã hội tin học hóa. II. CHUẨN BỊ 1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, … 2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập. III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC - Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp, thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm. - Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu có).
IV. TIẾN TRÌNH BÀI HỌC 1. Ổn định lớp, Kiểm tra sĩ số 2. Kiểm tra bài cũ: - Máy tính chưa có phần mềm có thể hoạt động được không? Vì sao? - Em biết gì về khái niệm: Lệnh, chương trình, từ máy? - Hãy cho ví dụ thiết bị nào vừa là thiết bị vào và thiết bị ra không? - Hãy trình bày hiểu biết của em về nguyên lý Phôn – Nôi man? 3.Tiến trình bài học mới: TG HOẠT ĐỘNG CỦA HOẠT ĐỘNG CỦA NỘI DUNG BÀI DẠY GIÁO VIÊN HỌC SINH Hoạt động 1: ! HS thảo luận: 1.Khái niệm bài toán: Hãy định nghĩa bài toán Bài toán trong tin học là Bài toán là một việc nào đó ta trong tin học? Cho ví dụ một việc nào đó ta muốn muốn máy tính thực hiện. về bài toán trong tin học? máy tính thực hiện. Ví dụ: Giải pt bậc 2, quản lý Khi cho máy giải bài Ví dụ: Đánh văn bản, nhân viên… toán ta cần quan tâm nghe nhạc. Khi giải bài toán có 2 yếu tố: những yếu tố nào? ! Hs thảo luận và cho ví + Đưa vào máy thông tin gì? Xem cãc ví dụ 1,2,3,4 dụ. (Input) và các em hãy cho ví dụ + Cần lấy ra thông tin gì? từng trường hợp cụ thể (Output) để xem Input và Output ? Vì vậy cần phải nói rõ Input và Hãy nhận xét mói quan Output và mối quan hệ giữa hệ giữa Input và Out put. Input và Output. • Các bài toán được cấu tạo bởi 2 thành phần cơ bản:
+ Input: các thông tin đã có. + Output: Các thông tin cần tìm Hoạt động 2: từ Output. ? Làm thế nào để tìm ra !Ta chỉ ra thuật toán của 2. Khái niệm thuật toán: Output? bài toán. Thuật toán để giải một bài toán ? Thế nào là thuật toán !Thuật toán là ta chỉ ra là một dãy hữu hạn các thao tác (Arithmetic) cách tìm Output. được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện ? Nêu các bước giải bài dãy thao tác ấy, từ Input của bài toán? ! Có 3 bước: Xác định bài toán, ta nhận ra Output cần tìm. Ví dụ: Tìm giá trị lớn toán, đưa ra ý tưởng, Tìm Ví dụ: Tìm giá trị lớn nhất của nhất của một dãy số thuật toán. 1 dãy số nguyên. nguyên Ta có 3 bước thực hiện như * Xác định bài toán: sau: Hãy xác định các bước Input: Cho dãy số + Xác định bài toán bài toán trên? nguyên + Ý tưởng. Giảng các bước thực Output: Giá trị lớn nhất + Thuật toán hiện trong SGK, cho ví của dãy số. Minh họa 3 bước trong sách dụ 3 số 5, 3, 9 và minh * Ý tưởng: Ta nhớ giá trị giáo khoa, cho ví dụ cụ thể. hoạt theo các bước. Mời đầu tiên, sau đó so sánh Hướng dẫn chi tiết sơ đồ khối, 1 hs cho ví dụ 3 số và với các số khác nếu bé các hình thoi, chữ nhật, ô van, thực hiện các bước giải hơn giá trị nào thì nhớ giá mũi tên. bài toán. trị đó. Ví dụ: Mô phỏng việc thực Ví dụ: Mô phỏng việc * Thuật toán:……… hiện thuật toánvới N=8 và dãy thực hiện thuật toán trên * Các nhóm học sinh thực số: với N = 8 số sau: 3 5 6 1 hiện, và trình bày. 5,1,4,7,6,3,15,11 7 2 9 13 Ds 5 1 4 7 6 3 1 11
Phát phiếu học tập các + Học sinh đại diện 5 i 2 3 4 5 6 7 8 9 nhóm thảo luận, theo yêu nhóm của mình trình bày. Ma 5 5 5 7 7 7 1 1 cầu: Các hs còn lại xem xét bổ x 5 5 Xác định 3 bước của bài sung. + Lưu bảng bài làm của hs. toán + xác định bài toán. • Ta thấy thuật toán có một số + Ý tưởng. tính chất sau: + Thuật toán. Qua 2 ví dụ trên chúng ta + Tính dừng: Thuật toán phải thảo luận xem thuật toán Thuật toán có 3 tính chất: kết thúc sau một số hữu hạn có những tính chất nào? Tính dừng. lần thực hiện các thao tác. Phân tích ví dụ thuật Tính xác định. toán tìm số nguyên lớn Tính đúng đắn. + Tính xác định: Sau một số nhất trên. lần thực hiện thao tác, hoặc là kết thúc hoặc xác định để thực hiện bước tiếp theo. + Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm. + Hs thảo luận và trả lời. Hoạt động 3: Kiểm tra Số nguyên tố là số chỉ tính nguyên tố của một có 2 ước số. 3. Một số ví dụ về thuật toán: số nguyên dương. Ví dụ: Kiểm tra tính nguyên tố Gợi ý: Thế nào là số của một số nguyên dương. nguyên tố? + Các nhóm đưa ra ý _ Input: N là một số nguyên Hãy xác định các bước kiến.
của bài toán này? Phát Thực hiện giải bài dương. phiếu học tập cho các toán. _ Output: “ N là nguyên tố” hoặc nhóm. “N không là nguyên tố” Giáo viên giải thích các + Lưu bảng các bước giải bài bước giải bài toán, giảng toán. chi tiết sơ đồ khối.Các em thực hiện? 4. Củng cố: Tìm số lớn nhất trong 3 số nguyên 5. Dặn dò: Xem lại bài đã học, chuẩn bị phần tiếp theo của bài. 6. Rút kinh nghiệm
Tuần……. Tiết ……. §4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 2) I. Mục đích, yêu cầu: 1. Về kiến thức: - Dạy học sinh hiểu hơn về thuật toán thông qua ví dụ tiếp theo. 2. Về kỹ năng: - Rèn luyện cho học sinh kỹ viết thuật toán để chu ẩn b ị cho vi ệc h ọc Tin học ở lớp 11. 3. Về tư duy và thái độ: - Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn học trong hệ thống kiến thức phổ thông và nh ững yêu cầu v ề m ặt đ ạo đ ức trong xã hội tin học hóa II. CHUẨN BỊ 1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, … 2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập. III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC - Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp, thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm. - Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu có). IV. TIẾN TRÌNH BÀI HỌC 1. Ổn định lớp, Kiểm tra sĩ số 2. Kiểm tra bài cũ:
- Khái niệm thuật toán là gì? Thuật toán có các tính chất nào? Hãy xác định Input và Output của bài toán giải phương trình bậc hai: ax2 + bx + c = 0? 3.Tiến trình bài học mới: TG HOẠT ĐỘNG CỦA HOẠT ĐỘNG CỦA NỘI DUNG BÀI DẠY GIÁO VIÊN HỌC SINH Ở tiết trước chúng ta đã Nghe giảng. biết khái niệm của bài toán và thuật toán, đồng thời chúng ta cũng đã xây dựng được thuật toán của bài toán tìm giá trị lớn nhất. Để hiểu 3. Các ví dụ về thuật thêm về thuật toán cũng như toán: đi xây dựng thuật toán của Ví dụ 1: Kiểm tra bài toán, hôm nay chúng ta tính nguyên tố của một sang tiếp các ví dụ tiếp theo. Trả lời. số nguyên dương. Em hãy cho biết Input và Output của bài toán trên là gì? Nghe giảng và ghi bài. Nhận xét và đưa ra Input, Output của bài toán.  Xác định bài Trả lời. toán: Em nào có thể nhắc lại khái  Input: Số niệm của số nguyên tố là gì? nguyên dương N. Nghe giảng.  Output: “N là Nhận xét và đưa ra khái số nguyên tố” hoặc “N niệm số nguyên tố. không là số nguyên tố”. Nghe giảng.
Nhắc lại định lý: “Nếu một số nguyên dương N không chia hết cho các số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì nó cũng không chia hết cho các số trong phạm vi từ phần nguyên căn bậc 2 của N đến Thảo luận nhóm và N – 1. trình bày ý tưởng. Từ định nghĩa và định lý trên, các em hãy thảo luận và trình bày ý tưởng để xây Nghe giảng và ghi dựng thuật toán của bài toàn bày. này. Nhận xét và trình bày ý tưởng để xây dụng thuật  Ý tưởng: Ta nhớ toán. lại định nghĩa: Một số nguyên dương N là số Từ ý tưởng trên, chúng ta đi Nghe giảng và trả lời nguyên tố nếu nó có xây dựng thuật toán bằng theo. đúng 2 ước số khác cách liệt kê như sau: nhau là 1 và chính nó. Do đó ta có: Xây dựng từng bước của  Nếu N = 1 thì thuật toán và giải thích. N không là nguyên tố. Trả lời.
 Nếu 1 < N < 4 thì N là số nguyên tố. Em nào hãy cho biết vai trò Nghe giảng.  Nếu N ≥ 4 và của biến i trong thuật toán không có ước số trong này là gì? phạm vi từ 2 đến phần Nhận xét. Lên bảng dán sơ đồ nguyên căn bậc 2 của N khối của bài toán. thì N là số nguyên tố. Nghe giảng và trả lời. Ngoài cách liệt kê trên, ta  Thuật toán: còn có cách sơ đồ khối. Em a. Cách liệt kê: nào hãy lên bảng xây dựng  B1: Nhập số thuật toán của bài toán này nguyên dương N. bằng cách sơ đồ khối?  B2: Nếu N = 1 Nhận xét! Nghe giảng và trả lời. thì thông báo N không là số nguyên tố rồi kết Bây giờ chúng ta đi vào một thúc. vài ví dụ mô phỏng việc thực  B3: Nếu N < 4 hiện của thuật toán trên. thì thông báo N là số Với N = 29 nguyên tố rồi kết thúc. Với N = 45  B4: i  2 Giải thích từng bước thực  B5: Nếu N>[ hiện của thuật toán qua 2 ví N ](*) thì thông báo N dụ mô phỏng để học sinh là số nguyên tố rồi kết hiểu hơn về thuật toán thúc.  B6: Nếu N chia hết chi i thì thông báo N
là số không nguyên tố rồi kết thúc.  B7: i  i + 1 rồi quay lại bước 5. b. Cách sơ đồ khối: (Sơ đồ khối) Sách giáo khoa 4. Củng cố kiến thức : Nhắc lại các bước của thuật toán thông qua ví dụ trên. 5 .Dặn dò:
Tuần……. Tiết ……. §4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 3)  I. Mục tiêu 1. Về 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 liệt kê các bước; - Hiểu một số thuật toán thông dụng. 2. Về 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 liệt kê các bước. 3. Về tư duy và thái độ: - Dùng để tìm thuật toán cho các bài toán khác… - Tích cực trong học tập và rèn luyện tính chính xác. II. CHUẨN BỊ 1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, … 2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập. III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC
- Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp, thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm. - Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu có). IV. TIẾN TRÌNH BÀI HỌC 1. Ổn định lớp, Kiểm tra sĩ số 2. Kiểm tra bài cũ: - Khái niệm thuật toán là gì? Thuật toán có các tính chất nào? Hãy xác định Input và Output của bài toán giải phương trình bậc hai: ax2 + bx + c = 0? 3.Tiến trình bài học mới: T HOẠT ĐỘNG CỦA HOẠT ĐỘNG CỦA HS NỘI DUNG BÀI DẠY G GIÁO VIÊN
+ Cho dãy số nguyên + Hs đưa ra ý tưởng, Ví dụ 2: Bài toán sắp xếp 6,1,5,3,7,8,10,7,12,4 làm thảo luận nhiều ý tưởng Cho dãy A gồm N số nguyên thế nào để sắp xếp dãy khác nhau. a1, a2, a3, …,aN. Cần sắp xếp số nguyên từ nhỏ đến các số hạng để dãy A trở lớn? thành dãy không giảm (tức là + Trước tiên ta cũng số hạng trước không lớn hơn thực hiện theo 3 bước. + Hs trao đổi, thảo luận. số hạng sau) Bước 1: Nhập , và dãy + Hs phát biểu từng • Xác định bài toán: số nguyên. bước liệt kê sơ đồ khối. + Input: Dãy A gồm N số Bước 2: M  N; nguyên Bước 3: Nếu M M thì bước sơ đồ khối theo Thuật toán sắp xếp bằng quay lại bước 3; các bước. tráo đổi Bước 7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho (Exchange Sort) nhau; Nhập N và a1, a2,..., aN Bước 8: Quay lại bước M ←N 5; MM? Sai + Các nhóm thảo luận Tráo đổi ai và ai+1 đúng ai > ai+1 ? Sai
và trình bày theo thuật toán các lần duyệt bài Sơ đồ khối cho thuật toán. toán sau? ( Sử dụng máy chiếu minh họa) 4. Củng cố : -Sắp xếp dãy số nguyên từ lớn đến nhỏ (dãy số giảm). 5. Dặn dò: - Xem lại bài đã học - Chuẩn bị phần tiếp theo của bài học “Thuật toán tìm kiếm tuần tự”. 6. Rút kinh nghiệm: Tuần……. Tiết …….
§4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 4)  I. Mục tiêu 1. Về 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 liệt kê các bước; - Hiểu một số thuật toán thông dụng. 2. Về 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 liệt kê các bước. 3. Về tư duy và thái độ: - Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn học trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã hội tin học hóa. II. CHUẨN BỊ 1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, … 2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập. III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC - Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp, thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm. - Phương tiện: Bảng phụ và các phiếu học tập, Computer và projector (nếu có). IV. TIẾN TRÌNH BÀI HỌC
1. Ổn định lớp, Kiểm tra sĩ số 2. Kiểm tra bài cũ: Sắp xếp dãy số nguyên từ lớn đến nhỏ (dãy số giảm). 3.Tiến trình bài học mới: TG HOẠT ĐỘNG HOẠT ĐỘNG CỦA GIÁO CỦA HỌC NỘI DUNG BÀI DẠY VIÊN SINH Trong cuộc sống + Ghi bài. * Thuật toán tìm kiếm tuần tự chúng ta, thường + Cho ví dụ tìm (Sequential sort) xảy ra việc tìm kiếm 1 đối Bài toán: Cho dãy A gồm N số kiếm. Chảng tượng nào đó. nguyên khác nhau: a1,a2,…,aN và mpptk hạn: tìm kiếm số nguyên k. Cần biết hay không chỉ tên của 1 học số I (1 ≤ i ≤ N ) mà ai = k. Nếu có hãy sinh trong 1 lớp, cho biết chỉ số đó. tìm 1 quyển sách Các bước giải bài toán: có 3 bước. trong thư viện. * Xác định bài toán: Điều quan tâm ở + Suy nghĩ Input: Dãy A gồm N số nguyên a1,a2, đây là tìm kiếm +I=5 …,aN và khóa k. như thế nào? + Không có i Output: chỉ số I mà a i = k.hoặc ? Ví dụ: 5 7 * Xác định bài không có số hạng nào. 1 4 2 toán: * Ý tưởng. Tìm kiếm tuần tự một cách +k=2 I Input: tự nhiên. Lần lượt từ số hạng thứ 1, =? Output: so sánh các số hạng đến khi gặp số + k = 6  I = ? * Ý tưởng. hạng bằng khóa, hoặc không có giá trị ? Nêu các bước * Thuật toán. nào bằng khóa. giải bài toán? * Thuật toán. B1: Nhập N, các số hạng khác nhau
* L ư u ý: a1,a2,…,aN và khóa k B1: Các số B2: i  1; khác nhau. B3: Nếu ai = k thì thông qua chỉ số i, B3 và B5 lưu ý rồi kết thúc + Học sinh nêu các biểu thức B4: i  i + 1; các bước của điều kiện. B5: Nếu i > N thì thông báo dãy A thuật toán? không có số hạng nào bằng k rồi kết Những điều cần thúc. lưu ý. B6: Quay lại bước 3. a. Vẽ sơ đồ: + Học sinh thực hiện. Nhập N và a1,a2,…,aN và k i  1 Đưa ra i rồi ai = k ? kết thúc Đúng + Mời học sinh Sai i  i + 1 lần lượt vẽ sơ +I=6 Sai i > N ? đồ khối. Đúng Dãy A không có số hạng bằng k, rồi kết thúc Dãy A có N = 7 khóa k = 10 + Cho dãy số Tìm chỉ số i để ai = k. bất kỳ. Các em + Từ 1 đến N + i 1 2 3 4 5 6 7 thực hiện theo 1. ai 7 12 4 6 11 10 8 thuật toán tìm k = 10  i = 6 chỉ số i. * Ghi chú:
+ Các nhóm Trong thuật toán trên, i là biến chỉ số + Trong thuật thực hiện lên và nhận giá trị nguyên lần lượt từ 1 toán trên giá trị bảng trình bày. đến N + 1 biến i biến đổi + Nhận xét. *Bài tập thảo luận nhóm: từ giá trị nào Cho N và dãy số a1,a2,…,aN, hãy đến giá trị nào? cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0 + Xem bài tập * Gợi ý: trang 7 SGK Sử dụng thuật toán trong bài, sử trang 44. Các dụng biến đếm để đếm số lần giá trị nhóm thực hiên. 0 xuất hiện trong dãy. + Gợi ý trình bày. 4. Củng cố: Cho N và dãy số a1,a2,…,aN, hãy cho bết có bao nhiêu số hạng trong dãy có giá trị bằng 0. 5. Dặn dò: - Xem lại bài đã học - Chuẩn bị phần tiếp theo của bài học “Thuật toán tìm kiếm nhị phân”. 6. Rút kinh nghiệm:
Tuần……. Tiết ……. §4. BÀI TOÁN VÀ THUẬT TOÁN (tiết 5)  I. Mục tiêu 1. Về 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 liệt kê các bước; Hiểu một số thuật toán thông dụng. 2. Về 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 liệt kê các bước. 3. Về tư duy và thái độ: Học sinh cần nhận thức được tầm quan trọng của môn học, vị trí của môn học trong hệ thống kiến thức phổ thông và những yêu cầu về mặt đạo đức trong xã hội tin học hóa II. CHUẨN BỊ 1. Giáo viên: Máy tính Projecter, sách giáo khoa, sách giáo viên, giáo án, … 2. Học sinh: Tập soạn bài, sgk, đồ dùng học tập. III. PHƯƠNG PHÁP VÀ PHƯƠNG TIỆN DẠY HỌC - Phương pháp: Sử dụng các phương pháp,dạy học cơ bản sau một cách linh họat nhằm giúp học sinh tìm tòi,phát hiện,chiếm lĩnh tri thức. Gợi mở vấn đáp, thảo luận. Phát hiện và giải quyết vấn đề. Đan xen hoạt động nhóm. IV. TIẾN TRÌNH BÀI HỌC 1. Ổn định lớp, Kiểm tra sĩ số
2. Kiểm tra bài cũ: - Cho N và dãy số a1,a2,…,aN, hãy cho bết có bao nhiêu số hạng trong dãy có giá trị bằng 0? 3.Tiến trình bài học mới: TG HOẠT ĐỘNG HOẠT ĐỘNG NỘI DUNG BÀI DẠY CỦA GIÁO VIÊN CỦA HỌC SINH + Các em cho dãy + Cho dãy số tăng Thuật toán tìm kiếm nhị phân số bất kỳ. dần. (Binary Search) k = 4 và N = 6 + Chia: * Xác định bài toán: 2 4 5 6 9 13 Dãy 1: 2 4 5 + Input: Dãy A gồm N số nguyên khác + Các em chia thành Dãy 2: 6 9 nhau và 1 số nguyên k; 2 dãy dãy con. 13 + Output: Chỉ số I mà ai = k hoặc thông + Chỉ số ở giữa dãy Ta thấy tìm kiếm báo không có số hạng nào của dãy có giá là bao nhiêu? So trên dãy 1 có giá trị trị bằng k. sánh agiua với khóa bằng k * Ý tưởng: k? + Giữa = 3. Sử dụng tính chất dãy A là dãy tăng, ta + Các em thảo luận + agiua = 5 > k nên ta thu hẹp phạm vi tìm kiếm sau mỗi lần so để hình thành ý tìm trên dãy 1. sánh với số hạng được chọn. tưởng cho bài toán? + Các nhóm thảo • Ta chọn a giua ở giữa dãy để so sánh luận và trình bày.  N + 1 với k, trong đó Giua =  + Ghi ý tưởng của  2   bài toán. • Xảy ra 1 trong 3 điều kiện sau: - Nếu a giua = k  tìm đợc chỉ số, kết thúc; + Học sinh thảo - Nếu a > k  do dãy A đã đợc giua luận trình bày các sắp xếp tăng nên việc tìm kiếm thu bước cho thuật toán + Lần lượt các hs hẹp chỉ xét từ a 1  a gua - 1; và vẽ sơ đồ khối? lên bảng. - Nếu a giua < k  do dãy A đã được