CHỦ ĐỀ 1. Máy tính và xã hội tri thức
Bài 1. Hệ điều hành
SAU BÀI HỌC NÀY EM SẼ:
Trình bày được sơ lược lịch sử phát triển của các hệ điều hành thông dụng cho máy tính cá nhân (PC).
Chỉ ra được một số đặc điểm của hệ điều hành cho thiết bị di động.
Trình bày được một cách khá quát mối quan hệ giữa phần cứng, hệ điều hành và phần mềm ứng dụng cũng như vai trò của mỗi thành phần trong hoạt động chung của cả hệ thống.
Khi chưa có hệ điều hành, con người phải can thiệp vào hầu hết quá trình hoạt động của máy tính nên hiệu quả khai thác sử dụng máy tính rất thấp. Sự ra đời của hệ điều hành đã giúp khắc phục được tình trạng đó. Việc sử dụng máy tính về cơ bản được thực hiện thông qua hệ điều hành. Em hãy chỉ ra một số công việc mà hệ điều hành thực hiện.
1. LỊCH SỬ PHÁT TRIỂN CỦA HỆ ĐIỀU HÀNH MÁY TÍNH CÁ NHÂN
Hoạt động 1 Tìm hiểu các chức năng của hệ điều hành
Hệ điều hành của các loại máy tính nói chung có năm nhóm chức năng sau:
– Quản lí thiết bị (CPU, bộ nhớ hay thiết bị ngoại vi).
– Quản lí việc lưu trữ dữ liệu (quản lí tệp và thư mục).
– Tổ chức thực hiện các chương trình, điều phối tài nguyên cho các tiến trình xử lí trên máy tính. Nói cách khác, hệ điều hành là môi trường để chạy các ứng dụng.
– Cung cấp môi trường giao tiếp với người sử dụng.
– Cung cấp một số tiện ích giúp nâng cao hiệu quả sử dụng máy tính như định dạng đĩa, nén tệp, kiểm tra lỗi đĩa cứng, cấu hình kết nối mạng,...
Theo em, nhóm chức năng nào thể hiện rõ nhất đặc thù của hệ điều hành máy tính cá nhân?
Khác với các máy chủ, siêu máy tính do kĩ sư vận hành, máy tính cá nhân dành cho người dùng phổ thông nên sự thân thiện, dễ sử dụng là tiêu chí quan trọng nhất. Quá trình hình thành và phát triển của hệ điều hành máy tính cá nhân có liên quan chặt chẽ tới tiêu chí này và được thể hiện ở hai điểm chính sau:
Giao diện đồ hoạ.
Cơ chế plug & play để tự động nhận biết thiết bị ngoại vi khi khởi động máy tính.

Có thể nói cơ chế plug & play (“cắm và chạy”, còn được hiểu là “cắm vào là chạy”) là bước phát triển hết sức quan trọng của hệ điều hành máy tính cá nhân. Thời kì đầu, thiết bị ngoại vi nhiều khi gây phiền phức cho người sử dụng, bởi lẽ mỗi thiết bị ngoại vi của một hãng đòi hỏi phải có một phần mềm điều khiển riêng, việc cài đặt không phải luôn dễ dàng với những người ít hiểu biết về tính năng của thiết bị ngoại vi và hoạt động của nó. Cơ chế plug & play giúp hệ điều hành nhận biết các thiết bị ngoại vi ngay khi khởi động máy và có thể hỗ trợ cài đặt các chương trình điều khiển một cách tự động.
Về giao diện, ban đầu hệ điều hành máy tính cá nhân sử dụng giao diện dòng lệnh, người dùng phải gõ các lệnh, chẳng hạn trong hệ điều hành DOS, lệnh:
“erase C:\dulieu\danhsach.txt”
sẽ xoá tệp danhsach.txt nằm trong thư mục dulieu của ổ đĩa C. Mặc dù đơn giản, nhưng DOS thiếu tính trực quan, đòi hỏi người dùng phải nhớ cú pháp của từng câu lệnh.
Bước phát triển tiếp theo của hệ điều hành là sử dụng giao diện đồ hoạ với các đối tượng thể hiện bằng hình ảnh. Một số thành phần cơ bản của giao diện đồ hoạ bao gồm:
Cửa sổ là một vùng hình chữ nhật trên màn hình dành cho một ứng dụng. Cửa sổ có thể phóng to, thu nhỏ, ẩn đi hoặc đóng lại.
Hình 1.1. Giao diện lệnh của DOS
Biểu tượng dễ gợi nhớ, cho phép quan sát đối tượng dưới dạng đồ hoạ.
Chuột là phương tiện chỉ định điểm làm việc trên màn hình thể hiện bởi một con trỏ màn hình.
Giao diện đồ hoạ có tính trực quan, giúp người sử dụng giao tiếp với máy dễ dàng hơn. Các hệ điều hành cho máy tính cá nhân càng ngày càng thân thiện, một số hệ điều hành đã hỗ trợ giao tiếp bằng giọng nói.
Hai dòng máy tính cá nhân chủ đạo là dòng Mac (MacBook, iMac) sử dụng hệ điều hành đồ hoạ macOS của Apple và dòng PC sử dụng hệ điều hành đồ hoạ Windows của Microsoft. Sau đây chúng ta sẽ tìm hiểu kĩ hơn lịch sử phát triển của một hệ điều hành thương mại và một hệ điều hành nguồn mở (mã nguồn mở) phổ biến nhất.
a) Hệ điều hành Windows
Windows đã trải qua nhiều phiên bản. Sau đây là một số phiên bản quan trọng, đánh dấu các mốc phát triển của Windows.
Phiên bản 1 của Windows phát hành vào năm 1985 với giao diện đồ hoạ.
Phiên bản 3, phát hành năm 1990 bắt đầu có khả năng đa nhiệm, cho phép chạy nhiều chương trình đồng thời, giúp nâng cao hiệu quả máy tính. Chức năng kéo thả tiện lợi bắt đầu có từ phiên bản 3.1. Các tính năng làm việc với mạng bắt đầu có từ phiên bản 3.11.
Hình 1.2. Giao diện đồ hoạ của Windows

Trong vòng 10 năm đầu, về cơ bản Windows chỉ là một vỏ bọc đồ hoạ và từ đó gọi các dịch vụ của DOS. Chỉ từ phiên bản Windows 95 (1995) nhiều tính năng cơ bản của hệ điều hành mới được tích hợp trực tiếp vào Windows. Không những thế Windows 95 còn có giao diện đẹp, giao tiếp tiện lợi. Nhiều công cụ bắt đầu có từ phiên bản này hiện nay vẫn được dùng như bảng chọn Start, thanh trạng thái (Status bar), thanh công việc (Taskbar) và biểu tượng shortcut. Cơ chế plug & play lần đầu tiên được sử dụng.
Năm 2001, Microsoft phát hành Windows XP với nhiều cải tiến đáng kể về giao diện và hiệu suất làm việc với một nâng cấp quan trọng để chạy trên các bộ xử lí tiên tiến thế hệ 64 bit. Đây là một trong các phiên bản hệ điều hành thành công nhất của Microsoft với số người sử dụng rất lớn.
Các phiên bản Windows 7 (2009), Windows 8 (2012), Windows 10 (2015) và Windows 11 (2021) là một thế hệ mới với những thay đổi lớn so với Windows XP về độ an toàn, ổn định và hiệu quả sử dụng tài nguyên. Chúng dễ dùng hơn và hầu như không còn lỗi bất thường như các phiên bản trước. Windows gần như thống trị thị trường hệ điều hành máy tính cá nhân. Một thống kê vào năm 2018 cho thấy hơn 86% người dùng máy tính sử dụng Windows.
b) Hệ điều hành LINUX và các phiên bản
LINUX có nguồn gốc từ hệ điều hành UNIX - một hệ điều hành đa nhiệm (có thể chạy đồng thời nhiều chương trình) và đa người dùng (nhiều người có thể làm việc đồng thời) được phát triển từ năm 1969. UNIX đã chứng tỏ được tính hiệu quả, ổn định và an toàn cao. Phần lớn các phiên bản UNIX thương mại đều có giá thành khá cao.
Ý tưởng xây dựng một hệ điều hành
kiểu UNIX chạy trên các máy tính cá nhân được quan tâm từ giữa những năm 1980 nhưng chỉ thực sự thành công với hệ điều hành LINUX, do Linus Torvalds viết vào năm 1991. Phiên bản LINUX 1.0 được công bố chính thức năm 1994 dưới dạng mã nguồn mở cho phép bất cứ ai cũng có thể sử dụng và phát triển thêm. LINUX đã khởi đầu trào lưu phần mềm nguồn mở, có ảnh hưởng rất Hình 1.3. Màn hình nền của Ubuntu lớn đến sự phát triển của công nghệ thông tin sau này. LINUX được cộng đồng người dùng đánh giá cao và sử dụng rộng rãi. LINUX không chỉ dùng cho máy tính cá nhân mà còn dùng cho cả máy chủ và các thiết bị nhúng - các thiết bị có phần mềm được tích hợp vào phần cứng và được thiết kế riêng như ti vi, xe ô tô tự lái,… Đối với máy tính cá nhân, đã có nhiều biến thể khác nhau ra đời từ LINUX như Red Hat (viết năm 1994 và phát hành rộng rãi năm 1999), Suse (1996), Ubuntu (2004), thậm chí hệ điều hành Android của phần lớn điện thoại di động cũng được xây dựng trên lõi của LINUX.
Các hệ điều hành máy tính cá nhân phát triển theo hướng ngày càng dễ sử dụng, thể hiện ở các điểm sau:
Giao diện thân thiện, từ giao diện dòng lệnh chuyển sang giao diện đồ hoạ và tích hợp với nhận dạng tiếng nói.
Khả năng nhận biết các thiết bị ngoại vi với cơ chế plug & play giúp người sử dụng không cần quan tâm tới trình điều khiển của thiết bị ngoại vi.

Các hệ điều hành thông dụng nhất trên máy tính cá nhân là MacOS trên dòng máy MAC và Windows trên dòng máy PC. Đặc biệt LINUX và các biến thể của nó như Red Hat, Suse hay Ubuntu là hệ điều hành nguồn mở, mang đến cho người dùng các hệ điều hành mạnh mẽ, tin cậy và chi phí thấp.
Nêu các nhóm chức năng chính của hệ điều hành.
Nêu các đặc điểm cơ bản của hệ điều hành máy tính cá nhân.
2. HỆ ĐIỀU HÀNH CHO THIẾT BỊ DI ĐỘNG
Hoạt động 2 Một số đặc điểm của hệ điều hành cho thiết bị di động
Điện thoại thông minh, máy tính bảng (gọi chung là thiết bị di động) thực chất là các máy tính cá nhân. Sự khác nhau giữa hệ điều hành cho thiết bị di động và hệ điều hành của máy tính có nguồn gốc từ sự khác biệt về tính năng, tác dụng của hai loại thiết bị này. Hãy cùng thảo luận để chỉ ra những điểm khác nhau đó.
Ra đời sau máy tính nhưng điện thoại thông minh và máy tính bảng được phổ cập
nhanh, thúc đẩy mạnh mẽ tiến trình tin học hoá xã hội. Điện thoại thông minh không chỉ dùng để nghe, gọi mà còn được trang bị rất nhiều tiện ích như chụp ảnh, quay phim, định vị, ghi nhận tình trạng sức khoẻ. Do tính di động mà hệ điều hành cho thiết bị di động chú trọng đến khả năng kết nối mạng không dây như wifi, Internet di động (dịch vụ 3G, 4G, 5G,…), bluetooth hay giao tiếp gần NFC. Các thiết bị di động phần lớn nhỏ, gọn và giao tiếp phổ biến nhờ các thao tác vuốt, chạm, lắc,… Chúng thường được trang bị màn hình cảm ứng, bàn phím ảo và nhiều cảm biến để tạo các giao tiếp hay ứng dụng độc đáo. Có nhiều hệ điều hành cho các thiết bị di động nhưng phổ biến hơn cả là iOS của Apple dùng cho iPhone, iPad và Android của Google dùng cho hầu hết các dòng điện thoại khác.
Một số khác biệt của hệ điều hành cho thiết bị di động so với hệ điều hành cho máy tính cá nhân: • Giao diện đặc biệt thân thiện nhờ nhận dạng hành vi của người dùng thông qua các cảm biến. • Dễ dàng kết nối mạng di động. • Nhiều tiện ích hỗ trợ cá nhân. Hai hệ điều hành phổ biến cho thiết bị di động là iOS của Apple và Android của Google.
1. Vì di, sao hệ điều hành di động ưu tiên cao cho giao tiếp thân thiện và kết nối mạng động?
Kể tên ba tiện ích thường có trên thiết bị di động và chức năng của nó.

3. QUAN HỆ GIỮA HỆ ĐIỀU HÀNH, PHẦN CỨNG VÀ PHẦN MỀM ỨNG DỤNG
Hoạt động 3 Vai trò của hệ điều hành
Có hay không trường hợp phần mềm chạy trên một thiết bị không có hệ điều hành? Khi nào cần phải có hệ điều hành?
Thời kì mới có máy tính, chưa có hệ điều hành, người sử dụng phải nạp thủ công
chương trình vào bộ nhớ như gõ lệnh hay nhập chương trình được mã hoá trên băng giấy hoặc bìa đục lỗ, sau đó nhấn một phím trên bàn điều khiển và đợi kết quả. Ngày nay, có nhiều thiết bị được điều khiển bởi các bộ vi xử lí, cài sẵn chương trình ghi trong bộ nhớ ROM, bật lên là chạy không cần hệ điều hành. Ví dụ hệ thống điều khiển lò vi sóng cho phép người dùng chọn lựa các chế độ nấu ăn. Tuy nhiên cách này chỉ phù hợp với những thiết bị chuyên dụng, chỉ làm một việc, không thích hợp với các thiết bị đa năng như máy tính có khả năng thực hiện nhiều công việc. Với thiết bị đa năng, người dùng có nhu cầu nạp nhiều phần mềm ứng dụng và dữ liệu vào bộ nhớ ngoài (cần tổ chức dữ liệu), chọn phần mềm để chạy (cần giao diện làm việc). Khi Người dùng chạy, cần điều phối tài nguyên cho các ứng dụng như bộ nhớ, công suất CPU, các thiết bị ngoại vi. Cần có hệ điều hành để đáp ứng các nhu cầu trên. Hệ điều hành cung cấp các dịch vụ điều khiển máy tính để thực hiện
Phần mềm, ứng dụng
Hệ điều, hành
thiết bị, vào/ra)
các dịch vụ do hệ điều hành cung cấp để thực hiện.
Như vậy, phần cứng là thiết bị xử lí thông tin, hệ điều Hình 1.4. Mối quan hệ giữa hành là môi trường trung gian giúp phần mềm ứng dụng khai phần cứng, phần mềm ứng thác phần cứng. Quan hệ giữa hệ điều hành, phần cứng và dụng và hệ điều hành phần mềm ứng dụng được minh hoạ trong Hình 1.4.
Hệ điều hành là môi trường để phần mềm ứng dụng khai thác hiệu quả phần cứng.
Nêu lí do thiết bị xử lí đa năng cần có hệ điều hành.
Nêu mối quan hệ giữa phần cứng, phần mềm ứng dụng và hệ điều hành.
LUYỆN TẬP
Em hiểu thế nào về tính thân thiện của hệ điều hành?
Hệ điều hành cung cấp môi trường giao tiếp với người sử dụng như thế nào? Môi trường giao tiếp đó thể hiện như thế nào trên hệ điều hành Windows?
VẬN DỤNG
Em hãy tìm hiểu xem ngoài máy tính còn có thiết bị điện gia dụng nào sử dụng hệ điều hành không.
Thực ra, LINUX là hệ điều hành có nguồn gốc từ hệ điều hành UNIX. Hãy tìm hiểu lịch sử của hệ điều hành LINUX để biết thêm về hệ điều hành UNIX.

