Giáo án Tin học 10 kì 1 soạn theo công văn 5512

Nội dung

Nhận biết

MĐ1

Thông hiểu

MĐ2

Vận dụng

MĐ3

Vận dụng cao

MĐ4

Bài toán

Nêu được bài toán tìm kiếm

Xác định được Input và Output

Ý tưởng

Nêu được ý tưởng thuật toán

Thuật toán

Nêu được thuật toán

Phân tích được các bước thực hiện của thuật toán. Giải thích được các biến trong thuật toán.

Nêu được thuật toán đếm các số có giá trị bằng K cho trước

Xây dựng được thuật toán khác từ thuật toán tìm kiếm tuần tự

Ví dụ

Demo được thuật toán thông qua các ví dụ cụ thể.

HOẠT ĐỘNG CỦA GV HS

SẢN PHẨM DỰ KIẾN

- Bước 1: Chuyển giao nhiệm vụ:

- Phân chia lớp thành 4 nhóm thảo luận ý tưởng để tìm số có giá trị bằng min.

- Theo dõi, hướng dẫn, giúp đỡ HS thực hiện nhiệm vụ

- Đánh giá kết quả (sản phẩm) thực hiện nhiệm vụ của học sinh.

- Bước 2: Thực hiện nhiệm vụ:

- HS thảo luận tìm ý tưởng:

Lấy min so sánh với các số trong dãy (so sánh từ 1 đến N). Nếu có thì thông báo vị trí tìm thấy.

- Thực hiện nhiệm vụ học tập

- Trao đổi thảo luận

- Bước 3: Báo cáo, thảo luận:

- Báo cáo kết quả, thảo luận. HS cập nhật sản phẩm của hoạt động học.

- Bước 4: Kết luận, nhận định:

Để thực hiện được việc tìm kiếm số có giá trị bằng min ta thực hiện tìm kiếm từ đầu dãy đến cuối dãy gọi là tìm kiếm tuần tự.

Tìm vị trí của giá trị bằng với giá trị nhỏ nhất trong dãy số nguyên. (Giả sử trong dãy có 1 số bằng min)

HOẠT ĐỘNG CỦA GV HS

SẢN PHẨM DỰ KIẾN

- Bước 1: Chuyển giao nhiệm vụ:

- Trong cuộc sống chúng ta, thường xảy ra việc tìm kiếm. Chẳng hạn: tìm kiếm tên của 1 học sinh trong 1 lớp, tìm 1 quyển sách trong thư viện. Điều quan tâm ở đây là tìm kiếm như thế nào?

- Dựa vào SGK/Tr40 hãy nêu bài toán tìm kiếm.

? Tìm kiếm trong bài toán đặt ra là thực hiện tìm kiếm số hay là thông tin khác?

? Em hãy cho ví dụ về tìm kiếm một số trong dãy?

? Với ý tưởng trên em hãy xác định bài toán?

- Bước 2: Thực hiện nhiệm vụ:

- Lắng nghe

- HS thực hiện

- Bước 3: Báo cáo, thảo luận:

- Gọi học sinh khác nhận xét.

- Bước 4: Kết luận, nhận định:

- Nhận xét và hoàn thành kiến thức.

- Trả lời:

Cho dãy A gồm N số nguyên khác nhau: a₁,a₂,…,a_N và mpptk số nguyên k. Cần biết hay không chỉ số I (1<=i<=N) mà a_i = k. Nếu có hãy cho biết chỉ số đó.

- Trả lời: Tìm số có giá trị bằng một số cho trước (khóa tìm kiếm).

- Trả lời:

Ví dụ: 5 7 1 4 2

+ k = 2 ... I = ?

+ k = 6 ... I = ?

- HS:

Input: Dãy A gồm N số nguyên a₁,a₂,…,a_N và khóa k.

Output: chỉ số I mà a_i = k.hoặc không có số hạng nào.

Thuật toán tìm kiếm tuần tự (Sequential sort)

Bài toán: Cho dãy A gồm N số nguyên khác nhau: a₁,a₂,…,a_N và mpptk số nguyên k. Cần biết hay không chỉ số I (1<=i<=N) mà a_i = k. Nếu có hãy cho biết chỉ số đó.

Các bước giải bài toán: có 3 bước.

Xác định bài toán:

Input: Dãy A gồm N số nguyên a₁,a₂,…,a_N và khóa k.

Output: chỉ số I mà a_i = k.hoặc không có số hạng nào.

HOẠT ĐỘNG CỦA GV HS

SẢN PHẨM DỰ KIẾN

- Bước 1: Chuyển giao nhiệm vụ:

- Yêu cầu học sinh thảo luận nhóm theo bàn : thảo luận và báo cáo về ý tưởng của thuật toán.

