BẢNG BĂM Bùi Tiến Lên 01/01/2017 LÝ THUYẾT ĐỒNG DƯ Các khái niệm Định nghĩa 1 Cho số nguyên dương n ∈ N, hai số nguyên a, b ∈ Z được gọi là đồng dư theo mô đun n nếu cả hai có cùng số dư khi chia cho[.]
BẢNG BĂM Bùi Tiến Lên 01/01/2017 LÝ THUYẾT ĐỒNG DƯ Các khái niệm Định nghĩa Cho số nguyên dương n ∈ N, hai số nguyên a, b ∈ Z gọi đồng dư theo mô-đun n hai có số dư chia cho n Được ký hiệu a ≡ b (modn) Ví dụ Ta có I 11 ≡ (mod3) (vì 11 chia cho có số dư 2) I −2 ≡ (mod7) (vì -2 chia cho có số dư 5) Spring 2017 Data structure & Algorithm Một số tính chất Tính chất Quan hệ đồng dư quan hệ tương đương I Tính phản xạ I Tính đối xứng a ≡ a (modn) a ≡ b (modn) ⇒ b ≡ a (modn) I Tính bắc cầu a ≡ b (modn) b ≡ c (modn) ⇒ a ≡ c (modn) Spring 2017 Data structure & Algorithm Một số tính chất (cont.) Tính chất Nếu a1 ≡ b1 (modn) a2 ≡ b2 (modn) Thì I a1 + a2 ≡ b1 + b2 (modn) I a1 − a2 ≡ b1 − b2 (modn) I a1 a2 ≡ b1 b2 (modn) I a1k ≡ b1k (modn) Spring 2017 Data structure & Algorithm Áp dụng Ví dụ Tìm phần dư phép chia 332 cho 17 Lời giải tính trực tiếp I Ta có 332 = 1853020188851841 I Và 1853020188851841 mod 17 = I Vậy, phần dư phép chia 332 cho 17 Spring 2017 Data structure & Algorithm Áp dụng (cont.) Lời giải đồng dư Ta có 32 22 22 ≡3 ≡ 92 (mod17) 22 (mod17) 22 22 ≡ 812 (mod17) ≡ 152 (mod17) 2 ≡ 2252 (mod17) ≡ 42 (mod17) ≡ 162 (mod17) ≡ 256 (mod17) ≡ (mod17) Spring 2017 Data structure & Algorithm Áp dụng (cont.) Ví dụ Tìm hai chữ số cuối số 716 Lời giải Hai chữ số cuối phần dư phép chia 716 cho 100 Ta có 16 ≡7 22 22 22 ≡ 49 (mod100) (mod100) 2 ≡ 24012 (mod100) ≡ 12 (mod100) ≡ (mod100) Vậy, hai chữ số cuối 01 Spring 2017 Data structure & Algorithm BẢNG BĂM Giới thiệu I I I Các thao tác tìm kiếm cấu trúc liệu danh sách, nhị phân, thường dựa việc so sánh khóa phần tử cấu trúc liệu Do đó, thời gian thao tác phụ thuộc vào kích thước liệu Bảng băm cấu trúc liệu giảm chi phí đến O(1) (khơng phụ thuộc vào kích thước liệu) Nội dung tham khảo từ http://www.giaithuatlaptrinh.com/ Spring 2017 Data structure & Algorithm 10 ... thao tác tìm kiếm cấu trúc liệu danh sách, nhị phân, thường dựa việc so sánh khóa phần tử cấu trúc liệu Do đó, thời gian thao tác phụ thuộc vào kích thước liệu Bảng băm cấu trúc liệu giảm chi phí... phụ thuộc vào kích thước liệu) Nội dung tham khảo từ http://www.giaithuatlaptrinh.com/ Spring 2017 Data structure & Algorithm 10 Các định nghĩa Định nghĩa Bảng băm (hash table) cấu trúc liệu chứa... 17 Lời giải tính trực tiếp I Ta có 332 = 1853020188851841 I Và 1853020188851841 mod 17 = I Vậy, phần dư phép chia 332 cho 17 Spring 2017 Data structure & Algorithm Áp dụng (cont.) Lời giải đồng