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

Tìm cặp có nhiều phần tử chung nhất

Lưu trên thiết bị này
Chuyên đề lựa chọn CS: Kĩ thuật duyệt · Chọn bài khác

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ì?
Chọn một đáp án

Bài luyện

Vì sao không dừng ở cặp đầu tiên có một phần tử chung?
Chọn một đáp án

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?
Chọn một đáp án

Đang học