Tài liệu Giáo án trọn bộ tin học 10

VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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ó). VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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 GIÁO VIÊN HỌC SINH Hoạt động 1: HS thảo luận: NỘI DUNG BÀI DẠY 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. những yếu tố nào? Khi giải bài toán có 2 yếu tố: Hs thảo luận và cho ví + Đưa vào máy thông tin Xem cãc ví dụ 1,2,3,4 và dụ. gì?(Input) các em hãy cho ví dụ từng + trường hợp cụ thể để xem gì?(Output) Input và Output ? Vì vậy cần phải nói rõ Input và Hãy nhận xét mói quan hệ giữa Input và Out put. Cần lấy ra thông tin Output và mối quan hệ giữa Input và Output.  Các bài toán được cấu tạo bởi 2 thành phần cơ bản: VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí + Input: các thông tin đã có. + Output: Các thông tin cần tìm Hoạt động 2: từ Output. 1. 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? Thuật toán để giải một bài toán bài toán. 2. 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 sắp xếp theo 1 trình tự xác cách tìm Output. định sao cho sau khi thực hiện 3. Nêu các bước giải bài toán? dãy thao tác ấy, từ Input của bài - Có 3 bước: Xác định bài Ví dụ: Tìm giá trị lớn toán, đưa ra ý tưởng, Tìm nhất của một dãy số thuật toán. Ta có 3 bước thực hiện như * Xác định bài toán: bài toán trên? Ví dụ: Tìm giá trị lớn nhất của 1 dãy số nguyên. nguyên Hãy xác định các bước toán, ta nhận ra Output cần tìm. Input: Cho dãy sau: số + Xác định bài toán nguyên + Ý tưởng. Giảng các bước thực hiện Output: Giá trị lớn nhất + Thuật toán trong SGK, cho ví dụ 3 số của dãy số. Minh họa 3 bước trong sách giáo 5, 3, 9 và minh hoạt theo * Ý tưởng: Ta nhớ giá trị khoa, cho ví dụ cụ thể. các bước. Mời 1 hs cho ví đầu tiên, sau đó so sánh Hướng dẫn chi tiết sơ đồ khối, dụ 3 số và thực hiện các với các số khác nếu bé các hình thoi, chữ nhật, ô van, bước giải bài toán. mũi tên. hơn giá trị nào thì nhớ giá Ví dụ: Mô phỏng việc trị đó. Ví dụ: Mô phỏng việc thực hiện thực hiện thuật toán trên * Thuật toán:……… thuật toánvới N=8 và dãy số: với N = 8 số sau: 3 5 6 1 * Các nhóm học sinh thực 5,1,4,7,6,3,15,11 7 2 9 13 Ds hiện, và trình bày. 5 1 4 7 6 3 15 11 VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí Phát phiếu học tập các i 2 3 4 5 6 7 8 9 nhóm thảo luận, theo yêu + Học sinh đại diện nhóm Max 5 5 5 7 7 7 15 15 cầu: + Lưu bảng bài làm của hs. của mình trình bày. Các Xác định 3 bước của bài hs còn lại xem xét bổ toán sung.  Ta thấy thuật toán có một số + xác định bài toán. tính chất sau: + Ý tưởng. + Thuật toán. + Tính dừng: Thuật toán phải Qua 2 ví dụ trên chúng ta kết thúc sau một số hữu hạn lần thảo luận xem thuật toán thực hiện các thao tác. có những tính chất nào? Thuật toán có 3 tính chất: Phân tích ví dụ thuật toán Tính dừng. tìm số nguyên lớn nhất Tính xác định. lần thực hiện thao tác, hoặc là kết trên. Tính đúng đắn. thúc hoặc xác định để thực hiện + Tính xác định: Sau một số 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. Hoạt động 3: Kiểm tra + Hs thảo luận và trả lời. tính nguyên tố của một số nguyên dương. Gợi ý: Thế nào là số nguyên tố? 3. Một số ví dụ về thuật toán: Số nguyên tố là số chỉ Ví dụ: Kiểm tra tính nguyên tố có 2 ước số. của một số nguyên dương. _ Input: N là một số nguyên dương. VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí Hãy xác định các bước + Các nhóm đưa ra ý kiến. của bài toán này? Phát _ Output: “ N là nguyên tố” hoặc Thực hiện giải bài toán. “N không là nguyên tố” phiếu học tập cho các + Lưu bảng các bước giải bài nhóm. toán. Giáo viên giải thích các bước giải bài toán, giảng 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 VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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ũ: VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí - 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 GIÁO VIÊN HỌC SINH NỘI DUNG BÀI DẠY Ở tiết trước chúng ta đã biết Nghe giảng. 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 thêm về 3. Các ví dụ về thuật thuật toán cũng như đi xây toán: dựng thuật toán của bài toán, Ví dụ 1: Kiểm tra hôm nay chúng ta sang tiếp tính nguyên tố của một các ví dụ tiếp theo. Trả lời. số nguyên dương. 1. 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. 2. Nhận xét và đưa ra Input, Output của bài toán. Xác định bài toán: Trả lời. Em nào có thể nhắc lại khái Nghe giảng. niệm số nguyên tố. Số nguyên dương N.------------------------- niệm của số nguyên tố là gì? Nhận xét và đưa ra khái Input:  VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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 N – 1. Thảo luận nhóm và 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 dựng thuật toán của bài toàn này. Nghe giảng và ghi bày.  Ý tưởng: Ta nhớ Nhận xét và trình bày ý lại định nghĩa: Một số tưởng để xây dụng thuật toán. nguyên dương N là số nguyên tố nếu nó có Từ ý tưởng trên, chúng ta đi đúng 2 ước số khác xây dựng thuật toán bằng cách nhau là 1 và chính nó. liệt kê như sau: Nghe giảng và trả lời Do đó ta có: theo. Xây dựng từng bước của thuật toán và giải thích.  Nếu N = 1 thì N không là nguyên tố.  Nếu 1 < N < 4 thì N là số nguyên tố.  Nếu N  4 và VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí Trả lời. không có ước số trong Em nào hãy cho biết vai trò phạm vi từ 2 đến phần của biến i trong thuật toán này nguyên căn bậc 2 của N là gì? Nghe giảng. thì N là số nguyên tố. Nhận xét.  Thuật toán: Lên bảng dán sơ đồ a. Cách liệt kê:  B1: Nhập số Ngoài cách liệt kê trên, ta còn khối của bài toán. có cách sơ đồ khối. Em nào Nghe giảng và trả lời. nguyên dương N. hãy lên bảng xây dựng thuật  B2: Nếu N = 1 toán của bài toán này bằng thì thông báo N không cách sơ đồ khối? là số nguyên tố rồi kết Nhận xét! thúc.  B3: Nếu N < 4 Bây giờ chúng ta đi vào một Nghe giảng và trả lời. thì thông báo N là số vài ví dụ mô phỏng việc thực nguyên tố rồi kết thúc.  B4: i  2 hiện của thuật toán trên.  Với N = 29 Với N = 45 N>[ B5: Nếu N ](*) thì thông Giải thích từng bước thực báo N là số nguyên tố hiện của thuật toán qua 2 ví dụ rồi kết thúc. mô phỏng để học sinh hiểu hơn về thuật toán  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 VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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ò: VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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. VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí - 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 GIÁO VIÊN HOẠT ĐỘNG CỦA HS NỘI DUNG BÀI DẠY VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí + Cho dãy số nguyên + Hs đưa ra ý tưởng, thảo Ví dụ 2: Bài toán sắp xếp 6,1,5,3,7,8,10,7,12,4 làm luận nhiều ý tưởng khác Cho dãy A gồm N số nguyên thế nào để sắp xếp dãy số nhau. a1, a2, a3, …,aN. Cần sắp xếp nguyên từ nhỏ đến lớn? các số hạng để dãy A trở thành + Trước tiên ta cũng dãy không giảm (tức là số thực hiện theo 3 bước. hạng trước không lớn hơn số Bước 1: Nhập , và dãy + Hs trao đổi, thảo luận. hạng sau) số nguyên. + Hs phát biểu từng bước  Xác định bài toán: Bước 2: M  N; liệt kê sơ đồ khối. + Input: Dãy A gồm N số Bước 3: Nếu M<2 thì nguyên đưa dãy A đã được sắp + Output: Dãy A được sắp xếp rồi kết thúc. xếp thành dãy không giảm. Bước 4: M  M – 1, i * Ý tưởng: Với 2 số liền kề,  0; nếu số trước lớn hơn số sau ta Bước 5: i  i + 1; đổi chổ cho nhau. Việc đó lập Bước 6: Nếu I > M thì lai, khi không còn sự đổi chổ quay lại bước 3; + Hs lần lượt vẽ các bước nào nữa. Bước 7: Nếu ai > ai+1 thì sơ đồ khối theo các bước. Thuật toán sắp xếp bằng tráo tráo đổi ai và ai+1 cho đổi nhau; (Exchange Sort) Bước 8: Quay lại bước 5; + Cho dãy số (xem màn hình) Nhập N và a1, a2,..., aN MN + Các nhóm thảo luận M<2? + Các nhóm thảo luận và trình bày. trình bày theo thuật toán các lần duyệt bài toán Sai M  M – 1; i  0 ii+1 đúng i>M? Sai Tráo đổi ai và ai+1 đúng ai > ai+1 ? Sai đúng đưa ra A rồi kết thúc VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí sau? Sơ đồ khối cho thuật toán. ( 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) VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí  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ố VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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 VIÊN SINH NỘI DUNG BÀI DẠY 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 kiếm. Chảng tượng nào đó. Bài toán: Cho dãy A gồm N số nguyên khác nhau: a1,a2,…,aN và hạn: tìm kiếm mpptk số nguyên k. Cần biết hay tên của 1 học không chỉ số I ( 1  i  N ) mà ai = k. Nếu sinh trong 1 lớp, có hãy 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ĩ đây là tìm kiếm +I=5 như thế nào? + Không có i Input: Dãy A gồm N số nguyên a1,a2,…,aN và khóa k. Output: chỉ số I mà ai = k.hoặc không ? Ví dụ: 5 7 * Xác định bài có số hạng nào. 1 toán: 4 2 +k=2 I =? Input: tự nhiên. Lần lượt từ số hạng thứ 1, so Output: sánh các số hạng đến khi gặp số hạng + k = 6  I = ? * Ý tưởng. ? Nêu các bước giải bài toán? * Ý tưởng. Tìm kiếm tuần tự một cách * Thuật toán. bằng khóa, hoặc không có giá trị nào bằng khóa. * Thuật toán. B1: Nhập N, các số hạng khác nhau VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí * Lưu ý: a1,a2,…,aN và khóa k B1: Các số khác B2: i  1; 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ơ đồ: Nhập N và a1,a2,…,aN và k i1 + Học sinh thực ai = k ? hiện. Đưa ra i rồi kết thúc Đúng Sai ii+1 Sai i>N? Đúng Dãy A không có số hạng bằng k, rồi kết thúc + Mời học sinh lần lượt vẽ sơ đồ +I=6 Dãy A có N = 7 khóa k = 10 khối. Tìm chỉ số i để ai = k. + Cho dãy số bất kỳ. Các em thực + Từ 1 đến N + hiện theo thuật 1. toán tìm chỉ số i. i 1 2 3 4 5 6 7 ai 7 12 4 6 11 10 8 k = 10  i = 6 * Ghi chú: Trong thuật toán trên, i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí N+1 + Trong thuật + Các nhóm *Bài tập thảo luận nhóm: toán trên giá trị thực hiện lên Cho N và dãy số a1,a2,…,aN, hãy biến i biến đổi từ bảng trình bày. cho biết có bao nhiêu số hạng trong giá trị nào đến dãy có giá trị bằng 0 + Nhận xét. giá trị nào? * Gợi ý: Sử dụng thuật toán trong bài, sử + Xem bài tập dụng biến đếm để đếm số lần giá trị 0 trang 7 SGK xuất hiện trong dãy. trang 44. Các nhóm thực hiên. + 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: VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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ố. VnDoc - Tải tài liệu, văn bản pháp luật, biểu mẫu miễn phí 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 CỦA GIÁO VIÊN HOẠT ĐỘNG CỦA NỘI DUNG BÀI DẠY HỌC SINH + Các em cho dãy + Cho dãy số Thuật toán tìm kiếm nhị phân số bất kỳ. tăng 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 + Input: Dãy A gồm N số nguyên khác nhau và 1 + Các em chia thành 5 2 dãy dãy con. Dãy 2: số nguyên k; 6 9 + Output: Chỉ số I mà ai = k hoặc thông báo + Chỉ số ở giữa dãy 13 không có số hạng nào của dãy có giá trị bằng k. là bao nhiêu? So Ta thấy tìm * Ý tưởng: sánh agiua với khóa kiếm trên dãy Sử dụng tính chất dãy A là dãy tăng, ta thu hẹp k? 1 có giá trị phạm vi tìm kiếm sau mỗi lần so sánh với số + Các em thảo luận bằng k để hình thành ý + Giữa = 3. tưởng cho bài toán? + agiua = 5 > k nên ta tìm trên hạng được chọn. • Ta chọn a giua ở giữa dãy để so sánh với k, N  1   2  trong đó Giua =  dãy 1. • Xảy ra 1 trong 3 điều kiện sau: + Các nhóm - Nếu a giua= k  tìm đợc chỉ số, kết thúc; thảo luận và trình bày. - Nếu a giua > k  do dãy A đã đợc sắp xếp tăng nên việc tìm kiếm thu hẹp chỉ xét từ