Bài 6 Python lớp 9: Thuật toán và hiệu quả

Chọn cách giải thông minh hơn

Tìm kiếm và sắp xếp là cơ hội để em so sánh nhiều cách giải. Em sẽ biết kiểm thử bằng dữ liệu nhỏ và dữ liệu lớn. Thuật toán là cách giải bài toán; một cách giải dễ viết chưa chắc nhanh nhất khi dữ liệu tăng lên.

1. Kiến thức cần nhớ

Tìm kiếm tuyến tính lần lượt xem từng phần tử trong danh sách. Cách này dễ hiểu và phù hợp với danh sách nhỏ hoặc chưa sắp xếp. Khi viết chương trình, hãy xác định dữ liệu đầu vào, kết quả cần in và điều kiện dừng.

names = ["An", "Bình", "Chi", "Dũng"]
key = input("Tên cần tìm: ")
found = False
for i, name in enumerate(names):
if name == key:
print("Tìm thấy ở vị trí", i)
found = True
if not found:
print("Không tìm thấy")

enumerate() cung cấp cả vị trí và giá trị. Biến found ghi nhớ chương trình đã tìm thấy hay chưa. Khi dữ liệu lớn, em có thể đo số lần lặp để nhận xét hiệu quả.

2. Bài tập tự luyện

Bài 1: Tìm tên trong danh sách

Hãy tự viết chương trình trước. Đừng xem lời giải ngay. Em nên chuẩn bị ít nhất ba bộ dữ liệu: dữ liệu thông thường, dữ liệu ở biên và dữ liệu có thể gây lỗi.

Gợi ý: dùng vòng lặp for, so sánh từng tên với tên cần tìm và dùng một biến Boolean để ghi nhận kết quả.

Hướng dẫn: tạo danh sách, nhận tên bằng input(), duyệt danh sách bằng enumerate(), in vị trí nếu tìm thấy và thông báo nếu duyệt hết mà không có.

Phân tích bài toán

Trước khi gõ code, em hãy tách bài toán thành các bước nhỏ. Bước một, tạo danh sách tên. Bước hai, yêu cầu người dùng nhập tên cần tìm. Bước ba, lần lượt lấy từng tên trong danh sách để so sánh với tên cần tìm. Bước bốn, nếu hai tên giống nhau thì ghi nhận vị trí và dừng tìm kiếm. Bước năm, sau vòng lặp, kiểm tra xem đã tìm thấy hay chưa để in thông báo phù hợp.

Ta dùng biến Boolean found. Ban đầu found = False, nghĩa là chưa tìm thấy. Khi gặp tên phù hợp, đổi thành True. Cách làm này giúp chương trình phân biệt được hai trường hợp: tên có trong danh sách và tên không có trong danh sách.

Gợi ý từng bước

- Danh sách có thể viết như sau: names = ["An", "Bình", "Chi", "Dũng"].

- Dùng input() để nhận tên. Dùng thêm strip() để bỏ khoảng trắng thừa ở đầu và cuối câu trả lời.

- Dùng enumerate(names) để nhận được cả vị trí và tên. Vị trí trong Python bắt đầu từ 0, vì vậy “An” ở vị trí 0, “Bình” ở vị trí 1.

- Khi tìm thấy tên, hãy lưu vị trí vào biến found_index và dùng break để dừng vòng lặp. Không cần kiểm tra các phần tử phía sau nữa.

Lời giải hoàn chỉnh có thể chạy ngay

Tạo một tệp có tên tim_ten.py, chép toàn bộ chương trình dưới đây vào tệp rồi lưu lại.

names = ["An", "Bình", "Chi", "Dũng"]

print("Danh sách tên:", ", ".join(names))
key = input("Nhập tên cần tìm: ").strip()

found = False
found_index = -1

if key == "":
    print("Em chưa nhập tên cần tìm.")
