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ẢNG BĂM Bùi Tiến Lên 01 01 2017 https tailieudientucntt LÝ THUYẾT ĐỒNG DƯ https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 amp Algorithm https tailieudientucntt 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 chữ số cuối cùng chính là phần dư của phép chia 716 cho 100. Ta có 22 16 22 7 7 mod100 2 22 49 mod100 2 2 24012 mod100 12 mod100 1 mod100 Vậy hai chữ số cuối cùng là 01 Spring 2017 Data structure amp Algorithm https tailieudientucntt 8 BẢNG BĂM https tailieudientucntt Giới thiệu I Các thao tác tìm kiếm trên các cấu