CHỦ ĐỀ 6. Kĩ thuật lập trình
Bài 17. Dữ liệu mảng một chiều và hai chiều
SAU BÀI HỌC NÀY EM SẼ:
Biết cách thiết lập và làm việc với cấu trúc dữ liệu mảng một chiều và hai chiều.
Em đã biết thiết lập cấu trúc dữ liệu đóng vai trò quan trọng khi giải quyết trong các bài toán thực tế trên máy tính. Trong các bài toán thực tế sau em sẽ thiết lập cấu trúc dữ liệu như thế nào?
– Lập danh sách họ tên các bạn lớp em. Sau đó có thể tìm kiếm, sắp xếp và thực hiện các bài toán quản lí khác.
– Giả sử lớp em cần khảo sát ý kiến về một vấn đề nào đó. Mỗi học sinh cần có đánh giá theo 4 mức, kí hiệu lần lượt là Đồng ý (2); Không phản đối (1); Không ý kiến (0); Phản đối (–1). Em sẽ tổ chức dữ liệu khảo sát như thế nào để có thể dễ dàng cập nhật và tính toán theo dữ liệu khảo sát.
– Em được giao nhiệm vụ thiết lập và lưu trữ một danh sách các địa điểm là nơi các bạn trong lớp sẽ thường xuyên đến tham quan và trải nghiệm thực tế. Mỗi địa điểm như vậy cần nhiều thông tin, nhưng thông tin quan trọng nhất là toạ độ (x, y) của thông tin đó trên bản đồ. Em sẽ dùng cấu trúc dữ liệu gì để mô tả danh sách các địa điểm này?
1. CẤU TRÚC DỮ LIỆU MẢNG MỘT CHIỀU
Trong Tin học, dữ liệu mảng một chiều, thường được gọi là cấu trúc dữ liệu tuyến tính, là cấu trúc dữ liệu bao gồm một dãy các phần tử dữ liệu có cùng kiểu. Các phần tử của mảng sẽ được truy cập theo chỉ số, cho phép các thao tác đơn giản như truy cập và thay đổi giá trị.
Trong Python, dữ liệu mảng một chiều có thể được biểu diễn bằng danh sách (list) với các phần tử có cùng kiểu dữ liệu.
Hoạt động 1 Tìm hiểu cấu trúc dữ liệu mảng một chiều trong Python
Thực hiện các thao tác sau, quan sát, trao đổi và thảo luận, từ đó nhận biết về cấu trúc dữ liệu mảng một chiều trong Python.
a) Thiết lập các mảng một chiều, thông qua kiểu dữ liệu list trong Python.
![](https://cloud.olm.vn/upload/thuvienso/sgk/md/tin-hoc-11-khmt/7e6cb63fb82de73f.webp)
>>> A = [1, 3, 5, 7, 9, 11]
>>> B = ["Hà","Bình","Ngọc","Anh"]
>>> C = [9.5, 8.0, 10, 7.2]

b) Có thể truy cập từng phần tử của mảng một chiều theo chỉ số. Toán tử in kiểm tra một đối tượng có nằm trong mảng hay không. Trong Python, chỉ số bắt đầu từ 0.
7 in A True c) Có thể dễ dàng duyệt từng phần tử của mảng một chiều bằng lệnh for. >>> for hs in B:
print(hs, end = " ") Hà Bình Ngọc Anh d) Các lệnh cơ bản làm việc với danh sách trong Python đã được học trong chương trình Tin học 10, ví dụ: append (bổ sung phần tử vào cuối), remove (xoá một phần tử), insert (bổ sung phần tử vào vị trí bất kì), clear (xoá toàn bộ các phần tử của danh sách).
Lưu ý: Mặc dù mảng được biểu diễn bằng dữ liệu list, nhưng không được đồng nhất khái niệm mảng của khoa học máy tính với kiểu dữ liệu list trong Python.
Cấu trúc dữ liệu mảng một chiều trong Python có thể biểu diễn bằng kiểu dữ liệu danh sách (list) với chức năng truy cập dễ dàng từng phần tử theo chỉ số, truy cập theo vùng chỉ số. Toán tử in và lệnh for .. in sẽ hỗ trợ duyệt từng phần tử của mảng.
1. Sử trung, dụng hàm sum() tính tổng các số của một dãy, hãy viết câu lệnh tính giá trị bình của dãy số A cho trước.
Có thể duyệt các phần tử của mảng theo chiều ngược lại, từ cuối về đầu, được không?
2. CẤU TRÚC DỮ LIỆU MẢNG HAI CHIỀU
Hoạt động 2 Mô hình danh sách trong danh sách của Python
Thực hiện các lệnh sau, quan sát, trao đổi và thảo luận, từ đó nhận biết về mô hình danh sách trong danh sách của Python.
a) Xét dữ liệu biểu diễn điểm của học sinh trong lớp, mỗi phần tử sẽ bao gồm hai
thông tin là tên học sinh và điểm số. Lệnh sau sẽ tạo một bộ dữ liệu như vậy. Ta thấy mỗi phần tử của dãy này lại là một danh sách bao gồm hai phần tử.
>>> DS_diem = [["Quang",7.5],["Hà",8.0],["Bình",9.5]]
b) Nếu truy cập một phần tử của danh sách, ta nhận được một dãy bao gồm tên và điểm của học sinh tương ứng.
>>> DS_diem[1]
['Hà', 8.0]

c) Muốn truy cập một giá trị điểm cụ thể, ví dụ điểm của học sinh tên "Quang", cần thực hiện lệnh sau: >>> DS_diem[0][1] 7.5 d) Lệnh duyệt các phần tử của dãy g

Ma trận kích thước m × n sẽ bao gồm m × n phần tử, có cấu trúc bao gồm m hàng, mỗi hàng có n cột. Trong Python, mô hình ma trận m × n sẽ dễ dàng được biểu diễn

LUYỆN TẬP Giả sử số đo chiều cao các bạn trong lớp được cho trong dãy số A. Hãy viết đoạn chương trình tính: - Số đo chiều cao trung bình của cả lớp. - Số bạn c

Thực hành dữ liệu mảng một chiều và hai chiều
SAU BÀI HỌC NÀY EM SẼ:
Sử dụng được mảng một chiều và hai chiều trong lập trình.
Sử dụng được kiểu dữ liệu list trong một vài bài toán cụ thể.
Trong bài học trước, em đã biết cấu trúc dữ liệu mảng có thể giúp giải quyết tốt các bài toán quản lí danh sách trong thực tế. Việc quản lí danh sách điểm kiểm tra của một môn học là quản lí danh sách học sinh và mỗi học sinh có một danh sách điểm kiểm tra. Bảng điểm môn học cả lớp được coi là danh sách của danh sách điểm của các học sinh. Theo em, người ta dùng mảng một chiều hay hai chiều để quản lí danh sách điểm một môn học của mỗi học sinh? để quản lí điểm một môn học của cả lớp?
Nhiệm vụ 1
Viết chương trình quản lí điểm kiểm tra một môn học của một học sinh trong một học kì.
Chương trình được thực hiện như sau:
– Nhập điểm: yêu cầu người dùng nhập các đầu điểm kiểm tra (từ hai đầu điểm trở lên).
– Thống kê điểm: chương trình duyệt qua các đầu điểm rồi tính và in ra điểm trung bình kiểm tra, điểm thấp nhất, cao nhất.
Hướng dẫn:
Phân tích: Nhiệm vụ này có thể được thực hiện bằng cách sử dụng mảng một chiều, cụ thể là sử dụng danh sách trong Python. Việc nhập điểm được thực hiện ngay trên màn hình. Sau khi đã có danh sách các đầu điểm, dùng cấu trúc for để duyệt qua các phần tử của mảng để tính tổng điểm, thống kê điểm cao nhất, thấp nhất.
qldiem.py
marks = []
line = input("Hãy nhập các điểm kiểm tra cách nhau bởi dấu cách: ")
marks = [float(x) for x in line.split()]
total = 0
Min = marks[0]
Max = marks[0]
for m in marks:
total = total + m
if Min > m:
Min = m
if Max < m:

12 Max = m
13 print("Điểm trung bình: ", total/len(marks))
14 print("Điểm cao nhất: ", Max)
15 print("Điểm thấp nhất: ", Min)
Nhiệm vụ 2
Viết chương trình quản lí điểm kiểm tra một môn học trong một học kì của tất cả học sinh trong lớp.
Chương trình được thực hiện như sau: - Nhập dữ liệu: yêu cầu người dùng nhập số học sinh trong lớp, sau đó với mỗi học sinh hỏi người dùng nhập tên học sinh rồi nhập các đầu điểm của học sinh đó. - Thống kê dữ liệu: chương trình in ra danh sách các học sinh với điểm trung bình kiểm tra của họ, tên học sinh có điểm trung bình cao nhất và điểm kiểm tra thấp nhất trong tất cả các đầu điểm.
Hướng dẫn:
Phân tích: Nhiệm vụ này có thể được thực hiện bằng cách sử dụng một mảng hai chiều để lưu tất cả điểm của học sinh trong lớp, mỗi hàng là điểm của một học sinh, điểm cụ thể là các phần tử của hàng. Để thống kê, cần dùng vòng lặp để duyệt qua từng hàng, tính trung bình từng hàng và xét từng điểm để tìm ra đầu điểm thấp nhất. Trong khi tính, tìm điểm trung bình kiểm tra của từng học sinh, cần lưu lại số thứ tự của học sinh có điểm trung bình cao nhất để tham chiếu in ra tên của học sinh đó.
qldiem_ca_lop.py
1 names = []
2 marks_all = []
3 n = int(input("Hãy nhập số lượng học sinh: "))
4
5 for i in range(n):
6 name = input("Tên học sinh thứ " + str(i+1) + ": ")
7 names.append(name)
8 line = input("Điểm kiểm tra của học sinh thứ "+str(i+1)+": ")
9 marks = [float(x) for x in line.split()]
10 marks_all.append(marks)
11 12# Định nghĩa các biến để thống kê 13 max_avg = 0 14 index_max_avg = 0 15 Min = marks_all[0][0] 16
17#Duyệt qua mảng 2 chiều
18 for i in range(n):
19 total = 0
20 for j in range(len(marks_all[i])):
21 total = total + marks_all[i][j]

22 if Min > marks_all[i][j]:
23 Min = marks_all[i][j]
24 avg = total/len(marks_all[i])
25 print("Điểm trung bình của",names[i],":",avg)
26 if max_avg < avg:
27 max_avg = avg
28 index_max_avg = i
29
30 #In ra kết quả
31 print(names[index_max_avg], "đạt điểm trung bình", max_avg,"cao nhất lớp.")
32 print("Điểm thấp nhất:",Min)
LUYỆN TẬP
Chỉnh sửa lại chương trình của Nhiệm vụ 1 để bổ sung chức năng:
a) Thông báo điểm đầu tiên và điểm cuối cùng trong danh sách.
b) Cho phép người dùng tra cứu đầu điểm thứ n với quy ước n bắt đầu từ 1 ứng với điểm đầu tiên. Nếu n lớn hơn tổng số đầu điểm hoặc nhỏ hơn 1, cần thông báo không hợp lệ và yêu cầu người dùng nhập lại.
Chỉnh sửa lại chương trình để người dùng có thể:
a) Tra cứu các đầu điểm kiểm tra theo STT (số thứ tự) của học sinh. Quy ước số thứ tự bắt đầu từ 1. Nếu người dùng nhập STT lớn hơn số lượng học sinh thì chương trình thông báo STT không hợp lệ và yêu cầu nhập lại.
b) Tra cứu điểm kiểm tra cụ thể lần thứ n của một học sinh theo STT. Nếu n và STT không hợp lệ chương trình cần thông báo và yêu cầu nhập lại.
VẬN DỤNG
Viết chương trình nhập vào từ bàn phím danh sách tên (không gồm họ và đệm) học sinh cách nhau bởi dấu cách và lưu vào trong một mảng. Giả thiết rằng tên không gồm khoảng trắng. Sau đó hãy thống kê xem có bao nhiêu tên khác nhau và mỗi tên xuất hiện bao nhiêu lần trong danh sách.
Viết chương trình nhập từ bàn phím số tự nhiên m và n. Sau đó lần lượt nhập m dòng, mỗi dòng bao gồm n số cách nhau bởi dấu cách. Đưa dữ liệu đã nhập vào ma trận A, in ma trận A ra màn hình. Sau đó:
a) Tính tổng các phần tử ma trận A.
b) In ra dòng có tổng các phần tử lớn nhất (nếu có nhiều dòng bằng nhau thì in tất cả các dòng).
c) In ra giá trị các phần tử phân biệt trong ma trận tức là nếu có các giá trị xuất hiện nhiều lần trong ma trận A thì chỉ in ra một lần.
d) Cho phép người dùng tìm số lần xuất hiện của một số bất kì trong ma trận A, ví dụ người dùng nhập vào số 3, chương trình thông báo số 3 xuất hiện x lần trong ma trận tại các vị trí (i, j) cụ thể.

Bài 19. Bài toán tìm kiếm
SAU BÀI HỌC NÀY EM SẼ:
Biết được ý nghĩa của bài toán tìm kiếm trên thực tế.
Biết và thực hiện được chương trình tìm kiếm tuần tự và tìm kiếm nhị phân.
Trò chơi lật thẻ
Giả sử có một bộ thẻ, trên mỗi thẻ in một số bất kì. Các thẻ được xếp úp mặt xuống bàn theo thứ tự tăng dần của các số ghi trên thẻ. Người chơi mỗi lần chỉ được lật một thẻ để xem giá trị số in trên đó. Nếu giá trị số in trên thẻ lật lên bằng số K cho trước thì trò chơi kết thúc. Bạn An đã chơi bằng cách lật lần lượt từng thẻ từ đầu đến cuối. Theo em, An có chắc chắn xác định được thẻ nào in số K không? Em có cách nào xác định được thẻ in số K nhanh hơn An không?
1. BÀI TOÁN TÌM KIẾM TRÊN THỰC TẾ
Hoạt động 1 Bài toán tìm kiếm
Với các bài toán tìm kiếm sau, hãy thảo luận về miền dữ liệu và khả năng các kết quả có thể tìm được của bài toán:
Bài toán 1. Em cần tìm hình ảnh các cây hoa hồng đẹp trên Internet để đưa vào bài trình bày về cách trồng hoa.
Bài toán 2. Em cần tìm một tệp văn bản có tên bai-hoc-1.docx trên máy tính của em nhưng đã lâu rồi chưa sử dụng lại.
Bài toán 3. Em cần tìm 5 bạn học sinh có điểm trung bình các bài thi cao nhất trong kì thi Olympic Tin học năm 2020 của thành phố Hà Nội.
– Với bài toán 1, miền dữ liệu là tất cả các ảnh có trên các máy tính kết nối mạng Internet. Kết quả là các ảnh có hình hoa hồng.
– Với bài toán 2, miền dữ liệu là các tệp văn bản có trên đĩa cứng máy tính của em. Kết quả là tệp có tên bai-hoc-1.docx.
– Với bài toán 3, miền dữ liệu là danh sách học sinh và điểm các bài dự thi của kì thi Olympic Tin học thành phố. Kết quả là danh sách 5 bạn có thành tích cao nhất tính theo điểm trung bình.
Có thể nói tìm kiếm là một trong những bài toán quan trọng nhất của Tin học. Việc thiết kế thuật toán tìm kiếm sẽ phụ thuộc vào cấu trúc của miền dữ liệu cần tìm kiếm và tiêu chí cụ thể của bài toán tìm kiếm.