- Chia nhóm và thảo luận:

Lần lượt từ số hạng thứ 1, so sánh các số hạng đến khi gặp số hạng bằng khóa, hoặc không có giá trị nào bằng khóa

- Bước 2: Thực hiện nhiệm vụ:

- Quan sát quá trình thảo luận của học sinh và nhắc nhở (nếu cần).

- Bước 3: Báo cáo, thảo luận:

- Yêu cầu một nhóm bất kỳ báo cáo bài thảo luận.

- Cho học sinh khác nhận xét.

- Bước 4: Kết luận, nhận định:

- Nhận xét và chốt kiến thức

- Nhận xét, hoàn thành ý tưởng.

Ý tưởng: Tìm kiếm tuần tự một cách tự nhiên. Lần lượt từ số hạng thứ 1, so sánh các số hạng đến khi gặp số hạng bằng khóa, hoặc không có giá trị nào bằng khóa.

HOẠT ĐỘNG CỦA GV HS

SẢN PHẨM DỰ KIẾN

- Bước 1: Chuyển giao nhiệm vụ:

- GV treo bảng phụ có chưa thuật toán và cho Hs đọc, suy nghĩ trong vòng 3 phút.

- Bước 2: Thực hiện nhiệm vụ:

- Yêu cầu một HS lên giải thích các bước của thuật toán.

- Theo dõi bảng phụ.

- Giải thích các bước của huật toán.

- Nhận xét phần trình bày của bạn.

- Lắng nghe, ghi bài.

- Trả lời: i <- 1 đến N + 1.

- Trả lời: B3, 4, 5.

- Bước 3: Báo cáo, thảo luận:

- Gọi HS khác nhận xét phần trình bày của bạn.

- Bước 4: Kết luận, nhận định:

- Nhận xét, hoàn thiện kiến thức.

? Trong thuật toán trên i có giá trị như thế nào?

? Có những bước nào có thể thực hiện lặp đi lặp lại nhiều lần?

Thuật toán. Tìm kiếm tuần tự

B1: Nhập N, các số hạng khác nhau a₁,a₂,…,a_N và khóa k

B2: i ... 1;

B3: Nếu a_i = k thì thông qua chỉ số i, rồi kết thúc

B4: i ... i + 1;

B5: Nếu i > N thì thông báo dãy A không có số hạng nào bằng k rồi kết thúc.

B6: Quay lại bước 3.

HOẠT ĐỘNG CỦA GV HS

SẢN PHẨM DỰ KIẾN

- Bước 1: Chuyển giao nhiệm vụ:

- Phân chia học sinh làm 4 nhóm, phát phiếu học tập 1 cho học sinh thảo luận.

- Bước 2: Thực hiện nhiệm vụ:

- Nhận nhóm, thảo luận hoàn thành phiếu học tập.

- Nộp phiếu học tập.

- Bước 3: Báo cáo, thảo luận:

- Hướng dẫn, quan sát các nhóm thảo luận.

- Yêu cầu các nhóm nộp phiếu học tập.

- Bước 4: Kết luận, nhận định:

- Chiếu phiếu học tập của một nhóm lên máy chiếu và yêu cầu nhóm khác nhận xét.

- Nhận xét và hoàn thiện kiến thức.

Dãy A có N = 7, A= 7, 12, 4, 6, 11, 10, 8 và khóa k = 10

Tìm chỉ số i để a_i = k.

i 1 2 3 4 5 6 7

a_i 7 12 4 6 11 10 8

k = 10 ... i = 6

HOẠT ĐỘNG CỦA GV HS

SẢN PHẨM DỰ KIẾN

- Bước 1: Chuyển giao nhiệm vụ:

- Phân chia học sinh làm 4 nhóm, phát phiếu học tập 2 cho học sinh thảo luận.

- Bước 2: Thực hiện nhiệm vụ:

- Nhận nhóm, thảo luận hoàn thành phiếu học tập.

- Nộp phiếu học tập.

- Bước 3: Báo cáo, thảo luận:

- Hướng dẫn, quan sát các nhóm thảo luận.

- Yêu cầu các nhóm nộp phiếu học tập.

- Bước 4: Kết luận, nhận định

- Chiếu phiếu học tập của một nhóm lên máy chiếu và yêu cầu nhóm khác nhận xét.

- Nhận xét và hoàn thiện kiến thức.

Dãy A có N = 7, A= 7, 12, 4, 6, 11, 10, 7 và khóa k = 7

Đếm số lần xuất hiện của khóa K trong dãy A..

i 1 2 3 4 5 6 7

a_i 7 12 4 6 11 7 8

k = 10 ... dem = 2