btvn.vn
Tìm kiếm Đăng nhập

Tìm điểm trong tệp đã sắp xếp

Lưu trên thiết bị này
Kĩ thuật lập trình — CS · Chọn bài khác

Tệp điểm mẫu

Tạo tệp `diem_tang.txt` trong cùng thư mục chạy mã. Mỗi dòng là một điểm giả đã sắp không giảm: ```text 5.5 6.0 7.0 7.0 8.5 ``` Bài toán hỏi một điểm có xuất hiện không và, nếu có, ở một dòng nào. Hai số 7.0 cho thấy hàm nhị phân chỉ cần trả một vị trí khớp. Nếu dữ liệu chưa sắp, không dùng hàm này.

Đọc và tìm bằng nhị phân

```python def tim_nhi_phan_tang(a, k): trai, phai = 0, len(a) - 1 while trai <= phai: giua = (trai + phai) // 2 if a[giua] == k: return giua if a[giua] < k: trai = giua + 1 else: phai = giua - 1 return -1 with open("diem_tang.txt", "r", encoding="utf-8") as f: diem = [float(dong) for dong in f] for can_tim in [7.0, 9.0]: chi_so = tim_nhi_phan_tang(diem, can_tim) if chi_so == -1: print(can_tim, "không có trong tệp") else: print(can_tim, "ở dòng", chi_so + 1) ``` Kết quả là `7.0 ở dòng 3` rồi `9.0 không có trong tệp`. Giữa đầu tiên của năm phần tử là chỉ số 2, tức dòng thứ 3. Python đánh chỉ số từ 0, còn dòng đầu tiên thường được gọi là dòng 1 nên phải cộng 1. Một dòng trống hoặc chữ không phải số sẽ làm `float` báo lỗi; sửa tệp đầu vào. Hàm tin vào điều kiện tệp đã sắp không giảm, không tự kiểm thứ tự.

Đổi sang dãy giảm và tra khoảng

Nếu tệp sắp không tăng, dùng hàm `tim_nhi_phan_giam` ở L13: phần tử giữa lớn hơn điểm cần tìm thì đi sang phải. Với yêu cầu tìm **mọi** tên có điểm từ 6 đến 8, dùng tệp cặp tên–điểm ở L15 và duyệt mọi dòng với điều kiện `6 <= diem <= 8`; cả hai đầu mút đều được lấy. Nếu dữ liệu đã sắp theo điểm, có thể tìm biên đầu có điểm ≥6 và biên đầu có điểm >8 bằng cách thu hẹp nửa dãy, rồi lấy các bản ghi giữa hai biên. Khi sắp, phải giữ tên đi cùng điểm; sắp riêng điểm sẽ làm sai kết quả tên.

Bài luyện

Chỉ số Python 2 ứng với dòng thứ mấy của tệp mẫu?
Chọn một đáp án

Bài luyện

Vì sao có thể bỏ nửa trái khi dãy tăng và phần tử giữa nhỏ hơn điểm cần tìm?
Chọn một đáp án

Bài luyện

Nếu tệp có hai dòng điểm 7.0, hàm nhị phân mẫu bảo đảm điều gì?
Chọn một đáp án

Đang học