Em hãy xác định miền dữ liệu và nghiệm có thể của các bài toán tìm kiếm sau.
Bài toán tìm đường đi từ nhà em đến trường học dựa trên bản đồ số.
Bài toán tìm tất cả các trường trung học phổ thông (tên trường, địa chỉ) ở quận (huyện) em đang cư trú.
2. TÌM KIẾM TUẦN TỰ
Cách An lần lượt lật các thẻ từ đầu đến cuối trong phần khởi động chính là việc thực hiện tìm kiếm tuần tự trong các thẻ bài. Đây là một trường hợp riêng của việc tìm kiếm trên mô hình dữ liệu là một dãy các đối tượng (danh sách) và thuật toán được thực hiện một cách tuần tự. Để cho đơn giản, ta xét danh sách tìm kiếm là một dãy các số. Bài toán tìm kiếm được mô tả như sau:
Đầu vào: Cho trước dãy số $A[0], A[1], ..., A[n-1]$ và giá trị K.
Đầu ra: Cần tìm ra chỉ số i mà phần tử $A[i]$ có giá trị bằng K. Nếu không thấy thì trả về giá trị -1.
Hoạt động 2 Thuật toán tìm kiếm tuần tự
Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi, thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.
Cho dãy số $A = [1, 4, 7, 8, 3, 9, 10]$ và cần tìm kiếm phần tử có giá trị bằng 9.
Có thể thực hiện tìm kiếm tuần tự như sau:
Bước 1. $i = 0$: $A[0] = 1$ không bằng 9.
Bước 2. $i = 1$: $A[1] = 4$ không bằng 9.
Bước 3. $i = 2$: $A[2] = 7$ không bằng 9.
Bước 4. $i = 3$: $A[3] = 8$ không bằng 9.
Bước 5. $i = 4$: $A[4] = 3$ không bằng 9.
Bước 6. $i = 5$: $A[5] = 9$ là phần tử cần tìm.
Như vậy phần tử cần tìm có chỉ số 5.
Các bước thực hiện như trên chính là các bước của thuật toán tìm kiếm tuần tự.
Thuật toán tìm kiếm tuần tự: Duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phần tử bằng K; Ngược lại, thông báo không tìm thấy và trả về giá trị -1. Thuật toán có thể duyệt từ đầu dãy hoặc từ cuối dãy.
Thuật toán tìm kiếm tuần tự có thể viết như sau:
def LinearSeach(A,K):
for i in range(len(A)):
if A[i] == K:
return i
return -1

Thuật toán tìm kiếm tuần tự được thực hiện bằng cách duyệt lần lượt các phần tử của dãy từ đầu đến cuối để tìm phần tử có giá trị bằng giá trị cần tìm.
1. Cho, dãy A = [1, 91, 45, 23, 67, 9, 10, 47, 90, 46, 86].
Thuật, toán tìm kiếm tuần tự cần thực hiện bao nhiêu lần duyệt để tìm ra phần tử
có giá trị bằng 47 trong dãy?
Khi nào thì tìm kiếm tuần tự sẽ tìm được ngay kết quả, cần ít bước nhất?
Khi nào thì tìm kiếm tuần tự sẽ cần nhiều bước nhất? Cho ví dụ.
3. TÌM KIẾM NHỊ PHÂN
Hoạt động 3 Thuật toán tìm kiếm nhị phân
Cho trước một dãy số đã được sắp xếp theo thứ tự tăng dần. Hãy đọc, quan sát và thảo luận cách làm sau đây để hiểu được thuật toán tìm kiếm nhị phân, biết được tính ưu việt của thuật toán này so với thuật toán tìm kiếm tuần tự trên một dãy các phần tử đã sắp xếp.
a) Phân tích bài toán
Khác với bài toán tìm kiếm tuần tự, bài toán tìm kiếm nhị phân tìm kiếm với dãy số đã được sắp xếp. Khi duyệt một phần tử bất kì của dãy số, em có thể xác định được phần tử cần tìm sẽ nằm ở bên trái hay bên phải phần tử đang duyệt, từ đó quyết định tìm tiếp theo hướng nào mà không cần duyệt tất cả các phần tử của dãy số.
b) Thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân được thực hiện bằng cách liên tục thu hẹp phạm vi tìm kiếm. Nếu giá trị của phần tử ở giữa bằng K thì thông báo tìm thấy. Nếu giá trị K nhỏ hơn giá trị của phần tử ở giữa thì thu hẹp phạm vi tìm kiếm là nửa đầu của dãy tăng A (ngược lại thì phạm vi tìm kiếm là nửa sau). Cứ tiếp tục thu hẹp phạm vi như vậy cho đến khi tìm thấy hoặc đã duyệt hết thì thông báo không tìm thấy. Thuật toán tìm kiếm nhị phân được thực hiện như sau: - Thiết lập các giá trị left, right là chỉ số phần tử đầu và cuối của dãy cần tìm. Như vậy cần tìm K trong dãy A[left..right]. Ban đầu đặt left = 0, right = n - 1. - So sánh K với phần tử giữa dãy A[mid], với mid là phần nguyên của phép chia (left + right) cho 2, có ba trường hợp có thể xảy ra:
Nếu K = A[mid] thì trả về chỉ số mid và kết thúc chương trình.
Nếu K < A[mid] thì phần tử cần tìm sẽ nằm ở dãy con bên trái của phần tử A[mid], cập nhật giá trị right = mid - 1, giữ nguyên giá trị left.

Nếu K > A[mid] thì phần tử cần tìm sẽ nằm ở dãy con bên phải của phần tử A[mid], cập nhật giá trị left = mid + 1, giữ nguyên giá trị right. Lặp lại bước trên ch

1 def BinarySearch(A,K):
2 left = 0
3 right = len(A) - 1
4 while left <= right:
5 mid = (left + right)//2
6 if A[mid] == K:
7 return mid
8 elif A[mid] < K:
9 left = mid + 1
10 else:
11 right = mid - 1
12 return -1
Thuật toán tìm kiếm nhị phân được áp dụng cho các dãy được sắp xếp
theo thứ tự xác định. Sau mỗi bước lặp của thuật toán, phạm vi tìm kiếm được thu hẹp dần. Ví dụ với dãy tăng dần, nếu giá trị cần tìm nhỏ hơn giá trị của phần tử ở giữa của dãy thì phạm vi tìm kiếm thu hẹp vào nửa đầu của dãy, ngược lại, phạm vi tìm kiếm là nửa cuối của dãy. Cứ tiếp tục như vậy cho đến khi tìm thấy hoặc phạm vi tìm kiếm bằng rỗng.
Cho dãy A = [0, 4, 9, 10, 12, 14, 17, 18, 20, 31, 34, 67].
Với thuật toán tìm kiếm tuần tự, cần duyệt bao nhiêu phần tử để tìm ra phần tử có giá trị bằng 34?
Với thuật toán tìm kiếm nhị phân, cần duyệt bao nhiêu phần tử để tìm ra phần tử có giá trị bằng 34?
Thay vì lần lượt lật các thẻ từ đầu đến cuối, bạn Minh đã chơi như sau: Đầu tiên Minh lật thẻ ở giữa, sau đó tuỳ theo số ghi trên thẻ là lớn hơn hay nhỏ hơn số K mà lật tiếp thẻ ở ngay bên trái, hoặc ngay bên phải thẻ ở giữa. Trong trường hợp này, số lần nhiều nhất mà Minh phải lật để tìm ra thẻ in số K là bao nhiêu?
LUYỆN TẬP
Em hãy chỉnh sửa thuật toán tìm kiếm tuần tự để tìm ra tất cả các phần tử trong dãy bằng giá trị cần tìm, biết dãy đó có nhiều phần tử bằng giá trị cần tìm.
Viết chương trình của thuật toán tìm kiếm nhị phân với dãy sắp xếp giảm dần.
VẬN DỤNG
Cho A là danh sách tên các học sinh trong lớp, viết chương trình tìm kiếm tuần tự để tìm ra các học sinh có tên là Hoàn.
Cho A là danh sách tên các học sinh trong lớp được sắp xếp theo thứ tự bảng chữ cái, viết chương trình tìm kiếm nhị phân để tìm ra các học sinh có tên là Minh.

Thực hành bài toán tìm kiếm
SAU BÀI HỌC NÀY EM SẼ:
Biết được cách đọc dữ liệu từ tệp dữ liệu trong máy tính.
Áp dụng được thuật toán tìm kiếm trong một vài bài toán cụ thể.
Trong bài học trước, các em đã được học cách triển khai thuật toán tìm kiếm tuần tự và tìm kiếm nhị phân; vậy chúng ta có thể áp dụng các thuật toán tìm kiếm đã học vào thực tế như thế nào? Trong các bài toán thực tế, các dữ liệu thường không được viết trực tiếp vào chương trình mà thường được lưu trong các tệp chứa dữ liệu. Ở bài học này, chúng ta sẽ được học cách đọc dữ liệu từ tệp chứa dữ liệu trong máy tính.
Nhiệm vụ 1. Đọc và ghi tệp trong Python
Hướng dẫn:
Để thực hiện được các bài tập thực hành trong sách, em cần biết một số lệnh và thao tác đọc, ghi dữ liệu từ tệp văn bản.
a) Đối tượng tệp
Python cho phép đọc, ghi dữ liệu với tệp văn bản (text file) rất dễ dàng. Các tệp đều được mở để đọc và ghi dưới dạng văn bản. Đối tượng tệp được tạo ra bằng lệnh open() với các cách như sau:
– Lệnh mở tệp để đọc:
f = open(<file name>,"r",encoding = "UTF-8")
Chú ý, tham số "r" có thể bỏ qua. Tham số encoding dùng khi mở tệp văn bản có mã Unicode, ví dụ tiếng Việt. Nếu không có tham số encoding thì chỉ đọc được văn bản có mã ASCII.
– Lệnh mở tệp để ghi dữ liệu từ đầu:
f = open(<file name>,"w",encoding = "UTF-8")
Chú ý, tham số "w" là bắt buộc.
– Lệnh mở tệp để ghi tiếp dữ liệu:
f = open(<file name>,"a",encoding = "UTF-8")
Chú ý, tham số "a" là bắt buộc.
Sau khi mở tệp thì có thể tiến hành đọc (hoặc ghi) dữ liệu. Sau khi thực hiện xong các thao tác đọc, ghi thì cần đóng đối tượng tệp bằng lệnh sau:
f.close()

b) Các lệnh đọc dữ liệu từ tệp văn bản Dữ liệu trong các tệp văn bản được lưu dưới dạng các dòng, mỗi dòng là một xâu kí tự. Sau khi mở tệp bằng lệnh open(), co

c) Ghi dữ liệu ra tệp văn bản
Việc ghi dữ liệu ra tệp văn bản đơn giản nhất là sử dụng lệnh print(). Cú pháp lệnh print() như sau:
print(<v1>, <v2>, …, file = <đối tượng file>)
Chú ý, tham số file = <đối tượng file> là bắt buộc khi cần đưa dữ liệu ra tệp. Tất cả các tham số khác của lệnh print() vẫn có giá trị khi đưa dữ liệu ra tệp.
Ví dụ 2. Giả sử có hai mảng TenHS và DiemHS tương ứng với dữ liệu tên và điểm
của các học sinh trong lớp. Chương trình sau ghi những thông tin này ra tệp Data.out có định dạng tương tự như Data.inp.
1 fname = "Data.out"
2 TenHS = ['Hà','Bình','Quang']
3 DiemHS = [9.6,8.5,7.2]
4
5 f = open(fname,"w",encoding = "UTF-8")
6 for i in range(len(TenHS)):
7 print(TenHS[i],DiemHS[i],file = f)
8 f.close()
Nhiệm vụ 2. Viết chương trình tra cứu điểm thi, diem .inp
Yêu cầu: Viết chương trình tra cứu điểm thi theo tên các học sinh trong lớp. Chương trình cho phép người dùng nhập tên của học sinh cần tra cứu, sau đó kiểm tra và thông báo điểm số của học sinh cần tìm. Nhập dữ liệu: Yêu cầu người dùng nhập dữ liệu điểm học sinh từ tệp trên máy tính. Tệp bao gồm nhiều hàng, mỗi hàng, Nam 7.8 Sơn 5.6 Hương 8.9 Huyền 7.4 Hà 9.5 Hùng 8.4
gồm tên học sinh và điểm cách nhau bởi dấu cách. Ví dụ tệp Hình 20.1 có cấu trúc như Hình 20.1. Tra cứu dữ liệu: Cho phép người dùng nhập tên học sinh cần tra cứu, tìm và in ra màn hình kết quả điểm thi của học sinh đó. Nếu không tìm thấy tên học sinh trong danh sách đã nhập, thông báo "không tìm thấy dữ liệu của học sinh".
Hướng dẫn:
Phân tích bài toán: Nhiệm vụ này có thể được thực hiện thông qua thuật toán tìm kiếm. Với dữ liệu đầu vào là tên của học sinh, chương trình cần sử dụng thuật toán tìm kiếm để kiểm tra xem tên của học sinh có tồn tại trong danh sách không. Nếu tồn tại thì học sinh cần tìm nằm ở vị trí nào trong danh sách. Do tên học sinh và điểm số được nhập vào danh sách theo cùng một thứ tự, từ vị trí tên học sinh trong danh sách tên, chúng ta có thể suy ra điểm số của học sinh đó trong danh sách điểm.
Chương trình có thể như sau:
Tracuuten.py
1 input_file = open("diem.inp", encoding="UTF-8") #encoding = utf8 để đọc
được tiếng Việt

2 ten_list = []
3 diem_list = []
4 for line in input_file.readlines():# đọc lần lượt từng dòng trong tệp
5 ten,diem =line.split() # tách tên và điểm ở từng dòng
6 ten_list.append(ten)
7 diem_list.append(float(diem))
8 ten=''
9 while(ten!='end'):
10 ten = input('Nhập tên học sinh cần tra cứu, nhập từ khoá end để kết thúc:')
11 if (ten!='end'):
12 vitri=-1
13 for i in range(0,len(ten_list)):
14 if ten==ten_list[i]: # kiểm tra xem tên có tồn tại ở vị trí i
15 vitri=i
16 if vitri==-1:
17 print('Không tìm thấy học sinh trong danh sách')
18 else:
19 print('Điểm số của học sinh là:',diem_list[vitri])
Nhiệm vụ 3. Viết chương trình kiểm tra điểm thi
Yêu cầu: Viết chương trình kiểm tra điểm thi của các học diemthi_sx.inp sinh trong một lớp học. Điểm thi của học sinh được ghi trong 5.6 tệp diemthi_sx.inp, trong đó mỗi điểm thi của các học sinh 5.8 được viết trong một hàng và được sắp xếp theo thứ tự tăng 6.8 dần. Chương trình đọc dữ liệu điểm thi từ tệp, sau đó cho 7.4 phép người dùng nhập một điểm số cần kiểm tra. Nếu điểm 7.5 số có tồn tại thì in ra vị trí mà điểm số đó xuất hiện trong tệp, 7.9 nếu điểm số không tồn tại thì in ra thông báo điểm số không tồn tại. Ví dụ tệp có cấu trúc như Hình 20 .2. Hình 20.2
Hướng dẫn:
Phân tích bài toán: Tương tự như Nhiệm vụ 2, nhiệm vụ này vẫn được thực hiện bằng cách sử dụng thuật toán tìm kiếm. Trong nhiệm vụ này, dữ liệu điểm số đã được sắp xếp theo thứ tự tăng dần do đó chúng ta có thể áp dụng thuật toán tìm kiếm nhị phân để gia tăng tốc độ tìm kiếm.
Chương trình có thể như sau:
Kiemtradiem_sx.py
1 def BinarySearch(A,K):
2 left = 0
3 right = len(A) - 1
4 while left <= right:
5 mid = (left + right)//2
6 if A[mid] == K:
7 return mid
8 elif A[mid] < K:

