🔙 Quay lại trang tải sách pdf ebook Thuật Toán Và Lập Trình Ebooks Nhóm Zalo NGUYỄN HỮU ĐIỂN THUẬT TOÁN VÀ LẬP TRÌNH NHÀ XUẤT BẢN ĐẠI HỌC QUỐC GIA HÀ NỘI LỜI NÓI ĐẦU Những năm trước khi lập trình VieTeX tôi toàn dùng C/C++ thu thập tài liệu nhiều nhưng không có thời gian để viết lại. Nay muốn viết lại thì sức khỏe không ổn định. Tôi đã cố gắng gom lại thành các tập lập trình theo chủ đề. Nội dung mỗi thuật toán bắt đầu từ lý thuyết đến lập trình bằng C/C++. Cuốn sách viết ra không dành riêng cho các bạn học tin học, mà các bạ học toán, thầy cô giáo, các bạn thích tìm hiểu về thuật toán. Cũng như tôi bắt đầu có biết gì về lập trình đâu, tự học và chăm chỉ là thành công thôi. Tôi dùng trình biên dịch Dev-C++: https://www.bloodshed.net/ Hiện nay Dev-C++ cải tiến rất nhiều và chạy tốt với môi trường uni code. Những ví dụ trong tài liệu các bạn chép thẳng vào soạn thảo và biên dịch không cần cấu hình trình biên dịch. Tôi đã làm các quyển sách: 1. Thuật toán và số học. 2. Thuật toán và dữ liệu. 3. Thuật toán xắp xếp 4. Thuật toán tìm kiếm 5. Thuật toán đồ thị, 6. Thuật toán quay lui 7. Thuật toán chia để trị 8. Thuật toán động 9. Thuật toán tham 10. Thuật toán nén 11. Một số đề thi Olympic Tin học. Cuốn sách dành cho học sinh phổ thông yêu toán, học sinh khá giỏi môn toán, các thầy cô giáo, sinh viên đại học ngành toán, ngành tin học và những người yêu thích Toán - Tin. Trong biên soạn không thể tránh khỏi sai sót và nhầm lẫn mong bạn đọc cho ý kiến. Hà Nội, ngày 25 tháng 2 năm 2022 Nguyễn Hữu Điển NHỮNG KÝ HIỆU Trong cuốn sách này ta dùng những kí hiệu với các ý nghĩa xác định trong bảng dưới đây: N tập hợp số tự nhiên N∗tập hợp số tự nhiên khác 0 Z tập hợp số nguyên Q tập hợp số hữu tỉ R tập hợp số thực C tập hợp số phức ≡ dấu đồng dư ∞ dương vô cùng (tương đương với +∞) −∞ âm vô cùng ∅ tập hợp rỗng Ckm tổ hợp chập k của m phần tử ... phép chia hết 6... không chia hết UCLN ước số chung lớn nhất BCNN bội số chung nhỏ nhất deg bậc của đa thức IMO International Mathematics Olympiad APMO Asian Pacific Mathematics Olympiad iv NỘI DUNG Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Những kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Danh sách hình. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii Danh sách bảng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix Chương 1. Số học và thuật toán. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Khái niệm toán học và thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1. Tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2. Tập hợp số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3. Phép chia hết và chia có dư. . . . . . . . . . . . . . . . . . . . . . . . . 11 1.1.4. Tính tổng và tích . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.1.5. Tính lũy thừa, logarit và căn. . . . . . . . . . . . . . . . . . . . . . . . 16 1.1.6. Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.1.7. Giai thừa và hồi qui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.1.8. Ma trận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.1.9. Tìm số chữ số của một tích . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.2. Số nguyên tố . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.2.1. Kiểm tra một số có phải là số nguyên tố . . . . . . . . . . . . 26 1.2.2. Sàng Eratosten. Tìm số nguyên tố trong khoảng . . . . 28 1.2.3. Phân tích một số thành tích thừa số nguyên tố . . . . . . 33 1.2.4. Tìm số lượng số không trong kết quả phép nhân. . . . 34 1.3. Số mensen và số hoàn thiện . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.3.1. Số mensen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.3.2. Số hoàn thiện . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.4. Những hệ số đa thức, tam giác Pascal và giai thừa . . . . . . 42 1.5. Hệ số đếm và sự biến đổi hệ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 1.5.1. Chuyển hệ cơ số 10 sang cơ số p . . . . . . . . . . . . . . . . . . . . 50 1.5.2. Chuyển hệ cơ số p vào cơ số 10. Sơ đồ Horner . . . . . . 53 v 1.6. Chữ số la mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1.6.1. Biểu diễn số thập phân thành chữ số La mã. . . . . . . . . 56 1.6.2. Chuyển đổi chữ số La Mã sang số thập phân . . . . . . . 58 1.7. Hồi quy và lặp lại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 1.7.1. Tính giai thừa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 1.7.2. Dãy Phibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 1.7.3. Ước số chung lớn nhất và thuật toán Euclid. . . . . . . . . 69 1.7.4. Bội số chung nhỏ nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 1.7.5. Trả lại giá trị từ đệ quy và dùng biến . . . . . . . . . . . . . . . 74 1.8. Thuật toán đếm cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 1.8.1. Hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 1.8.2. Mã hóa và giải mã. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 1.8.3. Hoán vị lặp lại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 1.9. Chỉnh hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 1.9.1. Các dạng chỉnh hợp và cách sinh ra. . . . . . . . . . . . . . . . . 88 1.10. Tổng bằng không . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 1.11. Tổ hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 1.12. Biểu diễn số thành tổng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 1.12.1. Tạo ngắt số dưới dạng tổng của các số đã cho. . . . . . 97 1.12.2. Sinh ra tất cả biểu diễn một số như là tích của các số tự nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 1.12.3. Sinh ra tất cả biểu diễn một số như là tổng của các số tự nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 1.12.4. Phân hoạch một tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . 103 1.13. Đánh giá và độ phức tạp của thuật toán . . . . . . . . . . . . . . 105 1.13.1. Lượng dữ liệu đầu vào . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 1.13.2. Ký hiệu tiệm cận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 1.13.3. Tính chất và ví dụ của O(F). . . . . . . . . . . . . . . . . . . . . . 111 1.13.4. Tính chất và ví dụ về Θ . . . . . . . . . . . . . . . . . . . . . . . . . . 113 1.13.5. Hàm tiệm cận và số thực . . . . . . . . . . . . . . . . . . . . . . . . . 116 1.13.6. Xác định độ phức tạp của một thuật toán. . . . . . . . . 117 1.14. Phương trình đặc trưng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 1.14.1. Phương trình thuần nhất tuyến tính với nghiệm đơn giản 127 1.14.2. Phương trình thuần nhất tuyến tính với nhiều nghiệm . 129 1.14.3. Phương trình tuyến tính không thuần nhất . . . . . . . 131 1.15. Các kỹ thuật đặc biệt để phân tích thuật toán. . . . . . . . . 135 1.15.1. Sử dụng phong vũ biểu . . . . . . . . . . . . . . . . . . . . . . . . . . 135 1.15.2. Phân tích khấu hao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 1.15.3. Định lý cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 1.15.4. Các vấn đề về ký hiệu tiệm cận. . . . . . . . . . . . . . . . . . . 139 1.16. Các câu hỏi và bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 1.16.1. Các bài toán về số, chuỗi, hàm . . . . . . . . . . . . . . . . . . . 140 1.16.2. Bài toán ma trận và bài toán chung . . . . . . . . . . . . . . . 146 1.16.3. Bài toán tổ hợp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148 Chương 2. Cấu trúc dữ liệu và thuật toán . . . . . . . . . . . . . . . . . . 153 2.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 2.2. Danh sách, ngăn xếp và hàng đợi. . . . . . . . . . . . . . . . . . . . . . 157 2.2.1. Danh sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 2.2.2. Ngăn xếp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 2.2.3. Hàng đợi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 2.2.4. Hàng đợi hai đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 2.3. Thực hiện cụ thể cấu trúc trên . . . . . . . . . . . . . . . . . . . . . . . . . 161 2.3.1. Danh sách . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 2.3.2. Ngăn xếp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162 2.3.3. Hàng đợi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 2.4. Thể hiện cấu trúc động. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 2.4.1. Đưa vào một phần tử . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 2.4.2. Cuộn qua một danh sách . . . . . . . . . . . . . . . . . . . . . . . . . . 169 2.4.3. Đưa vào sau một phần tử được chỉ định bởi một chỉ dẫn đã cho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 2.4.4. Đưa vào phía trước một phần tử được chỉ định bởi một thư mục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 2.4.5. Xóa theo khóa mặc định và con trỏ lên đầu danh sách . . . 172 2.4.6. Xóa một phần tử được chỉ định bởi một thư mục . . 173 2.5. Cây nhị phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 2.5.1. Tìm kiếm bằng chìa khóa. . . . . . . . . . . . . . . . . . . . . . . . . . 183 2.5.2. Thêm vào một đỉnh mới. . . . . . . . . . . . . . . . . . . . . . . . . . . 184 2.5.3. Xóa một đỉnh bằng từ khóa đã cho . . . . . . . . . . . . . . . . 184 2.5.4. Thu thập thông tin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 2.5.5. Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 2.6. Cây cân đối . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192 2.6.1. Vòng xoay. Cây đỏ và đen . . . . . . . . . . . . . . . . . . . . . . . . . 196 2.6.2. B-Cây . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198 2.7. Bảng băm (H-bảng) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 2.7.1. Hàm băm (H-hàm số) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202 2.7.2. Sự xung đột. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 2.7.3. Hàm băm cổ điển . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 2.7.4. Đối phó với xung đột. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 2.7.5. Triển khai bảng băm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 2.8. Câu hỏi và bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 2.26 Cây Fibonacci của hàng 3. . . . . . . . . . . . . . . . . . . 194 2.27 Cây Fibonacci của hàng 4. . . . . . . . . . . . . . . . . . . 194 2.28 Cây Fibonacci của hàng 5. . . . . . . . . . . . . . . . . . . 195 2.29 Xoay phải (A), trái (B), xoay trái-phải (C) và xoay phải-trái (D) quay. . . . . . . . . . . . . . . . . . . . . . . . 197 2.30 Ví dụ về cây đỏ-đen. . . . . . . . . . . . . . . . . . . . . . 198 2.31 2-3-4 cây. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 2.32 B-cây hàng 5. . . . . . . . . . . . . . . . . . . . . . . . . . . 200 2.33 Hàm băm khớp với địa chỉ của từng khóa trong bảng băm.203 2.34 χ2so sánh các hàm băm trên PIN, n = 1031, m = 1031000. 207 2.35 Bao gồm tuần tự của một phần tử. Cho phép xung đột với thử nghiệm tuyến tính với bước 1. . . . . . . . . . 215 2.36 Giải quyết xung đột bằng cách phân bổ bộ nhớ bổ sung. . 216 2.37 Kết nối động: bảng băm, sau khi bao gồm các phần tử 234, 235, 567, 123, 534, 647. . . . . . . . . . . . . . . . . 217 Chương 3. Sắp xếp dữ liệu và thuật toán . . . . . . . . . . . . . . . . . . 231 3.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 3.2. Sắp xếp theo so sánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 3.2.1. Cây so sánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 3.2.2. Sắp xếp theo cách chèn . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236 3.2.3. Sắp xếp theo thứ tự chèn với bước giảm dần. Thuật toán của Shell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 3.2.4. Phương pháp bong bóng . . . . . . . . . . . . . . . . . . . . . . . . . . 243 3.2.5. Sắp xếp bằng cách lắc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 3.2.6. Nhanh chóng phân loại Hoor . . . . . . . . . . . . . . . . . . . . . 246 3.2.7. Phương pháp Thỏ và Rùa . . . . . . . . . . . . . . . . . . . . . . . . . 256 3.2.8. Sắp xếp theo lựa chọn trực tiếp. . . . . . . . . . . . . . . . . . . . 259 3.2.9. Sắp xếp kim tự tháp Williams . . . . . . . . . . . . . . . . . . . . . 260 3.2.10. Độ phức tạp về thời gian tối thiểu của việc sắp xếp theo cách so sánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266 3.2.11. Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 3.3. Sắp xếp theo sự biến đổi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 3.3.1. Sắp xếp theo tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268 3.3.2. Sắp xếp theo số đếm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 3.3.3. Sắp xếp theo bit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 3.3.4. Phương pháp hệ đếm số . . . . . . . . . . . . . . . . . . . . . . . . . . 282 3.3.5. Sắp xếp theo hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 3.4. Sắp xếp song song . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 3.4.1. Nguyên tắc về số không và số một. . . . . . . . . . . . . . . . . 292 3.4.2. Trình tự bitonic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294 3.4.3. "Rõ ràng một nửa" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 3.4.4. Sắp xếp chuỗi bitonic. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295 3.4.5. Sắp xếp sơ đồ hợp nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 3.4.6. Sắp xếp sơ đồ phân loại . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 3.4.7. Sơ đồ phân loại chuyển vị . . . . . . . . . . . . . . . . . . . . . . . . . 297 3.4.8. Sơ đồ sáp nhập Betcher chẵn lẻ . . . . . . . . . . . . . . . . . . . . 298 3.4.9. Lược đồ sắp xếp chẵn-lẻ . . . . . . . . . . . . . . . . . . . . . . . . . . . 298 3.4.10. Lược đồ hoán vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 3.5. Câu hỏi và bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 Chương 4. Tìm kiếm và thuật toán . . . . . . . . . . . . . . . . . . . . . . . . 303 4.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 4.2. Tìm kiếm liên tiếp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306 4.2.1. Tìm kiếm liên tiếp trong danh sách đã sắp xếp. . . . . 309 4.2.2. Tìm kiếm liên tục với sự sắp xếp lại. . . . . . . . . . . . . . . . 311 4.3. Tìm kiếm theo từng bước. Tìm kiếm bậc hai . . . . . . . . . . . 313 4.4. Tìm kiếm nhị phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 4.5. Tìm kiếm Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 4.6. Tìm kiếm nội suy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 4.7. Câu hỏi và bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 Chương 5. Lý thuyết đồ thị và thuật toán. . . . . . . . . . . . . . . . . . . 330 5.1. Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 5.2. Trình bày và các thao tác đơn giản với đồ thị. . . . . . . . . . . 338 5.2.1. Danh sách các cạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338 5.2.2. Ma trận lân cận, ma trận trọng số. . . . . . . . . . . . . . . . . . 339 5.2.3. Danh sách những cạnh kề . . . . . . . . . . . . . . . . . . . . . . . . . 340 5.2.4. Ma trận tỷ lệ giữa các đỉnh và cạnh . . . . . . . . . . . . . . . . 341 5.2.5. Các thành phần kết nối. . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 5.2.6. Xây dựng và các hoạt động đơn giản với đồ thị . . . . 342 5.3. Trình duyệt trên đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 5.3.1. Duyệt theo chiều rộng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 5.3.2. Duyệt theo chiều sâu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 5.4. Đường dẫn, chu trình và dòng chảy tối ưu trong đồ thị 353 5.4.1. Các ứng dụng trực tiếp của thuật toán duyệt . . . . . . 354 5.4.2. Đường tối ưu trong đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 363 - Bất đẳng thức của tam giác . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 - Thuật toán Ford-Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 - Thuật toán của Floyd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367 - Thuật toán tổng quát của Floyd . . . . . . . . . . . . . . . . . . . . . . . . 371 - Thuật toán Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 - Lũy thừa ma trận của phần tử lân cận . . . . . . . . . . . . . . . . . 379 - Thuật toán Warshal và ma trận khả năng tiếp cận . . . . . . 380 - đường đi dài nhất trong thị chu trình . . . . . . . . . . . . . . . . . . 381 v - Đường đơn dài nhất giữa hai đỉnh trong bất kỳ đồ thị nào . . . 386 5.4.3. Chu trình . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 - tìm kiếm một tập hợp các chu trình cơ bản . . . . . . . . . . . . . 386 - chu trình tối thiểu qua đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 5.4.4. Các chu trình Hamilton. Bài toán đường thương mại . . . . 391 5.4.5. Chu trình Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 5.4.6. Luồng trong đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400 - Lưu lượng luồng cực đại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 - Nhiều nguồn và người tiêu dùng . . . . . . . . . . . . . . . . . . . . . . 408 - Công suất của các đỉnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 Chương 5. Lý thuyết đồ thị và thuật toán. . . . . . . . . . . . . . . . . . . 410 5.5. Tính bắc cầu và cách xây dựng. Sắp xếp cấu trúc liên kết . . . . 411 5.5.1. Đóng bắc cầu. Thuật toán Worschal . . . . . . . . . . . . . . . 411 5.5.2. Định hướng bắc cầu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 5.5.3. Giảm bắc cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418 5.5.4. Kiểm soát công ty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420 5.5.5. Bài tập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422 5.5.6. Sắp xếp theo cấu trúc liên kết . . . . . . . . . . . . . . . . . . . . . 422 5.5.7. Sắp xếp tô pô đầy đủ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 5.5.8. Bổ sung một đồ thị xoay chiều thành một đồ thị được liên kết yếu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430 5.5.9. Xây dựng đồ thị của các đỉnh đã cho . . . . . . . . . . . . . . 431 5.6. Khả năng tiếp cận và liên thông . . . . . . . . . . . . . . . . . . . . . . . 432 5.6.1. Các thành phần liên thông . . . . . . . . . . . . . . . . . . . . . . . . 433 5.6.2. Các thành phần liên kết mạnh trong đồ thị định hướng . 435 5.6.3. Điểm phân chia trong một đồ thị không định hướng . . . . 439 5.6.4. k−liên thông của đồ thị không định hướng . . . . . . . . 443 5.7. Các tập hợp con tối ưu và các tâm của đồ thị . . . . . . . . . . 444 5.7.1. Cây bao phủ tối thiểu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 - Thuật toán Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445 - Thuật toán của Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451 - Cây bao phủ tối thiểu một phần . . . . . . . . . . . . . . . . . . . . . . . 454 v 5.7.2. Tập đỉnh độc lập . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455 - Tập hợp độc lập tối đa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456 5.7.3. Tập đỉnh trội . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 5.7.4. Tập cơ sở. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 5.7.5. Tâm, bán kính và đường kính . . . . . . . . . . . . . . . . . . . . . 466 - p-tâm và p-bán kính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 5.7.6. Kết hợp cặp. Kết hợp cặp tối đa. . . . . . . . . . . . . . . . . . . . 475 5.8. Tô màu và đồ thị phẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 5.8.1. Tô màu đồ thị và sắc số. . . . . . . . . . . . . . . . . . . . . . . . . . . . 477 - Giới hạn dưới cùng của số sắc . . . . . . . . . . . . . . . . . . . . . . . . . 478 - Tìm sắc số đỉnh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478 5.8.2. Đồ thị phẳng. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 5.9. Câu hỏi và bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 Chương 6. Thuật toán quay lui. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488 6.1. Phân loại bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 6.1.1. Phức tạp về thời gian. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 6.1.2. Độ phức tạp tính toán theo bộ nhớ . . . . . . . . . . . . . . . . 490 6.1.3. Bài toán không thể giải được . . . . . . . . . . . . . . . . . . . . . . 490 6.1.4. Các ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490 6.2. Bài toán NP-đầy đủ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495 6.3. Tìm kiếm với quay lui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 6.3.1. Sự thỏa mãn của một hàm Boolean . . . . . . . . . . . . . . . . 500 6.3.2. Tô màu đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507 6.3.3. Đường đi đơn dài nhất trong đồ thị chu trình. . . . . . 511 6.3.4. Đường đi quân ngựa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 6.3.5. Bài toán tám quân Hậu. . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 6.3.6. Thời khóa biểu của trường học . . . . . . . . . . . . . . . . . . . . 524 6.3.7. Dịch mật mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 529 6.4. Phương pháp nhánh và ranh giới. . . . . . . . . . . . . . . . . . . . . . 534 6.4.1. Bài toán ba lô (lựa chọn tối ưu) . . . . . . . . . . . . . . . . . . . . 535 6.5. Các chiến lược tối ưu cho trò chơi . . . . . . . . . . . . . . . . . . . . . 539 6.5.1. Trò chơi "X" và "O" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541 6.5.2. Nguyên tắc minimum và maximum . . . . . . . . . . . . . . . 546 6.5.3. Nhát cắt alpha-beta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548 6.5.4. Duyệt alpha-beta đến một độ sâu nhất định . . . . . . . 551 6.6. Câu hỏi và bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553 Chương 7. Thuật toán chia để trị . . . . . . . . . . . . . . . . . . . . . . . . . . . 560 7.1. Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560 7.2. Tìm phần tử lớn nhất thứ k . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561 7.3. Phần tử trội . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572 7.4. Hợp nhất các mảng đã sắp xếp . . . . . . . . . . . . . . . . . . . . . . . . 590 7.5. Sắp xếp theo hợp nhất. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597 7.6. Nâng nhanh lũy thừa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607 7.7. Thuật toán Strassen để nhân nhanh các ma trận . . . . . . . 610 7.8. Nhân nhanh các số dài . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616 7.9. Bài toán tháp Hà Nội. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 620 7.10. Tổ chức giải vô địch bóng đá . . . . . . . . . . . . . . . . . . . . . . . . . 624 7.11. Sự dịch chuyển tuần hoàn của các phần tử mảng . . . . . 631 7.12. Câu hỏi và bài tập. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636 1.1. Khái niệm toán học và thuật toán 5 1.1. Khái niệm toán học và thuật toán Tài liệu trong đoạn này nhằm mục đích giúp người đọc làm quen với các ký hiệu, thuật ngữ, khái niệm và các tính chất cơ bản của một số đối tượng toán học được sử dụng trong cuốn sách. Khuyến nghị của chúng ta, ngay cả đối với những người đã có nhiều kinh nghiệm với các thuật toán máy tính, là hãy đọc kỹ chương giới thiệu này để những điều chưa giải thích được từ nó càng ít càng tốt. Đây là điều kiện cần để có thể hiểu đầy đủ hơn về tài liệu. Tất nhiên, không nhất thiết phải nhớ tất cả các thuật ngữ và định nghĩa. Chỉ cho thấy một chút “hiểu biết nhỏ” về ngôn ngữ chặt chẽ và trừu tượng của toán học. 1.1.1. Tập hợp Khái niệm tập hợp là chính và không được định nghĩa chặt chẽ bởi các khái niệm toán học khác. Nó được nhận thức một cách trực quan và thường được làm rõ qua các ví dụ. Giả thiết rằng một tập hợp được đưa ra khi một hệ thống (tập hợp) các đối tượng được đưa ra, hầu hết thường được thống nhất trên cơ sở một số đặc điểm, thuộc tính chung hoặc một số quy tắc nào đó. Ví dụ, những con ong tạo thành một tập hợp trong một tổ ong, các đỉnh của một đa giác, các đường thẳng đi qua một điểm cho trước, nghiệm nguyên của phương trình ax2 + bx + c = 0, v.v. Các chữ cái viết hoa của bảng chữ cái Latinh thường được sử dụng làm ký hiệu cho một tập hợp: A, B, C, .... Các đối tượng tham gia vào một tập hợp được gọi là các phần tử của tập hợp và thường được đánh dấu bằng các chữ cái Latinh viết thường (hoặc bằng cách đánh chỉ mục thích hợp). Chúng ta sẽ tránh định nghĩa chặt chẽ về tập chỉ mục là gì, nhưng thường đối với các phần tử của tập A, chúng ta sẽ sử dụng chuỗi được lập chỉ mục a1, a2, ..., an và chúng ta sẽ biểu thị nó theo cách này: A = {a1, a2, ..., an} Thực tế là phần tử ai, i = 1, 2, ..., n, thuộc tập A được ký hiệu là ai ∈ A và phần tử không thuộc - bởi ai 6∈ A. Số phần tử của một tập hợp được gọi là lũy thừa của tập hợp (đối với tập A ở trên số này bằng n), và đôi khi chúng ta sẽ sử dụng |A| để biểu thị lũy thừa. Với n = 0, tập được gọi là rỗng và được ký hiệu là ∅. Thông thường, Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 6 Chương 1. Số học và thuật toán các tập hợp được biểu diễn bằng biểu đồ Venn (xem Hình 1.1.): Mỗi tập hợp A được biểu diễn dưới dạng một vùng đóng và các phần tử (a, b, ...) - là các điểm nằm trong, hoặc bên ngoài nó, tùy thuộc vào việc chúng có thuộc bộ hay không. Hình 1.1. Sơ đồ Cen Có nhiều khái niệm, tính chất và phép toán thống nhất trong một lý thuyết tập hợp được xây dựng tốt [Dilova, Stoyanov-1973]. Chúng ta sẽ đề cập ngắn gọn thêm một số trong số đó, sẽ cần trong tài liệu sau. Định nghĩa 1.1. Nếu tất cả các phần tử của một tập hợp A đã cho là phần tử của một tập hợp B khác, thì A được gọi là một tập hợp con của B. Điều này được ký hiệu là A ⊆ B (xem Hình 1.2.). Khi biết thêm rằng B không trùng với A thì tập A được gọi là tập con thích hợp (thực) của B. Trong trường hợp này chúng ta sẽ sử dụng kí hiệu A ⊂ B. Hình 1.2. Tập hợp con (a), tập hợp hợp (b), tập giao (c) và tập hiệu (d) của các tập hợp. Định nghĩa 1.2. Tập hợp C được gọi là hợp của tập A và B nếu nó bao gồm tất cả các phần tử a sao cho a ∈ A hoặc a ∈ B. Viết C = A ∪ B. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 7 Định nghĩa 1.3. Giao C = A ∩ B của hai tập hợp A và B được gọi là tập hợp C, gồm tất cả các phần tử đồng thời thuộc A và B. Định nghĩa 1.4. Hiệu C = A \ B của tập A và B được gọi là tập C, gồm tất cả các phần tử thuộc A nhưng không thuộc B. Định nghĩa 1.5. Một tập hợp được gọi là hữu hạn nếu nó chứa một số hữu hạn phần tử. Nếu không nó được gọi là vô hạn. Trước khi chúng ta tiếp tục, đây là một vài định nghĩa quan trọng hơn. Khi xem xét một tập hợp, không quan trọng số lần một phần tử xuất hiện, cũng như thứ tự của các phần tử của nó. Do đó các tập hợp sau là tương đương (trùng nhau): {a, a, b} = {a, b, b} = {a, b, a} = {a, b} = {b, a} Định nghĩa 1.6. Một tập hợp trong đó sự lặp lại của các phần tử được cho phép được gọi là đa tập hợp . Định nghĩa 1.7. Nếu một thứ tự của các phần tử được nhập vào một tập hợp n phần tử, thì đối tượng kết quả được gọi là một n-bộ có thứ tự (danh sách). Chúng ta sẽ sử dụng dấu ngoặc tròn thay vì dấu ngoặc nhọn để biểu thị n-bộ có thứ tự. Ví dụ, ba thứ tự (a, b, c) khác với ba thứ tự (a, c, b), v.v. Bài tập . 1.1. Các tập hợp A = {1, 2, 4, 5, 7} và B = {2, 3, 4, 5, 6} được đưa ra. Xác định các tập hợp: A ∪ B, A ∩ B, A \ B, B \ A. . 1.2. Hai tập hợp A và B đã cho và biết rằng A ∩ B = A. Bạn có thể nói gì về tập hợp B? . 1.3. Toán tử hiệu đối xứng ⊕ của A và B được xác định như sau: A ⊕ B = (A ∪ B) \ (A ∩ B). Xác định hiệu đối xứng của các tập A = {1, 2, 4, 5, 7} và B = {2, 3, 4, 5, 6}. . 1.4. Một phép toán • được gọi là đối xứng nếu A • B = B • A. Phép toán nào sau đây là đối xứng: A ∪ B, A ∩ B, A \ B, B \ A, A ⊕ B? Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 8 Chương 1. Số học và thuật toán 1.1.2. Tập hợp số Các con số là cơ sở cho tất cả các loại tính toán toán học, cũng như các thuật toán là cơ sở của tin học máy tính. Theo trình tự thời gian (ban đầu chỉ có 3 "số" được dùng để đếm: một, hai và nhiều), chúng được coi là hình thức đầu tiên của tư duy trừu tượng và nhiều người coi chúng như một thứ gì đó kỳ diệu và đặc biệt. Các con số có liên quan đến hầu hết mọi thuật toán và chương trình. Đó là lý do tại sao các vấn đề liên quan đến việc trình bày, lưu trữ và sử dụng máy tính của họ là vô cùng quan trọng. Định nghĩa 1.8. Tập hợp các số tự nhiên (chúng ta sẽ ký hiệu là N) chứa các số mà chúng ta đếm được: 0, 1, 2, 3, .... Có tranh cãi về việc số 0 có nên được coi là một số tự nhiên hay không. Nó trừu tượng hơn các số tự nhiên khác và bị thiếu trong nhiều hệ thống số cũ: ví dụ, trong hệ thống số La Mã, việc biểu diễn các số bắt đầu bằng một. Mặt khác, trong toán học rời rạc, việc giới thiệu N thường được thực hiện từ đầu. Điều này là do khi làm việc với các tập hợp n phần tử, thường phải đưa tập hợp rỗng vào định nghĩa. Định nghĩa 1.9. Định nghĩa 1.9. Tập hợp các số nguyên Z bao gồm: ..., −3, −2, −1 (số nguyên âm), 0 (số không), 1, 2, 3, ... (số nguyên dương). Trong bộ nhớ máy tính, chúng được biểu diễn dưới dạng một chuỗi các bit - mã chuyển tiếp, mã ngược hoặc mã bổ sung [Shishkov-1995]. Ngày nay, mã bổ sung thường được sử dụng nhiều nhất, vì nó dễ dàng thu gọn vào phép cộng, thuận tiện cho việc thực hiện trên máy tính. Các trình biên dịch khác nhau của các loại C và phạm vi định nghĩa của chúng có thể khác nhau. ANSIC (American National Standards Institute [ANSIC]) không xác định các phạm vi cụ thể (Bảng 1.1 làm ví dụ cho thấy các phạm vi cho Borland C cho DOS), mà chỉ xác định các mối quan hệ, ví dụ: |short|≤|int| ≤ |long| Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 9 Theo mặc định, kích thước của int là một từ máy (điều này giải thích tại sao loại DOS là 2 byte và loại Windows là 4). Một cách chuẩn để nhận giá trị lớn nhất của một loại, chẳng hạn như unsigned, là dựa trên biểu diễn bên trong của các số trong mã bổ sung: (unsigned)(-1) Loại Giá trị Kích thước char −128, . . . , 127 8 bit có dấu unsigned char 0, . . . , 255 8 bit không dấu short int −32768, . . . , 32767 16 bit có dấu int −32768, . . . , 32767 16 bit có dấu long int −2147483648, . . . , 2147483647 32 bit có dấu unsigned short int 0, . . . , 65535 16 bit không dấu unsigned long int 0, . . . , 4294967295 32 bit không dấu Bảng 1.1. Các kiểu số nguyên trong Borland C dành cho DOS. Ở cột giữa của Bảng 1.1. phạm vi giá trị có thể chấp nhận một biến của kiểu tương ứng được đưa ra. Mỗi kiểu được đặc trưng bởi một số nguyên tối đa và tối thiểu mà nó có thể lưu trữ. Bất kỳ phép gán nào vượt quá giá trị tối đa (hoặc tối thiểu) của kiểu được gọi là tràn và có thể dẫn đến kết quả thảm hại cho từng thuật toán và chương trình. Định nghĩa 1.10. Số hữu tỉ là những số thuộc loại pq, trong đó p và q là các số nguyên và q là số dương. Tập hợp các số hữu tỉ được kí hiệu là Q. Định nghĩa 1.11. Số thực là những số có thể viết dưới dạng: x = n + 0, d1d2d3 . . . , với n là một số nguyên và dilà các chữ số thập phân từ 0 đến 9. Các số 0, d1d2d3 . . . được gọi là số thập phân. Trình bày ở dạng trên có nghĩa là bất đẳng thức 10 +d2 100 + · · · +dk 10k≤ x ≤ n +d1 10 +d2 100 + · · · +dk n +d1 10k+110k Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 10 Chương 1. Số học và thuật toán với mọi k ∈ N, k ≥ 0. Lưu ý rằng dãy chữ số di có thể là vô hạn. Điều này có thể xảy ra đối với cả số hữu tỉ và số vô tỉ (tức là số không hữu tỉ). Ví dụ, số 1/3 = 0, 333333..... Ở đây số 3 được lặp lại vô hạn và được gọi là chu kỳ của phân số. Viết thêm 1/3 = 0,(3) và đọc "không nguyên và ba trong khoảng thời gian". Dấu chấm có thể dài hơn một chữ số, ví dụ 1/7 = 0,(142857). Ví dụ về một số thực vô tỷ và không tuần hoàn, tức là không được biểu diễn chính xác dưới dạng p/q(p, q ∈ N, q > 0), là tỷ số giữa chu vi hình tròn với đường kính của nó - hằng số π: π = 3, 141592653 . . . . Giống như bất kỳ số thực nào, π có thể được tính gần đúng bằng một số hữu tỉ - ví dụ 355/113, sẽ xác định nó với độ chính xác sau dấu thập phân, nhưng sau một số chữ số nhất định (đối với ví dụ đã chọn, nó là 6 chữ số sau dấu dấu thập phân) độ chính xác này bị mất. Một giá trị gần đúng hữu ích khác là 22/7. Trong bộ nhớ máy tính, số thực về mặt lý thuyết có thể được biểu diễn theo ba cách: cố định, tự nhiên và dấu phẩy động [Shishkov 1995]. Trong thực tế, số dấu phẩy động được sử dụng phổ biến nhất theo tiêu chuẩn IEEE ((Institute of Electrical & Electronics Engi neers). Các nhận xét tương tự cũng áp dụng cho các kiểu thực cũng như kiểu số nguyên. Trong Bảng 1.2. phạm vi của các loại thực tế trong Borland C cho DOS được hiển thị Loại Giá trị Kích thước float 3,4.10 -38 , ..., 3,4.10 38 32 bit double 1,7.10 -308 , ..., 1,7.10 308 64 bit long double 3,4.10 -4932 , ..., 1,1.10 4932 80 bit Bảng 1.2. Các kiểu số th trong Borland C. Khi làm việc với số thực, phải cẩn thận để tránh hiện tượng tràn và mất độ chính xác sau dấu thập phân (underflow): Khi biểu diễn với một số bit cố định, độ chính xác bị mất khi làm tròn (kết quả là chúng ta chỉ có thể sử dụng một số lượng bit giới hạn). Khi biểu Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 11 diễn một số thực dưới dạng phân số hữu tỉ, độ chính xác bị mất đi so với tính gần đúng trong biểu diễn: 1/3 là phân số thập phân vô hạn tuần hoàn và không thể biểu diễn chính xác bằng một số thực hữu hạn. Do đó, đối với mỗi kiểu dữ liệu biểu diễn một số thực, tồn tại số e nhỏ nhất (e > 0) sao cho bất kỳ số nào (hoặc kết quả của một phép tính số học) nhỏ hơn e về giá trị tuyệt đối được làm tròn thành 0. Bài tập . 1.5. Ch minh rằng rằng các số thực có thể được biểu diễn dưới dạng số dấu phẩy động thực tiêu chuẩn trên thực tế là một tập con hữu hạn của các số hữu tỉ. 1.1.3. Phép chia hết và chia có dư Gọi m và n là các số nguyên, m 6= 0. Khi đó tồn tại các số nguyên q và r (0 ≤ r < m) sao cho n = q.m + r. Số q được gọi là thương của phép chia số nguyên n/m, và r được gọi là phần dư. Nếu phần dư r của phép chia số nguyên là 0, ta nói rằng m chia cho n (n là bội của m) và viết m|n. Trong ngôn ngữ C, phép chia với phần nguyên và phần dư (khi làm việc với số nguyên) được thực hiện với sự trợ giúp của các phép toán / và %. Để tránh "nhầm lẫn", chúng ta sẽ sử dụng hai ký hiệu này trong các văn bản toán học: q = n/m; r = n%m; Định nghĩa 1.12. Khi (n − m)%z = 0, ta nói rằng n có thể so sánh với m modulo z và viết n ≡ m (mod z). Phép chia cho thương và dư có thể dùng để tìm số chữ số của số tự nhiên n. Thuật toán như sau: Chia liên tiếp (nếu có thể) một số nguyên n cho 10. Rõ ràng, với mỗi phép chia như vậy, các chữ số của n giảm đi một. Như vậy, số chữ số của n được xác định bằng số phép chia ta thực hiện cho đến khi n bằng 0 Chương trình 1.1. Số chữ số (101digits.c) #include Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 12 Chương 1. Số học và thuật toán unsigned m, n = 424267; int main(void) { unsigned digits; m = n; for (digits = 0; n > 0; n /= 10, digits++); printf("So nhung chu so cua %u la %u\n", m, digits); getchar(); return 0; } Bài tập . 1.6. Tìm thương và dư của phép chia m cho n nếu (m, n) là: (7, 3),(−7, 3),(7, −3),(−7, −3), 3, 7),(−3, 7),(3, −7),(−3, −7). . 1.7. Đối với các mục tiêu đã cho, m và n (m 6= 0) cố gắng chứng minh sự tồn tại và tính duy nhất của biểu diễn n = q.m + r, 0 ≤ r < m, (q,r số nguyên). [Siderov-1995] . 1.8. Đề xuất giải thuật tìm số chữ số của một số thực. Những vấn đề gì phát sinh? 1.1.4. Tính tổng và tích Các số a1, a2, . . . , an được cho trước. Một trong ba ký hiệu sau đây thường được sử dụng nhất để biểu thị tổng của chúng S = a1 + a2 + · · · + an: S = n∑ i=1 ai, S = ∑ 1≤i≤n ai, hoặc c Có thể cho một hàm R(x) tạo ra các giá trị của i - khi đó tổng được viết dưới dạng: S = ∑ i:R(x) ai, Hàm rút gọn sau đây của trong ngôn ngữ C tìm tổng Sn của n số tự nhiên đầu tiên: Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 13 Chương trình 1.2. Tính tổng cách 1 (102sum1.c) #include unsigned sum(unsigned n) { unsigned i, s = 0; for (i = 1; i <= n; i++) s += i; return s; } int main(void) { unsigned s; s=sum(1000); printf("Tong la %u\n",s); getchar(); return 0; } Tương tự ta có thể tính tổng mà các phần tử nằm trong mảng n thành phần. Chương trình 1.3. Tính tổng cách 2 (103sum1.c) #include int sum(unsigned n) { unsigned i; int a[n]; for (i = 0; i < n; i++) a[i]= i ; int s = 0; for (i = 0; i < n; i++) s += a[i]; return s; } int main(void) { unsigned s; s=sum(100); printf("Tong la %u\n",s); getchar(); return 0; } Trong ví dụ đầu tiên, chu kỳ là dư thừa - tổng có thể được tìm Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 14 Chương 1. Số học và thuật toán trực tiếp bằng công thức cấp số cộng: Sn =n(n + 1) 2 Trong chương trình thứ hai - một công thức trực tiếp như vậy không thể tồn tại, bởi vì các phần tử của mảng có thể là các số nguyên tùy ý. Trường hợp tổng lồng nhau, ta sử dụng chu kỳ lồng nhau n∑ j=1 m ∑ ajbi = a1b1 + a1b2 + · · · + a1bn + · · · + anb1 + · · · + anbn i=1 = a1(b1 + · · · + bm) + a2(b1 + · · · + bm) + · · · + an(b1 + · · · + bm) = (a1 + · · · + an)(b1 + · · · + bm) = n∑ j=1 aj m ∑ i=1 bi. (1.1) Các đầu vào như vậy có thể được tính toán bằng cách sử dụng các chu kỳ đầu vào: Chu kỳ lồng nhau unsigned i, j ; int result = 0; for (j = 1; j <= n; j++) for (i = 1; i <= m; i++) result += a[i] * b[j]; Hai thuộc tính thú vị khác hợp lệ với số tổng là: ∑ i:R(x) ∑ j:S(x) aij = ∑ j:S(x) ∑ i:R(x) aij (1.2) ∑ R(x) ai + ∑ S(x) ai = ∑ S(x)||R(x) ai + ∑ S(x)&&R(x) ai. (1.3) Ở đây với S(x)||R(x) và S(x)&&R(x), chúng ta đã biểu thị tương ứng, liên hợp và giao điểm của các giá trị được tạo bởi các hàm S và R, có thể chấp nhận tham số i và j. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 15 Trong tích các số P = a1.a2.a3.....an ký hiệu toán học được sử dụng là: n P = ∏ i=1 ai, P = ∏ 1≤i≤n ai, hoặc P = ∏ i=1..n ai Một hàm của ngôn ngữ C để tìm tích các phần tử của mảng a[], với n phần tử, có thể có dạng sau: Tính tích của một mảng số trong C. Chương trình 1.4. Tính tích (104mult.c) #include int mult(unsigned n) { unsigned i; int a[n]; for (i = 0; i < n; i++) a[i]= i+1; int s = 1; for (i = 0; i < n; i++) s = s*a[i]; return s; } int main( ) { unsigned s; s = mult(13); printf("Tich la %u\n",s); getchar(); return 0; } Bài tập . 1.9. Tìm ra công thức tổng của một cấp số cộng. . 1.10. Chứng minh các tính chất (1.1), (1.2) và (1.3) của tổng. . 1.11. Công thức và chứng minh cho một tính chất sản phẩm tương tự như (1.1), (1.2) và (1.3). . 1.12. Sử dụng các thuộc tính (1.1), (1.2) và (1.3), kiểm tra tính hợp lệ của đẳng thức: ∑ i=1..n ai + ∑ i=n..m ai = ∑ i=1..m ai + an, 1 ≤ n ≤ m. Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 16 Chương 1. Số học và thuật toán 1.1.5. Tính lũy thừa, logarit và căn Định nghĩa 1.13. Nếu x là số thực và y là số tự nhiên thì tung độ được xác định như sau: xy = x.x. . . . .x(y lần ) Khi y < 0 thì xy = 1/x−y. Các thuộc tính sau là hợp lệ (x 6= 0): xy = xy−1.xxy = xy+1/xxy1+y2 = xy1.xy2 xy1.y2 = (xy1 )y2 Việc thực hiện đơn giản để tính xylà bằng cách thực hiện các phép nhân liên tiếp y: Chương trình 1.5. Tính lũy thừa (105power.c) #include float power(float x, unsigned y) { float res = x; unsigned i; for (i = 1; i < y; i++) res *= x; return res; } int main(void) { float s ; s=power(3,7); printf("Luy thua la %f\n",s); getchar(); return 0; } Sau đó (xem 7.5.) Chúng ta sẽ xem xét một số cách khác, thú vị hơn và hiệu quả hơn để tìm xy. Nếu xn = y (n là số tự nhiên, n > 1) thì x được gọi là căn bậc n của y và viết x =√n y. Phép toán trong đó gốc thứ y của y nhận được từ một y cho trước được gọi là phptnhcn. Đối với n = 2, thay vì căn bậc hai của y, hãy nói căn bậc hai hoặc chỉ căn y và viết √y. Sử dụng thao tác lấy căn, việc tăng một số có thể được xác định một cách hợp lý: xpq =√qxp. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 17 Trường hợp thú vị nhất là khi x và y là các số thực (x > 1). Gọi y được biểu diễn dưới dạng y = d, d1d2d3... và xét ràng buộc sau: 100+···+dk xd+d110 +d2 10k +110k. 100+···+dk 10k ≤ xy ≤ xd+d110 +d2 Rõ ràng, nó định nghĩa xylà một số thực duy nhất - chúng ta có thể nhận được bất kỳ số chữ số nào của nó sau dấu thập phân, miễn là chúng ta đã chọn một số k đủ lớn. Chúng ta sẽ xem xét một chức năng quan trọng khác sẽ cần thiết trong tài liệu sau này, đặc biệt là trong phân tích độ phức tạp của một thuật toán. Phương trình y = bx với b 6= 1, b > 0, y > 0 có nghiệm duy nhất là x. Nghiệm này được gọi là logarit của y tại cơ số b và được ký hiệu là logby. Dưới đây là một số tính chất của hàm logarit (x > 0, y > 0, b > 0, b 6= 1, c > 0, c 6= 1): x = blogbx = logbbs(1.4) logb(xy) = logbx + logby (1.5) logbxy = ylogbx (1.6) logbx =logcx logcb(1.7) Ở phần sau của cuốn sách, chúng ta thường sẽ bỏ qua cơ số của logarit khi nó là 2 và chúng ta sẽ chỉ đơn giản là viết logx thay vì log2x. Chúng ta cũng sẽ sử dụng ký hiệu ln x để biểu thị một logarit tự nhiên là logex: dựa trên số Hepper e = 2.71828... (xem 1.1.6.). 1.1.6. Bài tập . 1.13. Để chứng minh các thuộc tính nêu trên của mức độ, bắt đầu từ định nghĩa. . 1.14. Chứng minh các tính chất (1.4), (1.5) và (1.6) của lôgarit, bắt đầu từ định nghĩa. 1.1.7. Giai thừa và hồi qui Thừa số của n, n ∈ N (viết n!) Là tích của các số tự nhiên từ 1 đến n: n! = 1.2. . . . .n = n ∏ i=1 , Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 18 Chương 1. Số học và thuật toán theo định nghĩa 0! = 1. Trong ngôn ngữ C để tính n! không đặc biệt khó khăn: Chương trình 1.6. Giai thừa (106factorial.c) #include const unsigned n = 10; unsigned long factoriel(unsigned n) { unsigned i; unsigned long r = 1; for (i = 2; i <= n; i++) r *= i ; return r; } int main() { printf("%u! = %lu\n", n, factoriel(n)); return 0; } Đối với một số hàm toán học và dãy số, định nghĩa lặp lại tương ứng thuận tiện và rõ ràng hơn nhiều. Điều này có nghĩa là xác định hàm bằng chính nó hoặc tính toán từng phần tử kế tiếp của chuỗi các giá trị của hàm, sử dụng các giá trị của hàm trước đó. Trong trường hợp của chúng ta, định nghĩa lặp lại của một giai thừa trông giống như sau: n! = ( 1, n = 0 n(n − 1)!, n > 0 Tương tự với giai thừa cho tổng của n số tự nhiên Sn đầu tiên, chúng ta thu được định nghĩa truy hồi: ( Sn = 0, n = 0 Sn−1 + n, n > 0 Chúng ta sẽ thấy ở phần sau (xem 1.2.) Điều đó để tính toán cho mỗi hàm toán học lặp lại, một hàm đệ quy tương ứng của C có thể được viết. Bài tập . 1.15. Đề xuất công thức truy hồi để nâng x thành lũy thừa y(x ∈ R, y ∈ N). Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 19 . 1.16. Đề xuất công thức tìm ước số chung lớn nhất của hai số tự nhiên. 1.1.8. Ma trận Ma trận là một bảng số hình chữ nhật (nói chung là một bảng hình chữ nhật gồm các đối tượng ngẫu nhiên). Các số m và n xác định số chiều (m × n) của ma trận: tức là chứng tỏ rằng nó bao gồm m hàng và n cột (n ≥ 1, m ≥ 1). Khi m = n ma trận được gọi là hình vuông. Mỗi phần tử aij của ma trận được đặc trưng bởi một chỉ số kép: số đầu tiên trong đó xác định số hàng và số thứ hai - số bậc thang nơi nó nằm (xem Hình 1.3.). Hình 1.3. Ma trận m × n Ma trận được sử dụng rộng rãi trong đại số, trong giải hệ phương trình, trong hoạt hình máy tính, trong đó ma trận có kích thước 2 × 2, 3 × 3, 4 × 4 được sử dụng để dịch và quay các đối tượng, để đạt được các hiệu ứng đồ họa khác nhau (chẳng hạn như phối cảnh xem trong địa hình ba chiều), v.v. Việc sử dụng ma trận trong các trường hợp này và các trường hợp khác dẫn đến các thuật toán hiệu quả hơn đáng kể và do đó, năng suất cao hơn [Ayres-1962]. Trong ngôn ngữ C một bảng chữ nhật ta có thể biểu diễn như một mảng int A[m][n]; Trường hợp tổng quát hơn cũng có thể xảy ra khi các phần tử của ma trận là các đối tượng tùy ý của một số kiểu struct data được xác định trước, ví dụ: Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 20 Chương 1. Số học và thuật toán Loại dữ liệu ma trận struct data { int a; int b; . . . } A[m][n]; Nhập vào và in ra một ma trận Phần tử ma trận có thể được đọc/in theo nhiều cách khác nhau. Hai đơn giản nhất là ma trận hàng hoặc cột (Hình 1.1.1d). Hình 1.4. Thu thập thông tin các phần tử của ma trận: (a) theo hàng và (b) theo cột. Nhập dữ liệu ma trận / /Nhập theo hàng for (i = 0; i < m; i++) for (j = 0; j < n; j++) scanf("%d", &A[i][j]); / /Nhập theo cột for (i = 0; i < m; i++) for (j = 0; j < n; j++) scanf("%d", &A[j][i]); / / In theo hàng for (i = 0; i < m; i++) { for (j = 0; j < n; j++) printf("%.3d", A[i][j]); printf("\n"); Tổng hai ma trận Tổng của hai ma trận Am×n và Bm×n là ma trận thứ ba Cm×n sao cho cij = aij + bij (với i = 1, 2, ..., m, j = 1, 2, ..., .n), xem Hình 1.5. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.1. Khái niệm toán học và thuật toán 21 Hình 1.5. Tổng các ma trận. Tổng hai ma tận for (i = 0; i < m; i++) for (j = 0; j < n; j++) C[i][j] = A[i][j] + B[i][j]; Tích hai ma trận Tích của hai ma trận Am×n và Bn×p là ma trận thứ ba Cm×p mà: cij = n∑ k=1 (aikbkj), với mỗi i = 1, 2, ..., m và j = 1, 2, ..., p. Thực hiện bên dưới, áp dụng trực tiếp công thức từ định nghĩa và thực hiện phép nhân đơn giản m.p.n. Nếu n > m và n > p thì số phép nhân nguyên tố bị giới hạn bởi n3. Tích hai ma trận for (i = 0; i < m; i++) for (j = 0; j < p; j++) { C[i][j] = 0; for (k=0;k #include const unsigned long n = 123; int main(void) { float digits = 0; unsigned i; for (i = 1; i <= n; i++) { digits += log10(i); } / /Số [x] đưa ra số nguyên dài printf("So chu so cua %lu! la %lu\n", n, (unsigned long) digits + 1); getchar(); return 0; } Bài tập . 1.19. Chứng minh rằng với mọi số tự nhiên P có số chữ số thập phân của nó bằng [1 + log10(P)]. 1.2. Số nguyên tố Số nguyên tố đã được xem xét trong toán học từ thời cổ đại và gắn liền với nhiều vấn đề thú vị vượt xa biên giới của nó. Trong khoa học máy tính, chúng được sử dụng trong mã hóa, lưu trữ, v.v. Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 24 Chương 1. Số học và thuật toán Định nghĩa 1.14. Một số tự nhiên được gọi là đơn giản nếu không có ước nào khác ngoài 1 và chính nó, và số 1 không được coi là số nguyên tố. Nếu nó không đơn giản, nó được gọi là hợp chất. Dãy số nguyên tố bắt đầu như sau: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ... Người ta đã chứng minh (Euclid - 300 TCN) rằng các số nguyên tố là vô số. Như đã đề cập, một trong những ứng dụng của số nguyên tố là mã hóa dữ liệu được truyền qua mạng "không an toàn" (ví dụ: các giao dịch tài chính trên Internet). Một số thuật toán để mã hóa thông tin được truyền (ví dụ RSA [RSA-78]) sử dụng tích các số nguyên tố lớn. Để “phá vỡ” kênh truyền tải thông tin như vậy, bản thân các số nguyên tố phải được biết đến chứ không chỉ là tích của chúng. Nếu nhìn vào số 55, chúng ta có thể đoán ngay nó phân hủy như thế nào - là tích của 5 và 11. Đối với số 4853, chúng ta sẽ khó nhớ lại các ước số đơn giản của nó (211 và 23), nhưng chúng ta có thể biên dịch một chương trình. mà tìm thấy chúng. Nhiều số nguyên tố lớn hiện được biết đến - ví dụ: nếu chúng ta nhân hai số nguyên tố ngẫu nhiên có 100 chữ số và chỉ có tích kết quả, thì việc khôi phục các số bằng bất kỳ thuật toán nào sẽ mất một thời gian dài không thể chấp nhận được (ví dụ: gấp nhiều lần so với yêu cầu hoàn thành giao dịch ngân hàng). Khi chúng ta xem xét số lượng các số nguyên tố, một số câu hỏi nảy sinh: • Có bao nhiêu số nguyên tố trong khoảng [a, b] cho trước? • Phần vô cực là số nguyên tố? • Có công thức tìm số nguyên tố thứ n không? Nếu ta kí hiệu π(x) với tất cả các số nguyên tố không vượt quá một số tự nhiên x thì việc tìm công thức tính π(x) chính xác sẽ trả lời được ba câu hỏi trên. Thật không may, một công thức như vậy vẫn chưa tồn tại (và không chắc sẽ được tìm thấy - xem 6.2.), Nhưng có những công thức để tính gần đúng π(x), chẳng hạn (hãy nhớ lại rằng ln x ≡ logex): Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.2. Số nguyên tố 25 Định lý 1.1 (cho số nguyên tố). π(x) 'x ln(x − a), trong đó a là hằng số dương tùy ý, nhỏ hơn x. (Giá trị gần đúng nhất đạt được là a = 1.) Hệ quả 1.1. Số nguyên tố thứ n xấp xỉ [n. ln(n)]. Một xấp xỉ tốt hơn đạt được với [n[(ln(n) + ln(ln n − 1))]. Hệ quả 1.2. Xác suất để một số x là xấp xỉ 1ln x. Trước khi chuyển sang các thuật toán để kiểm tra xem một số có phải là số nguyên tố hay không, chúng ta sẽ đề cập đến một số tính chất và định lý thú vị hơn cho các số nguyên tố [Số nguyên tố-1] [Số nguyên tố-2]: Giả thuyết của Goldbach 1. Mọi số nguyên n > 2 đều có thể được biểu diễn dưới dạng tổng của hai số nguyên tố. 2. Mọi số nguyên n > 17 đều có thể được biểu diễn dưới dạng tổng của ba số nguyên tố khác nhau. 3. Mỗi số nguyên có thể được biểu diễn dưới dạng tổng của tối đa sáu số nguyên tố. 4. Mọi số nguyên lẻ n > 5 đều có thể được biểu diễn dưới dạng tổng của ba số nguyên tố. 5. Mỗi số chẵn có thể được biểu diễn dưới dạng hiệu của hai số nguyên tố. Định lý 1.2. Có vô số số rất nguyên tố loại n2 + m2 và n2 + m2 + 1. Giả thuyết. Có vô số số nguyên tố dạng n2 + 1. Định lý 1.3 (Operman). Luôn luôn có một số nguyên tố giữa n2 và (n + 1)2. Bài tập . 1.20. 1. Tại sao việc tìm một công thức chính xác cho π(x) sẽ trả lời được cả ba câu hỏi về số nguyên tố đã lập ở trên? 2. Viết chương trình kiểm tra các giả thuyết của Goldbach. 3. Viết chương trình kiểm tra định lý Operman. Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 26 Chương 1. Số học và thuật toán 1.2.1. Kiểm tra một số có phải là số nguyên tố Một thuật toán hiển nhiên, hệ quả trực tiếp của định nghĩa, là h như sau: chúng ta kiểm tra xem mỗi số trong khoảng 2, p2− 1icó chia hết cho p hay không và nếu chúng ta tìm thấy một thì theo đó p là hợp số. Có một số "công thức" để kiểm tra xem một số có đơn giản hay không, nhưng trong thực tế, chúng không thể áp dụng được, vì việc triển khai chúng đòi hỏi nhiều tài nguyên tính toán hơn so với thuật toán vừa mô tả. Một ví dụ là sau đây Định lý 1.4 (Wilson). Số p là số nguyên tố nếu và chỉ khi (p − 1)! ≡ −1 (mod p). Nó phải tính toán (p − 1)!, khó thực hiện hơn nhiều và đòi hỏi nhiều phép tính hơn so với việc thực hiện p2− 1 phép chia trong thuật toán trên. Dễ dàng thấy rằng không cần thiết phải kiểm tra tất cả các số có đến p2− 1: chỉ cần kiểm tra chia hết cho đến √p (bao gồm) là đủ. Điều này là do bất cứ khi nào p có một ước số x, x >√p, thì p được biểu diễn dưới dạng p = x.y, y <√p, tức là còn một số chia nhỏ hơn √p. Sau đây là cách triển khai thuật toán này: Chương trình 1.8. Số chữ số (111prime.c) #include #include const unsigned n = 23; / / Trả lại 1 thì $n$ là nguyên tố; 0 thì $n$ la hợp số char isPrime(unsigned n) { unsigned i = 2; if (n == 2) return 1; while (i <= sqrt(n)) { if (n % i == 0) return 0; i++; } return 1; Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.2. Số nguyên tố 27 } int main(void) { if (isPrime(n)) printf("So %u la nguyen to.\n", n); else printf("So %u la hop so.\n", n); } Chúng ta có thể mở rộng kết quả cuối cùng: để tìm rằng p là số nguyên tố, nó đủ để đảm bảo rằng nó không chia hết cho bất kỳ số nguyên tố nào khác trong khoảng [2, √p] (Chúng ta để lại như một bài tập cho bạn đọc để chứng minh rằng kết luận sau là đúng). Vì vậy, nếu chúng ta có k số nguyên tố đầu tiên (ký hiệu là Pi, với i = 1, 2, ..., k), chúng ta sẽ có thể kiểm tra xem có số nào trong khoảng [2,(Pk)2] Thì đơn giản. Triển khai trong ngôn ngữ C như sau: Chương trình 1.9. Kiểm tra số nguyên tố (112preproc.c) #include const unsigned n = 25; / /Số lượng số nguyên tố mà ta cần phải tính #define K 25 unsigned prime[K] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; / / Kiểm tra có phải chăng là số nguyên tố / /bằng cách kiểm tra có ước số trong danh sách prime[] char checkprime(unsigned n) { unsigned i = 0; while (i < K && prime[i] * prime[i] <= n) { if (n % prime[i] == 0) return 0; i++; } return 1; } int main(void) { if (checkprime(n)) Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 28 Chương 1. Số học và thuật toán printf("So %u la so nguyen to. \n", n); else printf("So %u la hop so. \n", n); return 0; } Bài tập . 1.21. Viết chương trình kiểm tra xem một số có phải là số nguyên tố hay không, sử dụng định lý Wilson. Có cần thiết phải tính (p − 1)!, với điều kiện chúng ta chỉ quan tâm đến modulo p phần dư của nó không? . 1.22. Để chứng minh rằng để chứng minh rằng p là số nguyên tố, chỉ cần biết chắc chắn rằng nó không chia hết cho bất kỳ số nguyên tố nào khác trong khoảng [2, √p]. 1.2.2. Sàng Eratosten. Tìm số nguyên tố trong khoảng Bài toán: Tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng một số tự nhiên n. Một cách tiếp cận rõ ràng để giải quyết vấn đề là kiểm tra xem có số tự nhiên nào nhỏ hơn n là đơn giản hay không. Do đó, n lần kiểm tra được thực hiện, và đối với mỗi số k, tối đa k số lần kiểm tra tính chia hết sẽ được yêu cầu. Với điều kiện có đủ bộ nhớ, chúng ta có thể áp dụng một phương pháp nhanh hơn để tìm các số nguyên tố trong một khoảng gọi là sàng Eratosthenes. Phương pháp này được đặt theo tên của người tạo ra nó - Eratosthenes of Siren (275-195 trước Công nguyên) - người đầu tiên dự đoán đường kính chính xác của Trái đất. Ông cũng được biết đến là người đã làm việc tại Thư viện Alexandria trong nhiều năm. Như tên cho thấy, "sàng" là một phương pháp lập trình loại trừ tất cả các phần tử của một tập hợp hữu hạn mà chúng ta không quan tâm [Rakhnev, Garov, Gavrilov-1995] [Reingold, Nivergelt, Deo-1980]. Nó có thể được minh họa bằng một cái rây lọc spaghetti - nước mà chúng ta muốn "tống khứ" hết đi và spaghetti vẫn còn. Theo cách tương tự, sàng lọc của Eratosthenes "ép" các số tổng hợp, khiến chúng trở nên đơn giản. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.2. Số nguyên tố 29 Hình 1.6. Eratosthenes và lưới của mình Trong trường hợp này, ý tưởng của cách tiếp cận này xuất phát từ đoạn trước: một số là đơn giản nếu không có ước số nguyên tố nào khác (ngoại trừ chính nó). Lưới của Eratosthenes: Chúng ta viết các số từ 2 đến n liên tiếp: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, . . . , n Chúng ta tìm thấy số đầu tiên chưa được đánh dấu và chưa được đánh dấu – đó là 2. Chúng ta đánh dấu nó, sau đó gạch bỏ mỗi số thứ hai sau nó: (2), 3, 4, 5, ✁ 6, 7, ✁ 8, 9, ✁ ✚10, 11, ✚ ✚12, 13, ✚ ✚14, 15, ✚ ✚16, 17, . . . , ✚ n Tiếp theo, chúng ta tìm lại số đầu tiên chưa được đánh dấu và chưa được đánh dấu: đây là số 3. Chúng ta đánh dấu nó và gạch bỏ tất cả các số trong dãy, bội số của 3: (2),(3), 4, 5, ✁ 6, 7, ✁ 8, ✁ 9, ✁ ✚10, 11, ✚ ✚12, 13, ✚ ✚14, ✚ ✚15, ✚ ✚16, 17, . . . , ✚ n Sau đó, đã đến lúc cho số 5 – chúng ta đánh dấu nó và gạch bỏ cứ sau mỗi ngày 5: (2),(3), 4, ✁ (5), 6, 7, ✁ 8, ✁ 9, ✁ ✚10, 11, ✚ ✚12, 13, ✚ ✚14, ✚ ✚15, ✚ ✚16, 17, . . . , ✚ n Do đó, tất cả các số tổng hợp đều được "sàng lọc" và chúng ta luôn chắc chắn rằng số i tối thiểu chưa được đánh dấu và chưa được Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 30 Chương 1. Số học và thuật toán đánh dấu là đơn giản. Quá trình tiếp tục cho đến khi không có số nào bị gạch chéo hoặc không có dấu - khi đó tất cả các số được đánh dấu là số nguyên tố và tất cả các số bị gạch bỏ đều là hợp số. Dưới đây là sơ đồ chi tiết hơn để thực hiện sàng lọc bằng phương pháp sàng Eratosthenes: Thuật toán sàng Eratosthenes 1. Khởi tạo mảng sieve[] với các số không. Sau này, khi gạch bỏ một số, chúng ta sẽ viết 1 ở vị trí tương ứng trong mảng i. Chúng ta khởi tạo i = 2. 2. Chúng ta tăng i cho đến khi sieve[i] trở thành 0. Khi đó số i là đơn giản và chúng ta in ra. 3. Đánh dấu bằng 1 tất cả các giá trị sieve[k], cho k = i, 2i, 3i, ...,(n/i).i (tức là tất cả các bội số của i giá trị). 4. Nếu i ≤ n thì chúng ta quay lại bước 2, ngược lại thì kết thúc. Chương trình 1.10. Danh sách số nguyên tố (113sieve.c) #include #define MAXN 30000 const unsigned n = 200; char sieve[MAXN]; / /Tìm và in ra số nguyên tố đến $n$ void eratosten(unsigned n) { unsigned j, i = 2; while (i <= n) { if (sieve[i] == 0) { printf("%5u", i); j = i ; while (j <= n) { sieve[j] = 1; j += i; } } i++; } } int main(void) { unsigned i; for (i = 0; i < n; i++) sieve[i] = 0; Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.2. Số nguyên tố 31 eratosten(n); return 0; } Kết quả thực hiện chương trình: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 Ngoài ra còn có một thuật toán thậm chí còn hiệu quả hơn để tìm kiếm tất cả các số nguyên tố trong một khoảng thời gian. Nó không yêu cầu bộ nhớ (mảng sieve[N]) với kích thước của khoảng, cũng như không cần thiết phải thu thập dữ liệu toàn bộ khoảng ở mỗi bước. Trong việc triển khai preproc.c từ đoạn trước, chúng ta đã nhập trước mảng số prime[], chứa k số nguyên tố đầu tiên và với sự trợ giúp của nó, chúng ta đã kiểm tra xem một số trong khoảng [2,(Pk)2] có số nguyên tố. Bây giờ chúng ta sẽ áp dụng lược đồ đã sửa đổi sau: chúng ta sẽ bắt đầu với một danh sách trống, mà chúng ta sẽ điền tuần tự. Ví dụ, đặt nó vào số nguyên tố đầu tiên 2, chúng ta có thể tìm thấy tất cả các số nguyên tố trong khoảng [3, 22] - chẳng hạn như 3 và chúng ta thêm nó vào danh sách. Hơn nữa, đã có các số nguyên tố đến 3, chúng ta có thể tìm thấy tất cả các số nguyên tố trong phạm vi [4, 32] - đây là 5 và 7, chúng ta cũng thêm vào danh sách. Chúng ta tiếp tục quá trình này cho đến khi các số nguyên tố được thêm vào prime[] để kiểm tra xem mỗi số trong khoảng [2, n] có phải là số nguyên tố hay không. Sau đây là một ví dụ triển khai: Kiểm tra một số nguyên tố có nằm trong khoảng [2, n] không? Chương trình 1.11. Số nguyên tố trong một khoảng (114proc.c) #include #define MAXN 10000 / /Tìm số nguyên tố đến $n$ const unsigned n = 500; unsigned primes[MAXN], pN = 0; Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 32 Chương 1. Số học và thuật toán char isPrime(unsigned n) { unsigned i = 0; while (i < pN && primes[i] * primes[i] <= n) { if (n % primes[i] == 0) return 0; i++; } return 1; } void findPrimes(unsigned n) { unsigned i = 2; while (i < n) { if (isPrime(i ) ) { primes[pN] = i; pN++; printf("%5u", i); } i++; } } int main(void) { findPrimes(n); printf("\n"); return 0; } Trong trường hợp chúng ta đang tìm n số nguyên tố đầu tiên, phương pháp sàng Eratosthenes cho kết quả rất tốt. Tuy nhiên, khi tìm các số nguyên tố trong khoảng [a, b] cho a(a >> 1) đủ lớn, tốt hơn nên sử dụng một thuật toán khác - một phiên bản cải tiến của thử nghiệm ngay lập tức. Ba số nguyên tố đầu tiên là 2, 3 và 5. Do đó, bất kỳ số tự nhiên nào cũng có thể được biểu diễn dưới dạng: n = 30.q + r,r ∈ [0..29] hoặc r ∈ [0, ±1, ±2, ..., ±14, 15]. 30.q = 2.3.5.q Khi đó trong số 30 số liên tiếp, chỉ có 8 số có thể là số nguyên tố, Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.2. Số nguyên tố 33 tức là chúng ta chỉ cần kiểm tra 4k/15 số, cụ thể là: 30.q ± 1, 30.q ± 7, 30.q ± 11, 30.q ± 13 Phương pháp được đề xuất dẫn đến tăng tốc gấp đôi so với phương pháp xác minh trực tiếp tất cả các con số trong khoảng thời gian xác định. Bài tập . 1.23. Thuật toán có thể được cải thiện: ở bước 3) tìm kiếm bắt đầu từ k = i2, trong khi tăng dần với giá trị i được giữ nguyên. Chứng minh cho kết quả này và sửa đổi việc triển khai cho phù hợp. So sánh với bản gốc. . 1.24. Để chứng minh thuật toán sàng. . 1.25. Để cải thiện thuật toán tìm kiếm các số nguyên tố trong một khoảng, vì mục đích này, 4 số nguyên tố đầu tiên được xem xét. 1.2.3. Phân tích một số thành tích thừa số nguyên tố Định lý 1.5 (Định lý cơ bản của số học). Mọi số tự nhiên P(P > 1) đều có thể được biểu diễn (thừa số) một cách duy nhất dưới dạng 2. . . . .Pqn 1.Pq2 Pq1 n , trong đó P1 < P2 < . . . < Pn và P là các số nguyên tố và qilà các số nguyên dương. [Siderov-1995]. Dưới đây là một số ví dụ: 520 = 23.51.131 64 = 26 2345 = 51.71.671 Thuật toán để có được sự phân rã như vậy cần thiết cho một số tác vụ tính toán (ví dụ: Thuật toán 2 của 1.1.5.) Là như sau: Hãy phân tích số P. 1) Ta đặt i = 2. 2) Ta đặt k = 0. Trong khi P chia hết cho i, ta thực hiện phép chia và tăng k lên một. Chúng ta chuyển sang 3). Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 34 Chương 1. Số học và thuật toán 3) Nếu k > 0, thì ta thu được số hạng tiếp theo của phân thức - đó là ik. Chuyển sang 4) 4) Nếu P > 1, ta tăng i lên một và trở về 2). Chúng ta để nó cho người đọc để chứng minh rằng thuật toán đang hoạt động bình thường. Sau đây là nhận thức đầy đủ của C: Chương trình 1.12. Phân tích số thành tích thừa số nguyên tố (115numdev.c) #include / /Số để phân tích ra thừa số unsigned n = 435; int main(void) { unsigned how, i, j ; printf("%u = ", n); i = 1; while (n != 1) { i++; how = 0; while ((n % i) == 0) { how++; n = n / i ; } for (j = 0; j < how; j++) printf("%u ", i); } printf("\n"); return 0; } Bài tập . 1.26. Chứng minh thuật toán được đề xuất để phân tích nhân tử. 1.2.4. Tìm số lượng số không trong kết quả phép nhân Bài toán: Cho trước một số số nguyên a1, a2, ..., an. Chúng ta tìm số lượng các số không mà tại đó tích P = a1.a2.....an. Như trong 1.1.2, phép nhân là không mong muốn và không phải lúc nào cũng dẫn đến kết quả mong muốn. Để giải quyết vấn đề, Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.2. Số nguyên tố 35 chúng ta sẽ chú ý đến thực tế sau: Các số duy nhất có tích kết thúc bằng 0 là 2 và 5, hoặc tích của bội số của 2 với bội số của 5. Thuật toán giải quyết vấn đề mà không cần thực hiện phép nhân như sau: 1. Với mỗi ai(i = 1, 2, ..., n) ta biểu diễn ai dưới dạng ai = 2Mi.5Ni.bi, bi%2 6= 0, bi%5 6= 0. 2. Kết quả của sản phẩm sẽ là P = 2∑i=1..n Mi.5∑i=1..n Ni.c, (c là hằng số), và số lượng các số không ở cuối sản phẩm sẽ là nhỏ nhất của ∑ni=1 Mi và ∑ni=1 Ni. Ví dụ, đối với chuỗi: 25, 4, 20, 11, 13, 15 sau khi phân hủy chúng ta sẽ nhận được: 20.52.1, 22.50.1, 22.51.1, 20.50.11, 20.50.13, 20.51.3, mà cho 4 số không. Ta có thể kiểm tra tính đúng đắn của kết quả thu được một cách trực tiếp: 25.4.20.11.13.15 = 4290000. Chúng ta sẽ để việc triển khai thuật toán vừa được mô tả như một bài tập cho người đọc. Nó sẽ là một sửa đổi nhỏ của thuật toán đã được xem xét để phân tách số lượng các ước số nguyên tố từ đoạn trước. Chúng ta sẽ kết thúc với một công thức để tìm số lượng các số không ở cuối n!. Số này bằng ∑[log5n] k=1 hn 5k i . Công thức được suy ra như một hệ quả của sơ đồ tổng quát hơn, sau khi tính xem có bao nhiêu lần các chữ số 2 và 5 tham gia làm ước của n số tự nhiên đầu tiên. Chương trình 1.13. Tìm số 0 làm phép nhân (116factzero.c) #include const unsigned n = 10; int main(void) { unsigned zeroes = 0, p = 5; while (n >= p) { zeroes += n / p; p *= 5; } Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 36 Chương 1. Số học và thuật toán printf("So luong so 0 cua %u! la %u\n", n, zeroes); return 0; } Bài tập . 1.27. Để chứng minh thuật toán được đề xuất để tìm số lượng các số không mà tại đó phép nhân kết thúc. . 1.28. Để thực hiện thuật toán được đề xuất tìm số lượng các số không tại đó thuật toán kết thúc. . 1.29. Biện minh cho công thức tìm số lượng các số không kết thúc bằng n! 1.3. Số mensen và số hoàn thiện 1.3.1. Số mensen Định lý 1.6. Một số nguyên tố được gọi là số nguyên tố Mersenne nếu nó có thể được biểu diễn dưới dạng 2p − 1, trong đó p là số nguyên tố. Hiện tại, 39 giá trị của p đã được biết, trong đó các số 2p − 1 là Mersenne: 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 37 giá trị đầu tiên của p số tương ứng với lũy thừa của 37 số Mersenne đầu tiên. Hai số cuối cùng là của Mersen (lần lượt được phát hiện vào năm 1999 và 2001), nhưng chúng không nhất thiết phải là số 38 và 39, vì chúng được tìm thấy bằng máy tính mà không cần kiểm tra tất cả các số nhỏ hơn. các giá trị của p. nghĩa là, có thể có số Mersenne nhỏ hơn. Số Mersenne tìm thấy một số ứng dụng: để tìm kiếm các số hoàn hảo, để tìm kiếm các số nguyên tố rất lớn và các ứng dụng khác. Chúng vừa có giá trị thực tế vừa mang giá trị biểu tượng. Khi số nguyên tố thứ 23 của Mersen được tìm thấy vào năm 1963, Trường Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.3. Số mensen và số hoàn thiện 37 Toán học của Đại học Illinois đã rất tự hào về khám phá của mình đến nỗi tất cả các bức thư được gửi kèm theo một con tem bổ sung là "211213 − 1 là số nguyên tố" (xem Hình1.7). Hình 1.7. 211213 − 1 là số nguyên tố Một số số nguyên tố lớn nhất được tìm thấy cho đến nay là Mersenne: 213466917 − 1 với 8107892 chữ số (?? số nguyên tố Mersenne thứ 39) 26972593 − 1 với 2098960 chữ số (?? số nguyên tố Mersenne thứ 38) 23021377 − 1 với 909526 chữ số (số nguyên tố Mersenne thứ 37) 22976221 − 1 với 895932 chữ số (số Mersenne thứ 36) 21398269 − 1 với 420921 chữ số (số Mersenne thứ 35) Việc công bố các giải thưởng tiền mặt lớn là một hiện tượng ngày càng phổ biến đối với các kết quả khoa học hoặc thực nghiệm nghiêm túc. Ví dụ, có những dự án phổ biến trên Internet để tìm kiếm số nguyên tố lớn tiếp theo (và rất có thể nó sẽ là số nguyên tố của Mersen - xem bên dưới). Những dự án như vậy được tài trợ bởi các tổ chức nghiên cứu nổi tiếng, và việc tham gia vào một dự án như vậy giống như một cuộc xổ số: người may mắn trúng số nguyên tố thứ 38 của Mersen thì trúng 50.000 USD. Giải thưởng cho những con số tiếp theo bắt đầu từ 250.000 đô la [Số nguyên tố-3]. Một thuật toán hiển nhiên để tìm kiếm các số Mersenne như sau: liên tiếp với mỗi số nguyên tố p = 2, 3, 5, 7, 11,... chúng ta kiểm tra xem M = 2 p - 1 có đơn giản không. Tuy nhiên, thuật toán này cực kỳ Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 38 Chương 1. Số học và thuật toán kém hiệu quả và trong thực tế không cho kết quả khả quan, áp dụng cho số lượng lớn. Chìa khóa để tìm ra các số lớn như vậy là định lý Lucas năm 1870, sau đó được Lehmer sửa đổi, và ứng dụng của nó cũng yêu cầu một chương trình nhân các số nhanh (một phương pháp nhân các số như vậy được tìm thấy sau này và dựa trên phép biến đổi Fourier nhanh chóng [Guinier -1991]). Phương pháp Lucas - Lehmer (1930) bao gồm các nội dung sau: Trình tự lặp lại được xác định: E1 = 4 En+1 = (En)2 − 2 Một số thành viên đầu tiên của loạt bài này là: 4, 14, 194, 37634, .... Định lý 1.7 (Lucas-Lemer). Số tự nhiên m = 2p − 1 là số nguyên tố Mersenne (với p lẻ) nếu và chỉ khi: (Ep−1)%(2p − 1) = 0 Chúng ta cho phép người đọc triển khai một chương trình để tìm một vài số nguyên tố Mersenne đầu tiên. Trong đoạn tiếp theo, chúng ta sẽ xem xét một trong những ứng dụng của số nguyên tố Mersenne - để tìm kiếm các số hoàn hảo. Bài tập . 1.30. Viết chương trình tìm n số Mersenne đầu tiên mà không sử dụng định lý Lucas-Lemmer. . 1.31. Viết chương trình tìm n số Mersenne đầu tiên sử dụng định lý Lucas-Lemmer. Để so sánh hiệu quả với bài toán trước đó. . 1.32. 2n − 1 có thể là số nguyên tố nếu n không phải là số nguyên tố không? 1.3.2. Số hoàn thiện Định nghĩa 1.15. Một số tự nhiên n được gọi là hoàn hảo nếu nó bằng tổng của tất cả các ước của nó (bản thân n không được coi là ước). Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.3. Số mensen và số hoàn thiện 39 3 số hoàn hảo đầu tiên là: 6 = 1 + 2 + 3, 28 = 1 + 2 + 4 + 7 + 14, 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248. Số lượng các số hoàn hảo tăng rất nhanh: 8128, 33550336, 8589869056, . . . Vì vậy, nếu chúng ta cố gắng tìm kiếm chúng bằng một thuật toán trực tiếp (liên tiếp với từng n = 1, 2, 3, . . . để kiểm tra xem nó có hoàn hảo hay không), chúng ta sẽ không thể tìm được nhiều hơn số hoàn hảo thứ 5 cho hợp lý. thời gian tính toán. Sau đây là sự hỗ trợ của chúng ta: Định lý 1.8 (Euler). Nếu 2p − 1 là số nguyên tố thì 2p−1(2p − 1) là hoàn hảo. Theo định lý trên, một chương trình tìm n số hoàn hảo đầu tiên có thể được biên soạn trực tiếp: chỉ cần biết lũy thừa pi của n số Mersenne đầu tiên (10 lũy thừa đầu tiên là 2, 3, 5, 7, 13, 17, 19, 31, 61, 89). Vấn đề nảy sinh bởi vì ngay cả ở các giá trị nhỏ của n, các số hoàn hảo được yêu cầu vượt quá giá trị lớn nhất cho phép đối với một kiểu số nguyên trong ngôn ngữ C. Do đó, chúng ta sẽ không sử dụng các kiểu tiêu chuẩn, nhưng sẽ thực hiện các phép toán cần thiết với các số "lớn": nhân một số với 2 và tăng một. Chúng ta sẽ giữ số "lớn" trong mảng một chiều number[]: mỗi phần tử của nó đại diện cho một chữ số thập phân. Để thuận tiện, các chữ số của số được sắp xếp theo thứ tự ngược lại trong mảng: chữ số đầu tiên được viết trong number[k-1] (nếu số có k chữ số), chữ số thứ hai trong number[k-2], v.v. Chữ số k cuối cùng được viết bằng number[0]. Thuật toán để tăng một số được viết bằng number[] như sau: Tăng một đơn vị i = 0; number[i]++; while(10==number[i]){number[i]=0; number[++i]++;} if (i == k) k++; Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 40 Chương 1. Số học và thuật toán Vì trong tìm kiếm các số hoàn hảo chỉ thực hiện phép nhân với 2 nên kết quả sẽ là lũy thừa của cặp số, tức là chữ số cuối cùng không được là 9, thì hai dòng cuối cùng, bắt đầu từ dấu kiểm while (10 == number [i]), là thừa. Tương tự, chúng ta nhân một số lớn với hai: Nhân một số lớn với hai unsigned i, carry = 0, temp; for (i = 0; i < k; i++) { temp = number[i] * 2 + carry; number[i] = temp % 10; carry = temp / 10; } if (carry > 0) number[k++] = carry; Sau đây là một triển khai hoàn chỉnh tìm 10 số hoàn hảo đầu tiên, với lũy thừa của mười số nguyên tố Mersenne đầu tiên được đặt làm hằng số trong mảng mPrimes[] Chương trình 1.14. Số hoàn thiện (117perfect.c) #include #define MN 10 unsigned mPrimes[MN]={2,3,5,7,13,17,19,31,61,89 }; unsigned k, number[200]; void doubleN(void) { unsigned i, carry = 0, temp; for (i = 0; i < k; i++) { temp = number[i] * 2 + carry; number[i] = temp % 10; carry = temp / 10; } if (carry > 0) number[k++] = carry; } void print(void) { unsigned i; for (i = k; i > 0; i--) printf("%u", number[i-1]); printf("\n"); } Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.3. Số mensen và số hoàn thiện 41 void perfect(unsigned s, unsigned m) { unsigned i; k = 1; number[0] = 1; for (i = 0; i < m; i++) doubleN();//đây là ước số có dạng $2^i$ number[0]--;//những chữ số cuối cùng chắc chắn giữa $\{2,4,8,6\}$ for (i = 0; i < m - 1; i++) doubleN(); printf("So hoan hao thu %2u la = ", s); print(); // In ra lần lượt các số } int main() { unsigned i; for (i=1; i<= MN; i++) perfect(i, mPrimes[i-1]); return 0; } Kết quả thực hiện chương trình: Số hoàn hảo đầu tiên là = 6 Số hoàn hảo thứ 2 là = 28 Số hoàn hảo thứ 3 là = 496 Số hoàn hảo thứ 4 là = 8128 Số hoàn hảo thứ 5 là = 33550336 Số hoàn hảo thứ 6 là = 8589869056 Số hoàn hảo thứ 7 là = 137438691328 Số hoàn hảo thứ 8 là = 2305843008139952128 Số hoàn hảo thứ 9 là = 2658455991569831744654692615953842176 Số hoàn hảo thứ 10 là = 1915619426082361072947933780843036381309973215481Lưu ý: Rõ ràng, định lý trên chỉ cho các số hoàn hảo chẵn (thực tế là tất cả các số hoàn hảo chẵn). Câu hỏi về việc liệu có những số hoàn hảo lẻ vẫn chưa được trả lời (có lẽ là không). Người ta đã chứng minh rằng nếu có thì chúng phải có ít nhất 300 chữ số và nhiều ước. Bài tập . 1.33. Chứng minh rằng tổng các giá trị nghịch đảo của các ước (bao gồm cả 1 và số chính nó) của mỗi số hoàn hảo là 2. Ví dụ, với 6 ta có: 1/1 + 1/2 + 1/3 + 1/6 = 2. Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 42 Chương 1. Số học và thuật toán . 1.34. Viết chương trình tìm tất cả các số mà tổng giá trị nghịch đảo của các ước (kể cả 1 và chính số đó) là 2. Chúng có hoàn hảo không? 1.4. Những hệ số đa thức, tam giác Pascal và giai thừa Định nghĩa 1.16. Cho một tập hợp n phần tử đã cho. Số của tất cả các tập con k phần tử có thể có của nó được gọi là hệ số nhị thức và được biểu thị và tính toán như sau: Ckn = Ckn =n(n − 1). . .(n − k + 1) k(k − 1). . . 1 . (1.8) Chúng ta sẽ lưu ý rằng các ký hiệu Ckn và Ckn không hoàn toàn tương đương và ký hiệu sau tổng quát hơn ký hiệu trước, vì nó thường cho phép các giá trị thực của n, nơi không có ý nghĩa tổ hợp. Tuy nhiên, đối với mục đích của chúng ta, các ký hiệu này là tương đương và chúng ta sẽ sử dụng chúng song song. Nếu n là số tự nhiên, ta có thể viết (1.8) là: Ckn = Ckn =n! k!(n − k)!. (1.9) Chúng ta sẽ lưu ý rằng đây chính xác là công thức cung cấp số tổ hợp không lặp lại n phần tử của lớp k (xem 1.3.3.) Và đây không phải là ngẫu nhiên (Tại sao?). Hệ số nhị thức có một số ứng dụng, ví dụ như trong khai triển của (a + b)n, do đó tên của chúng là: (a + b)n = C0nanb0 + C1nan−1b1 + · · · + Cnna0bn =n∑ i=0 Cinan−ibi. Có một số thuộc tính và công thức liên quan đến hệ số nhị thức [Knuth-1/1968]. Chúng ta sẽ xem xét một số trong số chúng trong đoạn này. Trong Bảng 1.3. các giá trị của Ckn được hiển thị, với 0 ≤ k ≤ n < 10. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.4. Những hệ số đa thức, tam giác Pascal và giai thừa 43 n C0n C1n C2n C3n C4n C5n C6n C7n C8n C9n 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 2 1 2 1 0 0 0 0 0 0 0 3 1 3 3 1 0 0 0 0 0 0 4 1 4 6 4 1 0 0 0 0 0 5 1 5 10 10 5 1 0 0 0 0 6 1 6 15 20 15 6 1 0 0 0 7 1 7 21 35 35 21 7 1 0 0 8 1 8 28 56 70 56 28 8 1 0 9 1 9 36 84 126 126 84 36 9 1 Bảng 1.3. Hệ số đa thức Một số tính chất của hệ số nhị thức trở nên rõ ràng nếu chúng ta phân tích Bảng 1.3 kỹ hơn, ví dụ: C0n = Cnn = 1, (1.10) Ckn = Cn−k n, (1.11) Ckn = Ckn−1 + Ck−1 n−1. (1.12) Nếu chúng ta loại bỏ các phần tử 0 khỏi Bảng 1.3. ở trên chúng ta sẽ nhận được một tam giác được gọi là tam giác Pascal: n = 0 1 n = 1 1 1 n = 2 1 2 1 n = 3 1 3 3 1 n = 4 1 4 6 4 1 n = 5 1 5 10 10 5 1 Hình 1.8. Tam giác Pascal Số đầu tiên và số cuối cùng trong mỗi hàng là 1 (theo sau từ thuộc tính (1.10) và (1.11)), và lấy nhau dưới dạng tổng của hai số ở Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 44 Chương 1. Số học và thuật toán trên nó (thuộc tính (1.12)). Do đó, các hệ số của bậc n có thể được tìm thấy nếu chúng ta có bậc (n − 1). Nếu chúng ta tìm Ckn = Ckn và bắt đầu từ hàng đầu tiên, chúng ta có thể tìm thấy tất cả các hàng cho đến thứ n và giá trị ở vị trí thứ k sẽ chính xác là Ckn. Lưu ý rằng khi tính toán các giá trị trong hàng i, chúng ta chỉ sử dụng các giá trị của hàng i − 1, chứ không sử dụng các giá trị trước đó. Sau đây là cách triển khai trực tiếp trong ngôn ngữ C: chúng ta sẽ giữ hàng được tính cuối cùng trong mảng lastLine[], và các tham số n và k cho Ckn bắt buộc được định nghĩa ở đầu chương trình dưới dạng hằng số. Chương trình 1.15. Tam giác Pascal (118pascalt.c) #include // Cỡ lớn nhất của tam giác #define MAXN 1000 unsigned n = 7; unsigned k = 3; unsigned long lastLine[MAXN + 1]; int main(void) { unsigned i, j ; lastLine[0] = 1; for (i = 1; i <= n; i++) { lastLine[i] = 1; for (j = i - 1; j >= 1; j--) lastLine[j] += lastLine[j - 1]; } printf("C(%u,%u) = %lu\n", n, k, lastLine[k]); return 0; } Chúng ta sẽ đề xuất một thuật toán khác dựa trên công thức (1.8) và trình bày một sơ đồ hữu ích để giảm các phân số hữu tỉ có tử số và mẫu số lớn. Nếu chúng ta thử tính toán trực tiếp trên (1.9) n! và k!(n − k)!, trong nhiều trường hợp thu được kết quả trung gian lớn, trong khi kết quả cuối cùng không phải là một số lớn như vậy: ví dụ, với n = 100 và k = 2, chúng ta sẽ phải tính 100! và 2!.98! (các số trên 150 chữ số), và kết quả của C2100 chỉ là 4950. Thuật toán 2 để tìm Ckn(với thừa số hóa) Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.4. Những hệ số đa thức, tam giác Pascal và giai thừa 45 1. Như một ví dụ, chúng ta sẽ xem xét C37. Chúng ta sẽ biểu diễn tử số của công thức (1.8) dưới dạng tích của các số, mỗi số chúng ta sẽ phân tích thành các thừa số nguyên tố. Bây giờ chúng ta có thể phân tích toàn bộ tác phẩm: đối với ví dụ 7! = 1.2.3...7 = 1.2.3.22.5.(2.3).7 = 24.32.51.71. 2. Tương tự, chúng ta phân tích mẫu số: 3!.(7 − 3)! = 1.2.3.1.2.3.22 = 24.32. 3. Viết tắt tử số và mẫu số: 24.32.51.71 24.32=51.71 1. 4. Sau khi rút gọn ta thực hiện các phép nhân còn lại ở tử số và được kết quả như ý: 51.71 = 35. Việc thực hiện thuật toán 2 như sau. Chương trình 1.16. Tính hệ số Newton (119cnk.c) #include #define MAXN 500 unsigned long n = 7; unsigned long k = 3; unsigned long pN, primes[MAXN], counts[MAXN]; void modify(long int x, int how) { unsigned i; for (i = 0; i < pN; i++) if (x == primes[i]) {counts[i] += how; return;} counts[pN] = how; primes[pN++] = x; } void solve(unsigned long start, unsigned long end, unsigned long inc) { unsigned long prime, mul, how, i, max; for (i = start ; i <= end; i++) { mul = i; prime = 2; while (mul != 1) { for (how = 0; mul % prime == 0; mul /= prime, how++); if (how > 0) modify(prime, inc * how); prime++; } } Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 46 Chương 1. Số học và thuật toán } long int calc(void) { int i , j ; long int result = 1; for (i = 0; i < pN; i++) for (j = 0; j < counts[i]; j++) result *= primes[i]; return result; } int main(void) { printf("C(%lu,%lu)= ", n, k); pN = 0; if (n - k < k) k = n - k; solve(n - k + 1, n, 1); // phân tích tử số (n-k+1),...,n solve(1, k, -1); // phân tích mẫu số 1,...,k printf("%lu\n", calc()); return 0; } Một cách tiếp cận thuật toán như vậy (tính toán thừa số, tức là thực hiện các hành động với các số ở dạng thừa số nhân với thừa số nguyên tố) được áp dụng thành công không chỉ khi tìm Ckn, mà luôn luôn khi thu được các giá trị trung gian lớn ở tử số và mẫu số, trong khi bản thân kết quả không phải là quá tuyệt vời. Lưu ý: Trong chương trình trên, nếu cần, chúng ta áp dụng công thức "đảo ngược" dữ liệu đầu vào. Đồng thời, những vết cắt rõ ràng được thực hiện đầu tiên và chỉ sau đó là sự phân hủy. Bài tập . 1.35. Chứng minh các tính chất (1.10), (1.11) và (1.12) bằng cách sử dụng định nghĩa hệ số của nhị thức. Ví dụ, bằng chứng của (1.10) có thể được thực hiện như sau: . 1.36. Đưa ra các chứng minh tổ hợp của các tính chất (1.10), (1.11) và (1.12). . 1.37. Thuật toán đề xuất 1 (pascalt.c) yêu cầu một mảng lastLine[] với n + 1 phần tử để tìm Ckn và ở các giá trị cao hơn của n, việc cấp Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.5. Hệ số đếm và sự biến đổi hệ 47 phát nhiều bộ nhớ như vậy sẽ không thể thực hiện được. Có thể sửa đổi nó theo cách sau: vòng lặp bên trong, lấp đầy hàng tiếp theo của tam giác, nên được thực hiện không phải từ 1 đến i, mà từ 1 đến k, vì đoạn của tam giác không còn quan tâm đến chúng ta. Lưu ý rằng khi k gần với n, chúng ta có thể áp dụng tính chất (1.11) và tìm Cn−k n thay cho Ckn. 1.5. Hệ số đếm và sự biến đổi hệ Nói chung, chúng ta có thể định nghĩa hệ thống số như một tập hợp các dấu hiệu đồ họa và các quy tắc để biểu diễn các số. Trong các thời đại khác nhau của sự phát triển lịch sử của nhân loại, nhiều hệ thống số khác nhau đã được sử dụng, phổ biến nhất ngày nay là hệ thống số Ả Rập. Nó sử dụng một hoặc nhiều ký hiệu đồ họa 0, 1, 2, 3, 4, 5, 6, 7, 8 và 9, được gọi là số, để đại diện cho các số tự nhiên. Thế giới Ả Rập khác với mười biểu tượng đồ họa được đề cập ở trên, nhưng nó là cùng một hệ thống số.). Số chữ số dùng để viết số sẽ được gọi là cơ sở của hệ thống. Ví dụ, hệ thống chữ số Ả Rập là hệ thập phân (sử dụng 10 chữ số). Cũng có những khái niệm khái quát về cơ số, cho phép nó là một số thực (môđun khác 0 và 1) tùy ý (hoặc thậm chí phức) với một dấu. Trong trường hợp chúng ta có p < 0 đối với cơ số p của hệ thống số, các số âm sẽ được viết mà không sử dụng dấu "-" một cách rõ ràng. Các hệ thống khác đóng một vai trò đặc biệt trong số học máy tính - hệ nhị phân, hệ thập lục phân và một phần là hệ bát phân. Hệ thống số nhị phân sử dụng các chữ số 0 và 1 để viết số. Ví dụ: số thập phân 11(10)sẽ giống như 1011(2)(Chúng ta sẽ sử dụng dấu ngoặc đơn và một phông chữ nhỏ để chỉ ra cơ sở của hệ thống số). . Cần có 16 chữ số để viết số trong hệ thống số thập lục phân. Do đó, ngoài các chữ số từ 0 đến 9 của hệ thống số thập phân, các chữ cái in hoa A, B, C, D, E và F được sử dụng, với các giá trị 10, 11, 12, 13, 14 và 15, tương ứng. số 254(10) được biểu thị là FE(16). Bằng phương pháp phân tích toán học, có thể chỉ ra rằng hệ thống số tối ưu là hệ thống có cơ số e = 2, 718281828...(số e định nghĩa như an = 1 +1n nvới n → ∞). Ở đây, tối ưu có nghĩa là tỷ lệ tốt nhất giữa độ dài bản ghi của một số trong hệ thống tương ứng Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 48 Chương 1. Số học và thuật toán và số chữ số được sử dụng bởi hệ thống. Vì số e là số vô tỷ (nó không thể được biểu diễn dưới dạng tỷ số của hai số nguyên), làm việc với hệ thống này là không thuận tiện và theo nghĩa này, chúng ta có thể coi các hệ thống số tối ưu dựa trên 3 và 2. Từ quan điểm toán học, hệ thống số bậc ba là thích hợp hơn vì số 3 gần với e hơn. Tuy nhiên, từ quan điểm kỹ thuật thuần túy, hệ thống số nhị phân được ưu tiên hơn. Hệ thống số nhị phân cực kỳ thuận tiện cho việc thực hiện kỹ thuật - ở 0 điện áp là 0V được so sánh và ở 1 − 5 V. Hầu như tất cả các máy tính hiện đại đều hoạt động trong hệ thống số nhị phân. Trước đây ở Liên Xô cũng đã có những máy móc hoạt động với hệ số đối xứng bậc ba, ví dụ như Setun, được tạo ra vào năm 1960 tại Moscow, sử dụng các số −1, 0 và 1. Ý nghĩa của hệ thập lục phân được xác định bởi thực tế rằng 16 là lũy thừa của 2(16 = 24). Cần 4 bit (chữ số nhị phân - 0 và 1) để mã hóa các số từ 0 đến 15. Để tạo điều kiện thuận lợi cho quá trình xử lý của chúng, các bit nhị phân này được nhóm thành các byte - nhóm 8 bit. Dễ dàng nhận thấy rằng các số từ 0 đến 255 có thể được viết trong một byte, tức là 256 số khác nhau. Vì 256 = 162 nên mỗi byte có thể được biểu diễn bằng hai chữ số thập lục phân liên tiếp. Việc chuyển từ hệ nhị phân sang hệ thập lục phân rất đơn giản - số nhị phân được chia từ phải sang trái thành các tứ phân (4 bit liên tiếp) và nếu cần thì bên trái được bổ sung bằng các số không, sau đó mỗi tứ phân được chuyển đổi riêng rẽ thành một hệ thập lục phân tương ứng chữ số. Chúng ta sẽ minh họa phương pháp vừa được mô tả bằng cách chuyển đổi số 10101000110111(2)sang hệ thống số thập lục phân. Chúng ta chia nó thành các sổ ghi chép: 10|1010|0011|0111 và thêm các số không vào nó: 0010|1010|0011|0111 Bây giờ chúng ta mã hóa mỗi sổ ghi chép bằng chữ số thập lục phân tương ứng của nó và thu được 2A37(16). Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.5. Hệ số đếm và sự biến đổi hệ 49 Tình hình cũng tương tự khi chuyển từ hệ thống số nhị phân sang hệ bát phân, trong trường hợp đó số được chia thành các bộ ba (ba chữ số nhị phân liên tiếp). Dưới đây chúng ta sẽ xem xét một phương pháp tổng quát hơn để chuyển đổi giữa các hệ thống số. Lưu ý rằng bản ghi số không thể xác định rõ ràng nó được viết trong hệ thống số nào. Ví dụ, đối với số 153, chúng ta chỉ có thể nói rằng nó có ít nhất là 6. Thực tế, dựa trên ý nghĩa của các số 1, 5 và 3, chúng ta có thể nói rằng số đó được viết trong một hệ thống dựa trên ít nhất 3 , bởi vì Có 3 chữ số khác nhau, có thể được hiểu là 0, 1 và 2. Để tránh những hiểu lầm như vậy, theo thông lệ, chúng ta chỉ định trong ngoặc sau số đó bằng phông chữ nhỏ hơn, như trên, cơ sở của hệ thống được sử dụng . Hệ thống chữ số Ả Rập là vị trí, tức là giá trị của các chữ số không được xác định chặt chẽ và thay đổi tùy thuộc vào vị trí của chữ số. Ví dụ, trong số 123, số 3 có giá trị là 3, trong khi ở số 34, nó có giá trị là 30. Cũng có các hệ thống số không vị trí (xem 1.1.7.), Trong đó giá trị của mỗi dấu hiệu được cố định nghiêm ngặt và không phụ thuộc vào vị trí mu. Nói chung có hai phương pháp để viết một số trong một hệ thống số: kỹ thuật số và đa thức. Ghi âm kỹ thuật số thường được ưu tiên là ngắn hơn. Trong trường hợp này, các chữ số tương ứng của số được viết liền kề nhau và giá trị của chúng tăng từ phải sang trái theo một cấp số nhân hình học với một phần p, trong đó p là cơ sở của hệ thống số được sử dụng. Ký hiệu số có dạng anan−1...a0(p), trong đó ai(1 ≤ i ≤ n) là một chữ số. Trong một bản ghi đa thức, số có dạng: A = an pn + an−1 pn−1 + ...a1 p + a0 Kí hiệu đa thức rất hữu ích khi chuyển từ hệ thống số này sang hệ thống số khác, như chúng ta sẽ thấy bên dưới. Bài tập . 1.38. Tại sao cơ sở của hệ thống số phải là môđun khác 0 và 1? . 1.39. Để trình bày các số 17 và −17 trong một hệ thống số, hãy dựa vào: 2;s8; 16. . 1.40. Để trình bày các số 17 và −17 trong một hệ thống số, dựa Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 50 Chương 1. Số học và thuật toán vào −2; −8; −16. . 1.41. Không cần thông qua hệ thập phân, chuyển đổi các số nhị phân: 111, 110100, 1110100101, 10010101, 10101010101 và 10111110101 sang hệ thống số thập lục phân. . 1.42. Không cần thông qua hệ thập phân, chuyển các số nhị phân: 11, 11001, 1010101, 111111, 1010101000, 10101101000 và 11010111000 thành một hệ thống số bát phân. . 1.43. Kí hiệu đa thức của một số trong hệ thống số đối xứng có dạng như thế nào? . 1.44. Biểu diễn các số 17 và −17 trong một hệ số đối xứng bậc ba. 1.5.1. Chuyển hệ cơ số 10 sang cơ số p Dựa vào cách biểu diễn một số ở dạng đa thức, ta có thể xây dựng thuật toán chuyển từ hệ thập phân sang hệ số p như sau: chia số A cho p theo thương và dư cho đến khi A trở thành 0, sau đó viết ngược lại số dư. đơn đặt hàng. biên nhận của họ (Tại sao?). Ví dụ, khi chuyển đổi số 29 thành một hệ thống số nhị phân, chúng ta nhận được (với chữ in nghiêng dưới mỗi phép chia là phần dư tương ứng): 29 : 2 = 14 : 2 = 7 : 2 = 3 : 2 = 1 : 2 = 0 1 0 1 1 1 Ta lấy các số dư còn lại thu được theo thứ tự ngược lại ta được: 29(10) = 11101(2). Hàm convert () thực hiện chuyển đổi và trả về kết quả là một chuỗi ký tự: Hàm chuyển đổi convert() trong 120base.c char getChar(char n) //Trả về ký hiệu tương ứng với $n$ { return (n < 10) ? n + ’0’ : n + ’A’ - 10; } void reverse(char *pch) { char *pEnd; Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.5. Hệ số đếm và sự biến đổi hệ 51 for (pEnd = pch + strlen(pch) - 1; pch < pEnd; pch++, pEnd--) { char c = *pch; *pch = *pEnd; *pEnd = c; } } void convert(char *rslt , unsigned long n, unsigned char base) / /Chuyển đổi số nguyên hệ thập phân n (n >= 0) / /thành hệ đếm có cơ sở { char *saveRslt = rslt ; while (n > 0) { * rslt ++ = getChar((char)(n % base)); n /= base; } * rslt = ’\0’; reverse(saveRslt); } Nếu số nhỏ hơn 1, lại có một ký hiệu ở dạng đa thức, trong trường hợp đó sẽ thu được một đa thức bậc âm của p. Khi chuyển A sang hệ số p, mọi thứ hoàn toàn ngược lại với trường hợp của một số tự nhiên: Ta nhân A với p, tách các phần nguyên và viết chúng theo thứ tự nhận. Ví dụ: chuyển đổi 0,125 thành một hệ thống số nhị phân trông giống như sau: 0, 125, 2 = 0, 25.2 = 0, 5.2 = 1, 0 Ta được 0, 125(10) = 0, 001(2). Ở đây một vấn đề khác nảy sinh - ký hiệu của A trong hệ số thứ p có thể là một phân số vô hạn (không tuần hoàn). Do đó, sẽ là khôn ngoan nếu giới thiệu một số chính xác số chữ số tối đa sau dấu thập phân. Hàm convertLessThan1()chuyển đổi số A(0 ≤ A < 1) thành cnt chữ số gần nhất sau dấu thập phân, bỏ qua các chữ số sau. Hàm chuyển đổi convertLessThan1() trong 120base.c void convertLessThan1(char *rslt, double n, unsigned char base, unsigned char cnt) / /Chuyển một số 0<= n <1 vào hệ đếm với cơ số Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 52 Chương 1. Số học và thuật toán / /không lớn hơn cnt của số chữ số sau dấu phẩy thập phân. { while (cnt--) { / /Phải chăng ta không nhân 0? if (fabs(n) < EPS) break; / /Nhận chữ số tiếp theo n *= base; * rslt ++ = getChar((char)(int)floor(n)); n -= floor(n); } * rslt = ’\0’; } Sau khi thực hiện các hàm chuyển đổi riêng biệt cho các trường hợp A > 1 và 0 ≤ A < 1, nó vẫn tổ hợp chúng theo cách tự nhiên, cho phép chuyển đổi bất kỳ số thực nào, kể cả các số âm. Chúng ta nhận được hàm convertReal() Hàm chuyển đổi convertReal() trong 120base.c void convertReal(char *rslt, double n,unsigned char base, unsigned char cnt) / /Biến đổi một số thực n thanh hệ đếm cơ số cơ bản { double integer, fraction ; / / Tìm dấu của số if (n < 0) { * rslt ++ = ’-’ ; n = -n; } / /chia phần nguyên và phần thập phân fraction = modf(n, &integer); / / Chuyển đổi phần nguyên convert(rslt , (unsigned long)integer, base); / / Đặt dấu chấm thập phân theo dấu phẩy if (’\0’ == * rslt ) * rslt ++ = ’0’ ; else rslt += strlen( rslt ); * rslt ++ = ’ . ’ ; / / Chuyển phần thập phân convertLessThan1(rslt, fraction , base, cnt); if (’\0’ == * rslt ) { * rslt ++ = ’0’ ; Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.5. Hệ số đếm và sự biến đổi hệ 53 * rslt = ’\0’; } } Bài tập . 1.45. Tìm kí hiệu thập phân của số 126(8); 10101(2); 3F2B(16); 3CB(14). . 1.46. Tìm kí hiệu thập phân của số 0, 233(8); 0, 01(2); 0, 34(16); 0, 2A(14). . 1.47. Tìm kí hiệu thập phân của số 126, 233(8); 10101.01(2); 3F2B, 34(16); 3CB, 2A(14). . 1.48. Để chứng minh thuật toán được đề xuất để chuyển đổi từ p-cơ số sang thập phân. 1.5.2. Chuyển hệ cơ số p vào cơ số 10. Sơ đồ Horner Việc chuyển đổi từ chữ số p sang hệ thống số thập phân được rút gọn để tính giá trị của đa thức từ ký hiệu đa thức của A, vì tất cả các phép toán số học được thực hiện trong hệ thống số thập phân. Ví dụ, đối với 12734(8), chúng ta nhận được như sau: 12734(8) = 1.84 + 2.83 + 7.82 + 3.8 + 4 = 5596(10) Lưu ý rằng chúng ta cần 10 phép nhân để tính toán. Chúng ta có thể giảm đáng kể con số này nếu chúng ta giữ các lũy thừa đã được tính ở mức 8, thay vì đếm lại chúng mỗi lần. Tuy nhiên, có một phương pháp khác tổng quát hơn cho phép chúng ta tính giá trị của đa thức bậc n với không quá n phép nhân n công thức của Horner. Ý tưởng là sử dụng (2) thay vì loại (1) trong phép tính. (1) Pn(x) = a0xn + a1xn−1 + · · · + an−1x + an (2) Pn(x) = an + x(an−1 + x(an−2 + · · · + x(a2 + x(a1 + xa0))...)) - công thức của Horner Một ví dụ về triển khai cách tiếp cận này là hàm calculate (): Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 54 Chương 1. Số học và thuật toán Hàm tính toán calculate() trong 120base.c char getValue(char c) / /Trả về giá tr ị của ký hiệu { return (c >= ’0’ && c <= ’9’) ? c - ’0’ : c - ’A’ + 10; } unsigned long calculate(const char *numb, unsigned char base) / /Tìm giá tr ị thập phân của số numb, được cho trong hệ đếm với cơ s ố numb>=0 { unsigned long result; for (result = 0; ’\0’ != *numb; numb++) result = result*base + getValue(*numb); return result; } Theo cách tương tự, chúng ta có thể nhận ra phép biến đổi một số không âm nhỏ hơn 1. Trường hợp này không khác nhiều so với trường hợp biến đổi một số tự nhiên. Sự khác biệt duy nhất là ở đây đa thức có bậc âm của p. Hàm chuyển đổi calculateLessThan1() trong 120base.c cho số âm double calculateLessThan1(const char *numb, unsigned char base) / /Tìm giá tr ị thập phân của số numb (0= numb; end--) result = (result + getValue(*end)) / base; return result; } Cuối cùng, vẫn tổ hợp hai trường hợp để có được một hàm chuyển đổi một số thực tùy ý với một dấu: Hàm tổ hợp calculateReal() trong 120base.c cho số âm double calculateReal(char *numb, unsigned char base) / /Tìm giá tr ị thập phân của số thực numb, cho trong hệ đếm với cơ s ố cơ sở { char *pointPos; char minus; double result; / /Kiểm tra dấu âm if (’-’ == *numb) { Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.6. Chữ số la mã 55 minus = -1; numb++; } else minus = 1; if (NULL == (pointPos = strchr(numb, ’.’))) return calculate(numb, base); //Không có phần thập phân / /Tính phần nguyên *pointPos = ’\0’; result = calculate (numb, base); *pointPos = ’ . ’ ; / /thêm vào phần thập phân result += calculateLessThan1(pointPos+1, base); return minus*result; } Bài tập . 1.49. Tìm kí hiệu thập phân của số 126(8); 10101(2); 3F2B(16); 3CB(14). . 1.50. Tìm kí hiệu thập phân của số 0, 233(8); 0, 01(2); 0, 34(16); 0, 2A(14). . 1.51. Tìm kí hiệu thập phân của số 126, 233(8); 10101.01(2); 3F2B, 34(16); 3CB, 2A(14). . 1.52. Để chứng minh thuật toán được đề xuất để chuyển đổi từ hệ thống số p sang số thập phân. 1.6. Chữ số la mã Nhiều hệ thống được thảo luận ở trên, mặc dù khác nhau về cơ sở của chúng, đều thuộc cùng một lớp: vị trí. Đối với họ, cùng một hình có các giá trị khác nhau tùy thuộc vào vị trí của nó. Tuy nhiên, có những hệ thống số khác, được gọi là không có vị trí, trong đó giá trị của các chữ số riêng lẻ là cố định và không phụ thuộc vào vị trí của nó. Một ví dụ kinh điển về vấn đề này là hệ thống chữ số La Mã. Nó sử dụng 7 chữ cái Latinh viết hoa để biểu thị các số tự nhiên Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 56 Chương 1. Số học và thuật toán trong phạm vi [1; 3999] (các giá trị tương ứng của chúng được cho trong ngoặc): I (1), V (5), X (10), L (50), C (100), D (500) và M (1000). Ví dụ, số 1989 được ghi là MCMLXXXIX. 1.6.1. Biểu diễn số thập phân thành chữ số La mã Chúng ta sẽ không đi sâu chi tiết vào các thuộc tính của hệ thống số La Mã. Chúng ta sẽ chỉ lưu ý rằng khi một hình nhỏ hơn đứng trước một hình lớn hơn, giá trị của nó sẽ bị trừ đi giá trị của hình lớn hơn. Nếu không, hãy thêm: X I = 10 + 1 = 11 IX = 10 − 1 = 9 Mỗi chữ số có thể được theo sau bởi bất kỳ chữ số nào nhỏ hơn. Tuy nhiên, có những giới hạn đối với số lượng chữ số liên tiếp của cùng một giá trị, cũng như chữ số nhỏ hơn có thể đứng trước chữ số lớn hơn nào. Điều này được thấy rõ trong Bảng 1.4. 1(I) 2(II) 3(III) 4(IV) 5(V) 6(VI) 7(VII) 8(VIII) 9(IX) 10(X) 20(XX) 30(XXX) 40(XL) 50(L) 60(LX) 70(LXX) 80(LXXX) 90(XC) 100(C) 200(CC) 300(CCC) 400(CD) 500(D) 600(DC) 700(DCC) 800(DCCC) 900(CM) Bảng 1.4. Ghi lại một số số bằng chữ số La mã. Chương trình 1.17. Chuyển số thập phân thành La Mã và ngược lại (121rom2dec.c) #define MAX_ROMAN_LEN 20 #include #include const char *roman1_9[] = {"", "A", "AA", "AAA", "AB", "B", "BA", " BAA", "BAAA", "AC"}; const char *romanDigits[] = {"IVX", "XLC", "CDM", "M" }; const char *roman2test = "MCMLXXXIX"; void getRomanDigit(char *rslt, char x, unsigned char power) { const char *pch; for (pch = roman1_9[x]; ’\0’ != *pch; pch++) * rslt ++ = romanDigits[power][*pch - ’A’]; * rslt = ’\0’; } Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.6. Chữ số la mã 57 / /Chuyển số cơ số 10 thành số La Mã char *decimal2Roman(char *rslt, unsigned x) { unsigned char power; char buf[10]; char oldRslt[MAX_ROMAN_LEN]; for (* rslt = ’\0’, power = 0; x > 0; power++, x /= 10) { getRomanDigit(buf, (char)(x % 10), power); strcpy(oldRslt, rslt ); strcpy(rslt,buf); strcat(rslt,oldRslt); } return rslt; } / /Chuyển số La Mã thành số cơ số 10 unsigned roman2Decimal(const char *roman, char *error) { unsigned rslt, value, old; const char *saveRoman = roman; char buf[MAX_ROMAN_LEN]; old = 1000; rslt = 0; while (’\0’ != *roman) { switch (*roman++) { case ’I’ : value = 1; break; case ’V’: value = 5; break; case ’X’: value = 10; break; case ’L’: value = 50; break; case ’C’: value = 100; break; case ’D’: value = 500; break; case ’M’: value = 1000; break; default: *error = 1; return (unsigned)(-1); } rslt += value; if (value > old) rslt -= 2*old; old = value; } return (*error = strcmp(saveRoman,decimal2Roman(buf,rslt))) ? (unsigned)(-1) : rslt ; } Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 58 Chương 1. Số học và thuật toán int main(void) { unsigned decimal; char error; decimal = roman2Decimal(roman2test,&error); if (error) printf("chuong trinh bi loi! "); else printf("Ket qua chuyen doi %u", decimal); return 0; } Bài tập . 1.53. Viết bằng số La mã: 10; 19; 159; 763; 1991; 1979; 1997; 2002 . 1.54. Viết dưới dạng số La mã: 0; −10; 0, 28; 3, 14; 1/7. . 1.55. Chứng minh thuật toán được đề xuất để chuyển đổi một số thập phân thành một hệ thống chữ số La Mã. 1.6.2. Chuyển đổi chữ số La Mã sang số thập phân Ở đây mọi thứ đơn giản hơn. Lần này chúng ta sẽ xem xét các con số từ trái sang phải, chúng ta sẽ tính toán giá trị thập phân của chúng, và sau đó chúng ta sẽ tích lũy nó một số tiền. Nếu nó chỉ ra rằng chữ số trước đó có giá trị thập phân thấp hơn giá trị hiện tại, điều này có nghĩa là chữ số trước đó đáng lẽ không được thêm vào mà phải bị trừ đi. Vì trong trường hợp này, chúng ta đã cộng nó một lần, chúng ta nên trừ nó đi hai lần: if (value> old) rslt -- 2 * old; Ví dụ, đối với số 19 (XIX), con số I phải được trừ đi tổng, trong khi đối với số 21 (XXI) - nó phải được thêm vào. Một vấn đề khác nảy sinh: làm thế nào để kiểm tra xem dãy số La Mã được cho dưới dạng tham số của roman2Decimal() có phải là một số La Mã chính xác hay không? Việc kiểm tra này rất phức tạp, nhưng chúng ta có thể làm cho mọi thứ đơn giản hơn nhiều. Với mục đích này, chỉ cần thực hiện phép biến đổi nghịch đảo và so sánh kết quả thu được với số ban đầu là đủ. Chi tiết có thể được nhìn thấy từ việc thực hiện được đề xuất. Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.7. Hồi quy và lặp lại 59 Hãy xem nội dung hàm số unsigned roman2Decimal(const char *roman, char *error) trong chương trình trên. Bài tập . 1.56. Viết các chữ số La Mã trong hệ thập phân: DCLXXXIV, DC CLXIV, LX, LXX, LXXX, XL, XXL, XXXL. . 1.57. Để chứng minh thuật toán được đề xuất để chuyển đổi một số La Mã thành một hệ thống số thập phân. . 1.58. Viết chương trình kiểm tra dãy số La Mã có phải là chữ số La Mã viết đúng mà không qua hệ thống số thập phân hay không. Để làm được điều này, hãy quan sát kỹ các mẫu trong Bảng 1.4. 1.7. Hồi quy và lặp lại Một câu nổi tiếng trong lập trình dân gian là: "Để xác định khái niệm đệ quy, trước tiên chúng ta phải xác định khái niệm đệ quy." Có rất nhiều "định nghĩa" như vậy trong thế giới UNIX (ví dụ, GNU là viết tắt của GNU không là UNIX, WINE là viết tắt của WINE không là Emulator, v.v.). Định nghĩa 1.17. Một đối tượng được gọi là đệ quy nếu nó được chứa trong chính nó hoặc được định nghĩa bởi chính nó. Trong tin học máy tính, đệ quy là một trong những kỹ thuật lập trình mạnh mẽ nhất: nó định nghĩa các thuật toán một cách trang nhã, tạo ra các cấu trúc dữ liệu thuận tiện và linh hoạt. Trong nhiều trường hợp, việc sử dụng đệ quy có thể dẫn đến các thuật toán không hiệu quả. Mục đích của đoạn này, ngoài việc giới thiệu đệ quy như một cách tiếp cận thuật toán cơ bản, sẽ là khám phá câu hỏi khi nào ứng dụng của nó hữu ích trong thực tế. Phương tiện của biểu thức đệ quy trong chương trình C là các hàm. Nếu trong phần thân của một hàm P đã cho có tham chiếu đến chính nó, chúng ta nói rằng nó trực tiếp đệ quy. Một kịch bản “phức tạp hơn” cũng có thể xảy ra: hàm P1 chuyển thành hàm P2, Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 60 Chương 1. Số học và thuật toán P2 thành P3, ..., Pn thành P1. Trong trường hợp này chúng ta nói rằng P1, cũng như P2, P3, ..., Pn, là các hàm đệ quy gián tiếp (gián tiếp). Khi lập trình các hàm đệ quy, một số điều kiện quan trọng phải được xem xét: 1. bài toán chúng ta đang xem xét nên được chia thành các bài toán con mà (đệ quy) cùng một thuật toán có thể được áp dụng. Kết hợp các giải pháp của tất cả các bài toán phụ sẽ dẫn đến một giải pháp của bài toán ban đầu. 2. Thực hiện một thuật toán đệ quy, chúng ta phải chắc chắn rằng sau một số bước hữu hạn, chúng ta sẽ đạt được một kết quả cụ thể, tức là phải có một số hữu hạn các trường hợp đơn giản (ít nhất một) mà lời giải của chúng có thể được tìm thấy trực tiếp. Thông thường người ta gọi chúng là đáy của đệ quy. 3. Tất cả các bài toán phụ của bài toán phải "khao khát" một trong những trường hợp đơn giản này, tức là sau một số lần gọi đệ quy hữu hạn để đạt đến đáy của đệ quy (Tương tự, trong các công thức truy hồi, cũng như trong suy luận quy nạp, cần phải có một cơ số.). Một vài ví dụ đầu tiên về các hàm C đệ quy mà chúng ta sẽ trình bày sẽ chứng minh việc tính toán các hàm toán học được xác định tuần hoàn. 1.7.1. Tính giai thừa Định nghĩa về giai thừa, cũng như phép tính lặp lại của hàm, chúng ta đã xem xét trong 1.1.1. Để thực hiện một hàm tính giai thừa đệ quy, chúng ta phải chắc chắn rằng hai điều kiện chính được đáp ứng: • Dưới cùng của đệ quy là trường hợp đơn giản n = 0 - khi đó giá trị của hàm là 1. • Trong tất cả các trường hợp khác, chúng ta giải quyết bài toán con cho n − 1 và nhân kết quả với n. Do đó tham số đệ quy giảm đơn điệu và sẽ đạt đến đáy của đệ quy sau một số bước hữu hạn (giữa n và 0 có một số lượng tự nhiên hữu hạn). Sau đây là một hàm của C, tính toán đệ quy n!: Chương trình 1.18. Tính giai thừa (121factrec.c) Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.7. Hồi quy và lặp lại 61 #include const unsigned n = 6; unsigned long fact(unsigned i) { if (i < 2) return 1; return i * fact(i - 1); } int main(void) { printf("%u! = %lu \n", n, fact(n)); return 0; } Theo cách tương tự, chúng ta có thể tính toán một cách đệ quy tổng của n số tự nhiên đầu tiên (trực tiếp bằng định nghĩa truy hồi từ 1.1.1.): Tính tổng đệ quy unsigned long sum(unsigned n){ if (0 == n) return 0; else return n + sum(n - 1); } Có thể nhận thấy một số điều trong các triển khai trên: khi một hàm toán học được xác định lặp lại được đưa ra, việc thực hiện một hàm C đệ quy tương ứng không khó, trong khi thuật toán lặp (tuần tự) để giải trong một số trường hợp, đặc biệt là khi hàm nhiều hơn phức tạp, không phải là quá rõ ràng. (xem 1.2.2.) Mặt khác, bộ nhớ bị tiêu tốn nhiều hơn. Điều này là do mỗi lần gọi đệ quy đến hàm trong ngăn xếp hệ thống sẽ cấp phát bộ nhớ mới cho các đối số và biến cục bộ, cũng như cho các kết quả được trả về bởi hàm. Trong các ví dụ trên, n sẽ là bắt buộc. sizeof (không dấu) byte bộ nhớ cho n cuộc gọi đệ quy. Để so sánh: chương trình tìm n! từ 1.1.1. đã sử dụng một biến duy nhất trong đó kết quả được tích lũy, tức là bộ nhớ kém hơn nhiều lần. Tuy nhiên, trong những ví dụ này, bộ nhớ không phải là một yếu tố quan trọng, vì sự phát triển nhanh chóng của n! chúng ta sẽ nhận được tràn số nguyên dài không dấu chứ không phải là thiếu bộ nhớ. Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 62 Chương 1. Số học và thuật toán 1.7.2. Dãy Phibonacci Số Fibonacci là một trong những ví dụ yêu thích của một số cuốn sách và sách hướng dẫn về thuật toán cho sự sang trọng của đệ quy như một kỹ thuật lập trình. Vì lý do này, đôi khi chúng ta sẽ không cưỡng lại sự cám dỗ để đi sâu vào chi tiết hơn về lịch sử, bản chất và tính chất của chúng, mà chúng ta tin rằng sẽ không khiến người đọc khó chịu. Hình 1.9. Số Fibonacci trong kiến trúc và nghệ thuật Bất cứ ai đã từng tham gia vào lập trình ít nhất một chút đều không tránh khỏi việc gặp phải những con số Fibonacci. Tại sao? Có một loạt các thuật toán và bài toán lập trình, dường như không liên quan theo bất kỳ cách nào, dựa trên những con số này. Sẽ không quá lời khi nói rằng sự hiện diện và vai trò của chúng trong khoa học máy tính, toán học và tự nhiên nói chung là thực sự gây sốc. Chỉ cần biết cách quan sát, người ta có thể tìm thấy các số Fibonacci xung quanh mình: từ cách sắp xếp các đàn chim đang bay, qua các hình nón và bài thơ, bánh hướng dương và các bản giao hưởng, Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.7. Hồi quy và lặp lại 63 nghệ thuật cổ đại (xem Hình 1.9) Và máy tính hiện đại, đến tận hệ thống năng lượng mặt trời và các sàn giao dịch chứng khoán. Chính xác thì những con số nổi tiếng này là gì? Đây là những phần tử của số sau: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ..., Mỗi phần tử của chuỗi được lấy là tổng của hai phần trước, hai phần đầu theo định nghĩa lần lượt là 0 và 1. các công thức hợp lệ: F0 = 0, F1 = 1, Fi = Fi−1 + Fi−2 Hình 1.10. Leonardo Fibonacci. Nhà nghiên cứu đầu tiên của dãy số trên là Leonardo Pisano (Leonardo of Pisa), hay còn được biết đến với cái tên Leonardo Fi bonacci (Filius Bonaccii, tức là con trai của Bonacio), người vào năm 1202 trong cuốn sách Liber Abacci (Sách đếm) đã đưa ra bài toán nổi tiếng của mình đối với thỏ. . Bài toán là tìm số thỏ sẽ có được từ một cặp trong một năm với các điều kiện sau: • mỗi cặp thỏ đậu quả sẽ tăng thêm hai con mỗi tháng; • thỏ mới kết trái khi được một tháng tuổi; • Thỏ không bao giờ chết. Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 64 Chương 1. Số học và thuật toán Như vậy, trong một tháng, chúng ta sẽ có hai cặp thỏ, sau đó là 3 cặp, tháng sau chúng ta sẽ có 5 cặp (một cặp thỏ mới ban đầu và một - của cặp đã nhận được trong tháng đầu tiên), vào tháng sau. chúng ta sẽ có tổng cộng 8 cặp đôi, v.v. Rõ ràng là quá trình được mô tả có thể diễn ra vô thời hạn. (xem Hình 1.12). Hình 1.11. Số Fibonacci trong tự nhiên. Sau đó vào năm 1611, Kepler, không biết về nghiên cứu của Fi bonacci, đã khám phá lại một số nghiên cứu của mình về sự sắp xếp các lá của một số cây trên thân cây (Hình 1.11). Nói chung, như đã đề cập ở trên, số Fibonacci có bản chất cực kỳ phổ biến, rất có thể là kết quả của các quá trình tương tự như của bài toán Fibonacci đối với thỏ. Mối quan hệ giữa số Fibonacci và thuật toán là gì? Mối liên hệ đầu tiên là chính Leonardo Fibonacci, người đã siêng năng nghiên cứu các tác phẩm của al-Khwarizmi (từ tên mà thuật toán từ bắt nguồn, như chúng ta đã đề cập trong chương giới thiệu). Sau đó, vào năm 1845, Lame sử dụng dãy Fibonacci trong quá trình nghiên cứu thuật toán Euclid nổi tiếng (xem 1.2.3) để tìm ước số chung lớn nhất. Kể từ đó, số Fibonacci dần dần bắt đầu chiếm vị trí xứng đáng trong việc phát triển và nghiên cứu các thuật toán khác nhau. Mối liên hệ giữa dãy Fibonacci và số sau rất thú vị φ =1 +√5 2= 1, 61803 Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/ 1.7. Hồi quy và lặp lại 65 Số của nó có một lịch sử rất thú vị và đã được mọi người biết đến từ thời cổ đại. Euclid gọi nó là tỷ số của số hữu hạn so với giá trị trung bình và định nghĩa nó là tỷ số của một cặp số A và B trong đó tỷ lệ có giá trị: B=A + B A A(= φ) Hình 1.12. Bài toán những con thỏ. Sau đó, vào thời kỳ Phục hưng, số φ được coi là một tỷ lệ thần thánh, và vào thế kỷ 19, nó có tên gọi cuối cùng như ngày nay: tỷ lệ vàng. Ký hiệu được chấp nhận φ xuất phát từ chữ cái đầu tiên trong tên của nhà điêu khắc Hy Lạp cổ đại Phidias, người thường sử dụng tỷ lệ này trong các tác phẩm điêu khắc của mình. Không khó để nhận thấy sự tương đồng giữa các định nghĩa về số Fibonacci và tỷ lệ vàng được đề xuất ở trên. Nó chỉ ra rằng tỷ lệ của hai số Fibonacci liên tiếp có xu hướng theo tỷ lệ vàng φ, và điều này đôi khi được xác định là giới hạn của tỷ lệ của hai số Fibonacci liên tiếp. (xem Hình1.12.) Lưu ý: Trước khi chúng ta chuyển sang các thuật toán tìm số Fibonacci, cần lưu ý rằng đôi khi có một định nghĩa khác, theo đó phần tử 0 của dãy Fibonacci là 1, không phải 0. Tất nhiên, định nghĩa sau không quá quan trọng. và người đọc, nếu cần, có thể dễ dàng Nguyễn Hữu Điển https://vietex.blog.fc2.com/ 66 Chương 1. Số học và thuật toán thay đổi các triển khai chương trình sau theo định nghĩa được ưu tiên. Hình 1.13. Mối quan hệ của hai số Fibonacci liên tiếp. Có lẽ cách thực hiện tự nhiên nhất của một hàm tìm số Fibonacci thứ n có được trực tiếp từ định nghĩa lặp lại được đưa ra ở trên: Chương trình 1.19. Tính Fibonacci (123fibrec.c) / / da oprawq w teksta / / fib(7) dawaha razlichno - da checkna koe e po definiciqta! ! ! #include const unsigned n = 7; unsigned long fib(unsigned n) { if (n < 2) return 1; else return fib(n - 1) + fib(n - 2); } int main() { printf("fib(%u) = %lu\n", n, fib(n)); return 0; } Mặc dù đủ đơn giản và có vẻ tự nhiên, nhưng nhận thức như vậy là cực kỳ kém hiệu quả. Người đọc có thể thử hàm trên, ví dụ với n = 40. Mỗi nghịch đảo đệ quy, ngoại trừ những nghịch đảo tầm thường (đối với n = 0 và 1), dẫn đến hai nghịch đảo nữa. Do đó cây bài toán con phát triển theo cấp số nhân. Đồng thời, nó hoàn Nguyễn Hữu Điển https://www.facebook.com/groups/vietex/