Giáo án Tin học 10 - Chương 1: Một số khái niệm cơ bản của tin học

phím kí tự + Nhóm phím di chuyển + Nhóm phím số b. Chuột (Mouse) Được sử dụng để lựa chọn và thực hiện lệnh trong khi làm việc với máy tính c. Máy quét (Scanner) Được sử dụng để đưa văn bản và hình ảnh vào máy tính. d. Webcam. Là Camera kĩ thuật số để thu và truyền trực tuyến hình ảnh qua mạng đến máy tính khác. Chương trình là một dãy lệnh, mỗi lệnh là một chỉ dẫn cho máy biết điều cần làm. GV: Trong 3 thành phần trên thành phần nào là quan trọng nhất? - HS trao đổi và trả lời câu hỏi. GV: Cho học sinh quan sát sơ đồ cấu trúc một máy tính và giải thích cho học sinh biết được việc trao đổi thông tin giữa các bộ phận của máy tính. Giới thiệu tầm quan trọng của CPU, thông thường người ta gọi tên một bộ máy tính dựa vào cấu hình của CPU. - GV: Cho học sinh quan sát một bộ CPU. - Giới thiệu tác dụng của bộ nhớ chính. Dung lượng bộ nhớ càng lớn thì máy hoạt động càng nhanh. - GV: Cho học sinh quan sát một bộ CPU Quan sát RAM Các máy tính ngày nay, bộ nhớ trong có dung lượng 128MB hoặc 256MB, một số máy chuyên dụng có thể lên đến cỡ hàng GB. Kích thước ngày càng nhỏ và dễ lắp đặt. - Quan sát tranh ảnh về đĩa cứng, đĩa mềm, Flash. GV: Cho học sinh quan sát một ổ đĩa cứng đã tháo hộp bảo vệ và giới thiệu chi tiết. - Theo dõi sơ đồ một bàn phím trên bảng GV : Giới thiệu các nhóm phím trên sơ đồ một bàn phím, nói rõ tính năng của các nhóm phím và cách sử dụng các phím. - Quan sát một thiết bị chuột do GV giới thiệu. 7. Thiết bị ra (Output device) a. Màn hình (Moniter) Để hiển thị thông tin. Chất lượng màn hình phụ thuộc vào độ phân giải và chế độ màu b. Máy in (Printer) Để in thông tin ra giấy, In màu hoặc đen - trắng c. Máy chiếu (Projector) Để hiển thị nội dung màn hình máy tính lên màn ảnh rộng d. Loa và tai nghe (Speaker and headphone) e. Môdem (Modem- Modulation demodulation) Thiết bị dùng để truyền thông tin giữa các hệ thống máy tính thông qua đường truyền như đường điện thoại. 8. Hoạt động của máy tính. * Nguyên lí điều khiển bằng chương trình - Máy tính hoạt động theo chương trình, tại mỗi thời điểm máy tính chỉ thực hiện được một lệnh. - Thông tin về một lệnh bao gồm : + Địa chỉ của lệnh trong bộ nhớ + Mã của thao tác cần thực hiện + Địa chỉ các ô nhớ liên quan - Mã thao tác chỉ dẫn cho máy biết phải làm gì. Phần địa chỉ thông báo cho máy biết nơi lưu trữ dữ liệu. * Nguyên lí lưu trữ chương trình. Lệnh được đưa vào máy tính dưới dạng mã nhị phân để lưu trữ, xử lí như những dữ liệu khác. * Nguyên lí truy cập theo địa chỉ Việc truy cập dữ liệu trong máy tính được thực hiện thông qua địa chỉ nơi lưu trữ dữ liệu đó. - Các bộ phận của máy tính nối với nhau bởi các dây dẫn gọi là các tuyến (bus) * Nguyên lí Phôn Nôi-man Mã hoá nhị phân, điều khiển bằng chương trình, lưu trữ chương trình và truy cập theo địa chỉ tạo thành một nguyên lí chung gọi là nguyên lí Phôn Nôi-man. - Hãy cho biết dữ liệu sẽ được hiển thị ở những thiết bị nào? - Giới thiệu về các thiết bị ra. - Các máy tính thường sử dụng độ phân giải “800 by 600” hoặc “1024 by 768”. Máy tính hiện nay đạt tới 32 triệu màu. Có thể xem modem là một thiết bị hỗ trợ cho cả việc đưa thông tin vào máy và lấy thông tin ra từ máy tính. Trong đời thường để làm một việc gì đó thì cần có một chương trình. VD : chương trình họp lớp liệt kê có thứ tự các việc (thao tác) cần làm. Theo chương trình đó, lớp trưởng điều khiển việc họp lớp : khi nào (thứ tự), làm gì (mã phép toán. Ä Mô phỏng việc lưu giữ dữ liệu trong RAM và truy cập để xử lí của CPU theo địa chỉ, theo mã thao tác - Địa chỉ của các ô nhớ là cố định nhưng nội dung ghi ở đó có thể thay đổi trong quá trình máy làm việc. GV : Vì sao phải mã hoá nhị phân ? HS: Trả lời Khi xử lí dữ liệu, máy tính xử lí đồng thời một dãy bit chứ không xử lí từng bit III. Củng cố: Các thành phần của hệ thống tin học: Phần cứng; phần mềm; Sự quản lý và điều khiển của con người. Các thành phần chính của máy tính: Bộ xử lý trung tâm; bộ nhớ trong; bộ nhớ ngoài; thiết bị vào; hiết bị ra. Các nguyên lý làm việc của máy tính và nguyên lý Phôn Nôi-man. IV. Bài tập về nhà Trả lời các câu hỏi 4, 6 trang 28. Bài tập 1.13 ® 1.31 sách bài tập. Chuẩn bị, đọc trước bài trang 27. BÀI TẬP VÀ THỰC HÀNH 2 (Làm quen với máy tính) A. Mục tiêu Quan sát và nhận biết được các bộ phận chính của máy tính và một số thiết bị khác như máy in, bàn phím, chuột, đĩa, ổ đĩa, cổng USB, .... Làm quen và tập một số thao tác sử dụng bàn phím, chuột. Biết được máy tính được thiết kế rất thân thiện với con người, rất tiện dùng. Có tinh thần và thái độ bảo vệ của công, an toàn cháy nổ, … B. Phương pháp và phương tiện dạy học. Chuẩn bị nội quy phòng máy để phổ biến. Đối với một tiết thực hành cần tổ chức khác với một tiết lý thuyết, phải hướng dẫn mẫu, kiểm tra các kiến thức liên quan và quan sát học sinh thao tác, sửa chữa lỗi của học sinh. Phòng máy và một số thiết bị đã được tháo rời. C. Tiến trình dạy – học: I. Ổn định lớp - kiểm tra sĩ số. II. Kiểm tra bài cũ: Trình bày chức năng từng bộ phận: CPU, bộ nhớ trong, bộ nhớ ngoài, thiết bị vào, thiết bị ra. Trình bày hiểu biết của em về hoạt động của máy tính. III. Bài mới Nội dung Hoạt động của giáo viên và học sinh 1. Làm quen với máy tính. - Các bộ phận của máy tính và một số thiết bị khác như : ổ đĩa, bàn phím, màn hình, máy in, bộ nguồn (Power supply), bản mạch chính, cáp nối, cổng USB, ... - Cách bật và tắt một số thiết bị như : Máy tính, màn hình, máy in, ... 2. Sử dụng bàn phím - Phân biệt được các nhóm phím - Phân biệt việc gõ một phím và gõ tổ hợp phím bằng cách nhấn giữ. - Phân biệt việc gõ phím kí tự đơn và đôi - Gõ một bài hát hoặc gõ một bài thơ 3. Sử dụng chuột - Di chuyển chuột. - Nháy chuột : Nhấn nút trái chuột 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ữ phím trái chuột, di chuyển con trỏ chuột đến vị trí cần thiết thì thả ngón tay nhấn giữ chuột GV: quy định chỗ ngồi thực hành cho các học sinh, nhắc nhở nội quy phòng thực hành và quy trình của giờ thực hành. - GV : giới thiệu và hướng dẫn - HS : quan sát và thực hành -GV : sử dụng máy chiếu giới thiệu và thao tác, giới thiệu cách khởi động chương trình soạn thảo và cách gõ tiếng Việt. - HS : quan sát và thực hành - GV : Bao quát và sửa lỗi cho HS - GV : sử dụng máy chiếu giới thiệu và thao tác - HS : quan sát và thực hành IV.Củng cố và bài tập. - Nhắc lại các thuật ngữ chính. - Xem trước bài toán và thuật toán §4. BÀI TOÁN VÀ THUẬT TOÁN A. Mục tiêu. Kiến thức Biết khái niệm bài toán và thuật toán, các đặc trưng chính của thuật toán. Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và ngôn ngữ liệt kê. Hiểu một số thuật toán thông dụng. 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 ngôn ngữ liệt kê. Thái độ. Có ý thức sử dụng các kiến thức trên góp phần phát triển tư duy khi giải quyết các vấn đề trong khoa học cũng như trong đời sống. B. Phương pháp và phương tiện dạy học: Đây là một bài dạy khó, vì thế càn chuẩn bị chu đáo một số thiết bị phụ như: các bảng vẽ trước các sơ đồ thuật toán trong sách, hoặc các bước theo cách liệt kê. Nếu có máy chiếu có thể vẽ trước để hướng dẫn được thuận tiện. C. Tiến trình dạy - học: I. Ổn định lớp. Điểm diện học sinh trong lớp. II. Kiểm tra bài cũ: Tùy theo thời điểm phân chia các tiết của bài dạy này mà giáo viên đặt ra các câu hỏi để chuẩn bị cho tiết dạy kế tiếp. Với các câu hỏi sau : Một máy tính chưa có phần mềm có thể hoạt động được chưa ? Hãy giới thiệu và vẽ sơ đồ cấu trúc máy tính. Trình bày những hiểu biết về nguyên lý Phôn Nôi man III. Bài mới Nội dung Hoạt động của giáo viên và học sinh 1. Khái niệm bài toán trong Tin học - Trong phạm vi Tin học, bài toán là một việc nào đó ta muốn máy tính thực hiện. - Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: + Đưa vào máy thông tin gì? (Input) + Cần lấy ra thông tin gì? (Output) Để phát biểu một bài toán ta cần trình bày rõ Input và Output của bài toán đó và mối quan hệ giữa Input và Output. * Một số ví dụ Ví dụ 1: Hãy xác định Input và Output của bài toán tìm UCLN của 2 số nguyên dương: Trả lời: Input: Hai số nguyên dương M và N Output: UCLN của M và N. Ví dụ 2: Cho biết Input và Output của bài toán Giải phương trình bậc hai ax2 + bx + c = 0 Trả lời: Input: Các số thực a, b, c (a ¹ 0) Output: nghiệm x của phương trình thoả mãn: ax2 + bx + c = 0 Ví dụ 3: Kiểm tra N có phải là một số nguyên tố không? Trả lời: Input: N là số nguyên Output: Trả lời câu hỏi “N có phải là một số nguyên tố hay không”. Ví dụ 4: Cho biết Input và Output của bài toán xếp loại học tập của một lớp. Trả lời: Input: Bảng điểm của học sinh trong lớp. Output: Bảng xếp loại học lực của học sinh. Trong toán học ta nhắc nhiều đến khái niệm “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 sao cho từ những dữ kiện đã có, phải tìm ra hay chứng minh một kết quả nào đó. GV: Trong nhà trường có phần mềm quản lí học sinh, nếu ta yêu cầu đưa ra những học sinh có điểm TB từ 7 trở lên, đó là bài toán. Hay đơn giản là yêu cầu máy cho ra kết quả của một phép nhân, chia ... Đó cũng là bài toán. GV: Vậy đứng trước một bài toán công việc đầu tiên là gì? HS: Công việc đầu tiên phải xác định đâu là dữ kiện đã cho và đâu là cái cần tìm. Với mỗi ví dụ: GV: Ghi ví dụ lên bảng. - Input? - Output? HS: Trả lời câu hỏi. GV: ghi câu trả lời lên bảng và giải thích thêm. GV: Bảng điểm của học sinh trong một lớp gồm những nội dung gì? HS: Trả lời. 2. Khái niệm thuật toán (Algorithm) * KN: Thuật toán (còn gọi là giải thuật) để giải một bài 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 khi thực hiện dãy thao tác đó, từ Input của bài toán ta nhận được Output cần tìm. * Biểu diễn thuật toán: - Liệt kê các dãy thao tác: Được diễn tả bằng ngôn ngữ tự nhiên. - Sơ đồ khối: Dùng một số khối, đường mũi tên thể hiện các thao tác: + So sánh (K.Tra điều kiện): + Thực hiện các phép toán: + Nhập, xuất dữ liệu : + Quy trình thực hiện: * Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên. Xác định bài toán: Input: số nguyên dương N và dãy N số (a1,..aN) Output: Giá trị lớn nhất (max) của dãy số. ý tưởng: - Khởi tạo giá trị Max = a1 - Lần lượt với i = 2 đến N, so sánh giá trị ai với giá trị Max, nếu ai > max thì Max nhận giá trị mới là ai. Thuật toán: a) Cách liệt kê: B1: Nhập N và dãy a1, .., aN B2: Đặt max ¬ a1, i ¬ 2 B3: Nếu i > N thì đưa ra giá trị Max rồi kết thúc. B4: b4.1: Nếu ai > max thì đặt max ¬ ai b4.2: i ¬ i+1 rồi quay về B3. B5: Đưa ra max rồi kết thúc. b) Sơ đồ khối: Sai Nhập N và dãy a1,..,.aN max ¬ a1 , i ¬ 2 i > N ? Đưa ra max rồi kết thúc ai >max? max ¬ ai i ¬ i +1 Sai Đúng Đúng * Các tính chất của thuật toán. Tính dừng ( tính kết thúc ): Sau hữu hạn bước thực hiện, thuật toán phải kết thúc. Tính xác định Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để thực hiện 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. Việc cho một bài toán có nghĩa là mô tả rõ Input và Output cần tìm. Vấn đề là làm thế nào để tìm ra Output? GV: Hãy liệt kê các bước và thứ tự các bước cần làm trước khi đi học? HS: trả lời. GV: cần giải thích để HS thấy được tầm quan trọng là các thao tác (trong định nghĩa thuật toán ) phải có thứ tự. GV: Hãy xác định Input và Output của bài toán? HS: Trả lời. GV: Có thể chọn bất kì số hạng nào trong dãy không phải là a1 để khởi tạo biến Max được không? HS: trả lời GV: giải thích vì sao lại khởi tạo biến Max = a1. Sử dụng biến i là để xác định tại mỗi bước, số hạng nào sẽ tham gia vào các thao tác. Sau đó mỗi lần, tuỳ kết quả so sánh với ai nếu ai > Max thì Max sẽ nhận giá trị mới là ai (biến Max tại thời điểm đang xét có giá trị lớn nhất trong dãy con từ a1 đến ai). GV: trình bày sơ đồ thuật toán Chú ý quy trình thực hiện, ở khối so sánh luôn có hai đường ra (đúng, sai) GV: hướng dẫn HS tự nghiên cứu bảng mô phỏng tìm giá trị lớn nhất của dãy số nguyên. GV: nêu lại thuật toán tìm Max và đặt câu hỏi đâu là tính dừng? tính xác định? tính đúng đắn của thuật toán? HS: trả lời. GV: giải thích rõ hơn để HS có thể hiểu sâu về tính chất của thuật toán. 3. Một số ví dụ về thuật toán Ví dụ 1: 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. - Output: “N là số nguyên tố” hoặc “N không là số nguyên tố” ý tưởng: - 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ố chung trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố. Thuật toán: a) Cách liệt kê. Bước 1. Nhập số nguyên dương N; Bước 2. Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc; Bước 3. Nếu N< 4 thì thông báo N là nguyên tố rồi k.thúc; Bước 4. i ¬ 2; Bước 5. Nếu i > [] thì thông báo N là nguyên tố rồi kết thúc; Bước 6. Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc; Bước 7. i ¬ i + 1 rồi quay lại bước 5; b) Sơ đồ khối. Đúng Sai Sai Đúng Nhập N N = 1? N < 4 ? i ¬ 2 i > [] ? N chi hết cho i ? Thông báo N là số nguyên tố rồi k.thúc i ¬ i + 1 Thông báo N không là số nguyên tố rồi KT Đúng Sai Sai Đúng GV: Hãy cho biết thế nào là một số nguyên tố? HS: trả lời - (số có đúng hai ước số khác nhau là 1 và chính nó). GV: Đưa ra một bài toán. Kiểm tra số 19 có phải là số nguyên tố không? HS: Trình bày cách làm. GV: Từ định nghĩa về số nguyên tố, hãy nêu ý tưởng về thuật toán? HS: Trả lời. GV: Giải thích cho học sinh biết thế nào là phần nguyên căn bậc hai của số N và vì sao khi kiểm tra tính nguyên tố của số nguyên dương N ta chỉ cần kiểm tra xem N không có USC trong phạm vi từ 2 đến phần nguyên căn bậc hai của số N, không chứng minh. GV: Cho HS nêu các bước, cũng có thể cho mỗi HS nêu một bước. Lưu ý học sinh kết thúc mỗi bước dùng dấu chấm phẩy (;) và bước kết thúc dùng dấu chấm (.) để phù hợp cho việc lập trình sau này. GV: Cần giải thích vì sao sử dụng biến i trong thuật toán. (là để xác định tại mỗi bước, số hạng nào sẽ tham gia vào các thao tác). GV: Trình bày bảng sơ đồ thuật toán, giải thích rõ từng thao tác, đặc biệt là các thao tác so sánh kiểm tra và sau đó là các thao tác tiếp theo (chỉ xác định đúng 1 bước tiếp theo) Ví dụ 2: Bài toán sắp xếp - Thuật toán sắp xếp bằng tráo đổi (Exchange Sort) - Sắp xếp nổi bọt. Xác định bài toán: - Input: Dãy A gồm N số nguyên a1, a2, … , aN. - Output: Dãy A được sắp xếp lại thành dãy không giảm ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số 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 không có sự đổi chỗ nào xảy ra nữa. Thuật toán: a) Cách liệt kê: Bước 1. Nhập N, các số hạng a1, a2, … , aN; Bước 2. M ¬ N; Bước 3. Nếu M < 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc; Bước 4. M ¬ M - 1, i ¬ 0; Bước 5. i ¬ i + 1; Bước 6. Nếu i > M thì quay lại bước 3; bước 7. Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau; Bước 8. Quay lại bước 5. Sai Đúng Nhập N và dãy a1,..,.aN M ¬ N M < 2 ? i > M ? M ¬ M - 1; i ¬ 0 i ¬ i + 1 Sai Đúng Sai Đúng ai > ai+1? Tráo đổi ai và ai+1 b) Sơ đồ khối. Đưa ra A rồi kết thúc Trong cuộc sống ta thường gặp những việc liên quan đến sắp xếp như xếp các học sinh theo thứ tự từ thấp đến cao hoặc xếp điểm trung bình của học sinh trong lớp theo thứ tự từ cao đến thấp. Vấn đề đặt ra là làm thế nào để sắp xếp được. GV: Hãy xác định bài toán? HS: Trả lời. GV: Hãy nêu ý tưởng về thuật toán? HS: Trả lời GV: Hướng dẫn học sinh tìm hiểu ví dụ mô phỏng việc thực hiện thuật toán sắp xếp lại dãy số nguyên: 6, 1, 5, 3, 7, 8, 10, 7, 12, 4 thành dãy số không giảm. - Sau khi học sinh đã nắm được cách làm, GV yêu cầu các HS hoặc cùng với các HS liệt kê các bước của thuật toán. GV: Ta thấy rằng, sau mỗi lần đổi chỗ giá trị lớn nhất của dãy A sẽ được chuyển dần về cuối dãy và sau lượt thứ nhất thì giá trị lớn nhất xếp đúng vị trí ở cuối dãy và không còn tham gia vào quá trình đổi chỗ nữa. - Quá trình đổi chỗ chỉ xảy ra với các số còn lại và thực hiện tương tự như lượt thứ nhất. GV: Lưu ý học sinh việc sử dụng biến M là để chỉ ra trong mỗi lần duyệt còn bao nhiêu cặp số hạng cần đổi chỗ cho nhau và biến i là để chỉ ra trong mỗi lần đổi chỗ số hạng nào sẽ tham gia vào thao tác. GV: Trình bày bảng sơ đồ thuật toán, giải thích rõ từng thao tác, đặc biệt là các thao tác so sánh kiểm tra và sau đó là các thao tác tiếp theo (chỉ xác định đúng 1 bước tiếp theo) GV: Sau khi trình bày song bảng sơ đồ thuật toán sẽ xoá một số hướng mũi tên của thao tác và yêu cầu HS điền lại cho thích hợp. HS: Lên bảng điền lại các hướng mũi tên đã bị xoá Ví dụ 3: Bài toán tìm kiếm - Thuật toán tìm kiếm nhị phân (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 a1, a2, … , aN và một số nguyên k. - Output: 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á rtị bằng k. ý tưởng: Sử dụng tính chất dãy A là dãy tăng, ta tìm cách 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 agiua ở “giữa dãy” để so sánh với k, trong đó Giua = . Khi đó, chỉ xảy ra một trong ba trường hợp sau: - Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc. - Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2, … , aGiua. - Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2, …, aN. Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy hoặc phạm vi tìm kiếm bằng rỗng. Thuật toán: a) Cách liệt kê: Bước 1. Nhập N, các số hạng a1, a2, … , aN và khóa k; Bước 2. Đau ¬ 1, Cuoi ¬ N; Bước 3. Giua ¬ ; 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ì đặt Cuoi = Giua - 1, ròi chuyển đến bước 7; Bước 6. Dau ¬ Giua + 1; Bước 7. Nếu Dau > Cuoi thi 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 ; b) Sơ đồ khối. Sai Đúng Nhập N và a1, a2,.., aN; k Dau ¬ 1; Cuoi ¬ N aGiua = k ? Đưa ra Giua rồi kết thúc aGiua > k ? Cuoi ¬ Giua - 1 Dau ¬ Giua + 1 Sai Đúng Sai Dau>Cuoi? Giua ¬ [(Dau + Cuoi)/2] 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 Tìm kiếm là việc thường xảy ra trong cuộc sống, chẳng hạn tìm số nhà trong dãy phố, tìm người có mức lương 2500000 trong bảng lương … Vấn đề đặt ra là tìm như thế nào cho nhanh chóng. GV: Hãy xác định bài toán? HS: Trả lời. GV: Hãy nêu ý tưởng về thuật toán? HS: Trả lời GV: Hướng dẫn học sinh tìm hiểu ví dụ mô phỏng việc thực hiện thuật toán + Tìm kiếm nhị phân trong dãy A đã được sắp xếp: 2, 4, 5, 6, 9, 21, 22, 30, 31, 33 với khoá k = 21. + Tìm kiếm nhị phân trong dãy A đã được sắp xếp: 2, 4, 5, 6, 9, 21, 22, 30, 31, 33 với khoá k = 25. - Sau khi học sinh đã nắm được cách làm, GV yêu cầu các HS hoặc cùng với các HS liệt kê các bước của thuật toán. GV: Ta nhận thấy, nếu agiua > k thì phạm vi tìm kiếm là ở nửa đầu của dãy A, nếu agiua < k thì phạm vi tìm kiếm ở nửa sau của dãy A. GV: Trình bày bảng sơ đồ thuật toán, giải thích rõ từng thao tác. GV: Sau khi trình bày song bảng sơ đồ thuật toán sẽ xoá một số hướng mũi tên của thao tác và yêu cầu HS điền lại cho thích hợp. HS: Lên bảng điền lại các hướng mũi tên đã bị xoá IV. Củng cố và bài tập. (Tùy theo thời gian và khả năng tiếp thu của học sinh mà giáo viên có thể chọn một số nối dung củng cố, bài tập phù hợp cho lớp) Khi dùng máy tính giải bài toán, ta cần quan tâm đến yếu tố nào? Làm bài tập 1.32 trong sách bài tập Thuật toán để giải một bài toán là: Dãy hữu hạn các thao tác; Sắp xếp có thứ tự; Từ Input cho ra Output. Thuật toán có thể mô tả bằng cách liệt kê các bước hoặc sơ đồ khối. Tính chất của thuật toán (tính dừng, tính xác định, tính đúng đắn). Bài tập 1.36 sách BT Thuật toán sắp xếp bằng tráo đổi sử dụng hai biến: M & i trong đó + Biến M chỉ ra số cặp số hạng còn lại, tham gia vào tráo đổi sau mỗi lượt. + Biến i chỉ ra số hạng nào tham gia vào tráo đổi của mỗi lần Bài tập 6 SGK và bài tập 1.38 Trong thuật toán, sau khi thực hiện một phép toán hoặc một lần tăng biến i đều kiểm tra điều kiện (thao tác so sánh) Sử dụng sơ đồ khối để trình bày thuật toán thường rõ ràng hơn, tránh được sự nhầm lẫn khi sử dụng bằng liệt kê các bước. Bài tập 4, 5 SGK và bài tập 1.37 sách BT Thuật toán tìm kiếm nhị phân sử dụng biến aGiua để so sánh với khoá tìm kiếm. + Nếu aGiua = k thì Giua là chỉ số cần tìm + Nếu aGiua > k thì việc tìm kiếm chỉ xét trên dãy a1, a2, …, aGiua-1. + Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2, …,aN. Bài tập 1.41, 1.42, 1.43, 1.44 (sách bài tập). BÀI TẬP (Bài toán và thuật toán) A. Mục tiêu Kiến thức Hiểu cách biểu diễn thuật toán bằng sơ đồ khối và ngôn ngữ liệt kê. Hiểu một số thuật toán thông dụng. 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 ngôn ngữ liệt kê. Đưa ra được Input và Output của bài toán. Rèn kĩ năng xây dựng thuật toán giải bài toán bằng cách liệt kê các bước hoặc sử dụng sơ đồ khối. B. Phương pháp và phương tiện dạy học Qua tiết bài tập này, sẽ trình bày thuật toán giải một số bài toán đơn giản như tìm ước chung lớn nhất của 2 số tự nhiên, kiểm tra một số tự nhiên là số nguyên tố hay hợp số, tìm kiếm và sắp xếp một dãy số nguyên. Chuẩn bị một số ví dụ gần gũi với học sinh để mô phỏng cho các thuật toán. Chuẩn bị trước một vài bộ tranh xẽ trước một số sơ đồ khó. C. Tiến trình dạy - học: I. Ổn định lớp - Kiểm tra sĩ số II. Kiểm tra bài cũ: III. Bài mới Nội dung Hoạt động của giáo viên và học sinh 1. Cho N và dãy các số a1, … , aN, hãy tìm giá trị nhỏ nhất của dãy đó. Thuật toán : Bước 1: Nhập N và dãy số a1, … , aN ; Bước 2: Min ¬ a1; i ¬ 2; Bước 3: nếu i > N thì đưa ra giá trị Min rồi kết thúc; Bước 4: + B4.1: Nếu ai < Min thì Min ¬ ai; + B4.2: i ¬ i+1 rồi quay lại bước 3; 2. Cho dãy A gồm N số nguyên a1, … , aN, hãy sắp xếp dãy số đó thành dãy số không tăng (số hạng trước lớn hơn hay bằng số hạng sau). Thuật toán : Bước 1: Nhập N, các số hạng a1, … , aN ; Bước 2: M ¬ N; Bước 3: Nếu M < 2 thì đưa ra dãy A đã sắp xếp rồi kết thúc; Bước 4: M ¬ M - 1; i ¬ 0; Bước 5: i ¬ i + 1; Bước 6: Nếu i > M thì quay lại bước 3; Bước 7: Nếu ai < ai+1 thì đổi chỗ ai và ai+1 cho nhau; Bước 8: quay lại bước 5; 3. Tìm nghiệm của phương trình bậc hai tổng quát : ax2 + bx + c = 0; (a¹0) ; Thuật toán : Bước 1: Nhập 3 số thực a, b, c (a¹0) ; Bước 2: D ¬ b2 - 4ac; Bước 3: Nếu D < 0 thì thông báo PT vô nghiệm rồi kết thúc ; Bước 4: Nếu D = 0 thì x ¬ ; thông báo PT có một nghiệm kép x rồi kết thúc ; Bước 5: Nếu D > 0 thì x1 ¬ , x2 ¬ và thông báo PT có hai nghiệm phân biệt là x1 và x2 rồi kết thúc. 4. Cho N và dãy số a1, … , aN , hãy cho biết có bao nhiêu số hạng trong dãy có giá trị bằng 0. Thuật toán : Bước 1: Nhập N và dãy a1,a2, … ,aN ; Bước 2: i ¬ 1; Count ¬ 0 íbiến Count dùng để đếmý Bước 3: Nếu i > N thì đưa ra giá trị bằng 0 rồi kết thúc ; Bước 4: Nếu ai = 0 thì Count ¬ Count + 1; Bước 5: i ¬ i+ 1 rồi quay lại bước 3; GV: Cho hai học sinh lên bảng, mỗi học sinh thực hiện viết thuật toán cho một bài toán theo cách liệt kê các bước. GV: cho học sinh nhận xét về cách viết thuật toán của hai học sinh đã thực hiện xong. GV phân tích bổ sung. Trong khi hai HS đang viết thuật toán trên bảng, GV cho học sinh dưới lớp làm việc theo nhóm (chia lớp thành 8 - 10 nhóm): Viết thuật toán theo cách liệt kê các bước hoặc sơ đồ khối. GV: Yêu cầu các nhóm nêu thuật toán sau đó các nhóm khác nhận xét, đóng góp thêm Sai Nhập 3 số thực a,b,c (a ¹ 0) D < 0 ? TB vô nghiệm rồi kết thúc D ¬ b2 + 4ac Đúng TB nghiệm kép x rồi KThúc Đúng Sai TB 2 nghiệm x1 và x2 rồi kết thúc D = 0 ? x ¬ x1 ¬ ; x2 ¬ ; GV: giải thích cho HS trong bài toán này ta sử dụng 2 biến là: biến chỉ số i (để tăng số hạng tìm) và biến Count (để đếm các số hạng có giá trị bằng 0) Nhập N và dãy a1,..,.aN i > N ? TB kết quả rồi kết thúc ai = 0 ? i ¬ 0; Count ¬ 0 i ¬ i + 1 Sai Đúng Sai Đúng Count ¬ Count + 1 IV. Củng cố và bài tập. - Khi giải một bài toán cần chú ý tới những vấn đề gì? + Yếu tố đã biết. + Yếu tố cần tìm. + Tìm hướng giải quyết. + Xác định các bước thực hiện (Diễn đạt bằng cách liệt kê các bước hoặc sơ đồ khối). Xem lại kiến thức §3.và §4. chuẩn bị kiểm tra 1 tiết. §5. NGÔN NGỮ LẬP TRÌNH A. Mục tiêu Kiến thức Học sinh biết được ngôn ngữ lập trình là phương tiện dùng để diễn đạt cho máy tính những việc con người muốn máy thực hiện. Biết chương trình là cách mô tả thuật toán bằng một ngôn ngữ lập trình mà máy tính có thể hiểu và thực hiện được