9 left = mid + 1 10 else: 11 right = mid - 1 12, return -1 13, input_file = open("diemthi_sx.inp") # đọc dữ liệu từ file diemthi_sx.inp 14, ds_diem = [] #khởi t

Bài 21. Các thuật toán sắp xếp đơn giản SAU BÀI HỌC NÀY EM SẼ: Biết và thực hiện được một số thuật toán sắp xếp đơn giản. Bái học trước cho em thấy việc tìm kiế

Quan sát sơ đồ mô phỏng và trả lời các câu hỏi sau: So sánh số bước lặp với độ dài của dãy số ban đầu. Vị trí xuất phát của mũi tên màu đỏ có quan hệ gì với chỉ

Chỉ số của dãy, 0, 1, 2, 3, 4 Trước vòng lặp, 5, 3, 9, 7, 2 Vòng lặp 1, i = 0, 2 là phần tử nhỏ nhất, đổi chỗ 2 với 5 Sau vòng lặp, 2, 3, 9, 7, 5 Vòng lặp 2, i

Thuật toán sắp xếp chọn thực hiện một vòng lặp với chỉ số i chạy từ 0 (phần tử đầu tiên) đến n – 2 (phần tử gần cuối). Tại mỗi bước lặp, chọn phần tử nhỏ nhất nằm trong dãy A[i], A[i+1],..., A[n-1] và đổi chỗ phần tử này với A[i].
Thực hiện mô phỏng sắp xếp theo thuật toán sắp xếp chọn dãy sau: 4, 5, 2, 1, 3.
Theo thuật toán sắp xếp chọn, sau mỗi bước thứ i thì các phần tử A[0], A[1],..., A[i] đã được sắp xếp đúng. Đúng hay sai?
3. THUẬT TOÁN SẮP XẾP NỔI BỘT
Hoạt động 3 Tìm hiểu các ý tưởng thuật toán sắp xếp nổi bọt
Cùng trao đổi, thảo luận về các ý tưởng của thuật toán sắp xếp nổi bọt.
Thuật toán sắp xếp nổi bọt lấy ý tưởng từ hiện tượng "nổi bọt" của không khí dưới nước. Các bọt khí nổi dần lên mặt nước. Ý tưởng của thuật toán nổi bọt là liên tục đổi chỗ hai phần tử cạnh nhau nếu chúng chưa được sắp thứ tự đúng.
Thuật toán này sẽ thực hiện nhiều vòng lặp. Quan sát vòng lặp sau để hiểu cách thực hiện: chỉ số j chạy từ 0 đến n – 2 và kiểm tra hai phần tử liền nhau A[j], A[j+1], nếu chúng chưa sắp thứ tự đúng thì đổi chỗ.
1 for j in range(n-1):
2 if A[j] > A[j+1]:
3 Đổi chỗ A[j], A[j+1]
Quan sát vòng lặp đầu tiên của thuật toán nổi bọt để thấy sau vòng lặp này, phần tử lớn nhất được chuyển về cuối dãy A.
Chỉ số của dãy:, 0, 1, 2, 3, 4
Trước vòng lặp, 5, 3, 9, 7, 2
Bước lặp 1, j = 0, 5 ↔ 3, 9, 7, 2, So sánh phần tử thứ nhất và phần tử thứ hai
Bước lặp 2, j = 1, 3, 5 ↛ 9, 7, 2, So sánh phần tử thứ hai và phần tử thứ ba
Bước lặp 3, j = 2, 3, 5, 9 ↔ 7, 2, So sánh phần tử thứ ba và phần tử thứ tư
Bước lặp 4, j = 3, 3, 5, 7, 9 ↔ 2, So sánh phần tử thứ tư và phần tử thứ năm
Kết thúc vòng 1, 3, 5, 7, 2, 9
Trong sơ đồ trên, mũi tên màu đỏ cho biết có đổi chỗ hai phần tử, mũi tên màu tím cho biết không thay đổi vị trí.
Hình 21.3. Mô phỏng thuật toán sắp xếp nổi bọt

Sau vòng lặp thứ nhất, phần tử lớn nhất được chuyển về cuối dãy. Sau vòng lặp thứ hai, phần tử lớn thứ hai được chuyển về đúng vị trí ở cuối dãy. Cứ như vậy, sau n - 1 vòng lặp thì dãy được sắp xếp. Có thể mô tả thuật toán nổi bọt như sau:
1 for 2 3 4, i in range(n-1): for j in range(n-1): if A[j] > A[j+1]: Đổi chỗ A[j],A[j+1]
Quan i phần dòng 2 BubbleSort(A) 1 def 2 3 4 5 6, sát dòng 2, ta thấy không cần phải có đủ n - 1 bước lặp vì sau i vòng lặp thì tử lớn nhất đã chuyển về đúng vị trí ở cuối dãy, nên với chỉ số i thì vòng lặp ở chỉ cần n - 1 - i bước lặp. Thuật toán sắp xếp nổi bọt được mô tả bằng hàm như sau: BubbleSort(A): n = len(A) for i in range(n-1): for j in range(n-1-i): if A[j] > A[j+1]: A[j],A[j+1]=A[j+1],A[j]
Thuật toán sắp xếp nổi bọt thực hiện nhiều vòng lặp, kiểm tra hai phần
tử cạnh nhau, nếu chúng chưa sắp xếp đúng thì đổi chỗ. Có nhiều cách thể hiện thuật toán này, nhưng cách thường dùng là sử dụng hai vòng lặp lồng nhau, vòng lặp trong thực hiện thao tác đổi chỗ hai phần tử cạnh nhau cho đến khi dãy được sắp xếp xong.
Mô tả các bước thuật toán sắp xếp nổi bọt của dãy A = [4, 3, 1, 2].
Khi nào thì các mũi tên ở tất cả các bước trong sơ đồ mô phỏng thuật toán sắp xếp nổi bọt đều có màu đỏ?
LUYỆN TẬP
Cho dãy A = [5, 8, 1, 0, 10, 4, 3]. Viết các chương trình sắp xếp dãy A theo thứ tự tăng dần theo các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt.
Viết chương trình nhập một dãy số từ bàn phím, các số cách nhau bởi dấu cách, thực hiện sắp xếp dãy đã nhập theo một trong các thuật toán sắp xếp rồi in kết quả ra màn hình.
VẬN DỤNG
Viết lại các thuật toán sắp xếp trong bài theo thứ tự giảm dần.
Nêu ý nghĩa thực tế của các thuật toán sắp xếp đã học, chẳng hạn sắp xếp các học sinh trong lớp theo chiều cao tăng dần.

Bài 23. Kiểm thử và đánh giá chương trình
SAU BÀI HỌC NÀY EM SẼ:
Biết được vai trò của kiểm thử làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của chương trình.
Biết được các tiêu chí đánh giá hiệu quả và tính đúng của chương trình.
Trong các bài trước em đã học cách thiết kế thuật toán cho một số bài toán như bài toán tìm kiếm, bài toán sắp xếp và thiết lập chương trình thực hiện thuật toán đó. Một bài toán có thể có nhiều thuật toán khác nhau và do đó có thể có nhiều chương trình khác nhau cùng giải quyết một bài toán. Hãy thảo luận và trả lời các câu hỏi sau:
– Làm thế nào để biết trong các thuật toán giải cùng một bài toán thì thuật toán nào là tốt nhất?
– Có những tiêu chí nào để đánh giá tính "tối ưu" của một thuật toán?
1. VAI TRÒ CỦA KIỂM THỬ CHƯƠNG TRÌNH
Hoạt động 1 Tìm hiểu ý nghĩa của kiểm thử chương trình
Ở lớp 10, em đã học một số phương pháp kiểm thử chương trình. Em hãy thảo luận với các bạn về các phương pháp kiểm thử sau, nêu ý nghĩa của chúng trong việc đánh giá độ tin cậy và chứng minh tính đúng của chương trình:
Tạo các bộ dữ liệu kiểm thử (test) để kiểm tra dữ liệu đầu ra có chính xác hay không.
Thiết lập điểm dừng hoặc cho chương trình chạy theo từng lệnh để kiểm tra và tìm ra lỗi (bug) của chương trình.
Thực hiện in dữ liệu trung gian trong quá trình kiểm thử để tìm ra lỗi của chương trình (nếu có).
– Phương pháp 1 sử dụng các bộ dữ liệu kiểm thử để kiểm tra tính đúng của chương trình. Nếu phát hiện lỗi không chính xác của dữ liệu đầu ra thì kết luận ngay thuật toán và chương trình không đúng. Nếu với các bộ dữ liệu kiểm thử, dữ liệu đầu ra đều đúng thì điều đó chưa chứng minh được thuật toán hay chương trình đúng. Kết quả đó chỉ làm tăng khả năng đúng của chương trình.
– Mục đích của các phương pháp 2 và 3 là tìm ra lỗi và sửa lỗi của chương trình. Như vậy, với việc tìm ra và sửa lỗi chứng tỏ chương trình trở nên tin cậy hơn, tốt hơn. Tuy nhiên, điều đó không chứng minh được tính đúng của thuật toán và chương trình.
Một thuật toán nếu được thiết kế đúng thì với mọi bộ dữ liệu đầu vào sẽ nhận được bộ dữ liệu đầu ra đúng tương ứng. Các phương pháp kiểm thử không có tính năng chứng minh được tính đúng của một thuật toán.

Kiểm thử sẽ giúp tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán và chương trình.
1. Giả dữ, sử em thiết lập chương trình giải bài toán nào đó. Em đã kiểm thử với 10 bộ liệu và tất cả các kết quả đều đúng. Khi đó có thể kết luận chương trình đó đúng
hay chưa?
Giả sử một chương trình kiểm thử với 10 bộ dữ liệu cho kết quả 9 lần đúng, 1 lần sai. Chương trình đó là sai hay đúng?
2. KIỂM TRA TÍNH ĐÚNG CỦA CHƯƠNG TRÌNH
Hoạt động 2 Tìm hiểu cách kiểm tra tính đúng của chương trình
Quan sát chương trình mô tả thuật toán sắp xếp chèn. Hãy thảo luận và đưa lập luận để kiểm tra tính đúng của thuật toán sắp xếp chèn., ra các
Chương trình thực hiện thuật toán sắp xếp chèn để sắp xếp dãy A cho thứ tự tăng dần như sau:, trước theo
1 def InsertionSort(A,n):
2 for i in range(1,n):
3 value = A[i]
4 k = i-1
5 # di chuyển các phần tử A[k] > value qua phải
6 while k >= 0 and A[k] > value:
7 A[k+1] = A[k]
8 k = k - 1
9 A[k+1] = value
Trao đổi 1. Cài đặt chương trình sắp xếp chèn, nhập một số bộ dữ liệu đầu vào
bất kì cho dãy A và kiểm tra kết quả đầu ra. Ta sẽ nhận thấy các kết quả đầu ra của chương trình đều đúng là dãy A được sắp xếp theo thứ tự tăng dần. Từ đó kết luận thuật toán sắp xếp chèn của chương trình trên là đúng.
Trao đổi 2. Giả sử dãy A ban đầu là A[0], A[1], ..., A[n-1] với n là độ dài dãy A.
Dòng lệnh 2 là một vòng lặp gồm n - 1 bước, mỗi bước gán i chạy từ 1 đến n - 1. Với mỗi i (từ 1 đến n - 1), các dòng lệnh từ 3 đến 9 thực hiện việc "chèn" phần tử A[i] vào một vị trí trong dãy con phía trước A[0], A[1], ..., A[i - 1]. Giá trị A[i] sẽ được chèn vào vị trí giữa hai phần tử A[k] và A[k+1] nếu A[k] ≤ A[i] < A[k+1]. Do đó các dòng lệnh từ 3 đến 9 sẽ chèn phần tử A[i] vào đúng vị trí ở dãy đầu ra được sắp xếp tăng dần. Từ đó suy ra đến bước cuối cùng dãy A đã được sắp xếp đúng theo thứ tự.
Trao đổi 3. Trong khoa học máy tính, việc kiểm tra tính đúng của thuật toán đều
phải chứng minh bằng lôgic toán học. Một phương pháp chứng minh thường dùng là bất biến vòng lặp. Ví dụ với thuật toán sắp xếp chèn ở trên cần chứng minh mệnh đề sau bằng bất biến vòng lặp: Mệnh đề: Sau mỗi bước lặp i của vòng lặp, dãy con A[0], A[1], ..., A[i - 1], A[i] đã được sắp xếp đúng theo thứ tự tăng dần.

Nếu mệnh đề trên được chứng minh bằng toán học thì áp dụng với i = n - 1 ta sẽ kết luận thuật toán sắp xếp chèn là đúng.
Qua các trao đổi trên ta có nhận xét: - Trong trao đổi 1, việc sử dụng các bộ dữ liệu kiểm thử chưa chứng minh được tính đúng của thuật toán và chương trình. Tuy nhiên, nếu thử được càng nhiều bộ dữ liệu kiểm thử thì độ tin cậy của chương trình càng cao. - Trao đổi 2 là một suy luận lôgic vì nó bắt nguồn từ ý tưởng chính của thuật toán sắp xếp chèn. Đây là một cách lập luận đơn giản thường được sử dụng để chứng minh tính đúng của thuật toán. - Trao đổi 3 cho biết việc chứng minh tính đúng của chương trình thường bằng lập luận toán học, sử dụng phương pháp quy nạp toán học. Đây là cách tốt nhất để chứng minh tính đúng của một thuật toán.
Tính đúng của thuật toán cần được chứng minh bằng lập luận toán học. Sử dụng các bộ dữ liệu kiểm thử có thể làm tăng độ tin cậy của chương trình nhưng chưa chứng minh được tính đúng của thuật toán.
1 n = 2 S = 3 for 4 5, int(input("Nhập số tự nhiên n: ")) 0 i in range(n+1): S = S + i print(S)
Chương 2. Chương, trình trên có đúng không? trình sau giải bài toán đếm số các ước số thực sự của số tự nhiên n.
1 def 2 3 4 5 6 7 8, dem(n): count = 0 k = 2 while k < n: if n%k == 0: count = count + 1 k = k + 1 return count
Chương 3. ĐÁNH, trình trên là đúng hay sai? GIÁ HIỆU QUẢ CHƯƠNG TRÌNH
Hoạt, động 3 Những tiêu chí đánh giá tính hiệu quả của chương trình
Thảo luận một bài 1. Tiêu quan 2. Tiêu chương 3. Các cách, về các tiêu chí đánh giá tính hiệu quả của thuật toán hay chương trình giải toán. chí quan trọng nhất là thời gian chạy chương trình phải nhanh, không cần tâm đến không gian bộ nhớ sử dụng của chương trình. chí tiết kiệm bộ nhớ là quan trọng nhất, sau đó mới đến thời gian chạy trình. tiêu chí 1 và 2 không quan trọng mà quan trọng là chương trình được viết một đơn giản, rõ ràng, dễ hiểu và áp dụng.

