Soạn mới giáo án Khoa học máy tính 11 kết nối tri thức bài 30: Thiết lập thư viện cho chương trình

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV chia lớp thành các nhóm, mỗi nhóm 2 - 4 HS.

- GV đưa một số hàm của thư viện math, yêu cầu nhóm HS thảo luận trả lời câu hỏi Hoạt động 1 tr.137 SGK:

Em hãy đọc, thảo luận và trả lời các câu hỏi sau:

1. Vì sao lại cần thư viện chương trình?

2. Ý nghĩa của các hàm trong thư viện chương trình là gì?

- GV giao cho mỗi nhóm thực hiện tạo riêng một thư viện tự định nghĩa.

- GV yêu cầu HS trả lời câu hỏi Củng cố tr.138 SGK: Những câu nào sau đây sai về ý nghĩa của việc sử dụng thư viện khi viết chương trình?

A. Chương trình sẽ ngắn hơn.

B. Các hàm thư viện được viết một lần và sử dụng nhiều lần.

C. Chương trình sáng sủa, dễ hiểu hơn.

D. Chương trình sẽ chạy nhanh hơn.

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và thực hiện nhiệm vụ được giao.

- GV quan sát, hướng dẫn (nếu cần).

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- Đại diện nhóm HS trình bày

*Câu hỏi củng cố tr.138 SGK: Dáp án D.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV chốt kiến thức và chuyển sang hoạt động tiếp theo..

1. Thiết lập thư viện cho chương trình

a) Một số hàm của thư viện math

- math là một thư viện các hàm chuẩn của Python liên quan đến các tính toán toán học.

Ví dụ:

sqrt() - hàm tính căn bậc hai

floor() - làm tròn xuống

ceil() - làm tròn lên.

- Để đưa thư viện vào bộ nhớ có thể dùng lệnh import hoặc from <thư viện> import <các hàm> như sau:

import math # đưa toàn bộ thư viện math vào bộ nhớ

hoặc

from  math import sqrt, floor, ceil # chỉ đưa vào bộ nhớ ba hàm

Ví dụ:

>>> from  math import sqrt, floor, ceil

>>> sqrt(5)

2.23606797749979

>>> floor(8.7)

8

>>> ceil(7.1)

8

b) Tự thiết lập thư viện

- Cách thiết lập: Đưa các hàm chuẩn vào một tệp chương trình và đặt tên của tệp này chính là tên thư viện muốn lưu trữ.

Ví dụ: Tệp chương trình lib.py đóng vai trò như một thư viện. Thư viện này có hai hàm như sau:

lib.py

1 def NhapDL():

2     S = input("Nhập dãy số nguyên cách nhau bởi dấu cách")

3     A = [int(x) for x in S.split()]

4     return A

5 def InsertionSort(A):

6     n = len(A)

7     for i in range(1,n):

8       value = A[i]

9       j = i-1

10     while j >= 0 and A[j] > value:

11          A[j+1] = A[j]

12          j = j-1

13      A[j+1] = value

