Bai 12 mang

Người soạn: Đặng Thị Thơm
GVHD: Trịnh Thanh Hải



Bài 11. Kiểu mảng (Tiết 3)


I.Mục đích, yêu cầu
1. Về kiến thức:
- Giúp học sinh hiểu sâu sắc hơn những thuật toán tìm kiếm, sắp xếp cơ bản mà học sinh đã được học ở lớp 10.
- Minh họa, củng cố và naamg cao những hiểu biết của học sinh trong tiết 1 về mảng 1 chiều: cấu trúc, cách khai báo, cách tham chiếu một phần tử và lợi ích của kiểu dữ liệu này.
2. Về kĩ năng:
Hình thành kĩ năng cơ bản về sử dụng kiểu mảng trong cài đặt chương trình.
3. Về tư tưởng, tình cảm:
- Giúp học sinh hiểu rõ hơn tầm quan trọng của kiểu mảng.
- Làm cho học sinh thêm yêu thích lập trình, yêu thích môn học hơn.
II. Phương pháp, phương tiện dạy học
Phương pháp:
Kết hợp các phương pháp giảng dạy như: Thuyết trình, vấn đáp…
Phương tiện:
Sách giáo khoa Tin học 11.
Bảng, máy (chiếu nếu có).
III. Nội dung bài học
Ổn định lớp
Ổn định lớp
Yêu cầu lớp trưởng báo cáo sĩ số
Tổng: Vắng: Có phép: Không phép:
Nội dung bài học
Đặt vấn đề: Ở các tiết trước các em đã được tìm hiểu về mảng 1 chiều: cách khai báo, nhập và in mảng 1 chiều cũng như cách sử dụng mảng 1 chiều trong chương trình thể hiện các thuật toán cơ bản về tìm phần tử Max và sắp xếp. Hôm nay chúng ta tiếp tục tìm hiểu về cách sử dụng mảng 1 chiều trong chương trình thể hiện thuật toán tìm kiếm.
Hoạt động của giáo viên
Hoạt động của học sinh
Thời gian

GV: Nhập vào từ bàn phím 1 số nguyên dương N ( N<= 50) và dãy A tăng gồm N số nguyên A1, A2,..,AN. Nhập vào 1 số k bất kì. Tìm xem trong dãy A có phần tử nào có giá trị bằng k hay không? Nếu có hãy cho biết vị trí của nó trong dãy hoặc thông báo “khong tim thay” trong trường hợp ngược lại?
GV: Hãy xác định Input và Output của bài toán trên?
GV: Nhận xét hoàn chỉnh câu trả lời của HS
GV: Với bài toán này thì cần thực hiện các công việc sau:
Khai báo
Nhập số nguyên dương N, dãy tăng A và số nguyên k.
Tìm kiếm xem k có trong dãy A hay không?
Thông báo kết quả ra màn hình.
GV: Trong bài này, ở phần khai báo thì ta khai báo dãy A như thế nào?
GV: Ở phần nhập thì ta thực hiện 3 việc sau:
-Nhập số phần tử của dãy: 0<= N <= 250.
-Nhập các phần tử của dãy số tăng.
-Nhập số nguyên k bất kì.
Với việc nhập số nguyên dương N ( 0< N<= 250) tức là ta phải kiểm tra điều kiện khi nhập N thì cô đã hướng dẫn ở tiết trước các em về nhà xem lại.
GV: Việc nhập dãy A các em lưu ý: đó là dãy nhập vào phải là dãy số tăng tức là mặc định dãy đã được sắp xếp tăng dần (trong trường hợp vô tình dãy số mà các em nhập vào chưa phải là dãy số tăng thì chúng ta có thể sử dụng thuật toán sắp xếp trên mảng một chiều mà cô đã hướng dẫn ở tiết trước vào bài này). Đây cũng chính là điều kiện của dãy số để có thể áp dụng được thuật toán tìm kiếm nhị phân.
GV: Một em lên bảng viết cho cô đoạn chương trình nhập dãy A?
GV: Nhận xét, hoàn chỉnh bài làm của HS.
GV: Việc tìm kiếm số nguyên k có trong dãy A không chúng ta có thể thực hiện như thế nào?
Giả sử như cô có dãy A như sau:
2 3 4 6 7 9 và số nguyên k = 6
Các em hãy nêu cách thực hiện việc tìm kiếm số k trong dãy trên và đưa ra vị trí của nó trong dãy?
GV: Với cách này thì ta phải thực hiện lần lượt từ phần tử đầu đến phần tử cuối của dãy. Em nào có cách khác không?






GV: với cách 2 mà em đã nêu ra thì đó chính là thuật toán tìm kiếm nhị phân mà các em đã được học từ lớp 10. Cụ thể, thuật toán đó như sau:
- Bước 1: Nhập N, các số hạng A1, A2,..,AN và khóa k;
- Bước 2: Dau <- 1, cuoi <- n;
- Bước 3: Giua <- [
];
- Bước 4: Nếu AGiua = k thì thông báo chỉ số giữa, rồi kết thúc