Hiệu quả hay tính tối ưu của chương trình thường được xem xét trên cơ sở đánh giá
độ phức tạp tính toán (computational complexity) là lượng tài nguyên (amounts of resources) cần thiết để thực hiện chương trình. Hai loại độ phức tạp tính toán phổ biến nhất đó là: - Độ phức tạp thời gian (time complexity) được xác định là thời gian thực hiện chương trình/thuật toán. Thời gian này phụ thuộc vào khối lượng của dữ liệu cần phải lưu trữ trong quá trình thực hiện chương trình/thuật toán, đặc biệt liên quan tới các bước giải quyết một vấn đề cụ thể đưa ra trong chương trình/thuật toán. - Độ phức tạp không gian (space complexity) được xác định là tài nguyên của máy tính trong đó có phần bộ nhớ được sử dụng để thực hiện chương trình. Một chương trình/thuật toán là hiệu quả (efficient) nếu độ phức tạp của thuật toán này là thấp, nghĩa là tốn ít thời gian và tốn ít bộ nhớ cần thiết để thực hiện chương trình/thuật toán. Ngoài ra để đánh giá hiệu quả chương trình đôi khi người ta còn quan tâm tới các tiêu chí như tính dễ hiểu, rõ ràng, ngắn gọn, dễ bảo trì, dễ cài đặt,… của chương trình. Độ phức tạp thời gian thường bị ảnh hưởng bởi số lần thực hiện các phép toán/ câu lệnh có trong chương trình/thuật toán. Với các bài toán kĩ thuật, thiết kế, nghiên cứu khoa học đòi hỏi khối lượng tính toán rất lớn thì việc thiết kế các chương trình/ thuật toán có độ phức tạp thời gian thấp luôn là mối quan tâm hàng đầu. Còn đối với những bài toán chạy liên tục như các dịch vụ trực tuyến thì độ tin cậy của phần mềm, tính dễ cài đặt, dễ duy trì, dễ sử dụng lại có vai trò quan trọng. Trong phạm vi kiến thức phổ thông, ta sẽ chỉ quan tâm tới độ phức tạp thời gian của chương trình/thuật toán. Trong các bài học sau em sẽ làm quen với việc xác định độ phức tạp thời gian dựa trên cơ sở ước lượng thời gian thực hiện các bước (các câu lệnh) trong chương trình/thuật toán. Chương trình sau cho em biết một cách đơn giản đo thời gian chạy của chương trình. Hàm chính mô tả thuật toán sắp xếp chèn là InsertionSort(A) với A là dãy số đầu vào. Hàm perf_counter() đo nhịp xung CPU tại thời điểm thực hiện, đơn vị tính thời gian là giây. Chương trình sau tính được thời gian chạy của hàm InsertionSort(A) hay chính là thời gian chạy của thuật toán sắp xếp chèn. Hàm tính thời gian tại thời điểm trước và sau khi chạy hàm chính tại các dòng 10, 12 . Lệnh tại dòng 13 sẽ in ra thời gian chạy của hàm chính InsertionSort(A).
1 from time import perf_counter
2 def InsertionSort(A):
3 n = len(A)
4 for i in range(1,n):
5 value = A[i]
6 j = i-1
7 while j >= 0 and A[j] > value:
8 A[j+1] = A[j]
9 j = j -1
10 A[j+1] = value
11 A = [3,0,1,10,7,9,5]

12 t1 = perf_counter()
13 InsertionSort(A)
14 t2 = perf_counter()
15 print(t2-t1)
Tính hiệu quả của chương trình/thuật toán được xem xét trên cơ sở đánh giá độ phức tạp tính toán. Độ phức tạp tính toán quan trọng nhất là độ phức tạp thời gian có liên quan trực tiếp tới các câu lệnh được thực hiện trong chương trình/thuật toán.
Hai tiêu chí đánh giá độ phức tạp tính toán quan trọng nhất là gì?
LUYỆN TẬP
Hãy xây dựng các bộ dữ liệu kiểm thử để tìm lỗi cho chương trình tính n! với n là một số nguyên dương nhập từ bàn phím.
1 n = int(input("Nhập số n: "))
2 if n > 0:
3 giaithua=1
4 for i in range(1,n+1):
5 giaithua = giaithua*i
6 print(n,"giai thừa bằng:",giaithua)
Xét hàm mô tả thuật toán tính tổng các số chẵn của một dãy số cho trước.
1 def tongchan(A):
2 S = 0
3 for i in range(len(A)):
4 if A[i] % 2 == 0:
5 S = S + A[i]
6 return S
Tìm hai bộ dữ liệu đầu vào có cùng kích thước của thuật toán trên nhưng có thời gian chạy khác nhau.
VẬN DỤNG
Cho dãy các số A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11].
a) Viết chương trình mô tả thuật toán tìm kiếm phần tử C = 9 của dãy trên. Tính thời gian chính xác thực hiện công việc tìm kiếm này.
b) Giả sử dãy A ở trên đã được sắp xếp theo thứ tự tăng dần: A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]. Viết chương trình tìm kiếm phần tử C = 9 theo thuật toán tìm kiếm nhị phân. Tính thời gian thực hiện thuật toán. So sánh với kết quả tìm kiếm ở câu a.
Viết ba chương trình mô phỏng các thuật toán sắp xếp chèn, sắp xếp chọn và sắp xếp nổi bọt mà em đã biết. Cho biết thời gian thực hiện các chương trình trên với bộ dữ liệu đầu vào là dãy A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11].

Bài 24. Đánh giá độ phức tạp thời gian thuật toán
SAU BÀI HỌC NÀY EM SẼ:
Biết cách phân tích độ phức tạp thời gian thuật toán.
Nhận biết được phép toán tích cực trong chương trình.
Biết và thực hiện được tính toán độ phức tạp thời gian của một số thuật toán đã biết.
Quan sát Hình 24.1 chúng ta dễ thấy phép nhân hai số có n chữ số sẽ cần $n^2$ phép nhân và 2n phép cộng, vậy tổng số các phép tính đơn của phép nhân này là $n^2 + 2n$, chúng ta nói độ phức tạp thời gian của phép nhân này có bậc $n^2$.
Năm 1960, trong một tiết dạy về công nghệ thông tin, nhà toán học Nga, Viện sĩ Kolmogorov đã hỏi các sinh viên của mình là có ai tìm được cách tính phép nhân trên với thời gian tốt hơn bậc $n^2$ được không? Khi đó đây là một bài toán chưa có lời giải. Đúng một tuần sau, một sinh viên tên là Karatsuba đã đưa cho Viện sĩ Kolmogorov một lời giải tốt hơn về phép tính nhân trên chỉ với độ phức tạp thời gian bậc $n^{1,58496}$.
Hình 24.1
Quan sát và ước lượng thời gian thực hiện các đoạn chương trình 1 và 2 trong Hình 24.2. Chương trình nào chạy nhanh hơn? Vì sao?
Chương trình 1, Chương trình 2
1 n = 100, 1 n = 100
2 C = 0, 2 C = 0
3 for k in range(n):, 3 for i in range(n):
4 C = C + 1, 4 for j in range(n):
5 print(C), 5 C = C + 1
6 print(C)
Hình 24.2
1. ĐÁNH GIÁ THỜI GIAN THỰC HIỆN CHƯƠNG TRÌNH
Có thể không cần cài đặt và chạy chương trình mà vẫn ước lượng được thời gian chạy dựa trên việc tính tổng thời gian các phép tính đơn và các lệnh đơn của chương trình. Cách tính này có thể không chính xác hoàn toàn như thời gian thực nhưng có thể dùng để so sánh và ước lượng thời gian chạy chương trình khá chính xác. Khi tính thời gian chạy chương trình, có thể coi tất cả các lệnh đơn (ví dụ lệnh gán) và các phép tính đơn (ví dụ phép tính số học, phép so sánh) có thời gian chạy như nhau, được gọi chung là một đơn vị thời gian. Cách tính này sẽ làm đơn giản hoá cách phân tích thời gian tính toán nhưng vẫn bảo đảm độ chính xác của tính toán.

Hoạt động 1 Tìm hiểu cách đánh giá thời gian thực hiện chương trình
Quan sát và thực hiện đánh giá thời gian chạy của các chương trình 1 và 2 trong Hình 24.2. Từ đó biết và hiểu được cách đánh giá thời gian thực hiện chương trình.
Chương trình 1. Gọi T1 là thời gian chạy của chương trình này.
Mỗi lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian để thực hiện. - Vòng lặp tại dòng 3 có n bước lặp, mỗi bước của vòng lặp sẽ thực hiện lệnh tại dòng 4, lệnh này cần 1 đơn vị thời gian. Vậy suy ra tổng thời gian của vòng lặp 3 là n thời gian.
Lệnh cuối tại dòng 5 cần 1 đơn vị thời gian. Vậy để thực hiện toàn bộ chương trình 1 cần: T1 = T1(n) = 2 + n + 1 = n + 3 đơn vị thời gian.
Chương trình 2. Gọi T2 là thời gian chạy của chương trình này.
Mỗi lệnh tại dòng 1 và 2 cần 1 đơn vị thời gian. - Các lệnh tại dòng 3, 4 là hai vòng lặp lồng nhau. Mỗi vòng lặp có n bước như vậy thực chất có n2 bước lặp của hai lệnh này. Mỗi bước lặp sẽ thực hiện các lệnh tại dòng 5, lệnh này cần 1 đơn vị thời gian. Vậy suy ra tổng thời gian của vòng lặp 3, 4 là n2 đơn vị thời gian.
Lệnh cuối tại dòng 6 cần 1 đơn vị thời gian. Vậy tổng hợp toàn bộ chương trình 2 ta có: T2 =T2(n) = 2 + n2 + 1 = n2 + 3 đơn vị thời gian.
Cách đánh giá thời gian chạy chương trình được dựa trên một bộ khung các nguyên tắc dùng làm căn cứ để tính toán. Các nguyên tắc khung như sau:
Các phép toán đơn giản như phép tính số học +, -, *, /, phép lấy thương nguyên và số dư, các phép so sánh sẽ tính là 1 đơn vị thời gian.
Các phép toán lôgic cơ bản như AND, OR, NOT sẽ tính là 1 đơn vị thời gian.
Các lệnh đơn như lệnh gán, lệnh in, đọc dữ liệu,... tính là 1 đơn vị thời gian.
Vòng lặp for hoặc while sẽ được tính thời gian bằng tổng đơn vị thời gian thực hiện của mỗi bước lặp.
Lệnh if với nhiều trường hợp rẽ nhánh sẽ được tính thời gian bằng đơn vị thời gian lớn nhất của các lệnh nhánh. Áp dụng các nguyên tắc tính khung thời gian trên chúng ta có thể tính được gần chính xác thời gian thực hiện chương trình mà không cần cài đặt và chạy chương trình trên máy tính.
Lưu ý: Trong một chương trình, phép toán được thực hiện nhiều nhất và đóng vai trò chính khi thực hiện tính thời gian, được gọi là phép toán tích cực. Ví dụ trong chương trình 1 thì phép toán tích cực là phép cộng C = C + 1 tại dòng 4. Với chương trình 2 thì phép cộng C = C + 1 tại dòng 6 chính là phép toán tích cực.

Các lệnh và đoạn chương trình sau cần chạy trong bao nhiêu đơn vị thời gian?
(a) (b)
1 n = 1000000 1 n = 1000000
2 for k in range(n): 2 b = 3
3 if k%3 == 0: 3 for k in range(0,n,b):
4 print(k) 4 print(k)
Khẳng định "Trong mọi chương trình chỉ có đúng một phép toán tích cực" là đúng hay sai?
2. PHÂN TÍCH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
Hoạt động 2 Tìm hiểu khái niệm độ phức tạp thời gian thuật toán
Cùng trao đổi và tìm hiểu cách phân loại thuật toán dựa trên độ phức tạp thời gian thuật toán.
Trong phạm vi kiến thức phổ thông có thể hiểu độ phức tạp thời gian thuật toán là
khối lượng thời gian cần thiết để chạy chương trình thể hiện thuật toán. Một trong các cách phân loại thuật toán đó là dựa trên việc ước lượng độ phức tạp thời gian thuật toán. Độ phức tạp thời gian, trong trường hợp tổng quát, có thể coi là một hàm số T(n), với n là một số tự nhiên được xác định tuỳ thuộc từng bài toán cụ thể liên quan tới dữ liệu đầu vào. Giá trị của T(n) thường được xác định trên cơ sở số lượng các phép toán/câu lệnh cần thực hiện trong chương trình/thuật toán. Khi n càng lớn thì thời gian T(n) sẽ tăng lên nhưng tốc độ tăng khác nhau. Để phân loại được các hàm thời gian này, các nhà khoa học đã đưa vào định nghĩa O-lớn. Kí hiệu O-lớn (big-O) dùng để so sánh và phân tích bậc của hàm thời gian T(n) khi n tăng lên vô cùng. Ví dụ chương trình 1 ở Hình 24.2 có độ phức tạp thời gian bậc n và viết là T1(n) = O(n), ý nghĩa là khi n tiến tới vô cùng, T1(n) sẽ tăng nhưng không quá bậc của n. Tương tự, chương trình 2 có độ phức tạp thời gian bậc n2, và viết là T2(n) = O(n2), ý nghĩa là khi n tăng lên thì T2(n) sẽ tăng không vượt quá bậc của n2.
Định nghĩa kí hiệu O-lớn: Cho f(n) và g(n) là hai hàm có đối số tự nhiên. Ta viết f(n) = O(g(n)) và nói f(n) có bậc O-lớn của g(n) nếu tồn tại hằng số c > 0 và số tự nhiên n0 ≥ 1 sao cho với mọi n ≥ n0 ta có f(n) ≤ c.g(n). Nếu f(n) là O-lớn của g(n) thì có thể viết: f(n) = O(g(n)).
Xét một số ví dụ. - Chương trình 1 ở Hình 24.2 có hàm thời gian T1(n) = n + 3. Chọn c = 2, n0 = 3. Khi đó với n ≥ n0 ta có: T1(n) = n + 3 ≤ n + n = c.n. Do đó T1(n) = O(n). Chúng ta nói chương trình 1 có độ phức tạp thời gian O(n) - tuyến tính.
Chương trình 2 ở Hình 24.2 có hàm thời gian T2(n) = n2 + 3. Chọn c = 2, n0 = 2. Khi đó với n ≥ n0, ta có:
T2(n) = n2 + 3 < n2 + n02 ≤ n2 + n2 = 2n2 = c.n2.
Vậy suy ra T2(n) = O(n2). Ta nói chương trình 2 ở trên có độ phức tạp thời gian O(n2) - bình phương.
Kí hiệu O-lớn dùng để đánh giá và phân loại độ phức tạp thời gian của thuật toán khi kích thước đầu vào của bài toán tăng lên vô cùng. Các thuật toán sẽ được đánh giá qua độ phức tạp của một số hàm chuẩn như: O(1) - hằng số, O(logn) - logarit, O(n) - tuyến tính, O(nlogn) - tuyến tính logarit, O(n2) - bình phương, O(nk) - đa thức, O(an) - luỹ thừa, O(n!) - giai thừa.