else:
    for index, name in enumerate(names):
        if name.casefold() == key.casefold():
            found = True
            found_index = index
            break

    if found:
        print("Tìm thấy tên", key, "ở vị trí", found_index)
    else:
        print("Không tìm thấy tên", key, "trong danh sách.")

Giải thích chi tiết từng phần

Dòng đầu tiên tạo danh sách gồm bốn tên. Danh sách là kiểu dữ liệu cho phép lưu nhiều giá trị theo thứ tự. Dòng print() giúp người chạy nhìn thấy dữ liệu đang được tìm kiếm.

Lệnh input() đọc dữ liệu do người dùng gõ vào. Kết quả của input() luôn là chuỗi. Phương thức strip() loại bỏ khoảng trắng thừa, nhờ đó nhập “ Chi ” vẫn được xử lý giống như nhập “Chi”.

Hai biến found và found_index được chuẩn bị trước vòng lặp. Giá trị False cho biết chưa tìm thấy; giá trị -1 là một vị trí đặc biệt, dùng để biểu thị chưa có vị trí hợp lệ.

Điều kiện if key == "" xử lý trường hợp người dùng chỉ nhấn Enter. Nếu bỏ qua bước này, chương trình vẫn chạy nhưng thông báo sẽ kém rõ ràng. Đây là ví dụ về việc kiểm tra dữ liệu đầu vào trước khi xử lý.

Vòng lặp for index, name in enumerate(names) đi qua từng phần tử. Ở mỗi lượt, index là vị trí và name là tên tại vị trí đó. Phương thức casefold() hỗ trợ so sánh không phân biệt chữ hoa, chữ thường. Vì vậy, nhập “chi” vẫn có thể tìm thấy “Chi”.

Nếu điều kiện so sánh đúng, chương trình đổi found thành True, lưu vị trí vào found_index rồi thực hiện break. Lệnh break kết thúc vòng lặp ngay lập tức. Đây là cách làm hiệu quả khi chỉ cần vị trí xuất hiện đầu tiên.

Sau vòng lặp, chương trình dùng if found. Nếu biến này là True, chương trình in vị trí tìm thấy. Ngược lại, nhánh else thông báo rằng tên không có trong danh sách.

Bài 2: Đếm số lần xuất hiện của một từ trong danh sách

Ý tưởng giải bài

Chương trình thực hiện các bước:

1. Tạo danh sách các từ.
2. Nhập từ cần tìm.
3. Tạo biến đếm count với giá trị ban đầu bằng 0.
4. Duyệt từng từ trong danh sách bằng vòng lặp for.
5. Nếu từ đang xét giống từ cần tìm thì tăng count lên 1.
6. Sau khi duyệt hết danh sách, in kết quả.

Gợi ý trước khi xem lời giải

Em hãy thử tự viết chương trình theo gợi ý sau:

words = [...]
target = input(...)

count = 0

for word in words:
    if ...:
        count = count + 1

print(...)

Lưu ý:

• count = 0 vì ban đầu chưa tìm thấy từ nào.
• Mỗi lần gặp từ giống từ cần tìm, tăng count lên 1.
• Dùng strip() để bỏ khoảng trắng thừa.
• Dùng casefold() để không phân biệt chữ hoa và chữ thường.

Lời giải hoàn chỉnh

Em hãy sao chép toàn bộ chương trình dưới đây vào tệp dem_tu.py:

words = ["python", "java", "python", "html", "Python", "css"]

print("Danh sách từ:")
print(", ".join(words))

target = input("Nhập từ cần đếm: ").strip()

count = 0

if target == "":
    print("Em chưa nhập từ cần tìm.")
else:
    for word in words:
        if word.casefold() == target.casefold():
            count = count + 1

    print(f'Từ "{target}" xuất hiện {count} lần trong danh sách.')

Giải thích từng phần của chương trình

- Tạo danh sách

words = ["python", "java", "python", "html", "Python", "css"]

Biến words lưu một danh sách gồm 6 từ.

