Hai chỉ số thỏa i<j
```python
def best_pair(names, lists):
best_names = None, None
best_count = -1
for i in range(len(names) - 1):
for j in range(i + 1, len(names)):
count = len(common_values(lists[i], lists[j]))
if count > best_count:
best_names = names[i], names[j]
best_count = count
if best_count < 0:
return None, None, 0
return best_names[0], best_names[1], best_count
```
Vòng trong bắt đầu ở i+1 nên không có(i,i), cũng không lặp cả(i,j)và(j,i). Mỗi cặp khác nhau xuất hiện đúng một lần. So số phần tử chung với best_count, nếu lớn hơn thì giữ cả hai tên và số lượng.
Nếu có nhiều cặp đạt cùng tối đa, mã giữ cặp gặp trước theo thứ tự i,j. Nếu dữ liệu có ít hơn hai tài khoản, trả(None,None,0)để báo chưa có cặp. Khi có hai tài khoản nhưng không chung phần tử nào, cặp đó vẫn hợp lệ với số lượng0.
Chạy với cả hai tệp dữ liệu
Chạy:
```text
python3 g11-cs-danh-sach-chung.py cap g11-cs-lien-he.inp
python3 g11-cs-danh-sach-chung.py cap g11-cs-nhom.inp
```
Tệp liên hệ cho cặp A,B với3 phần tử chung, nhiều hơn các cặp còn lại. Tệp nhóm có A,B và B,C đều đạt3 nhóm chung; mã giữ A,Bvì gặp trước. Không dùng một kết quả đồng hạng để khẳng định chỉ có duy nhất một cặp tối ưu.
Bài này tìm cặp lớn nhất nên không dừng ở cặp đầu có phần tử chung. Cần xét mọi cặp trong miền, trừ khi có căn cứ khác chứng minh không thể tốt hơn; bản đang học duyệt toàn bộ các cặp.
Bài luyện
Với n tài khoản, dùng j từ i+1 có tác dụng gì?
Các cặp đảo chiều không được lặp.
Các giá trị i,j đi qua toàn bộ miền cặp.
Số lượng chung được tính sau khi chọn cặp.
Miền cặp là 0<=i<j<n.
Lời giải
Mỗi cặp khác nhau có một chỉ số nhỏ hơn chỉ số kia. Chỉ lấy i<j vừa phủ đủ các cặp, vừa bỏ(i,i)và chiều lặp(j,i).
Bài luyện
Vì sao không dừng ở cặp đầu tiên có một phần tử chung?
Mục tiêu là tối đa, không chỉ tồn tại phần tử chung.
Yêu cầu còn cần số lượng lớn nhất.
Số lượng phụ thuộc từng cặp danh sách.
Đó là ứng viên cần ưu tiên.
Lời giải
Có chung một phần tử chỉ cho một ứng viên. Cần tiếp tục so các cặp khác để chứng minh cặp giữ lại đạt số lượng lớn nhất.
Bài luyện
Chỉ có hai tài khoản, hai danh sách không chung phần tử nào. Kết luận nào đúng?
Tên tài khoản trong tệp là duy nhất.
Tồn tại hai tài khoản khác nhau dù số giao bằng 0.
Khác trường hợp dữ liệu có ít hơn hai tài khoản.
Không được sửa dữ liệu để tạo kết quả.
Lời giải
Hai tài khoản tạo đúng một cặp khác nhau. Khi giao rỗng thì số chung0, nhưng cặp vẫn tồn tại và cũng là cặp tối đa duy nhất trong miền này.
Đang học