Tính độ phức tạp của các hàm thời gian sau:
a) T(n) = 2n(n – 2) + 4.
b) T(n) = n³ + 5n – 3.
3. MỘT SỐ QUY TẮC THỰC HÀNH TÍNH ĐỘ PHỨC TẠP THỜI GIAN THUẬT TOÁN
Hoạt động 3 Tìm hiểu một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán
Đọc, quan sát, thảo luận để biết một số quy tắc đơn giản tính độ phức tạp thời gian thuật toán.
Một số quy tắc tính đơn giản để tính độ phức tạp thời gian thuật toán.
QT1. Quy tắc cộng: O(f(n) + g(n)) = O(max(f(n), g(n))). Quy tắc này được áp dụng khi tính độ phức tạp thời gian cho hai chương trình được thực hiện nối tiếp nhau.
QT2. Quy tắc nhân: Phép nhân với hằng số: O(C·f(n)) = O(f(n)), với C là hằng số bất kì.
Phép nhân với hàm số: O(f(n)·g(n)) = O(f(n)·O(g(n))). Quy tắc này được áp dụng tính độ phức tạp thời gian cho chương trình có hai vòng lặp lồng nhau.
Ví dụ:
T(n) = 10n² = O(n²) (Quy tắc nhân với hằng số).
T(n) = 3n² + nlogn = O(max(3n², nlogn)) (Quy tắc cộng) = O(3n²) = O(n²) (Quy tắc nhân với hằng số).
Áp dụng các quy tắc trên để tính độ phức tạp của các hàm thời gian sau:
a) T(n) = n³ + nlogn + 2n + 1.
b) T(n) = 3n⁴ + 2n²logn + 10.
LUYỆN TẬP
Xác định độ phức tạp thời gian tính toán cho chương trình sau:
1 n = 1000
2 S = 0
3 for i in range(n):
4 S = S + i(i+1)
5 print(S)
Xác định độ phức tạp thời gian tính toán cho chương trình sau:
1 n = 1000
2 Sum=0
3 i = 1
4 while i < n:
5 i = i*2
6 Sum = Sum + i
7 print(Sum)
VẬN DỤNG
Xác định độ phức tạp thời gian của thuật toán sắp xếp chọn đã được học trong Bài 21.
Em hãy thiết lập chương trình và tính thời gian chạy thực tế trên máy tính của các chương trình 1 và 2 ở Hình 24.2 với các giá trị n khác nhau, từ đó thấy được ý nghĩa sự khác biệt độ phức tạp thời gian của hai chương trình này.

Thực hành xác định độ phức tạp thời gian thuật toán
SAU BÀI HỌC NÀY EM SẼ:
Thực hành xác định độ phức tạp (O-lớn) của hàm thời gian.
Biết cách phân tích, đánh giá độ phức tạp thuật toán là kĩ năng quan trọng của người thiết kế thuật toán và chương trình. Các quy tắc đơn giản tính độ phức tạp thời gian mang lại cho em điều gì khi đánh giá thuật toán?
Nhiệm vụ 1
Xác định độ phức tạp thời gian tính toán của thuật toán tìm kiếm tuần tự được thể hiện bằng chương trình sau:
def LinearSearch(A, K):
for i in range(len(A)):
if A[i] == K:
return i
return -1
Hướng dẫn:
Bước 1. Phân tích thời gian tính toán của thuật toán.
Gọi n là kích thước của mảng đầu vào, T(n) là thời gian thực hiện thuật toán.
– Đối với mã lệnh trên, chương trình sẽ thực hiện duyệt mảng và với mỗi bước lặp sẽ kiểm tra phần tử thứ i có bằng với phần tử cần tìm kiếm không (dòng 3). Nếu bằng thì chương trình sẽ trả về chỉ số của phần tử tìm thấy và kết thúc (dòng 4). Như vậy, chương trình có thể kết thúc khi chưa duyệt hết mảng (trường hợp đã tìm thấy phần tử) và tối đa là duyệt hết mảng. Như vậy, trong trường hợp tồi nhất vòng lặp ở dòng 2 sẽ thực hiện n bước lặp, mỗi bước lặp sẽ thực hiện lệnh so sánh ở dòng 3 tốn 1 đơn vị thời gian.
– Lệnh trả về sẽ được thực hiện duy nhất một lần ở dòng 4 (trường hợp tìm thấy phần tử trong mảng) hoặc dòng 5 (trường hợp không tìm thấy phần tử trong mảng) mất 1 đơn vị thời gian.
Do đó, tổng số phép tính cơ bản của chương trình trong trường hợp tồi nhất là
$$T(n) = n+1.$$
Bước 2. Xác định độ phức tạp O-lớn của thuật toán
$$T(n) = n + 1 = O(n+1) = O(\max(n, 1)) = O(n).$$
Vậy thuật toán tìm kiếm tuần tự có độ phức tạp tuyến tính.

Nhiệm vụ 2 Xác định độ phức tạp của thuật toán sắp xếp chọn được thể hiện bằng chương trình sau: 1 def SelectionSort(A): 2 n = len(A) 3 for i in range(n-1): 4 i

T(n) = n2 + 3n - 3 Xác định độ phức tạp O-lớn của thuật toán: T(n) = O(max(n2, 3n, - 3)) = O(n2) Vậy thuật toán sắp xếp chọn có độ phức tạp thời gian bình phươn

Bài 26. Phương pháp làm mịn dần trong thiết kế chương trình
SAU BÀI HỌC NÀY EM SẼ:
Biết và giải thích được phương pháp làm mịn dẫn trong lập trình.
Vận dụng được phương pháp làm mịn dẫn để thiết kế chương trình.
Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Tất cả các thiết kế chương trình đó có điểm nào chung?
Theo em, để thiết kế một thuật toán đúng giải một bài toán cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.
1. PHƯƠNG PHÁP THIẾT KẾ LÀM MỊN DẪN
Hoạt động 1 Tìm hiểu các bước thiết kế làm mịn dần
Cùng trao đổi, thảo luận các bước thiết kế chương trình theo thuật toán sắp xếp chèn, từ đó đưa ra phương pháp chính khi thiết kế chương trình. Sau mỗi bước thiết kế cần trao đổi và trả lời các câu hỏi sau:
Bước này đã thực hiện được công việc gì?
Kết quả vừa thực hiện với kết quả của bước trước đó khác nhau như thế nào?
Bài toán gốc. Cho trước dãy số A: $A[0], A[1], ..., A[n-1]$. Cần tiến hành sắp xếp dãy trên theo thứ tự tăng dần. Kết quả phải nhận được:
$A[0] \le A[1] \le ... \le A[n-1]$
Ví dụ với bộ dữ liệu đầu vào là dãy [2,1,7,10,4] thì kết quả thu được dãy [1,2,4,7,10].
Quá trình phân tích, thiết kế được mô tả theo các bước sau.
a) Tìm hiểu bài toán
Bài toán gốc là cho trước dãy A, cần sắp xếp lại dãy này theo thứ tự tăng dần.
b) Thiết kế chương trình giải bài toán
Việc thiết kế chương trình giải bài toán được chia thành nhiều bước, trong đó các hành động ở bước sau là sự cụ thể hoá hơn ý tưởng, thao tác được nêu trong bước trước.
Bước 1. Thiết lập ý tưởng thiết kế ban đầu.
Ý tưởng ban đầu của thuật toán đơn giản như sau: Cần duyệt một lượt từ phần tử thứ hai đến phần tử cuối của dãy sao cho khi kết thúc thì dãy cũng được sắp xếp xong. Như vậy phần chính của thuật toán là một vòng lặp với biến i chạy từ chỉ số 1 đến n – 1. Với mỗi giá trị i, cần thực hiện một số thao tác để bổ sung $A[i]$ vào dãy các phần tử đã được sắp xếp $A[0], A[1],..., A[i-1]$ sao cho dãy mới thu được từ $A[0]$ đến $A[i]$ được sắp xếp đúng.
Như vậy, thuật toán ban đầu có thể được mô tả như sau:

1 for i in range(1,n): 2 <Đặt A[i] vào đúng vị trí của dãy A[0],A[1],...,A[i-1]>
Tại dòng 2 của sơ đồ trên, bài toán được đặt ra là: "Chèn phần tử A[i] vào đúng vị trí của dãy A[0], A[1], ..., A[i-1]". Bước 2. Làm chi tiết hơn, thực hiện việc "Chèn A[i] vào đúng vị trí." Vì các phần tử bên trái của A[i] là A[0], A[1], ..., A[i-1] đã được sắp xếp đúng nên thao tác "chèn" phần tử A[i] sẽ được thực hiện như sau: <Lấy phần tử A[i] ra và lần lượt chuyển các phần tử bên trái A[i] nhưng có giá trị lớn hơn A[i] sang phải. Sau đó đặt A[i] vào vị trí trống> Theo mô tả trên, việc "Chèn A[i] vào đúng vị trí" có thể được thực hiện như sau: Chèn A[i] vào đúng vị trí
1 Nhấc phần tử A[i] lên. 2 Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải. 3 Chèn A[i] vào vị trí trống.
Các bước tiếp theo sẽ làm mịn hơn, chi tiết hơn các thao tác trên.
Bước 3. Nhấc A[i] lên.
Thao tác này sẽ được thực hiện đơn giản bằng việc tạo ra một biến mới value để lưu trữ giá trị A[i].
value = A[i]
Bước 4. Chuyển các phần tử bên trái A[i] và lớn hơn A[i] sang phải.
Thao tác này có thể được thực hiện như sau: Thiết lập biến j = i - 1 là chỉ số của phần tử ngay bên trái A[i]. Sau đó liên tục so sánh A[j] với value. Nếu A[j] > value thì chuyển A[j] sang phải một vị trí bằng lệnh A[j+1] = A[j] và giảm j = j - 1. Quá trình sẽ kết thúc khi đi hết bên trái của dãy hoặc A[j] <= value. Tất cả các công việc này được thể hiện bằng đoạn chương trình sau:
1 j = i-1
2 while j >= 0 and A[j] > value:
3 A[j+1] = A[j]
4 j = j - 1
Bước 5. Chèn A[i] vào đúng vị trí trống.
Từ bước 4 chúng ta đã biết quá trình chuyển sang phải của các phần tử A[j] sẽ kết thúc khi A[j] <= A[i], do đó vị trí j+1 chính là vị trí trống cần chèn. Việc chèn phần tử A[i] (giá trị được lưu trong value) vào vị trí j + 1 được thực hiện bằng câu lệnh:
A[j+1] = value
Như vậy ba thao tác đã nêu ở bước 2 trên có thể được thực hiện bằng các câu lệnh chương trình như sau:
Chèn A[i] vào đúng vị trí
1 value = A[i]
2 j = i-1
3 while j >= 0 and A[j] > value:
4, A[j+1] = A[j]
5, j = j - 1
6 A[j+1], = value

Tới đây quá trình thiết kế kết thúc vì chúng ta đã chi tiết hoá bằng các câu lệnh tất cả các thao tác được mô tả trong các bước trên.
c) Chương trình hoàn chỉnh
Chương trình giải bài toán đặt ra được thiết kế hoàn chỉnh dưới dạng hàm InsertionSort(A). Tổng hợp các bước trên chúng ta có chương trình hoàn chỉnh như sau.
1 def InsertionSort(A):
2 n = len(A)
3 for i in range(1,n):
4 value = A[i]
5 j = i-1
6 while j >= 0 and A[j] > value:
7 A[j+1] = A[j]
8 j = j -1
9 A[j+1] = value
Như vậy quá trình thiết kế chương trình theo thuật toán sắp xếp chèn đã trải qua một số bước, mỗi bước sẽ thực hiện chi tiết hoá hay còn gọi là làm mịn dần các phân tích của bước trước đó.
Phương pháp làm mịn dần trong thiết kế chương trình là quá trình chi tiết hoá từ ý tưởng của các bước trước thành những hành động cụ thể hơn ở các bước sau. Ở bước cuối cùng, các hành động tương ứng với các câu lệnh của ngôn ngữ lập trình để viết chương trình hoàn chỉnh.
1. Trong giản, các bước đã thực hiện của bài toán sắp xếp chèn ở trên, bước nào là đơn nhất theo nghĩa có thể thực hiện ngay bằng các lệnh lập trình?
Nếu bài toán đặt ra là sắp xếp dãy A theo thứ tự giảm dần thì các bước thiết kế như trên có cần thay đổi không? Thay đổi như thế nào?
2. THIẾT KẾ CHƯƠNG TRÌNH BẰNG PHƯƠNG PHÁP LÀM MỊN DẦN
Hoạt động 2 Thiết kế chương trình bằng phương pháp làm mịn dần
Thực hiện thiết kế thuật toán và chương trình bằng phương pháp làm mịn dần theo các bài toán sau. Trao đổi, thảo luận với bạn bè để thiết lập được lời giải tốt hơn.
Bài toán. Cho trước dãy số A: A[0], A[1], ..., A[n-1]. Cặp phần tử A[i], A[j] được gọi
là nghịch đảo nếu i < j nhưng A[i] > A[j]. Cần viết chương trình đếm số các cặp nghịch đảo của dãy A. Ví dụ dãy 3, 4, 2, 1 sẽ có 5 cặp nghịch đảo là (3,2), (3,1), (4,2), (4,1), (2,1).
Thiết kế theo phương pháp làm mịn dần
a) Tìm hiểu bài toán
Bài toán gốc là cho trước dãy số A có n phần tử, cần đếm số các cặp phần tử nghịch đảo của A.

b) Thiết kế chương trình giải bài toán
Chúng ta sẽ thiết kế lời giải bài toán theo phương pháp làm mịn dần.
Bước 1. Thiết lập ý tưởng thiết kế ban đầu.
Bài toán có yêu cầu chính là đếm tất cả các cặp chỉ số nghịch đảo của dãy A. Vậy phần khung chính của chương trình sẽ là:
<Đếm số lượng các cặp số nghịch đảo (A[i],A[j]) của dãy A, trả về giá trị này>
Như vậy để thực hiện được yêu cầu trên chúng ta cần thực hiện hai công việc: cần tìm tất cả các cặp chỉ số (i, j) có thể tạo cặp nghịch đảo A[i], A[j], sau đó kiểm tra xem cặp này có là nghịch đảo không, nếu có thì tăng biến đếm lên 1 đơn vị.
Lược đồ thuật toán ban đầu có thể được mô tả như sau:
1 count = 0 2 Tìm tất cả các cặp chỉ số (i,j) có thể tạo ra cặp phần tử nghịch đảo 3 Kiểm tra nếu cặp A[i], A[j] là nghịch đảo thì tăng count lên 1 đơn vị. 4 return count
Bước 2. Tìm tất cả các cặp chỉ số (i,j) Cách tìm tự nhiên tất cả các cặp nghịch đảo là cần duyệt trên tất cả các cặp (i, j) trong đó i, j chạy từ 0 đến n - 1. Như vậy có thể thiết lập hai vòng lặp theo i, j để tìm. Chú ý để tiết kiệm thời gian chúng ta sẽ chỉ tìm các chỉ số i chạy từ 0 đến n-2, chỉ số j tính từ i+1 đến n - 1. Kết quả bước làm mịn này là đoạn chương trình sau: for i in range(n-1): for j in range(i+1,n): Như vậy tới bước này, thuật toán gốc có thể được mô tả như sau:
1 count = 0 2 for i in range(n-1): 3 for j in range(i+1,n): 4 if <cặp (i,j) là nghịch đảo>: 5 tăng count lên 1 đơn vị 6 return count
Bước 3. Kiểm tra tính nghịch đảo của cặp (i,j).
Chúng ta đã biết cặp (i, j) sẽ là nghịch đảo khi và chỉ khi i < j và A[i] > A[j]. Tuy nhiên tại bước 2 chúng ta đã thiết lập được tất cả các cặp (i, j) với điều kiện i < j do đó việc kiểm tra nghịch đảo chỉ còn một điều kiện là A[i] > A[j]. Kết quả làm mịn của bước 3 như sau:
if A[i] > A[j]:
count = count + 1
Tới bước này các thao tác chi tiết cần thực hiện để giải bài toán đã gần hoàn thành như sau:
1 count = 0
2 for i in range(n-1):
3 for j in range(1,n):
4 if A[i] > A[j]:
5 count = count + 1
6 return count