Trong danh sách này:

• python xuất hiện 2 lần.
• Python xuất hiện 1 lần.
• Vì chương trình không phân biệt chữ hoa, chữ thường nên tổng cộng từ Python xuất hiện 3 lần.

- In danh sách

print("Danh sách từ:")
print(", ".join(words))

Lệnh join() nối các phần tử trong danh sách thành một dòng.

Kết quả:

Danh sách từ:
python, java, python, html, Python, css

- Nhập từ cần tìm

target = input("Nhập từ cần đếm: ").strip()

Lệnh input() cho phép người dùng nhập dữ liệu từ bàn phím.

Phương thức strip() loại bỏ khoảng trắng thừa. Ví dụ, nếu người dùng nhập:

  python

thì chương trình sẽ xử lý giống như nhập:

python

- Khởi tạo biến đếm

count = 0

Ban đầu chưa kiểm tra phần tử nào nên số lần xuất hiện bằng 0.

- Kiểm tra dữ liệu rỗng

if target == "":
    print("Em chưa nhập từ cần tìm.")

Nếu người dùng chỉ nhấn Enter mà không nhập từ, chương trình thông báo và không thực hiện tìm kiếm.

- Duyệt danh sách

for word in words:

Vòng lặp lần lượt lấy từng phần tử trong danh sách và lưu vào biến word.

Các lượt lặp sẽ lần lượt kiểm tra:

python
java
python
html
Python
css

- So sánh hai từ

if word.casefold() == target.casefold():

Phương thức casefold() chuyển chuỗi về dạng phù hợp để so sánh không phân biệt chữ hoa, chữ thường.

Nhờ đó:

"python".casefold() == "Python".casefold()

cho kết quả:

True

- Tăng biến đếm

count = count + 1

Mỗi khi tìm thấy từ giống từ cần tìm, biến count tăng thêm 1.

Có thể viết ngắn gọn hơn:

count += 1

Hai cách viết có ý nghĩa giống nhau.

- In kết quả

print(f'Từ "{target}" xuất hiện {count} lần trong danh sách.')

Ký tự f trước chuỗi cho phép đưa giá trị của biến vào nội dung cần in.

Bài 3: Tìm điểm cao nhất trong danh sách điểm.

Cho một danh sách điểm của học sinh. Hãy viết chương trình tìm và in ra điểm cao nhất trong danh sách.

Ví dụ: scores = [7.5, 8.0, 9.25, 6.5, 8.75]

Kết quả: Điểm lớn nhất là: 9.25

Gợi ý: lấy phần tử đầu tiên làm giá trị lớn nhất tạm thời rồi so sánh các phần tử còn lại.

Tạo tệp chương trình

Tạo tệp có tên: tim_diem_lon_nhat.py

Lời giải hoàn chỉnh

Sao chép toàn bộ chương trình sau vào tệp tim_diem_lon_nhat.py để chạy và kiểm tra kết quả.

scores = [7.5, 8.0, 9.25, 6.5, 8.75]

if len(scores) == 0:
    print("Danh sách điểm đang rỗng.")
else:
    largest = scores[0]

    for score in scores[1:]:
        if score > largest:
            largest = score

    print("Danh sách điểm:", scores)
    print("Điểm lớn nhất là:", largest)

Bài tập về nhà

Bài 1: Sắp xếp điểm tăng dần

Sắp xếp danh sách điểm và in danh sách sau khi sắp xếp.

Gợi ý: có thể dùng sorted() để tập trung vào ý nghĩa của việc sắp xếp.

Bài 2: Tìm tên bị lặp và số lần xuất hiện trong danh sách

Hãy viết chương trình cho phép người dùng nhập danh sách tên, tìm tất cả vị trí của một tên bị lặp và in số lần xuất hiện. Sau đó tách phần tìm kiếm thành hàm find_name() để có thể dùng lại.

Đọc tiếp Bài 7: Dự án Python lớp 9.