Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm cung cấp cho người học các kiến thức: Khái niệm các lý thuyết đồng dư, áp dụng lý thuyết đồng dư, bảng băm, chuyển kiểu cho khóa, các loại hàm băm | Bài giảng Cấu trúc dữ liệu và giải thuật: Bảng băm - Bùi Tiến Lên 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 n. Được ký hiệu a ≡ b (modn) Ví dụ 1 Ta có I 11 ≡ 8 (mod3) (vì 11 và 8 chia cho 3 đều có số dư là 2) I −2 ≡ 5 (mod7) (vì -2 và 5 chia cho 7 đều có số dư là 5) Spring 2017 Data structure & Algorithm 3 Một số tính chất Tính chất Quan hệ đồng dư là một quan hệ tương đương I Tính phản xạ a ≡ a (modn) I Tính đối xứng a ≡ b (modn) ⇒ b ≡ a (modn) I Tính bắc cầu a ≡ b (modn) và b ≡ c (modn) ⇒ a ≡ c (modn) Spring 2017 Data structure & Algorithm 4 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 5 Áp dụng Ví dụ 2 Tìm phần dư của 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 = 1 I Vậy, phần dư của phép chia 332 cho 17 là 1 Spring 2017 Data structure & Algorithm 6 Áp dụng (cont.) Lời giải đồng dư Ta có 2 22 32 22 3 ≡3 (mod17) 2 22 ≡ 92 (mod17) 22 22 ≡ 812 (mod17) ≡ 152 (mod17) 2 2 ≡ 2252 (mod17) ≡ 42 (mod17) ≡ 162 (mod17) ≡ 256 (mod17) ≡ 1 (mod17) Spring 2017 Data structure & Algorithm 7 Áp dụng (cont.) Ví dụ 3 Tìm hai chữ số cuối cùng của số 716 Lời giải Hai