c) Chương trình hoàn chỉnh
Trên cơ sở các phân tích trên chúng ta có thể thiết lập hàm Nghichdao(A) để đếm
số các cặp nghịch đảo của dãy A cụ thể như sau:
1 def Nghichdao(A):
2 n = len(A)
3 count = 0
4 for i in range(n-1):
5 forj in range(i+1,n):
6 if A[i] > A[j]:
7 count = count + 1
8 return count
Phương pháp làm mịn dần trong thiết kế chương trình phải tuân thủ các
quy trình và nguyên tắc sau:
● Chia việc thiết kế thành từng bước và thực hiện lần lượt các bước.
● Mỗi bước lớn có thể được chia thành nhiều bước nhỏ hơn để giải
quyết độc lập.
● Tiếp cận bài toán từ tổng quan đến chi tiết, mỗi bước tiếp theo sẽ phải
là thiết kế chi tiết hơn bước trước đó. Quá trình như vậy sẽ tiếp tục cho
đến khi viết xong toàn bộ các câu lệnh của chương trình giải bài toán
đã cho.
Với Bài toán ở Hoạt động 1, có thể tách các dòng lệnh từ 4 đến 9 thành một hàm
con độc lập được không?
Trong thiết kế bài toán tìm các cặp phần tử nghịch đảo, các bước sau đã thực hiện
những thay đổi quan trọng nào so với bước trước đó?
LUYỆN TẬP
Phát biểu sau đúng hay sai?
Khi thiết kế chương trình thì việc đầu tiên là tìm hiểu yêu cầu chung của bài toán,
xác định đầu vào, đầu ra của bài toán, sau đó mới đi cụ thể vào chi tiết.
Sử dụng thiết kế của Bài toán ở Hoạt động 2, tìm tất cả các cặp nghịch đảo của
dãy: 3, 2, 1, 5, 4.
VẬN DỤNG
Sử dụng phương pháp làm mịn dần để giải bài toán sau: Cho trước số tự nhiên
không âmn, viết chương trình kiểm tra xem sốn có phải là số nguyên tố hay
không. Chương trình cần thông báo "CÓ" nếun là số nguyên tố, ngược lại thông
báo "KHÔNG".
Với thuật toán sắp xếp chèn, chứng minh rằng nếu thay toàn bộ phần
<Chèn A[i] vào vị trí đúng của dãy con A[0], A[1], ..., A[i – 1]>
bằng các lệnh sau thì chương trình vẫn đúng:
1 j = i
2 whilej > 0 and A[j] < A[j-1]:
3 Đổi chỗ A[j] và A[j-1]
4 j = j – 1
122

Thực hành thiết kế chương trình theo phương pháp làm mịn dần
SAU BÀI HỌC NÀY EM SẼ:
Thực hành thiết kế chương trình theo phương pháp làm mịn dần.
Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ hình cây để mô tả phương pháp này không?
Nhiệm vụ 1. Kiểm tra hoán vị
Cho trước một dãy n số, các số được kí hiệu A[0], A[1], ..., A[n-1]. Cần thiết kế chương trình kiểm tra xem dãy trên có phải là một hoán vị của dãy số 1, 2, ..., n hay không. Chương trình cần thông báo kết quả là CÓ hoặc KHÔNG.
Hướng dẫn: Phân tích thiết kế
a) Tìm hiểu bài toán
Bài toán gốc: Cho trước dãy số A gồm n phần tử, cần kiểm tra xem A có phải là một hoán vị của dãy số 1, 2,..., n hay không.
b) Thiết kế theo phương pháp làm mịn dần
Bước 1. Thiết lập ý tưởng thiết kế ban đầu.
Ý tưởng ban đầu để giải bài toán này khá đơn giản: Sắp xếp A theo thứ tự tăng dần. Sau đó chỉ cần so sánh A có trùng khít với dãy [1, 2, ..., n] hay không. Như vậy sơ đồ khung ban đầu của lời giải sẽ như sau:
1 Sắp xếp dãy A theo thứ tự tăng dần.
2 Kiểm tra A có phải là dãy 1, 2, ..., n hay không
Bước 2. Sắp xếp dãy A
Việc sắp xếp dãy A theo thứ tự tăng dần được mô tả bằng hàm sapxep(A) theo một trong các thuật toán sắp xếp mà chúng ta đã biết. Ví dụ bằng thuật toán sau:
1 def sapxep(A):
2 for i in range(len(A)):
3 j = i
4 while j > 0 and A[j] < A[j-1]:
5 A[j],A[j-1] = A[j-1],A[j]
6 j = j - 1
Bước 3. Với dãy A đã được sắp xếp, kiểm tra A có phải là dãy [1, 2, ..., n]?
Việc kiểm tra này có thể được thực hiện đơn giản như sau:
Kiểm tra lần lượt các phần tử của A với các phần tử tương ứng của dãy 1, 2,..., n. Nếu tất cả các so sánh đều bằng nhau thì trả về kết quả True, ngược lại trả về False.

Sử dụng biến kq để trả lại kết quả của việc so sánh A và dãy các số 1, 2, ..., n, ta có thể viết đoạn chương trình chi tiết thực hiện công việc được mô tả trên

19 if kt_hoanvi(A):
20 print("CÓ")
21 else:
22 print("KHÔNG")
Nhiệm vụ 2. Đếm số lần lặp
Thiết kế và viết chương trình theo phương pháp làm mịn dần cho bài toán sau: Cho trước dãy số A[0], A[1], ..., A[n-1]. Cần tính được mỗi giá trị của các phần tử của dãy trên được lặp lại bao nhiêu lần trong dãy đó. Kết quả cần được đưa ra dãy B. Như vậy dãy B sẽ có ý nghĩa như sau: B[k] = số lần lặp của phần tử A[k] trong dãy A.
Ví dụ nếu A = [2, 1, 1, 3, 5, 10, 2, 5] thì B = [2, 2, 2, 1, 2, 1, 2, 2].
Hướng dẫn: Phân tích thiết kế
a) Tìm hiểu bài toán
Bài toán gốc: cho trước dãy số A có n phần tử. Cần tạo ra một dãy mới là số các lần lặp của các phần tử tương ứng trong A.
b) Thiết kế theo phương pháp làm mịn dần
Bước 1. Thiết lập ý tưởng thiết kế ban đầu.
Theo yêu cầu chúng ta cần xây dựng dãy B có cùng kích thước với dãy A và các phần tử của B liên hệ với dãy A như sau: B[k] = số lần lặp của phần tử A[k] trong dãy A. Do vậy thiết kế lời giải sơ lược ban đầu của bài toán như sau:
1 Thiết lập dãy B rỗng
2 for i in range(len(A)):
3, Tính số lần lặp của A[i] trong dãy A
4, Bổ sung giá trị này vào dãy B
5 Trả, về dãy B
Bước 2. Thiết lập dãy B rỗng.
Việc này được thực hiện đơn giản bằng lệnh B = [].
Bước 3. Tính số lần lặp của A[i] trong dãy A.
Công việc này có thể được thực hiện thông qua lời gọi hàm lap(x,A) tính số lần lặp của một giá trị bất kì trong dãy A. Hàm lap(x,A) có thể được viết như sau:
1 def lap(x,A):
2 S = 0
3 for a in A:
4 if a == x:
5 S = S + 1
6 return S
Bước 4. Bổ sung số lần lặp vào dãy B.
Tổng hợp kết quả của các bước trên, chúng ta thu được đoạn chương trình hoàn chỉnh đã nêu ở bước 1 như sau:
1 B = []
2 for i in range(len(A)):
3 B.append(lap(A[i],A))
4 return B

Bước 5. Trả về dãy B cần tìm của bài toán. Để hoàn thiện toàn bộ chương trình chúng ta sẽ thiết lập hàm tinh_lap(A) mô tả đoạn chương trình đã nêu trong bước 4

Bài 28. Thiết kế chương trình theo mô đun SAU BÀI HỌC NÀY EM SẼ: Biết và vận dụng được cách thiết kế chương trình theo mô đun cho một số bài toán cụ thể. Nhận b

Bước 1. Thiết kế chung Từ yêu cầu của bài toán, ta thấy có thể chia bài toán đã cho thành ba công việc chính, các công việc này tương đối độc lập với nhau. Công

5 print(P[i],S[i],file = f)
6 for i in range(2,-1,-1):
7 print(P[i],S[i],file = f)
8 f.close()
Sau các bước trên, chúng ta đã thực hiện xong việc thiết kế các công việc chính được đặt ra ban đầu. Mỗi công việc đó được viết thành một hàm riêng biệt, độc lập với nhau. Các hàm này được gọi là các mô đun con của chương trình. Chương trình chính sử dụng các chương trình con trên được mô tả đơn giản như sau:
1 fin = "Data.inp"
2 fout = "Data.out"
3 P,S = NhapDL(fin)
4 Sapxep(S,P)
5 GhiDL(P,S,fout)
Phương pháp thiết kế chương trình như trên được gọi là thiết kế theo mô đun. Mỗi mô đun thường là các chức năng độc lập, riêng biệt theo yêu cầu của chương trình. Tuỳ thuộc vào từng bài toán và quan điểm thiết kế có thể tạo các mô đun này theo nhiều cách khác nhau.
Phương pháp thiết kế chương trình theo mô đun sẽ tách bài toán lớn thành các bài toán nhỏ hơn, hay thành các mô đun, tương đối độc lập với nhau, sau đó tiến hành thiết kế thuật toán và chương trình cho từng mô đun con. Mỗi mô đun có thể là một số hàm hoặc thủ tục độc lập. Chương trình chính là một bản ghép nối các hàm và thủ tục con.
Chương trình trên được thiết kế có bao nhiêu mô đun?
Các mô đun của chương trình trên có quan hệ với nhau như thế nào?
2. LỢI ÍCH CỦA PHƯƠNG PHÁP THIẾT KẾ THEO MÔ ĐUN
Hoạt động 2 Tìm hiểu lợi ích của phương pháp thiết kế theo mô đun
Với chương trình đã có trong Hoạt động 1, em sẽ làm gì nếu có các yêu cầu bổ sung như sau:
Yêu cầu thay đổi thông tin trong báo cáo: Ghi hai mặt hàng có doanh số cao nhất và bốn mặt hàng có doanh số thấp nhất.
Cập nhật, bổ sung các mặt hàng mới và doanh số trong ngày.
Yêu cầu làm thêm một báo cáo trong đó ghi doanh số bán trung bình trong ngày và danh sách các mặt hàng có doanh số lớn hơn doanh số trung bình này, kết quả đưa ra tệp Data2.out. Em có nhận xét gì về việc thực hiện các công việc bổ sung này?

Công việc bổ sung 1 Đây là công việc cần nâng cấp hàm GhiDL() và độc lập với các mô đun khác. Việc nâng cấp này rất đơn giản và được mô tả trong chương trình sa

Phân loại các công việc bổ sung trên vào ba loại sau:
Công việc mới hoàn toàn. - Công việc nâng cấp một mô đun cũ. - Công việc không liên quan đến thuật toán và lập trình.
Công việc sau đây, nếu có, sẽ thuộc nhóm công việc nào? Nhập một giá trị số nào đó, ví dụ K, cần tìm trong danh sách các mặt hàng có doanh số xấp xỉ K (hơn kém nhau không quá hằng số C = 1).
LUYỆN TẬP
Nếu công việc bổ sung 3 có thêm yêu cầu in ra số lượng mặt hàng đã bán trong ngày thì cần thêm hay sửa lệnh nào của chương trình BC2().
Viết thêm một chương trình cho công việc bổ sung 4 như sau: Cần in ra danh sách 1 số mặt hàng có doanh số thấp nhất trong ngày. 3
VẬN DỤNG
Thiết lập chương trình cho công việc thường làm vào cuối giờ bán hàng: Cho trước số K (một doanh số giả định), cần tìm ra mặt hàng có doanh số nhỏ hơn K nhưng gần với K nhất. Bài toán này có thể sử dụng thuật toán tìm kiếm nào để giải?
Thiết kế thuật toán và chương trình theo mô đun cho bài toán sau. Một công ti du lịch có n địa điểm tham quan được đánh số theo thứ tự 0, 1, 2,..., n - 1. Công ti này luôn tổ chức các tour du lịch đi lần lượt từ vị trí 0, 1, 2,... và kết thúc tại vị trí cuối cùng n - 1. Để thuận tiện cho việc quảng bá du lịch công ti đã lấy ý kiến khách hàng đánh giá bằng điểm số cho từng địa điểm du lịch trên, các đánh giá có thể là các số dương, 0 hoặc số âm bất kì. Số lớn hơn 0 biểu thị đánh giá tốt, số nhỏ hơn 0 biểu thị đánh giá xấu về địa điểm đó. Mỗi khách hàng sẽ gửi lên công ti du lịch bảng đánh giá của mình, được biểu thị bằng một dãy n số, ví dụ như sau: 1, -3, 4, 10, 0, -5, -8, 2, -1, 7, 2 Công ti du lịch hứa sẽ tổ chức một tour riêng cho mỗi khách hàng, bảo đảm sự hài lòng cao nhất của khách hàng. Tour du lịch riêng của khách hàng sẽ là một dãy các vị trí liên tục các địa điểm, ví dụ từ vị trí i đến j, tức là xuất phát từ i, khách hàng sẽ lần lượt đi qua các vị trí i, i + 1, i + 2,... và kết thúc tại j. Công ti du lịch bảo đảm rằng tổng các đánh giá của khách hàng trên tour riêng của mình là lớn nhất. Em hãy giúp công ti du lịch thiết lập tour du lịch tối ưu cho khách hàng nếu biết trước các đánh giá của khách hàng đó.

Thực hành thiết kế chương trình theo mô đun
SAU BÀI HỌC NÀY EM SẼ:
Thực hành thiết kế một số chương trình hoàn chỉnh theo mô đun.
Trong Bài 28, em đã biết tầm quan trọng và ý nghĩa của việc thiết kế chương trình theo mô dun. Mỗi mô dun chính là một chương trình con được xác định khi phân tích thiết kế bài toán lớn. Mỗi mô dun được viết một cách độc lập, có thể sử dụng lại như các thư viện và có thể chia sẻ trong nhóm làm việc. Trong bài thực hành này em sẽ được tự mình thiết kế chương trình cho một bài toán hoàn chỉnh theo mô dun.
Nhiệm vụ. Tính điểm tổng hợp của vận động viên
Trong một cuộc thi đấu thể thao khu vực dạng Sea Games, các cầu thủ tham gia thi đấu ở các bộ môn khác nhau và do sự phức tạp của truyền tin nên ban tổ chức (BTC) đã quyết định nhập thông tin kết quả thi đấu của các vận động viên vào các tệp văn bản, sau đó các tệp này được chuyển về trung tâm để xử lí. Mỗi bộ môn thể thao sẽ có số lượng ban giám khảo khác nhau. Mỗi tệp dữ liệu lưu thông tin sẽ có khuôn dạng gồm nhiều dòng, mỗi dòng là thông tin của một vận động viên thi đấu tại một bộ môn nào đó. Mỗi dòng của tệp thông tin sẽ bao gồm:
– Đầu tiên là mã số của vận động viên.
– Tiếp theo là điểm cho của các giám khảo, giữa các điểm số đều có dấu cách.
– Điểm số được cho có thể là số nguyên hoặc số thập phân, thang điểm 10.
Theo quy định của BTC, quy định tính điểm chung cho mỗi vận động viên như sau: Điểm tổng hợp của mỗi vận động viên là trung bình cộng điểm của ban giám khảo. Tuy nhiên trong mỗi ban giám khảo luôn có hai giám khảo đặc biệt, hai giám khảo này có hệ số tổng hợp là 2, trong khi các giám khảo khác có hệ số 1. Theo quy định của BTC thì các giám khảo đặc biệt sẽ ở vị trí đầu tiên và cuối cùng của danh sách. Ở tất cả các bộ môn thể thao số lượng thành viên ban giám khảo phải lớn hơn 2.
Nhiệm vụ của em là tính điểm tổng hợp của các vận động viên từ tệp văn bản SeaGames.inp. Kết quả ghi ra tệp ketqua.out có dạng như sau:
– Tệp sẽ có nhiều dòng, số dòng bằng đúng số dòng của tệp đầu vào.
– Trên mỗi dòng ghi mã của vận động viên và điểm tổng hợp tương ứng. Yêu cầu ghi điểm tổng hợp với hai chữ số sau dấu phẩy.