Chương trình sử dụng thư viện có thể như sau (đặt tệp chương trình này cùng thư mục với tệp thư viện lib.py

1 from lib import *# Đưa tất cả các hàm của thư viện lib vào bộ nhớ

2 A = NhapDL()

3 InsertionSort(A)

4 print(A)

⇨ Kết luận: Thư viện chương trình là tập hợp các hàm được đặt trong các mô đun độc lập để dùng chung cho nhiều chương trình khác nhau. Các thư viện này có thể được dùng nhiều lần và có thể cập nhật, nâng cấp bất cứ lúc nào. Trong Python, lệnh import có chức năng đưa thư viện vào bộ nhớ để sẵn sàng sử dụng.

HOẠT ĐỘNG CỦA GV VÀ HS

SẢN PHẨM DỰ KIẾN

Bước 1: GV chuyển giao nhiệm vụ:

- GV tổ chức cho HS tiếp tục hoạt động nhóm và giao nhiệm vụ:

+ Nhiệm vụ 1. Mô hình danh sách liên kết: Nhóm HS thực hiện Hoạt động 2 tr.139 SGK:

Đọc, trao đổi và thảo luận để biết cấu trúc dữ liệu của danh sách liên kết và các thao tác dữ liệu cơ bản trên danh sách liên kết.

+ Nhiệm vụ 2. Lập trình cấu trúc danh sách liên kết trên Python: Nhóm HS thực hiện lập trình, cài đặt cấu trúc danh sách liên kết trên Python và các hàm tương ứng.

- Sau khi hoạt động hình thành kiến thức, GV yêu cầu HS trả lời câu hỏi Củng cố tr.142 SGK:

1. Đoạn chương trình sau thực hiện công việc gì?

from LinkedList import *

L = LL()

insert(L,10)

insert(L,20)

show(L)

2. Viết đoạn chương trình ngắn sử dụng thư viện LinkedList để thiết lập một danh sách liên kết L và bổ sung các tên "Bình", "Hoa", "Hà" vào danh sách này.

Bước 2: HS thực hiện nhiệm vụ học tập:

- HS thảo luận nhóm, đọc SGK và thực hiện nhiệm vụ được giao.

- GV quan sát, hướng dẫn (nếu cần).

Bước 3: Báo cáo kết quả hoạt động, thảo luận:

- GV mời 1 - 2 nhóm trình bày kết quả (Toàn bộ chương trình - Dưới hoạt động).

- HS xung phong trả lời câu hỏi củng cố:

1. Chương trình thực hiện các công việc sau:

+ Tạo một danh sách liên kết rỗng

+ Bổ sung các phân tử có khóa 10, 20 vào danh sách

+ In danh sách ra màn hình

2. Cần thực hiện các lệnh sau:

L = LL()

insert(L,"Bình")

insert(L,"Hoa")

insert(L,"Hà"

show(L)

- Các nhóm khác nhận xét, bổ sung cho nhóm bạn.

Bước 4: Đánh giá kết quả thực hiện:

- GV nhận xét, đánh giá kết quả thảo luận của HS.

- GV chú ý thêm về cách thiết lập cấu trúc danh sách liên kết (Linked List) trong Python:

+ Mô hình danh sách liên kết tổng quát được mô tả trong sơ đồ sau:

+ Để thiết lập danh sách liên kết chúng ta cần tạo hai cấu trúc (lớp) chính là cấu trúc LL và Node.

Cấu trúc Node:

class Node:

   def _init­_(self,key):

    self.key = key

    self.next = None

Cấu trúc LL:

class LL:

   def_init_(self):

   self.head = None

+ Lệnh sau sẽ tạo một danh sách rỗng: L = LL()

+ Danh sách L trên là rỗng vì đầu của danh sách chỉ vào None (L.head = None).

+ Để tạo một Node có khóa, ví dụ 10, chúng ta thực hiện lệnh:

x = Node(10)

+ Sau đó sẽ đặt node này vào vị trí đầu tiên của L bằng lệnh sau:

L.head = x

- GV tổng kết và chốt kiến thức.

2. Cấu trúc danh sách liên kết

- Mỗi danh sách liên kết sẽ bao gồm hai cấu trúc dữ liệu:

+ Cấu trúc Node mô tả các phần tử độc lập của danh sách. Tối thiểu mỗi node cần có thông tin dữ liệu key (khóa) và thuộc tính next dùng để kết nối sang phần tử tiếp theo trong danh sách.

+ Cấu trúc LL (Linked list) sẽ có thông tin head (đầu) sẽ luôn chỉ vào node đầu tiên của danh sách liên kết.

- Một số lệnh, thao tác chính với kiểu dữ liệu danh sách liên kết:

+ Khởi tạo một danh sách liên kết mới.

+ Bổ sung một phần tử với khóa k cho trước vào danh sách.

+ Tìm kiếm phần tử có khóa k trong danh sách cho trước.

+ Xóa phần tử có khóa k trong danh sách.

- Thiết lập một số hàm là các thao tác chuẩn trên dữ liệu danh sách liên kết.

1. Hàm insert(L,k) sẽ bổ sung (chèn) node với khóa k vào đầu của danh sách L.

Chương trình như sau:

1 def insert(L,k):

2     node = Node(k)

3     node.next = L.head

4     L.head = node

2. Hàm delete_first(L) sẽ xóa node đầu tiên của danh sách (nếu danh sách không rỗng).

Chương trình như sau:

1 def delete_first(L,k):

2     if L.head != None:

3        L.head = L.head.next

3. Hàm tìm kiếm phần tử có khóa k trong danh sách L. Nếu tìm thấy sẽ trả về phần tử (node) tương ứng, nếu không tìm thấy trả về None.

Việc tìm kiếm bắt đầu từ node đầu tiên của danh sách (dòng 2). Lần lượt duyệt theo từng phàn tử của danh sách cho đến khi nào tìm thấy phần tử có khóa k hoặc đi đến cuối danh sách thì dừng (các lệnh dòng 3,4).

1 def search(L,k):

2     x = L.head

3     while x != None and x.key != k:

4         x = x.next

5     return x

4. Hàm xóa phần tử có khóa k trong danh sách L.

- Nếu phần tử cần tìm là node đầu tiên của danh sách thì cách xóa giống hàm delete_first().

- Trong trường hợp tổng quát cần duyệt để tìm phần tử của danh sách có khóa k. Trong quá trình tìm luôn lưu trữ biến z là node trước của biến y cần xóa (lệnh x.next = y.next).

5. Hàm show(L) có tính năng hiển thị toàn bộ thông tin của danh sách liên kết.

1 def show(L):

2     x = L.head

3     while x != None:

4         print(x.key, end = " ")

5         x = x.next

6     print()

- Toàn bộ thư viện chuẩn của cấu trúc danh sách liên kết (Đính kèm dưới hoạt động)

- Một số ví dụ thiết lập cấu trúc dữ liệu Linked List:

a) Thiết lập một danh sách rỗng

L = LL()

b) Thiết lập một danh sách bao gồm hai node có khóa là 5, 2.

L = LL()

insert(L,5)

insert(L,2)

c) Thiết lập một danh sách bao gồm các phần tử lấy từ dãy A cho trước

A = [5,2,8,10,0,3]

L = LL()

for k in A:

     insert(L,k)

⇨ Kết luận:

* Danh sách liên kết là cấu trúc dữ liệu bao gồm:

- Cấu trúc node mô tả các phần tử của danh sách. Mỗi node sẽ có dữ liệu khoá (key) là thông tin chính và thông tin next để kết nối sang phần tử tiếp theo của danh sách.

- Cấu trúc head là đầu của mỗi danh sách liên kết. Head luôn chỉ vào node đầu tiên của danh sách.

- Node cuối cùng của danh sách sẽ có thông tin next = None (dữ liệu rỗng).

* Có thể thiết lập các hàm tìm kiếm, bổ sung hoặc xóa thông tin trên danh sách liên kết.