SeaGames.inp Ketqua.out 101 7.5 8.0 9.0 9.5 7.1 6.8 101 7.77 200 8.5 9.1 9.5 8.6 9.9 200 9.14 003 6.6 7.0 7.5 6.8 5.9 8.1 003 7.08 045 8.5 7.9 9.3 9.0 8.9 045 8

c) Thiết kế mô đun xử lí dữ liệu chính
Mục đích của mô đun này là tính điểm tổng hợp cho mỗi vận động viên.
Mỗi vận động viên sẽ tương ứng với một dãy các điểm số được lấy từ mảng Diem. Từ dãy này sẽ tính được điểm tổng hợp theo cách tính đặc biệt của BTC. Mô đun này sẽ cần hai hàm.
Hàm diem_gk() sẽ tính điểm tổng hợp các giám khảo từ dãy các điểm. Chú ý theo yêu cầu thì các giám khảo đầu tiên và cuối cùng có hệ số 2 nên cần tính điểm các giám khảo này hai lần. Điều này được mô tả tại dòng lệnh 2. Hàm này được thiết kế chi tiết như sau:
1 def diem_gk(d):
2 diem = sum(d) + d[0] + d[len(d)-1]
3 diem = diem/(len(d)+2)
4 return round(diem,2)
Hàm Xuly() sẽ tính toán điểm tổng hợp cho tất cả các vận động viên với đầu vào là mảng Diem. Hàm này sẽ sử dụng hàm diem_gk() đã thiết lập ở phần trên. Kết quả tính toán là một dãy điểm tổng hợp và là giá trị trả lại của hàm này. Kết quả của hàm Xuly() là dãy kq.
1 def Xuly(B):
2 kq = []
3 for i in range(len(B)):
4 diem = diem_gk(B[i])
5 kq.append(diem)
6 return kq
d) Thiết kế mô đun đưa kết quả ra
Cuối cùng là mô đun đưa kết quả ra tệp đầu ra theo yêu cầu của bài toán.
Hàm ghiDL() sẽ có ba tham số đầu vào là tên tệp dữ liệu ra, hai mảng DS và kq. Khai báo của hàm này là ghiDL(fout, A, B), trong đó fout là tên tệp dữ liệu đầu ra, A là mảng danh sách các mã số của vận động viên, B là mảng ghi kết quả điểm tổng hợp của các vận động viên. Kết quả đưa ra màn hình.
1 def ghiDL(fout,A,B):
2 f = open(fout,"w")
3 for i in range(len(A)):
4 print(A[i],B[i],file = f)
5 f.close()
e) Tổng hợp chương trình chính
1 finp = "SeaGames.inp"
2 fout = "ketqua.out"
3 DS,Diem = nhapDL(finp)
4 kq = Xuly(Diem)
5 ghiDL(fout,DS,kq)

Sau đây là toàn bộ chương trình: SeaGames.py 1 def nhapDL(finp): 2 f = open(finp) 3 A = [] 4 B = [] 5 for line in f: 6 S = line.split() 7 A.append(S[0]) 8 temp

LUYỆN TẬP
Hãy chỉnh sửa lại chương trình trên nếu bổ sung thêm điều kiện sau vào nhiệm vụ: Trong tệp kết quả đầu ra, thứ tự các vận động viên được ghi theo thứ tự giảm dần của điểm đánh giá.
Trong nhiệm vụ trên, nếu công thức tính điểm tổng hợp của Sea Games thay đổi thì chúng ta có phải sửa lại toàn bộ chương trình hay không? Nếu cần thì chỉ phải sửa mô đun nào? Hàm nào?
VẬN DỤNG
Thiết lập chương trình thiết kế theo mô đun cho các bài toán sau:
Cho trước số tự nhiên n, cần in ra trên màn hình dãy n số nguyên tố đầu tiên. Ví dụ nếu n = 5 thì dãy cần in ra sẽ là 2, 3, 5, 7, 11.
Trong một kì thi Tin học trẻ, mỗi học sinh sẽ phải làm 3 bài thi. Với mỗi bài, nếu học sinh làm sẽ được ban giám khảo chấm và cho điểm, nếu không làm thì sẽ không tính điểm. Sau khi thi, dữ liệu điểm thi của học sinh sẽ được lưu trong một tệp văn bản và gửi về ban tổ chức. Mẫu một tệp điểm thi có dạng sau:
Diemthi.inp
A12 12 -1 15 B123 9 14 -1 C11 10 12 18 A110 10 -1 -1 B01 12 10 4 Quy định ghi trong tệp trên như sau: - Mỗi dòng sẽ bắt đầu bằng số báo danh của thí sinh, tiếp theo là ba giá trị điểm tương ứng với ba bài thi. - Điểm thi sẽ là một số tự nhiên từ 0 đến 20. - Nếu học sinh không làm thì bài đó ghi -1. Em có nhiệm vụ tính toán tổng số điểm thi của các bạn học sinh và đưa dữ liệu ra tệp ketqua.out là danh sách ba bạn có tổng điểm cao nhất được sắp xếp giảm dần từ trên xuống dưới. Khuôn dạng dữ liệu đưa ra bao gồm: số báo danh, các điểm thi từng bài và cuối cùng là tổng điểm cả ba bài. Ví dụ với dữ liệu trên thì kết quả như sau:
ketqua.out
C11 10 12 18 40 A12 12 -1 15 27 B01 12 10 4 26

Bài 30. Thiết lập thư viện cho chương trình
SAU BÀI HỌC NÀY EM SẼ:
Tạo được một thư viện nhỏ của người lập trình.
Trình bày được cấu trúc danh sách liên kết.
Em đã học về cấu trúc mảng (một chiều hoặc hai chiều). Cấu trúc mảng là một danh sách các phần tử được đánh chỉ số và quan hệ với nhau thông qua hệ thống chỉ số này. Giả sử $A[0]$, $A[1]$, ..., $A[n - 1]$ là mảng n phần tử, nếu thực hiện lệnh, ví dụ del A[1], xoá một phần tử của dãy trên, thì các phần tử còn lại sẽ tự động điều chỉnh lại chỉ số để đối tượng vẫn là mảng (nhưng có n – 1 phần tử).
Cấu trúc danh sách liên kết (hay danh sách móc nối, linked list) là đối tượng có cấu trúc gần giống với mảng nhưng có liên kết không chặt chẽ như mảng. Một ví dụ của cấu trúc danh sách liên kết là mô hình các trang web. Khi duyệt web, em không thể đánh chỉ số cho từng trang web đã duyệt, mà chỉ có thể di chuyển đến các trang trước và trang sau.
Em hãy tìm thêm các ví dụ thực tế của mô hình danh sách liên kết.
1. THIẾT LẬP THƯ VIỆN CHO CHƯƠNG TRÌNH
Hoạt động 1 Tìm hiểu ý nghĩa của thư viện chương trình
Em hãy đọc, thảo luận và trả lời các câu hỏi sau:
Vì sao lại cần thư viện chương trình?
Ý nghĩa của các hàm trong thư viện chương trình là gì?
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ụ một số hàm thường dùng của thư viện math là hàm tính căn bậc hai sqrt(), làm tròn xuống floor() và làm tròn lên ceil(). Để đưa một 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 một thư viện r

2. CẤU TRÚC DANH SÁCH LIÊN KẾT Hoạt động 2 Tìm hiểu cấu trúc danh sách liên kết Đọ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á

Hàm delete_first(L) sẽ xoá node đầu tiên của danh sách (nếu danh sách không rỗng). Thao tác xoá node đầu tiên của danh sách. head → 5 • → 2 • → 8 • → None Chươn

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.nex

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ó khoá là 5, 2. L =

Thực hành thiết lập thư viện chương trình
SAU BÀI HỌC NÀY EM SẼ:
Viết được chương trình vận dụng những kiến thức tích hợp liên môn để giải quyết vấn đề.
Trong Bài 30, em đã tìm hiểu ý nghĩa và cách thiết lập thư viện chương trình. Em có thể thấy xung quanh em, đặc biệt là trong các lĩnh vực khoa học tự nhiên như Toán học, Vật lí và Hoá học, thường xuất hiện nhiều vấn đề hoặc nhiệm vụ tính toán mang tính tổng quát. Em hãy xây dựng thuật toán cho các vấn đề như vậy thành các thư viện để có thể sử dụng lại nhiều lần cũng như làm toàn bộ chương trình có cấu trúc trong sáng, rõ ràng, dễ phát triển, dễ bảo trì hơn.
Nhiệm vụ 1
Viết thư viện hinh_tron gồm hai hàm để tính chu vi và diện tích của hình tròn với tham số của hàm số là bán kính. Trong thư viện này, hãy sử dụng hằng số math.pi là giá trị của số Pi được định nghĩa ở thư viện math. Sau đó, viết một tệp mã nguồn main.py để yêu cầu người dùng nhập bán kính đường tròn là một số dương rồi sử dụng thư viện trên để tính diện tích và chu vi hình tròn.
Hướng dẫn:
Nhiệm vụ này được thực hiện bằng cách định nghĩa hai hàm tinhChuVi và tinhDienTich được viết trong tệp circle.py và đoạn mã nguồn sử dụng thư viện hinh_tron trong tệp main.py.
hinh_tron.py
import math #Khai báo sử dụng thư viện math từ thư viện chuẩn của python
def tinhChuVi(r):
return 2*math.pi*r
def tinhDienTich(r):
return math.pi*r*r
main.py
import hinh_tron #Khai báo sử dụng thư viện hinh_tron vừa định nghĩa
r = float(input("Nhập bán kính hình tròn: "))
p = hinh_tron.tinhChuVi(r)
print("Chu vi hình tròn là", p)
s = hinh_tron.tinhDienTich(r)
print("Diện tích hình tròn là", s)

Nhiệm vụ 2
Tạo thư viện cong_thuc_ly gồm hai hàm machSongSong(dsDienTro) và machNoiTiep(dsDienTro) để tính điện trở tương đương của mạch song song và nối tiếp gồm các điện trở được cho giá trị tính theo Ω trong mảng dsDienTro. Hãy viết chương trình trong tệp main.py sử dụng hai hàm vừa định nghĩa để tính điện trở tương đương của mạch gồm các điện trở với giá trị 3, 6 và 8 Ω.
Hướng dẫn:
Áp dụng kiến thức vật lí: điện trở tương đương của mạch gồm các điện trở mắc nối tiếp bằng tổng các điện trở và mạch gồm các điện trở mắc song song bằng nghịch đảo của tổng các nghịch đảo giá trị điện trở thành phần. Ngoài ra kiểm tra nếu có một giá trị điện trở không hợp lệ (nhỏ hơn hoặc bằng 0) thì in thông báo và hàm trả về giá trị -1 với ý nghĩa dữ liệu không hợp lệ.
cong_thuc_ly.py
1 def machSongSong(dsDienTro):
2 for r in dsDienTro:
3 if r <= 0:
4 print("Dữ liệu không hợp lệ, tồn tại một điện trở <= 0")
5 return -1
6 return sum(dsDienTro)
7
8 def machNoiTiep(dsDienTro):
9 tongNghichDao = 0
10 for r in dsDienTro:
11 if r <= 0:
12 print("Dữ liệu không hợp lệ, tồn tại một điện trở <= 0")
13 return -1
14 tongNghichDao = tongNghichDao + 1/r
15 return round(1/tongNghichDao,2)
main.py
1 from cong_thuc_ly import *
2
3 dsDienTro = [3, 6, 8]
4 print("Điện trở tương đương của mạch mắc nối tiếp:", machSongSong(dsDienTro))
5 print("Điện trở tương đương của mạch mắc song song:", machNoiTiep(dsDienTro))
Nhiệm vụ 3
Em hãy định nghĩa hàm tinhNtkTB(dsNtk, dstyLe) trong tệp cong_thuc_hoa.py để tính nguyên tử khối trung bình của một nguyên tố hoá học, trong đó tham số dsNtk là mảng giá trị các nguyên tử khối của các đồng vị và dstyLe là tỉ lệ phần trăm số nguyên tử của các đồng vị của nguyên tố đó. Sau đó, em hãy viết chương trình trong tệp main.py để sử dụng hàm tinhNtkTB tính nguyên tử khối trung bình của carbon biết carbon có hai đồng vị bền là 12C chiếm 98,89% và 13C chiếm 1,11%.
Hướng dẫn:
Áp dụng kiến thức hoá học: nguyên tử khối trung bình của một nguyên tố ffifl1n ntk tyLe * gồm n đồng vị được tính theo công thức ntkTB fl i i i trong đó ntki > 0

và tyLei ∈(0,100) lần lượt là nguyên tử khối và tỉ lệ phần trăm của các đồng vị thứ i (i = 1,2,...,n) của nguyên tố đó.
cong_thuc_hoa.py
1 def tinhNtkTB(dsNtk,dstyLe):
2 if len(dstyLe) > 0 and len(dsNtk) == len(dstyLe):
3 tong = 0
4 for i in range(len(dsNtk)):
5 tong = tong + dsNtk[i] * dstyLe[i]
6 return tong/100
7 else:
8 return 0
main.py
1 from cong_thuc_hoa import tinhNtkTB
2
3 dsNtk = [12,13]
4 dsTyLe = [98.89, 1.11]
5 ntkTB = tinhNtkTB(dsNtk, dsTyLe)
6 print("Nguyên tử khối trung bình của Carbon là", ntkTB)
LUYỆN TẬP
Đặt tất cả các tệp thư viện đã định nghĩa ở nhiệm vụ 1, 2 và 3 vào thư mục myLibs rồi viết mã nguồn ở tệp main.py (đặt cùng đường dẫn với thư mục myLibs) để sử dụng các hàm trong các thư viện đó.
Sửa lại thư viện hinh_tron ở nhiệm vụ 1 bằng cách không sử dụng thư viện chuẩn math mà hãy định nghĩa thư viện my_math trong đó có định nghĩa hằng số Pi.
VẬN DỤNG
Tạo thư viện phuong_trinh gồm hàm phuongTrinhBac2(a, b, c) với a, b, c là các hệ số của phương trình ax2 + bx + c = 0 . Tuỳ vào các giá trị của các tham số, hàm sẽ in ra thông báo nghiệm của phương trình.
Viết chương trình quản lí các bài hát trong một đĩa CD hay một play list, sử dụng cấu trúc LinkedList (đã được định nghĩa ở bài trước). Chương trình gồm hai tệp:
Tệp quan_ly_cd.py gồm ba hàm:
Hàm nhapDL(): Yêu cầu người dùng nhập số lượng bài hát, rồi sau đó nhập lần lượt tên các bài hát và bổ sung vào đĩa CD (hay play list), trả lại biến kiểu LinkedList chứa các bài hát. - Hàm timBai(): Tham số gồm đối tượng LinkedList và tên bài hát <ten_bai>. Nếu có bài hát cần tìm, hàm in ra vị trí đầu tiên xuất hiện bài hát, nếu không in ra thông báo "Không tìm thấy bài hát <ten_bai>". - Hàm inTT(): tham số là đối tượng LinkedList, thực hiện in mỗi bài hát trên một dòng theo định dạng <Số thứ tự>.<Tên bài hát>.
Tệp main.py sử dụng thư viện quan_ly_cd.

Báo lỗi

Giao bài

Đang tải dữ liệu câu hỏi