Bài giảng Các kỹ thuật lập trình

Nội dung text: Bài giảng Các kỹ thuật lập trình

1. HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG  KHOA CÔNG NGHỆ THÔNG TIN 1 BÀI GIẢNG CÁC KỸ THUẬT LẬP TRÌNH PTIT Hà Nội 2013
2. LỜI NÓI ĐẦU Sự phát triển công nghệ thông tin trong những năm vừa qua đã làm thay đổi bộ mặt kinh tế xã hội toàn cầu, trong đó công nghệ phần mềm trở thành một ngành công nghiệp quan trọng đầy tiềm năng. Với sự hội tụ của công nghệ viễn thông và công nghệ thông tin, tỷ trọng về giá trị phần mềm chiếm rất cao trong các hệ thống viễn thông cũng như các thiết bị đầu cuối. Chính vì lý do đó, việc nghiên cứu, tìm hiểu, tiến tới phát triển cũng như làm chủ các hệ thống phần mềm của các kỹ sư điện tử viễn thông là rất cần thiết. Môn học Kỹ thuật lập trình là môn học cơ sở bắt buộc đối với sinh viên chuyên ngành điện tử viễn thông và công nghệ thông tin của Học viện công nghệ Bưu chính Viễn thông. Cuốn giáo trình “Kỹ thuật lập trình”, được hình thành trên cơ sở các kinh nghiệm đã được đúc rút từ bài giảng của môn học Kỹ thuật lập trình cho sinh viên các ngành nói trên trong những năm học vừa qua với mục đích cung cấp cho sinh viên những kiến thức cơ bản nhất, có tính hệ thống liên quan tới môn học này. Khi học môn Kỹ thuật lập trình, sinh viên chỉ cần học qua môn “Tin học cơ sở” và chỉ cần thế các bạn đã có đủ kiến thức cơ sở cần thiết để tiếp thu kiến thức của Kỹ thuật lập trình. Thông qua cuốn giáo trình này, chúng tôi muốn giới thiệu với các bạn đọc về kỹ năng lập trình cấu trúc thông qua một số thuật toán quan trọng, bao gồm: Đại cương về lập trình cấu trúc; Con trỏ và mảng; Duyệt và đệ qui; Ngăn xếp, hàng đợi và danh sách móc nối; Cây; Đồ thị và cuối cùng là Sắp xếp và tìm kiếm. Phần phụ lục là bài tập tổng hợp lại những kiến thức cơ bản nhất đã được đề cập trong giáo trình và được thể hiện bằng một chương trình. Tuy đã rất chú ý và cẩn trọng trong quá trình biên soạn, nhưng giáo trình chắc chắn không tránh khỏi những thiếu sót và hạn chế. Chúng tôi xin chân thành mong bạn đọc đóng góp ý kiến để giáo trình nay ngày càng hoàn thiện hơn. Mọi sự đóng góp ý kiến xin gửi về Khoa Công nghệ thông tinPTIT – Học viện Công nghệ Bưu chính Viễn thông. Chúng tôi xin tỏ lòng biết ơn tới TS. Từ Minh Phương, giảng viên khoa Công nghệ thông tin – Học viện Công nghệ Bưu chính Viễn thông đã đọc và hiệu đính lại toàn bộ bản thảo của giáo trình này. Hà Nội, ngày 24 tháng 8 năm 2002 Các tác giả 1
3. MỤC LỤC CHƯƠNG 1. MỞ ĐẦU 5 1.1. Sơ lược về lịch sử lập trình cấu trúc 5 1.2. Cấu trúc lệnh - Lệnh có cấu trúc- Cấu trúc dữ liệu 6 1.2.1. Cấu trúc lệnh (cấu trúc điều khiển) 6 1.2.2. Lệnh có cấu trúc 8 1.2.3. Cấu trúc dữ liệu 8 1.3. Nguyên lý tối thiểu 10 1.3.1. Tập các phép toán 10 1.3.2. Tập các lệnh vào ra cơ bản 12 1.3.3. Thao tác trên các kiểu dữ liệu có cấu trúc 13 1.4. Nguyên lý địa phương 15 1.5. Nguyên lý nhất quán 16 1.6. Nguyên lý an toàn 18 1.6. Phương pháp Top-Down 19 1.7. Phương pháp Bottom - Up 24 BÀI TẬP CHƯƠNG 1 28 CHƯƠNG 2. MẢNG VÀ CON TRỎ 29 2.1. Cấu trúc lưu trữ mảng 29 2.1.1. Khái niệm về mảng 29 2.1.2. Cấu trúc lưu trữ của mảng một chiều 29 2.1.3. Cấu trúc lưu trữ mảng nhiều chiều 31 2.2. Các thao tác đối với mảng 32 2.3. Mảng và đối của hàm 34 2.4. Xâu kí tự (string) 36 2.5. Con trỏ (Pointer) PTIT 38 2.5.1. Các phép toán trên con trỏ 38 2.5.2. Con trỏ và đối của hàm 39 2.5.3. Con trỏ và mảng 40 BÀI TẬP CHƯƠNG 2 46 CHƯƠNG 3. DUYỆT VÀ ĐỆ QUI 53 3.1. Định nghĩa bằng đệ qui 53 3.2. Giải thuật đệ qui 54 3.3. Thuật toán sinh kế tiếp 55 3.3.1. Bài toán liệt kê các tập con của tập n phần tử 56 3.3.2. Bài toán liệt kê tập con m phần tử của tập n phần tử 58 3.3.3. Bài toán liệt kê các hoán vị của tập n phần tử 60 2
4. 3.3.4. Bài toán chia số tự nhiên n thành tổng các số nhỏ hơn 62 3.4. Thuật toán quay lui (Back track) 65 3.4.1. Thuật toán quay lui liệt kê các xâu nhị phân độ dài n 66 3.4.2. Thuật toán quay lui liệt kê các tập con m phần tử của tập n phần tử 67 3.4.3. Thuật toán quay lui liệt kê các hoán vị của tập n phần tử 69 3.4.4. Bài toán Xếp Hậu 70 3.5. Thuật toán nhánh cận 72 3.5.1. Thuật toán nhánh cận giải bài toán cái túi 74 3.5.2. Thuật toán nhánh cận giải bài toán người du lịch 78 BÀI TẬP CHƯƠNG 3 82 CHƯƠNG 4. NGĂN XẾP, HÀNG ĐỢI, DANH SÁCH LIÊN KẾT 89 4.1. Kiểu dữ liệu ngăn xếp và ứng dụng 89 4.1.1. Định nghĩa và khai báo 89 4.1.2. Các thao tác với stack 90 4.1.3. ứng dụng của stack 91 4.2. Hàng đợi (Queue) 96 4.2.1. Giới thiệu hàng đợi 96 4.2.2. ứng dụng hàng đợi 97 4.3. Danh sách liên kết đơn 103 4.3.1. Giới thiệu và định nghĩa 103 4.3.2. Các thao tác trên danh sách móc nối 104 4.3.3. ứng dụng của danh sách liên kết đơn 109 4.4. Danh sách liên kết kép 114 BÀI TẬP CHƯƠNG 4 128 CHƯƠNG 5. CÂY NHỊ PHÂN 132 5.1. Định nghĩa và khái niệm 132 5.2. Cây nhị phân 132 5.3. Biểu diễn cây nhị phân PTIT 134 5.3.1. Biểu diễn cây nhị phân bằng danh sách tuyến tính 134 5.3.2. Biểu diễn cây nhị phân bằng danh sách móc nối 135 5.4. Các thao tác trên cây nhị phân 135 5.4.1. Định nghĩa cây nhị phân bằng danh sách tuyến tính 135 5.4.2. Định nghĩa cây nhị phân theo danh sách liên kết: 135 5.4.3. Các thao tác trên cây nhị phân 135 5.5. Ba phép duyệt cây nhị phân (Traversing Binary Tree) 139 5.5.1. Duyệt theo thứ tự trước (Preorder Travesal) 140 5.5.2. Duyệt theo thứ tự giữa (Inorder Travesal) 140 5.5.3. Duyệt theo thứ tự sau (Postorder Travesal) 141 5.6. Cài đặt cây nhị phân bằng danh sách tuyến tính 141 5.7. Cài đặt cây nhị phân hoàn toàn cân bằng bằng link list 148 3
5. 5.8. Cài đặt cây nhị phân tìm kiếm bằng link list 153 BÀI TẬP CHƯƠNG 5 162 CHƯƠNG. ĐỒ THỊ (Graph) 166 6.1. Những khái niệm cơ bản về đồ thị 166 6.1.1. Các loại đồ thị 166 6.1.2. Các thuật ngữ cơ bản 169 6.1.3. Đường đi, chu trình, đồ thị liên thông 170 6.2. Biểu diễn đồ thị trên máy tính 171 6.2.1. Ma trận kề, ma trận trọng số 171 6.2.2. Danh sách cạnh (cung ) 173 6. 2.3. Danh sách kề 174 6.3. Các thuật toán tìm kiếm trên đồ thị 174 6.3.1. Thuật toán tìm kiếm theo chiều sâu 174 6.3.2. Thuật toán tìm kiếm theo chiều rộng (Breadth First Search) 176 6.3.3. Kiểm tra tính liên thông của đồ thị 179 6.3.4. Tìm đường đi giữa hai đỉnh bất kỳ của đồ thị 182 6.4. Đường đi và chu trình Euler 184 6.5. Đường đi và chu trình Hamilton 192 6.6. Cây bao trùm 196 6.6.1. Tìm một cây bao trùm trên đồ thị 197 6.6.2. Tìm cây bao trùm ngắn nhất 200 6.6.3. Thuật toán Kruskal 203 6.6.4. Thuật toán Prim 206 6.7. Bài toán tìm đường đi ngắn nhất 209 6.7.1. Thuật toán gán nhãn 209 6.7. 2. Thuật toán Dijkstra 210 6.7.3. Thuật toán Floy 213 BÀI TẬP CHƯƠNG 6 217 CHƯƠNG 7. SẮP XẾP VÀ TÌMPTIT KIẾM 221 7.1. Đặt bài toán 221 7.2. Giải thuật Selection Sort 222 7.3. Giải thuật Insertion Sort 224 7.4. Giải thuật Bubble Sort 226 7.5. Giải thuật Shaker Sort 227 7.6. Giải thuật Quick Sort 229 7.7. Giải thuật Heap Sort 231 7.8. Giải thuật Merge Sort 234 7.9. Tìm kiếm (Searching) 236 BÀI TẬP CHƯƠNG 7 241 4
6. CHƯƠNG 1. MỞ ĐẦU 1.1. Sơ lược về lịch sử lập trình cấu trúc Lập trình là một trong những công việc nặng nhọc nhất của khoa học máy tính. Có thể nói, năng suất xây dựng các sản phẩm phần mềm là rất thấp so với các hoạt động trí tuệ khác. Một sản phẩm phần mềm có thể được thiết kế và cài đặt trong vòng 6 tháng với 3 lao động chính. Nhưng để kiểm tra tìm lỗi và tiếp tục hoàn thiện sản phẩm đó phải mất thêm chừng 3 năm. Đây là hiện tượng phổ biến trong tin học của những năm 1960 khi xây dựng các sản phẩm phần mềm bằng kỹ thuật lập trình tuyến tính. Để khắc phục tình trạng lỗi của sản phẩm, người ta che chắn nó bởi một mành che mang tính chất thương mại được gọi là Version. Thực chất, Version là việc thay thế sản phẩm cũ bằng cách sửa đổi nó rồi công bố dưới dạng một Version mới, giống như: MS-DOS 4.0 chỉ tồn tại trong thời gian vài tháng rồi thay đổi thành MS-DOS 5.0, MS-DOS 5.5, MS-DOS 6.0 . . . Đây không phải là một sản phẩm mới như ta tưởng mà trong nó còn tồn tại những lỗi không thể bỏ qua được, vì ngay MS-DOS 6.0 cũng chỉ là sự khắc phục hạn chế của MS-DOS 3.3 ban đầu. Trong thời kỳ đầu của tin học, các lập trình viên xây dựng chương trình bằng các ngôn ngữ lập trình bậc thấp, quá trình nạp và theo dõi hoạt động của chương trình một cách trực tiếp trong chế độ trực tuyến (on-line). Việc tìm và sửa lỗi (debbugging) như ngày nay là không thể thực hiện được. Do vậy, trước những năm 1960, người ta coi việc lập trình giống như những hoạt động nghệ thuật nhuộm màu sắc cá nhân hơn là khoa học. Một số người nắm được một vài ngôn ngữ lập trình, cùng một số mẹo vặt tận dụng cấu hình vật lý cụ thể của hệ thống máy tính, tạo nên một số món lạ của phần mềm được coi là một chuyên gia nắm bắt được những bí ẩn của nghệ thuật lập trình. Các hệ thống máy tính trong giai đoạn này có cấu hình yếu, bộ nhớ nhỏ, tốc độ các thiết bị vào ra thấp làm chậm quáPTIT trình nạp và thực hiện chương trình. Chương trình được xây dựng bằng kỹ thuật lập trình tuyến tính mà nổi bật nhất là ngôn ngữ lập trình Assembler và Fortran. Với phương pháp lập trình tuyến tính, lập trình viên chỉ được phép thể hiện chương trình của mình trên hai cấu trúc lệnh, đó là cấu trúc lệnh tuần tự (sequential) và nhảy không điều kiện (goto). Hệ thống thư viện vào ra nghèo nàn làm cho việc lập trình trở nên khó khăn, chi phí cho các sản phẩm phần mềm quá lớn, độ tin cậy của các sản phẩm phần mềm không cao dẫn tới hàng loạt các dự án tin học bị thất bại, đặc biệt là các hệ thống tin học có tầm cỡ lớn. Năm 1973, Hoare khẳng định, nguyên nhân thất bại mà người Mỹ gặp phải khi phóng vệ tinh nhân tạo về phía sao Vệ nữ ( Sao Kim) là do lỗi của chương trình điều khiển viết bằng Fortran. Thay vì viết: DO 50 I = 12, 523 ( thực hiện số 50 với I là 12, 13, , 523) 5
7. Lập trình viên (hoặc thao tác viên đục bìa) viết thành: DO 50 I = 12.523 (Dấu phảy đã thay bằng dấu chấm) Gặp câu lệnh này, chương trình dịch của Fortran đã hiểu là gán giá trị thực 12.523 cho biến DO50I làm cho kết quả chương trình sai. Để giải quyết những vướng mắc trong kỹ thuật lập trình, các nhà tin học lý thuyết đã đi sâu vào nghiên cứu tìm hiểu bản chất của ngôn ngữ, thuật toán và hoạt động lập trình, nâng nội dung của kỹ thuật lập trình lên thành các nguyên lý khoa học ngày nay. Kết quả nổi bật nhất trong giai đoạn này là Knuth xuất bản bộ 3 tập sách mang tên “Nghệ thuật lập trình” giới thiệu hết sức tỉ mỉ cơ sở lý thuyết đảm bảo toán học và các thuật toán cơ bản xử lý dữ liệu nửa số, sắp xếp và tìm kiếm. Năm 1968, Dijkstra công bố lá thư “ Về sự nguy hại của toán tử goto”. Trong công trình này, Dijkstra khẳng định, có một số lỗi do goto gây nên không thể xác định được điểm bắt đầu của lỗi. Dijkstra còn khẳng định thêm: “Tay nghề của một lập trình viên tỉ lệ nghịch với số lượng toán tử goto mà anh ta sử dụng trong chương trình”, đồng thời kêu gọi huỷ bỏ triệt để toán tử goto trong mọi ngôn ngữ lập trình ngoại trừ ngôn ngữ lập trình bậc thấp. Dijkstra còn đưa ra khẳng định, động thái của chương trình có thể được đánh giá tường minh qua các cấu trúc lặp, rẽ nhánh, gọi đệ qui là cơ sở của lập trình cấu trúc ngày nay. Những kết quả được Dijikstra công bố đã tạo nên một cuộc cách mạng trong kỹ thuật lập trình, Knuth liệt kê một số trường hợp có lợi của goto như vòng lặp kết thúc giữa chừng, bắt lỗi . . ., Dijkstra, Hoare, Knuth tiếp tục phát triển tư tưởng coi chương trình máy tính cùng với lập trình viên là đối tượng nghiên cứu của kỹ thuật lập trình và phương pháp làm chủ sự phức tạp của các hoạt động lập trình. Năm 1969, Hoare đã phát biểu các tiên đề phục vụ cho việc chứng minh tính đúng đắn của chương trình, phát hiện tính bất biến của vòng lặp bằng cách coi chương trình vừa là bản mã hoá thuật toán đồng thời là bản chứng minh tính đúng đắn của chương trình. Sau đó Dahl, Hoare, Dijiksta đã phát triển thành ngôn ngữ lập trình cấu trúc. Để triển khai các nguyên lýPTIT lập trình cấu trúc, L. Wirth đã thiết kế và cài đặt ngôn ngữ ALGOL W là một biến thể của ALGOL 60. Sau này, L. Wirth tiếp tục hoàn thiện để trở thành ngôn ngữ lập trình Pascal. Đây là ngôn ngữ lập trình giản dị, sáng sủa về cú pháp, dễ minh họa những vấn đề phức tạp của lập trình hiện đại và được coi là một chuẩn mực trong giảng dạy lập trình. Năm 1978, Brian Barninghan cùng Denit Ritche thiết kế ngôn ngữ lập trình C với tối thiểu các cấu trúc lệnh và hàm khá phù hợp với tư duy và tâm lý của của người lập trình. Đồng thời, hai tác giả đã phát hành phiên bản hệ điều hành UNIX viết chủ yếu bằng ngôn ngữ C, khẳng định thêm uy thế của C trong lập trình hệ thống. 1.2. Cấu trúc lệnh - Lệnh có cấu trúc- Cấu trúc dữ liệu 1.2.1. Cấu trúc lệnh (cấu trúc điều khiển) 6
8. Mỗi chương trình máy tính về bản chất là một bản mã hoá thuật toán. Thuật toán được coi là dãy hữu hạn các thao tác sơ cấp trên tập đối tượng vào (Input) nhằm thu được kết quả ra (output). Các thao tác trong một ngôn ngữ lập trình cụ thể được điều khiển bởi các lệnh hay các cấu trúc điều khiển, còn các đối tượng chịu thao tác thì được mô tả và biểu diễn thông qua các cấu trúc dữ liệu. Trong các ngôn ngữ lập trình cấu trúc, những cấu trúc lệnh sau được sử dụng để xây dựng chương trình. Dĩ nhiên, chúng ta sẽ không bàn tới cấu trúc nhảy không điều kiện goto mặc dù ngôn ngữ lập trình cấu trúc nào cũng trang bị cấu trúc lệnh goto. Cấu trúc tuần tự Cấu trúc rẽ nhánh dạng đầy đủ câuA; lệnh GOTO. If (E) A; S E A Else B; Đ B A B; B Sau khi thực hiện lệnh A thì thực hiện lệnh B Nếu biểu thức E có giá trị đúng (khác 0) thì thực hiện A; Nếu E sai thì thực hiện B; Cấu trúc lặp với điều kiện trước Cấu trúc lặp với điều kiện sau While (E) A; do A S E A; S Đ Đ while (E); E A Thực hiện A cho tới khi nào E vẫn còn đúng; Trong khi biểu thức E còn có giá trị đúng thì thực hiện A; PTIT Cấu trúc lặp FOR For (E1; E2;E3) A; E1 E3 S Đ E2 A Thực hiện E1; kiểm tra E2 nếu E2 có giá trị đúng thì thực hiện A; Quá trình được lặp lại bằng việc thực hiện E3 và kiểm tra E2; 7
9. A, B : ký hiệu cho các câu lệnh đơn hoặc lệnh hợp thành. Mỗi lệnh đơn lẻ được gọi là một lệnh đơn, lệnh hợp thành là lệnh hay cấu trúc lệnh được ghép lại với nhau theo qui định của ngôn ngữ, trong Pascal là tập lệnh hay cấu trúc lệnh được bao trong thân của begin . . . end; trong C là tập các lệnh hay cấu trúc lệnh được bao trong hai ký hiệu { }. E, E1, E2, E3 là các biểu thức số học hoặc logic. Một số ngôn ngữ lập trình coi giá trị của biểu thức logic hoặc đúng (TRUE) hoặc sai (FALSE), một số ngôn ngữ lập trình khác như C coi giá trị của biểu thức logic là đúng nếu nó có giá trị khác 0, ngược lại biểu thức logic có giá trị sai. Cần lưu ý rằng, một chương trình được thể hiện bằng các cấu trúc điều khiển lệnh : tuần tự, tuyển chọn if else, switch . . case default, lặp với điều kiện trước while , lặp với điều kiện sau do . . while, vòng lặp for bao giờ cũng chuyển được về một chương trình, chỉ sử dụng tối thiểu hai cấu trúc lệnh là tuần tự và lặp với điều kiện trước while. Phuơng pháp lập trình này còn được gọi là phương pháp lập trình hạn chế. 1.2.2. Lệnh có cấu trúc Lệnh có cấu trúc là lệnh cho phép chứa các cấu trúc điều khiển trong nó. Khi tìm hiểu một cấu trúc điều khiển cần xác định rõ vị trí được phép đặt một cấu trúc điều khiển trong nó, cũng như nó là một phần của cấu trúc điều khiển nào. Điều này tưởng như rất tầm thường nhưng có ý nghĩa hết sức quan trọng trong khi xây dựng và kiểm tra lỗi có thể xảy ra trong chương trình. Nguyên tắc viết chương trình theo cấu trúc: Cấu trúc con phải được viết lọt trong cấu trúc cha, điểm vào và điểm ra của mỗi cấu trúc phải nằm trên cùng một hàng dọc. Ví dụ sau sẽ minh họa cho nguyên tắc viết chương trình: if (E) while (E1) A; PTITelse do B; while(E2); Trong ví dụ trên, while (E1) A; là cấu trúc con nằm trong thân của cấu trúc cha là if (E) ; còn do B while(E2); là cấu trúc con trong thân của else. Do vậy, câu lệnh while(E1); do . . . while(E2) có cùng cấp với nhau nên nó phải nằm trên cùng một cột, tương tự như vậy với A, B và if với else. 1.2.3. Cấu trúc dữ liệu 8
10. Các ngôn ngữ lập trình cấu trúc nói chung đều giống nhau về cấu trúc lệnh và cấu trúc dữ liệu. Điểm khác nhau duy nhất giữa các ngôn ngữ lập trình cấu trúc là phương pháp đặt tên, cách khai báo, cú pháp câu lệnh và tập các phép toán được phép thực hiện trên các cấu trúc dữ liệu cụ thể. Nắm bắt được nguyên tắc này, chúng ta sẽ dễ dàng chuyển đổi cách thể hiện chương trình từ ngôn ngữ lập trình này sang ngôn ngữ lập trình khác một cánh nhanh chóng mà không tốn quá nhiều thời gian cho việc học tập ngôn ngữ lập trình. Thông thường, các cấu trúc dữ liệu được phân thành hai loại: cấu trúc dữ liệu có kiểu cơ bản (Base type) và cấu trúc dữ liệu có kiểu do người dùng định nghĩa (User type) hay còn gọi là kiểu dữ liệu có cấu trúc. Kiểu dữ liệu cơ bản bao gồm: Kiểu kí tự (char), kiểu số nguyên có dấu (signed int), kiểu số nguyên không dấu (unsigned int), kiểu số nguyên dài có dấu (signed long), kiểu số nguyên dài không dấu (unsigned long ), kiểu số thực (float) và kiểu số thực có độ chính xác gấp đôi (double). Kiểu dữ liệu do người dùng định nghĩa bao gồm kiểu xâu kí tự (string), kiểu mảng (array), kiểu tập hợp (union), kiểu cấu trúc (struct), kiểu file, kiểu con trỏ (pointer) và các kiểu dữ liệu được định nghĩa mới hoàn toàn như kiểu danh sách móc nối (link list), kiểu cây (tree) . . . Kích cỡ của kiểu cơ bản đồng nghĩa với miền xác định của kiểu với biểu diễn nhị phân của nó, và phụ thuộc vào từng hệ thống máy tính cụ thể. Để xác định kích cỡ của kiểu nên dùng toán tử sizeof( type). Chương trình sau sẽ liệt kê kích cỡ của các kiểu cơ bản. Ví dụ 1.1. kiểm tra kích cỡ của kiểu. #include #include void main(void) { printf(“\n Kích cỡ kiểu kí tự:%d”, sizeof(char)); printf(“\n Kích cỡ kiểu kí tự không dấu:%d”, sizeof(unsigned char)); printf(“\n Kích cỡ kiểu số nguyên không dấu:%d”, sizeof(unsigned int)); printf(“\n Kích cỡ kiểu số PTITnguyên có dấu:%d”, sizeof(signed int)); printf(“\n Kích cỡ kiểu số nguyên dài không dấu:%d”, sizeof(unsigned long )); printf(“\n Kích cỡ kiểu số nguyên dài có dấu:%d”, sizeof(signed long )); printf(“\n Kích cỡ kiểu số thực có độ chính xác đơn:%d”, sizeof(float )); printf(“\n Kích cỡ kiểu số thực có độ chính xác kép:%d”, sizeof(double )); getch(); } Kích cỡ của các kiểu dữ liệu do người dùng định nghĩa là tổng kích cỡ của mỗi kiểu thành viên trong nó. Chúng ta cũng vẫn dùng toán tử sizeof(tên kiểu) để xác định độ lớn tính theo byte của các kiểu dữ liệu này. Một điểm đặc biệt chú ý trong khi lập trình trên các cấu trúc dữ liệu là cấu trúc dữ liệu nào thì phải kèm theo phép toán đó, vì một biến được gọi là thuộc kiểu dữ liệu nào đó 9
11. nếu như nó nhận một giá trị từ miền xác định của kiểu và các phép toán trên kiểu dữ liệu đó. 1.3. Nguyên lý tối thiểu Hãy bắt đầu từ một tập nguyên tắc và tối thiểu các phương tiện là các cấu trúc lệnh, kiểu dữ liệu cùng các phép toán trên nó và thực hiện viết chương trình. Sau khi nắm chắc những công cụ vòng đầu mới đặt vấn đề mở rộng sang hệ thống thư viện tiện ích của ngôn ngữ. Khi làm quen với một ngôn ngữ lập trình nào đó, không nhất thiết phải lệ thuộc quá nhiều vào hệ thống thư viện hàm của ngôn ngữ, mà điều quan trọng hơn là trước một bài toán cụ thể, chúng ta sử dụng ngôn ngữ để giải quyết nó thế nào, và phương án tốt nhất là lập trình bằng chính hệ thống thư viện hàm của riêng mình. Do vậy, đối với các ngôn ngữ lập trình, chúng ta chỉ cần nắm vững một số các công cụ tối thiểu như sau: 1.3.1. Tập các phép toán Tập các phép toán số học: + (cộng); - (trừ); * (nhân); % (lấy phần dư); / (chia). Tập các phép toán số học mở rộng: ++a  a = a +1; // tăng giá trị biến nguyên a lên một đơn vị; a  a = a-1; //giảm giá trị biến nguyên a một đơn vị; a+= n  a = a+n; // tăng giá trị biến nguyên a lên n đơn vị; a-=n  a = a - n; // giảm giá trị biến nguyên a n đơn vị); a%=n  a = a%n; // lấy giá trị biến a modul với n; a/=n a=a/n;// lấy giá trị biến a chia cho n; a*=n  a = a*n; // lấy giáPTIT trị biến a nhân với n; Tập các phép toán so sánh: >, =, b) { . . } // nếu a lớn hơn b if ( a =b) { . . } // nếu a lớn hơn hoặc bằng b if ( a<=b) { . . } // nếu a nhỏ hơn hoặc bằng b if ( a==b) { . . } // nếu a đúng bằng b if ( a!=b) { . . } // nếu a khác b Tập các phép toán logic: &&, ||, ! (và, hoặc, phủ định) 10
12. && : Phép và logic chỉ cho giá trị đúng khi hai biểu thức tham gia đều có giá trị đúng (giá trị đúng của một biểu thức trong C được hiểu là biểu thức có giá trị khác 0). || : Phép hoặc logic chỉ cho giá trị sai khi cả hai biểu thức tham gia đều có giá trị sai. ! : Phép phủ định cho giá trị đúng nếu biểu thức có giá trị sai và ngược lại cho giá trị sai khi biểu thức có giá trị đúng. Ngữ nghĩa của các phép toán được minh họa thông qua các câu lệnh sau: int a =3, b =5; if ( (a !=0) && (b!=0) ) // nếu a khác 0 và b khác 0 if ((a!=0) || (b!=0)) // nếu a khác 0 hoặc b khác 0 if ( !a ) // phủ định a khác 0 if (a==b) // nếu a đúng bằng b Các toán tử thao tác bít (không sử dụng cho float và double) & : Phép hội các bít. | : Phép tuyển các bít. ^ : Phép tuyển các bít có loại trừ. > : Phép dịch phải (dịch sang phải n bít có giá trị 0) ~ : Phép lấy phần bù. Ví dụ 1.2: Viết chương trình kiểm tra các toán tử thao tác bít. #include #include void main(void){ unsigned int a=3, b=5,PTIT c; clrscr(); c = a & b; printf(“\n c = a & b=%d”,c); c = a | b; printf(“\n c = a | b=%d”,c); c = a ^ b; printf(“\n c = a ^ b=%d”,c); c = ~a; printf(“\n c = ~a =%d”,c); c = a >b; printf(“\n c = a >> b=%d”,c); getch(); } Toán tử chuyển đổi kiểu: Ta có thể dùng toán tử chuyển đổi kiểu để nhận được kết quả tính toán như mong muốn. Qui tắc chuyển đổi kiểu được thực hiện theo qui tắc: (kiểu) biến. Ví dụ 1.3: Tính giá trị phép chia hai số nguyên a và b. 11
13. #include void main(void) int a=3, b=5; float c; c= (float) a / (float) b; printf(“\n thương c = a / b =%6.2f”, c); getch(); } Thứ tự ưu tiên các phép toán : Khi viết một biểu thức, chúng ta cần lưu ý tới thứ tự ưu tiên tính toán các phép toán, các bảng tổng hợp sau đây phản ánh trật tự ưu tiên tính toán của các phép toán số học và phép toán so sánh. Bảng tổng hợp thứ tự ưu tiên tính toán các phép toán số học và so sánh Tên toán tử Chiều tính toán ( ), [] , -> L -> R - , ++, , ! , ~ , sizeof() R -> L * , /, % L -> R + , - L -> R >>, R , >=, L -> R == != L -> R & L -> R ^ L -> R | L -> R && PTIT L -> R || L -> R ?: R -> L =, +=, -=, *=, /=, %=, &=, ^=, |=, >= R -> L 1.3.2. Tập các lệnh vào ra cơ bản Nhập dữ liệu từ bàn phím: scanf(“format_string, . . .”, ¶meter . . .); Nhập dữ liệu từ tệp: fscanf( file_pointer,”format_string, . . .”, ¶meter, . . .); Nhận một ký tự từ bàn phím: getch(); getchar(); Nhận một ký tự từ file: fgetc(file_pointer, character_name); 12
14. Nhập một string từ bàn phím: gets(string_name); Nhận một string từ file text : fgets(string_name, number_character, file_pointer); Xuất dữ liệu ra màn hình: printf(“format_string . . .”, parameter . . .); Xuất dữ liệu ra file : fprintf(file_pointer, “format_string . . .”, parameter. . .); Xuất một ký tự ra màn hình: putch(character_name); Xuất một ký tự ra file: fputc(file_pointer, character_name); Xuất một string ra màn hình: puts(const_string_name); Xuất một string ra file: fputs(file_pointer, const_string_name); 1.3.3. Thao tác trên các kiểu dữ liệu có cấu trúc Tập thao tác trên string: + Cách tổ chức string và các thao tác trên string: char *strchr(const char *s, int c) : tìm ký tự c đầu tiên xuất hiện trong xâu s; char *stpcpy(char *dest, const char *src) : copy xâu scr vào dest; int strcmp(const char *s1, const char *s2) : so sánh hai xâu s1 và s2 theo thứ tự từ điển, nếu s1 s2 hàm trả lại giá trị dương. Nếu s1==s2 hàm trả lại giá trị 0. char *strcat(char *dest, const char *src) : thêm xâu scr vào sau xâu dest. char *strlwr(char *s) : chuyển xâu s từ ký tự in hoa thành ký tự in thường. char *strupr(char *s): chuyển xâu s từ ký tự thường hoa thành ký tự in hoa. char *strrev(char *s): đảo ngược xâu s. char *strstr(const char *s1, const char *s2): tìm vị trí đầu tiên của xâu s2 trong xâu s1. PTIT int strlen(char *s): cho độ dài của xâu ký tự s. Tập thao tác trên con trỏ: Thao tác lấy địa chỉ của biến: & parameter_name; Thao tác lấy nội dung biến (biến có kiểu cơ bản): *pointer_name; Thao tác trỏ tới phần tử tiếp theo: ++pointer_name; Thao tác trỏ tới phần tử thứ n kể từ vị trí hiện tại: pointer_name = pointer_name +n; Thao tác trỏ tới phần tử sau con trỏ kể từ vị trí hiện tại: pointer_name; Thao tác trỏ tới phần tử sau n phần tử kể từ vị trí hiện tại: 13
15. Pointer_name = pointer_name - n; Thao tác cấp phát bộ nhớ cho con trỏ: void *malloc(size_t size);void *calloc(size_t nitems, size_t size); Thao tác cấp phát lại bộ nhớ cho con trỏ : void *realloc(void *block, size_t size); Thao tác giải phóng bộ nhớ cho con trỏ: void free(void *block); Tập thao tác trên cấu trúc: Định nghĩa cấu trúc: struct struct_name{ type_1 parameter_name_1; type_2 parameter_name_2; . . . . . . . . . . . . . . . . . . . . . . type_k parameter_name_k; } struct_parameter_name; Phép truy nhập tới thành phần cấu trúc: struct_parameter_name.parameter_name. Phép gán hai cấu trúc cùng kiểu: struct_parameter_name1 = struct_parameter_name2; Phép tham trỏ tới thành phần của con trỏ cấu trúc: pointer_struct_parameter_name -> struct_parameter_name. Tập thao tác trên file: Khai báo con trỏ file: FILE * file_pointer; Thao tác mở file theo mode: FILE *fopen(const char *filename,const char *mode); Thao tác đóng file : int fclose(FILEPTIT *stream); Thao tác đọc từng dòng trong file: char *fgets(char *s, int n, FILE *stream); Thao tác đọc từng khối trong file: size_t fread(void *ptr, size_t size,size_t n, FILE *stream); Thao tác ghi từng dòng vào file: int fputs(const char *s, FILE *stream); Thao tác ghi từng khối vào file: size_t fwrite(const void *ptr, size_t size, size_t n, FILE *stream); Thao tác kiểm tra sự tồn tại của file: int access(const char *filename, int amode); Thao tác đổi tên file: int rename(const char *oldname,const char *newname); Thao tác loại bỏ file: int unlink(const char *filename); 14
16. 1.4. Nguyên lý địa phương Các biến địa phương trong hàm, thủ tục hoặc chu trình cho dù có trùng tên với biến toàn cục thì khi xử lý biến đó trong hàm hoặc thủ tục vẫn không làm thay đổi giá trị của biến toàn cục. Tên của các biến trong đối của hàm hoặc thủ tục đều là hình thức. Mọi biến hình thức truyền theo trị cho hàm hoặc thủ tục đều là các biến địa phương. Các biến khai báo bên trong các chương trình con, hàm hoặc thủ tục đều là biến địa phương. Khi phải sử dụng biến phụ nên dùng biến địa phương và hạn chế tối đa việc sử dụng biến toàn cục để tránh xảy ra các hiệu ứng phụ. Ví dụ hoán đổi giá trị của hai số a và b sau đây sẽ minh họa rõ hơn về nguyên lý địa phương. Ví dụ 1.4. Hoán đổi giá trị của hai biến a và b. #include int a, b; // khai báo a, b là hai biến toàn cục. void Swap(void) { int a,b, temp; // khai báo a, b là hai biến địa phương a= 3; b=5; // gán giá trị cho a và b temp=a; a=b; b=temp;// đổi giá trị của a và b printf(“\n Kết quả thực hiện trong thủ tục a=%5d b=%5d:,a,b); } void main(void) { a=1; b=8; // khởi đầu giá trị cho biến toàn cục a, b. Swap(); printf(“\n Kết quả sau khi thực hiện thủ tục a =%5d b=%5d”,a,b); getch(); PTIT } Kết quả thực hiện chương trình: Kết quả thực hiện trong thủ tục a = 5 b=3 Kết quả sau khi thực hiện thủ tục a = 1 b =8 Trong ví dụ trên a, b là hai biến toàn cục, hai biến a, b trong thủ tục Swap là hai biến cục bộ. Các thao tác trong thủ tục Swap gán cho a giá trị 3 và b giá trị 5 sau đó thực hiện đổi giá trị của a =5 và b =3 là công việc xử lý nội bộ của thủ tục mà không làm thay đổi giá trị của biến toàn cục của a, b sau thi thực hiện xong thủ tục Swap. Do vậy, kết quả sau khi thực hiện Swap a = 1, b =8; Điều đó chứng tỏ trong thủ tục Swap chưa bao giờ sử dụng tới hai biến toàn cục a và b. Tuy nhiên, trong ví dụ sau, thủ tục Swap lại làm thay đổi giá trị của biến toàn cục a và b vì nó thao tác trực tiếp trên biến toàn cục. 15
17. Ví dụ 1.5. Đổi giá trị của hai biến a và b #include #include #include #include int a, b; // khai báo a, b là hai biến toàn cục. void Swap(void) { int temp; // khai báo a, b là hai biến địa phương a= 3; b=5; // gán giá trị cho a và b temp=a; a=b; b=temp;// đổi giá trị của a và b printf(“\n Kết quả thực hiện trong thủ tục a=%5d b=%5d:,a,b); } void main(void) { a=1; b=8; // khởi đầu giá trị cho biến toàn cục a, b. Swap(); printf(“\n Kết quả sau khi thực hiện thủ tục a =%5d b=%5d”,a,b); getch(); } Kết quả thực hiện chương trình: Kết quả thực hiện trong thủ tục a = 8 b=1 Kết quả sau khi thực hiện thủ tục a = 1 b =8 1.5. Nguyên lý nhất quán Dữ liệu thế nào thì phải thao tác thế ấy. Cần sớm phát hiện những mâu thuẫn giữa cấu trúc dữ liệu và thao tác để kịp thời khắc phục. Như chúng ta đã biết, kiểu là một tên chỉ tập các đối tượng thuộc miền xác định cùng với những thao tác trên nó. Một biến khi định nghĩa bao giờ cũng thuộc một kiểu xác định nào đó hoặc là kiểu cơ bản hoặc kiểu do người dùng định nghĩa. Thao tác với biến phụ thuộc vào những thao tácPTIT được phép của kiểu. Hai kiểu khác nhau được phân biệt bởi tên, miền xác định và các phép toán trên kiểu dữ liệu. Tuy nhiên, trên thực tế có nhiều lỗi nhập nhằng giữa phép toán và cấu trúc dữ liệu mà chúng ta cần hiểu rõ. Đối với kiểu ký tự, về nguyên tắc chúng ta không được phép thực hiện các phép toán số học trên nó, nhưng ngôn ngữ C luôn đồng nhất giữa ký tự với số nguyên có độ lớn 1 byte. Do vậy, những phép toán số học trên các ký tự thực chất là những phép toán số học trên các số nguyên. Chẳng hạn, những thao tác như trong khai báo dưới đây là được phép: char x1=’A’, x2 =’z’; x1 = (x1 + 100) % 255; x2 = (x2-x1) %255; 16
18. Mặc dù x1, x2 được khai báo là hai biến kiểu char, nhưng trong thao tác x1 = (x1 + 100) % 255; x2 = (x2 +x1) %255; chương trình dịch sẽ tự động chuyển đổi x1 thành mã của ký tự ‘A’ là 65, x2 thành mã ký tự ‘z’ là 122 để thực hiện phép toán. Kết quả nhận được x1 là một ký tự có mã là (65+100)%255 = 165; x2 là ký tự có mã là 32 ứng với mã của ký tự space. Chúng ta có thể thực hiện được các phép toán số học trên kiểu int, long, float, double. Nhưng đối với int và long, chúng ta cần đặc biệt chú ý phép chia hai số nguyên cho ta một số nguyên, tích hai số nguyên cho ta một số nguyên, tổng hai số nguyên cho ta một số nguyên mặc dù thương hai số nguyên là một số thực, tích hai số nguyên hoặc tổng hai số nguyên có thể là một số long int. Do vậy, muốn nhận được kết quả đúng, chúng ta cần phải chuyển đổi các biến thuộc cùng một kiểu trước khi thực hiện phép toán. Ngược lại, ta không thể lấy modul của hai số thực hoặc thực hiện các thao tác dịch chuyển bít trên nó, vì những thao tác đó không nằm trong định nghĩa của kiểu. Điều tương tự cũng xảy ra với các string. Trong Pascal, phép toán so sánh hai string hoặc gán trực tiếp hai Record cùng kiểu với nhau là được phép, ví dụ : Str1>Str2, Str1 := Str2; Nhưng trong C thì các phép toán trên lại không được định nghĩa, nếu muốn thực hiện nó, chúng ta chỉ có cách định nghĩa lại hoặc thực hiện nó thông qua các lời gọi hàm. Ví dụ đơn giản sau sẽ minh họa cho những lỗi thường xảy ra sự nhập nhằng giữa phép toán và cấu trúc dữ liệu. Ví dụ 1.6. Viết chương trình tính tổng, hiệu, tích, thương của hai số nguyên a và b. #include long int tong( int a, int b) { return(a+b); } int hieu(int a, int b) { return(a-b); } long int tich(int a, int b) { return(a*b);} float thuong(int a, int b){ return(a/b);} void main(void){ int a=30000, b = 2000PTIT0;// khai báo và gán giá trị hai số nguyên a, b printf(“\n Tổng hai số nguyên a + b =%ld”, tong(a,b)); printf(“\n Hiệu hai số nguyên a - b =%d”,hieu(a,b)); printf(“\n Tích hai số nguyên a*b=%ld”, tich(a,b)); printf(‘\n Thương hai số nguyên a/b =%f”, thuong(a,b)); getch(); } Trong ví dụ trên, hàm tong(30000,20000) cho ta một số unsigned int là giá trị là tổng của hai số nguyên dương, vì tổng của hai số nguyên dương có thể vượt quá kích cỡ kiểu int để trở thành một số unsigned int, điều đó cũng xảy ra tương tự đối với hàm tich(30000, 20000); Do đó, việc thực hiện việc gán một số nguyên dương thế này sẽ cho ta kết quả không mong muốn. 17
19. Với hàm thương(a,b) thì hoàn toàn ngược lại đối với một số ngôn ngữ ( C, C++). Khi chúng ta phát biểu thương của hai số nguyên dương là một số thực được tính là a/b (b long int tong( int a, int b) { return((long) a+ (long) b); } int hieu(int a, int b) { return(a-b); } long int tich(int a, int b) { return((long) a* (long) b);} float thuong(int a, int b){ float k; k = (float) a / (float) b; return(k); } void main(void){ int a=30000, b = 20000;// khai báo và gán giá trị hai số nguyên a, b printf(“\n Tổng hai số nguyên a + b =%ld”, tong(a,b)); printf(“\n Hiệu hai số nguyên a - b =%d”,hieu(a,b)); printf(“\n Tích hai số nguyên a*b=%ld”, tich(a,b)); printf(‘\n Thương hai số nguyên a/b =%f”, thuong(a,b)); getch(); } Kết quả thực hiện chương trình: Tổng hai số nguyên a+b = 50000 Hiệu hai số nguyên a-b = 10000 Tích hai số nguyên a*b = 6000000000 Hiệu hai số nguyên a/b = 1.500000 Tóm lại, cần nắm vững nguyên tắc, định nghĩa và những qui định riêng của ngôn ngữ cho từng kiểu dữ liệu và cácPTIT phép toán trên nó để đảm bảo tính nhất quán trong khi xử lý dữ liệu. 1.6. Nguyên lý an toàn Lỗi nặng nhất nằm ở mức cao nhất (mức ý đồ thiết kế) và ở mức thấp nhất thủ tục phải chịu tải lớn nhất. Mọi lỗi, dù là nhỏ nhất cũng phải được phát hiện ở một bước nào đó của chương trình. Quá trình kiểm tra và phát hiện lỗi phải được thực hiện trước khi lỗi đó hoành hành. Các loại lỗi thường xảy ra trong khi viết chương trình có thể được tổng kết lại như sau: 18
20. Lỗi được thông báo bởi từ khoá error (lỗi cú pháp): loại lỗi này thường xảy ra trong khi soạn thảo chương trình, chúng ta có thể viết sai các từ khoá ví dụ thay vì viết là int chúng ta soạn thảo sai thành Int (lỗi chữ in thường thành in hoa), hoặc viết sai cú pháp các biểu thức như thiếu các dấu ngoặc đơn, ngoặc kép hoặc dấu chấm phảy khi kết thúc một lệnh, hoặc chưa khai báo nguyên mẫu cho hàm . Lỗi được thông báo bởi từ khoá Warning (lỗi cảnh báo): lỗi này thường xảy ra khi ta khai báo biến trong chương trình nhưng lại không sử dụng tới chúng, hoặc lỗi trong các biểu thức kiểm tra khi biến được kiểm tra không xác định được giá trị của nó, hoặc lỗi do thứ tự ưu tiên các phép toán trong biểu thức. Hai loại lỗi error và warning được thông báo ngay khi dịch chương trình thành file *.OBJ. Quá trình liên kết (linker) các file *.OBJ để tạo nên file chương trình mã máy *.EXE chỉ được tiếp tục khi chúng ta hiệu đính và khử bỏ mọi lỗi error. Lỗi xảy ra trong quá trình liên kết: lỗi này thường xuất hiện khi ta sử dụng tới các lời gọi hàm , nhưng những hàm đó mới chỉ tồn tại dưới dạng nguyên mẫu (function prototype) mà chưa được mô tả chi tiết các hàm, hoặc những lời hàm gọi chưa đúng với tên của nó. Lỗi này được khắc phục khi ta bổ sung đoạn chương trình con mô tả chi tiết cho hàm hoặc sửa đổi lại những lời gọi hàm tương ứng. Ta quan niệm, lỗi cú pháp (error), lỗi cảnh báo (warning) và lỗi liên kết (linker) là lỗi tầm thường vì những lỗi này đã được Compiler của các ngôn ngữ lập trình phát hiện được. Để khắc phục các lỗi loại này, chúng ta chỉ cần phải đọc và hiểu được những thông báo lỗi thường được viết bằng tiếng Anh. Cũng cần phải lưu ý rằng, do mức độ phức tạp của chương trình dịch nên không phải lỗi nào cũng được chỉ ra một cách tường minh và chính xác hoàn toàn tại nơi xuất hiện lỗi. Loại lỗi cuối cùng mà các compiler không thể phát hiện nổi đó là lỗi do chính lập trình viên gây nên trong khi thiết kế chương trình và xử lý dữ liệu. Những lỗi này không được compiler thông báo mà nó phải trả giá bằng quá trình tự test hoặc chứng minh được tính đúng đắn của chương trình. Lỗi có thể nằm ở chính ý đồ thiết kế, hoặc lỗi do không lường trước được tính chất của mỗiPTIT loại thông tin vào. 1.6. Phương pháp Top-Down Quá trình phân tích bài toán được thực hiện từ trên xuống dưới. Từ vấn đề chung nhất đến vấn đề cụ thể nhất. Từ mức trừu tượng mang tính chất tổng quan tới mức đơn giản nhất là đơn vị chương trình. Một trong những nguyên lý quan trọng của lập trình cấu trúc là phương pháp phân tích từ trên xuống (Top - Down) với quan điểm “thấy cây không bằng thấy rừng”, phải đứng cao hơn để quan sát tổng thể khu rừng chứ không thể đứng trong rừng quan sát chính nó. Quá trình phân rã bài toán được thực hiện theo từng mức khác nhau. Mức thấp nhất được gọi là mức tổng quan (level 0), mức tổng quan cho phép ta nhìn tổng thể hệ 19
21. thống thông qua các chức năng của nó, nói cách khác mức 0 sẽ trả lời thay cho câu hỏi “Hệ thống có thể thực hiện được những gì ?”. Mức tiếp theo là mức các chức năng chính. ở mức này, những chức năng cụ thể được mô tả. Một hệ thống có thể được phân tích thành nhiều mức khác nhau, mức thấp được phép sử dụng các dịch vụ của mức cao. Quá trình phân tích tiếp tục phân rã hệ thống theo từng chức năng phụ cho tới khi nào nhận được mức các đơn thể ( UNIT, Function, Procedure), khi đó chúng ta tiến hành cài đặt hệ thống. Chúng ta sẽ làm rõ hơn từng mức của quá trình Top-Down thông qua bài toán sau: Bài toán: Cho hai số nguyên có biểu diễn nhị phân là a=(a1, a2, . . ., an), b = (b1, b2, , bn); ai, bi =0, 1, i=1, 2, . . .n. Hãy xây dựng tập các thao tác trên hai số nguyên đó. Mức tổng quan (level 0): Hình dung toàn bộ những thao tác trên hai số nguyên a=(a1, a2, . . ., an), b=(b1,b2, ,bn) với đầy đủ những chức năng chính của nó. Giả sử những thao tác đó bao gồm: F1- Chuyển đổi a, b thành các số nhị phân; F2- Tính tổng hai số nguyên: a + b; F3- Tính hiệu hai số nguyên: a - b; F4 Tính tích hai số nguyên: a *b; F5- Thương hai số nguyên : a/b; F6- Phần dư hai số nguyên: a % b; F7- Ước số chung lớn nhất của hai số nguyên. Mức 1. Mức các chức năng chính: mỗi chức năng cần mô tả đầy đủ thông tin vào (Input), thông tin ra (Output), khuôn dạng (Format) và các hành động (Actions). Chức năng F1: Chuyển đổi a, b thành các số ở hệ nhị phân Input : a : integer;PTIT Output : a=(a1, a2, . . ., an)b; (*khai triển cơ số b bất kỳ*) Format : Binary(a); Actions Q = n; k=0; While Q 0 Begin ak = q mod b; q = q div b; k = k +1; 20
22. end; ; EndAction; Chức năng F2: Tính tổng hai số nguyên a, b. Input: a=(a1, a2, . . ., an), b = (b1, b2, , bn); Output: c = a + b; Format: Addition(a, b); Actions c = 0; for j = 0 to n-1 do begin d = (aj + bj + c) div 2; sj = aj + bj + c - 2d; c = d; end; sn = c; EndAction; Chức năng F3: Hiệu hai sốPTIT nguyên a, b. Input: a=(a1, a2, . . ., an), b = (b1, b2, , bn); Output: c = a - b; Format: Subtraction(a, b); Actions b = -b; c = Addition(a, b); 21
23. return(c); EndAction; Chức năng F4: Tích hai số nguyên a, b. Input: a=(a1, a2, . . ., an), b = (b1, b2, , bn); Output: c = a * b; Format: Multual(a, b); Actions For j =0 to n-1 do Begin If bj =1 then cj = a = b ) do 22
24. begin c = c +1; a = Subtraction(a, b); end; return(c); EndAction; Chức năng F6: Modul hai số nguyên a, b. Input: a=(a1, a2, . . ., an), b = (b1, b2, , bn); Output: c = a mod b; Format: Modulation(a, b); Actions while ( a>= b ) do a = Subtraction(a, b); return(a); EndAction; Chức năng F7: Ước số chung lớn nhất hai số nguyên a, b. Input: a=(a1, a2, . . ., an), PTIT b = (b1, b2, , bn); Output: c = USCLN(a,b); Format: USCLN(a, b); Actions while ( a b ) do begin if a > b then a = Subtraction(a, b) 23
25. else b = Subtraction(b,a); return(a); EndAction; Để ý rằng, sau khi phân rã bài toán ở mức 1, chúng ta chỉ cần xây dựng hai phép toán cơ bản cho các số nguyên a và b, đó là phép tính cộng và phép tính nhân các số nhị phân của a và b. Vì hiệu hai số a và b chính là tổng số của (a,-b). Tương tự như vậy, tích hai số a và b được biểu diễn bằng tổng của một số lần phép nhân một bít nhị phân của với a. Phép chia và lấy phần dư hai số a và b chính là phép trừ nhiều lần số a. Phép tìm USCLN cũng tương tự như vậy. Đối với các hệ thống lớn, quá trình còn được mô tả tiếp tục cho tới khi nhận được mức đơn vị chương trình. Trong ví dụ đơn giản này, mức đơn vị chương trình xuất hiện ngay tại mức 1 nên chúng ta không cần phân rã tiếp nữa mà dừng lại để cài đặt hệ thống. 1.7. Phương pháp Bottom - Up Đi từ cái riêng tới cái chung, từ các đối tượng thành phần ở mức cao tới các đối tượng thành phần ở mức thấp, từ mức đơn vị chương trình tới mức tổng thể, từ những đơn vị đã biết lắp đặt thành những đơn vị mới. Nếu như phương pháp Top-Down là phương pháp phân rã vấn đề một cách có hệ thống từ trên xuống, được ứng dụng chủ yếu cho quá trình phân tích và thiết hệ thống, thì phương pháp Bottom- Up thường được sử dụng cho quá trình cài đặt hệ thống. Trong ví dụ trên, chúng ta sẽ không thể xây dựng được chương trình một cách hoàn chỉnh nếu như ta chưa xây dựng được các hàm Binary(a), Addition(a,b), Subtraction(a,b), Multial(a,b), Division(a,b), Modulation(a,b), USCLN(a,b). Chương trình sau thể hiện quá trình cài đặt chương trình theo nguyên lý Botton-Up: #include #include PTIT #include void Init(int *a, int *b){ printf("\n Nhap a=");scanf("%d", a); printf("\n Nhap b=");scanf("%d", b); } void Binary(int a){ int i, k=1; for(i=15; i>=0; i ){ if ( a & (k<<i)) printf("%2d",1); else printf("%2d",0); 24
26. } printf("\n");delay(500); } int bit(int a, int k){ int j=1; if (a & (j =b) a = Subtraction(a,b); return(a); 25
27. } int Division(int a, int b){ int d=0; while(a>=b) { a= Subtraction(a,b); d++; } return(d); } int USCLN(int a, int b){ while(a!=b){ if(a>b) a = Subtraction(a,b); else b = Subtraction(b,a); } return(a); } void main(void){ int a, b, key, control=0; do { clrscr(); printf("\n Tap thao tac voi so nguyen"); printf("\n 1- Nhap hai so a,b"); printf("\n 2- So nhi phan cua a, b"); printf("\n 3- Tong hai so a,b"); printf("\n 4- Hieu hai so a,b"); printf("\n 5- Tich hai so a,b"); printf("\n 6- ThuongPTIT hai so a,b"); printf("\n 7- Phan du hai so a,b"); printf("\n 8- USCLN hai so a,b"); printf("\n 0- Tro ve"); key=getch(); switch(key){ case '1': Init(&a, &b); control=1; break; case '2': if (control){ Binary(a); Binary(b); } break; case '3': if (control) 26
28. printf("\n Tong a+b = %d", Addition(a, b)); break; case '4': if (control) printf("\n Hieu a-b =%d", Subtraction(a, b)); break; case '5': if(control) printf("\n Tich a*b =%d", Multial(a,b)); break; case '6': if(control) printf("\n Chia nguyen a div b=%d",Division(a,b)); break; case '7': if(control) printf("\n Phan du a mod b =%d", Modul(a,b)); break; case '8': if(control) printf("\n Uoc so chung lon nhat:%d",USCLN(a,b)); break; } delay(1000); } while(key!='0'); } PTIT 27
29. BÀI TẬP CHƯƠNG 1 1.1. Tìm các nghiệm nguyên dương của hệ phương trình: X + Y + Z = 100 5X + 3Y + Z/3 = 100 1.2. Cho số tự nhiên n. Hãy tìm tất cả các bộ 3 các số tự nhiên a, b, c sao cho a2+b2 = c2 trong đó a 39. 1.5. Cho số tự nhiên n. Hãy liệt kê tất cả các số nguyên tố nhỏ hơn n. 1.6. Cho số tự nhiên n. Hãy tìm tất cả các số nguyên tố nhỏ hơn n bằng phương pháp sàng Estheven. 1.7. Cho số tự nhiên n. Dùng phương pháp sàng Estheven để tìm 4 số nguyên tố bé hơn n nằm trong cùng bậc chục ( ví dụ : 11, 13, 15, 17). 1.8. Cho số tự nhiên n. Hãy liệt kê tất cả các cặp số p, 4p+1 đều là số nguyên tố nhỏ hơn n. Trong đó p cũng là số nguyên tố nhỏ hơn n. 1.9. Hãy liệt kê tất cả các số nguyên tố có 5 chữ số sao cho tổng số các chữ số trong số nguyên tố đó đúng bằng S cho trước 1 S 45. 1.10. Một số được gọi là số Mersen nếu nó là số nguyên tố được biểu diễn dưới dạng 2P - 1 trong đó P cũng là một số nguyên tố. Cho số tự nhiên n, tìm tất cả các số Mersen nhỏ hơn n. 1.11. Cho số tự nhiên n. Hãy phân tích n thành tích các thừa số nguyên tố. Ví dụ 12 = 2*2*3. 1.12. Hai số tự nhiên a, b được gọi là “hữu nghị” nếu tổng các ước số thực sự của a (kể cả 1) bằng b và ngược lại. PTITCho hai số tự nhiên P , Q. Hãy tìm tất cả các cặp số hữu nghị trong khoảng [P, Q]. 1.13. Cho số tự nhiên n. Hãy tìm tất cả các số 1, 2, , n sao cho các số trùng với phần cuối bình phương chính nó (Ví dụ : 62 = 36, 252 = 625). 1.14. Một số tự nhiên được gọi là số amstrong nếu tổng các lũy thừa bậc n của các chữ số của nó bằng chính số đó. Trong đó n là số các chữ số ( Ví dụ 153 = 13 + 23 + 33 ). Hãy tìm tất cả các số amstrong gồm 2, 3, 4 chữ số. 1.15. Một số tự nhiên là Palindrom nếu các chữ số của nó viết theo thứ tự ngược lại thì số tạo thành là chính số đó ( Ví dụ: 4884, 393). Hãy tìm: - Tất cả các số tự nhiên nhỏ hơn 100 mà khi bình phương lên thì cho một Palindrom. - Tất cả các số Palindrom bé hơn 100 mà khi bình phương lên chúng cho một Palindrom. 28
30. CHƯƠNG 2. MẢNG VÀ CON TRỎ 2.1. Cấu trúc lưu trữ mảng 2.1.1. Khái niệm về mảng Mảng là một tập cố định các phần tử cùng có chung một kiểu dữ liệu được lưu trữ kế tiếp nhau trong bộ nhớ. Các thao tác trên mảng bao gồm: tạo lập mảng (create), tìm kiếm một phần tử của mảng (retrieve), lưu trữ mảng (store). Ngoài giá trị, mỗi phần tử của mảng còn được đặc trưng bởi chỉ số của nó (index). Index của một phần tử thể hiện thứ tự của phần tử đó trong mảng. Không có các thao tác bổ sung thêm phần tử hoặc loại bỏ phần tử của mảng vì số phần tử trong mảng là cố định. Một mảng một chiều gồm n phần tử được coi như một vector n thành phần được đánh số từ 0, 1, 2, . . ., n-1. Chúng ta có thể mở rộng khái niệm mảng một chiều cho mảng nhiều chiều như sau: Một mảng một chiều gồm n phần tử, trong đó mỗi phần tử của nó lại là một mảng một chiều gồm m phần tử được gọi là một mảng hai chiều gồm n m phần tử. Tổng quát, một mảng gồm n phần tử mà mỗi phần tử của nó lại là một mảng k - 1 chiều thì nó được gọi là mảng k chiều. Số phần tử của mảng k chiều là tích số giữa số các phần tử của mỗi mảng một chiều. Khai báo mảng một chiều được thực hiện theo qui tắc như sau: Tên_kiểu Tên_biến[Số_phần tử]; Chẳng hạn với khai báo: int A[10]; /* khai báo mPTITảng gồm 10 phần tử nguyên*/ char str[20]; /* khai báo mảng gồm 20 kí tự */ float B[20]; /* khai báo mảng gồm 20 số thực */ long int L[20]; /* khai báo mảng gồm 20 số nguyên dài */ 2.1.2. Cấu trúc lưu trữ của mảng một chiều Cấu trúc lưu trữ của mảng: Mảng được tổ chức trong bộ nhớ như một vector, mỗi thành phần của vector được tương ứng với một ô nhớ có kích cỡ đúng bằng kích cỡ của kiểu phần tử và được lưu trữ kế tiếp nhau trong bộ nhớ. Nếu chúng ta có khai báo mảng gồm n phần tử thì phần tử đầu tiên là phần tử thứ 0 và phần tử cuối cùng là phần tử thứ n - 1, đồng thời mảng được cấp phát một vùng không gian nhớ liên tục có số byte được tính theo công thức: 29
31. Kích_cỡ_mảng = ( Số_phần_tử * sizeof (kiểu_phần_tử). Chẳng hạn trong có khai báo: int A[10]; Khi đó kích cỡ tính theo byte của mảng là : 10 *sizeof(int) = 20 byte; float B[20]; => mảng được cấp phát: 20 * sizeof(float) = 80byte; Chương trình dịch của ngôn ngữ C luôn qui định tên của mảng đồng thời là địa chỉ phần tử đầu tiên của mảng trong bộ nhớ. Do vậy, nếu ta có một kiểu dữ liệu nào đó là Data_type, tên của mảng là X, số phân tử của mảng là N thì mảng được tổ chức trong bộ nhớ như sau: Data_type X[N]; X[0] X[1] X[2] X[3] . . . . . . . X[N-1] X - là địa chỉ đầu tiên của mảng. X = &X[0] = ( X + 0 ); &X[1] = ( X + 1 ); . . . . . . . . . . . . . . . . . . . . . . . . . . . . &X[i] = (X + i ); Ví dụ 2.1. Kiểm tra cấu trúc lưu trữ của mảng trong bộ nhớ của mảng một chiều. #include void main(void) { int A[10], i ; /* khai báo mảng gồm 10 biến nguyên */ printf(“\n Địa chỉ đầu của mảng A là : %p”, A); printf(“\n Kích cỡ của mảng : %5d byte”, 10 * sizeof(int)); for ( i =0 ; i <10; i ++){ printf(“\n Địa chỉ phầnPTIT tử thứ %5d : %p”, i, &A[i]); } } Kết quả thực hiện chương trình: Địa chỉ đầu của mảng: FFE2 Kích cỡ của mảng : 20 Địa chỉ phần tử thứ 0 = FFE2 Địa chỉ phần tử thứ 1 = FFE4 Địa chỉ phần tử thứ 2 = FFE6 Địa chỉ phần tử thứ 3 = FFE8 Địa chỉ phần tử thứ 4 = FFEA Địa chỉ phần tử thứ 5 = FFEC Địa chỉ phần tử thứ 6 = FFEE 30
32. Địa chỉ phần tử thứ 7 = FFF0 Địa chỉ phần tử thứ 8 = FFF2 Địa chỉ phần tử thứ 9 = FFF4 Ví dụ 2.1 in ra địa chỉ của các phần tử trong mảng A gồm 10 phần tử nguyên. Kết quả như được đưa ra ở trên cho ta thấy địa chỉ của mảng trong bộ nhớ trùng với địa chỉ của phần tử A[0] đều bằng FFE2, tiếp đến các phần tử được lưu trữ kế tiếp và cách nhau đúng bằng kích cỡ của kiểu int. Bạn đọc có thể dùng chương trình đơn giản này để kiểm tra cấu trúc lưu trữ của mảng cho các kiểu dữ liệu khác. 2.1.3. Cấu trúc lưu trữ mảng nhiều chiều Đa số các ngôn ngữ không hạn chế số chiều của mảng, chế độ cấp phát bộ nhớ cho mảng nhiều chiều được thực hiện theo cơ chế ưu tiên theo hàng. Khai báo mảng nhiều chiều : Data_type tên_biến[số_chiều_1] [số_chiều_2]. . . [số_chiều_n] int A[3][3]; khai báo mảng hai chiều gồm 9 phần tử nguyên được lưu trữ liên tục từ A[0][0] , A[0][1] , A[0][2] , A[1][0] , A[1][0] , A[1][1] , A[1][2] , A[2][0] , A[2][1] , A[2][2] ; Ví dụ 2.2 . Kiểm tra cấu trúc lưu trữ của bảng hai chiều trong bộ nhớ. #include #include void main(void) { float A[3][3] ; /* khai báo mảng hai chiều gồm 9 phần tử nguyên*/ int i, j; /* Địa chỉ của các hàng*/ for(i=0; i<3; i++) printf(“\n Địa chỉ hàng thứ %d là :%p”, i, A[i]); for(i=0; i<3;i++){ printf(“\n”); for(j=0;j<3;j++) printf(“%10p”,&A[i][j]);PTIT } } Kết quả thực hiện chương trình: Địa chỉ hàng thứ 0 = FFD2 Địa chỉ hàng thứ 1 = FFDE Địa chỉ hàng thứ 2 = FFEA Địa chỉ phần tử A[0][0]= FFD2 Địa chỉ phần tử A[0][1]= FFD6 Địa chỉ phần tử A[0][2]= FFDA Địa chỉ phần tử A[1][0]= FFDE Địa chỉ phần tử A[1][1]= FFE2 Địa chỉ phần tử A[1][2]= FFE6 31
33. Địa chỉ phần tử A[2][0]= FFEA Địa chỉ phần tử A[2][1]= FFEE Địa chỉ phần tử A[2][2]= FFF2 Dễ dàng nhận thấy, địa chỉ hàng thứ i trùng với địa chỉ phần tử đầu tiên trong hàng tương ứng. Tiếp đến các phần tử trong mỗi hàng được lưu trữ cách nhau đúng bằng kích cỡ của kiểu float. Ghi chú: Kết quả thực hiện ví dụ 2.1, 2.2 có thể cho ra kết quả khác nhau trên các máy tính khác nhau, vì việc phân bổ bộ nhớ cho mảng tùy thuộc vào không gian nhớ tự do của mỗi máy. 2.2. Các thao tác đối với mảng Các thao tác đối với mảng bao gồm : tạo lập mảng, tìm kiếm phần tử của mảng, lưu trữ mảng. Các thao tác này có thể được thực hiện ngay từ khi khai báo mảng. Chúng ta có thể vừa khai báo mảng vừa khởi đầu cho mảng, nhưng cần chú ý một số kỹ thuật khởi đầu cho mảng để vừa đạt được mục đích đề ra vừa tiết kiệm bộ nhớ. Chẳng hạn với khai báo int A[10] = { 5, 7, 2, 1, 9 }; chương trình vẫn phải cấp phát cho mảng A kích cỡ 10 * sizeof(int) = 20 byte bộ nhớ, trong khi đó số byte cần thiết thực sự cho mảng chỉ là 5 * sizeof(int) = 10 byte. Để tránh lãng phí bộ nhớ, chúng ta có thể vừa khai báo vừa đồng thời khởi đầu cho mảng như sau. int A[] = { 5, 7, 2, 1, 9 }; Với cách khai báo này, miền bộ nhớ cấp phát cho mảng chỉ là số các số nguyên được khởi đầu trong dãy và bằng 5 * sizof(int) = 10 byte. Sau đây là một số ví dụ minh họa cho các thao tác xử lý mảng một và nhiều chiều. Ví dụ 2.3. Tạo lập mảng các số thựcPTIT gồm n phần tử , tìm phần tử lớn nhất và chỉ số của phần tử lớn nhất trong mảng. #include #include #include #include #define MAX 100 /*số phần tử tối đa trong mảng*/ void main(void) { float A[MAX], max; int i, j, n; /* Khởi tạo mảng số */ printf(“\n Nhập số phần tử của mảng n=”); scanf(“%d”, &n); for(i=0; i<n; i++){ printf(“\n Nhập A[%d] =”,i); scanf(“%f”, &A[i]); 32
34. } max = A[0]; j =0; for(i=1; i max) { max=A[i]; j = i; } } printf(“\n Chỉ số của phần tử lớn nhất là : %d”,j); printf(“\n Giá trị của phần tử lớn nhất là: %6.2f”, max); getch(); } Kết quả thực hiện chương trình: Nhập số phần tử của mảng n=7 Nhap A[0]=1 Nhap A[1]=9 Nhap A[2]=2 Nhap A[3]=8 Nhap A[4]=3 Nhap A[5]=7 Nhap A[6]=4 Chỉ số của phần tử lớn nhất là : 1 Giá trị của phần tử lớn nhất là : 9 Ví dụ 2.4. Tạo lập ma trận cấp m x n và tìm phần tử lớn nhất, nhỏ nhất của ma trận. #include #include #define M 20 #define N 20 void main(void){ float A[M][N], max, t; int i, j, k, p, m, n; clrscr(); PTIT printf(“\n Nhập số hàng của ma trận:”); scanf(“%d”, &m); printf(“\n Nhập số cộ của ma trận:”); scanf(“%d”, &n); for(i=0; i max) {max=A[i][j]; k=i ; p =j; } } 33
35. } printf(“\n Phần tử có giá trị max là A[%d][%d] = % 6.2f”, k,p, max); } } Ghi chú: C không hỗ trợ khuôn dạng nhập dữ liệu %f cho các mảng nhiều chiều. Do vậy, muốn nhập dữ liệu là số thực cho mảng nhiều chiều chúng ta phải nhập vào biến trung gian sau đó gán giá trị trở lại. Đây không phải là hạn chế của C++ mà hàm scanf() đã được thay thế bởi toán tử “cin”. Tuy nhiên, khi sử dụng cin, cout chúng ta phải viết chương trình dưới dạng *.cpp. 2.3. Mảng và đối của hàm Như chúng ta đã biết, khi hàm được truyền theo tham biến thì giá trị của biến có thể bị thay đổi sau mỗi lời gọi hàm. Hàm được gọi là truyền theo tham biến khi chúng ta truyền cho hàm là địa chỉ của biến. Ngôn ngữ C qui định tên của mảng đồng thời là địa chỉ của mảng trong bộ nhớ. Do vậy, nếu chúng ta truyền cho hàm là tên của một mảng thì hàm luôn thực hiện theo cơ chế truyền theo tham biến, trường hợp này giống như ta sử dụng từ khoá var trong khai báo biến của hàm trong Pascal. Trong trường hợp muốn truyền theo tham trị với đối của hàm là một mảng, ta cần phải thực hiện trên một bản sao khác của mảng, khi đó các thao tác đối với mảng thực chất đã được thực hiện trên một vùng nhớ khác dành cho bản sao của mảng. Ví dụ 2.5. Tạo lập và sắp xếp dãy các số thực A1, A2, . . . An theo thứ tự tăng dần. Để giải quyết bài toán, chúng xây dựng chương trình thành 3 hàm riêng biệt: hàm Init_Array() có nhiệm vụ tạo lập mảng số A[n], hàm Sort_Array() thực hiện việc sắp xếp dãy các số được lưu trữ trong mảng, hàm In_Array() in lại kết quả sau khi mảng đã được sắp xếp. #include #define MAX 100 /* Khai báo nguyên mẫu cho hàmPTIT */ void Init_Array ( float A[], int n); void Sort_Array( float A[], int n); void In_Array( float A[], int n); /* Mô tả hàm */ /* Hàm tạo lập mảng số */ void Init_Array( float A[], int n) { int i; for( i = 0; i < n; i++ ) { printf(“\n Nhập A[%d] = “, i); scanf(“%f”, &A[i]); } } 34
36. /* Hàm sắp xếp mảng số */ void Sort_Array( float A[], int n ){ int i , j ; float temp; for(i=0; i A[j]) { temp = A[i]; A[i] = A[j]; A[j] = temp; } } } } /* Hàm in mảng số */ void In_Array ( float A[], int n) { int i; for(i=0; i #include /* khai báo sử dụng hàm delay() trong chương trình*/ #define M 20 /* Số hàng của ma trận*/ #define N 20 /* Số cột của ma trận */ /* Khai báo nguyên mẫu cho hàm*/ void Init_Matrix( float A[M][N], int m, int n, char ten); void Tong_Matrix(float A[M][N],float B[M][N], float C[M][N], int m, int n); void In_Matrix(float A[M][N], int m, int n); /*Mô tả hàm */ void Init_Matrix( float A[M][N], int m, int n, char ten) { int i, j; float temp; clrscr(); for(i=0; i<m; i++){ 35
37. for(j=0; j<n; j++){ printf(“\n Nhập %c[%d][%d] =”, ten, i,j); scanf(“%f”, &temp); A[i][j]=temp; } } } void Tong_Matrix(float A[M][N],float B[M][N], float C[M][N], int m,int n){ int i, j; for(i=0; i<m; i++){ for(j=0; j<n; j++){ C[i][j]=A[i][j] + B[i][j]; } } } void In_Matrix(float A[M][N], int m, int n) { int i, j , ch=179; /* 179 là mã kí tự ‘|’ */ for(i=0; i<m; i++){ printf(“\n %-3c”, ch); for(j=0; j<n; j++){ printf(“ %6.2f”, A[i][j]; } printf(“%3c”, ch); } getch(); } /* Chương trình chính */ void main(void) { float A[M][N], B[M][N], C[M][N]; int n, m; clrscr(); printf(“\n Nhập số hPTITàng m =”); scanf(“%d”, &m); printf(“\n Nhập số cột n =”); scanf(“%d”, &n); Init_Matrix(A, m, n, ‘A’); Init_Matrix(B, m, n, ‘B’); Tong_Matrix(A, B, C, m, n); In_Matrix(C, m, n); } 2.4. Xâu kí tự (string) Xâu kí tự là một mảng trong đó mỗi phần tử của nó là một kí tự, kí tự cuối cùng của xâu được dùng làm kí tự kết thúc xâu. Kí tự kết thúc xâu được ngôn ngữ C qui định là kí tự ‘\0’, kí tự này có mã là 0 (NULL) trong bảng mã ASCII. Ví dụ trong khai báo : 36
38. char str[]=’ABCDEF’ khi đó xâu kí tự được tổ chức như sau: 0 1 2 3 4 5 6 A B C D E F ‘\0’ Khi đó str[0] = ‘A’; str[1] = ‘B’, . ., str[5]=’F’, str[6]=’\0’; Vì kí hiệu kết thúc xâu có mã là 0 nên chúng ta có thể kiểm chứng tổ chức lưu trữ của xâu thông qua đoạn chương trình sau: Ví dụ 2.7. In ra từng kí tự trong xâu. #include #include /* sử dụng hàm xử lý xâu kí tự gets() */ void main(void) { char str[20]; int i =0; printf(“\n Nhập xâu kí tự:”); gets(str); /* nhập xâu kí tự từ bàn phím */ while ( str[i]!=’\0’){ putch(c); i++; } } Ghi chú: Hàm getch() nhận một kí tự từ bàn phím, hàm putch(c) đưa ra màn hình kí tự c. Hàm sacnf(“%s”, str) : nhận một xâu kí tự từ bàn phím nhưng không được chứa kí tự trống (space), hàm gets(str) : cho phép nhận từ bàn phím một xâu kí tự kể cả dấu trống. Ngôn ngữ C không cung cấp các phép toán trên xâu kí tự, mà mọi thao tác trên xâu kí tự đều phải được thực hiện thông qua các lời gọi hàm. Sau đây là một số hàm xử lý xâu kí tự thông dụng được khai báo trong tệp string.h: puts (string) : Đưa ra màn hình một string. gets(string) : Nhận từ bànPTIT phím một string. scanf(“%s”, string) : Nhận từ bàn phím một string không kể kí tự trống (space) . strlen(string): Hàm trả lại một số là độ dài của string. strcpy(s,p) : Hàm copy xâu p vào xâu s. strcat(s,p) : Hàm nối xâu p vào sau xâu s. strcmp(s,p) : Hàm trả lại giá trị dương nếu xâu s lớn hơn xâu p, trả lại giá trị âm nếu xâu s nhỏ hơn xâu p, trả lại giá trị 0 nếu xâu s đúng bằng xâu p. strstr(s,p) : Hàm trả lại vị trí của xâu p trong xâu s, nếu p không có mặt trong s hàm trả lại con trỏ NULL. strncmp(s,p,n) : Hàm so sánh n kí tự đầu tiên của xâu s và p. strncpy(s,p,n) : Hàm copy n kí tự đầu tiên từ xâu p vào xâu s. 37
39. strrev(str) : Hàm đảo xâu s theo thứ tự ngược lại. 2.5. Con trỏ (Pointer) Con trỏ là biến chứa địa chỉ của một biến khác. Con trỏ được sử dụng rất nhiều trong C và được coi là thế mạnh trong biểu diễn tính toán và truy nhập gián tiếp các đối tượng. 2.5.1. Các phép toán trên con trỏ Để khai báo con trỏ, chúng ta thực hiện theo cú pháp: Kiểu_dữ_liệu * Biến_con_trỏ; Vì con trỏ chứa địa chỉ của đối tượng nên có thể thâm nhập vào đối tượng “gián tiếp” thông qua con trỏ. Giả sử x là một biến kiểu int và px là con trỏ được khai báo: int x, *px; Phép toán một ngôi & cho địa chỉ của đối tượng cho nên câu lệnh px = &x; sẽ gán địa chỉ của x cho biến px; px bây giờ được gọi là “trỏ tới” x. Phép toán & chỉ áp dụng được cho các biến và phần tử mảng; kết cấu kiểu &(x + 1) và &3 là không hợp lệ. Phép toán một ngôi * coi đối tượng của nó là địa chỉ cần xét và thâm nhập tới địa chỉ đó để lấy ra nội dung của biến. Ví dụ, nếu y là int thì y = *px; sẽ gán cho y nội dung của biến mà px trỏ tới. Vậy dãy px= &x; y = *px; sẽ gán giá trị của x cho y như trongPTIT lệnh y = x; Cũng cần phải khai báo cho các biến tham dự vào việc này: int x, y; int *px; Khai báo của x và y là điều ta đã biết. Khai báo của con trỏ px có điểm mới int *px; có ngụ ý rằng tổ hợp *px có kiểu int. Con trỏ có thể xuất hiện trong các biểu thức. Chẳng hạn, nếu px trỏ tới số nguyên x thì *px có thể xuất hiện trong bất kì ngữ cảnh nào mà x có thể xuất hiện 38
40. y = *px + 1; sẽ đặt y lớn hơn x 1 đơn vị; printf(“%d \ n”,*px); in ra giá trị hiện tại của x. phép toán một ngôi * và & có mức ưu tiên cao hơn các phép toán số học, cho nên biểu thức này lấy bất kì giá trị nào mà px trỏ tới, cộng với 1 rồi gán cho y. Con trỏ cũng có thể xuất hiện bên vế trái của phép gán. Nếu px trỏ tới x thì *px = 0; sẽ đặt x thành không và *px += 1; sẽ tăng x lên như trong trường hợp (*px) + +; Các dấu ngoặc là cần thiết trong ví dụ cuối; nếu không có chúng thì biểu thức sẽ tăng px thay cho việc tăng ở chỗ nó trỏ tới, bởi vì phép toán một ngôi như * và + + được tính từ phải sang trái. Cuối cùng, vì con trỏ là biến nên ta có thể thao tác chúng như đối với các biến khác. Nếu py là con trỏ nữa kiểu int, thì: py = px; sẽ sao nội dung của px vào py, nghĩa là làm cho py trỏ tới nơi mà px trỏ. Ví dụ sau minh họa những thao tác truy nhập gián tiếp tới biến thông qua con trỏ. Ví dụ 2.10. Thay đổi nội dung của hai biến a và b thông qua con trỏ. #include void main(void){ int a = 5, b = 7; /* giả sử có hai biến nguyên a =5, b = 7*/ int *px, *py; /* khai báo hai con trỏ kiểu int */ px = &a; /* px trỏ tới x */ printf(“\n Nội dung con trỏ px =%d”, *px); *px = *px + 10; /* Nội dung của *px là 15*/ /* con trỏ px đã thay đổi nội dung của a */ printf(“\n Giá trị của a = %d”, a); px = &b; /* px trỏ tới b */ py = px; /* con trỏ py thay đổi giá trị của b thông qua con trỏ px*/ *py = *py + 10; printf(“\n Giá trị của b=%d”,PTIT b); } Kết quả thực hiện chương trình: Nội dung con trỏ px : 5 Giá trị của a : 15 Giá trị của b : 17 2.5.2. Con trỏ và đối của hàm Để thay đổi trực tiếp nội dung của biến trong hàm thì đối của hàm phải là một con trỏ. Đối với những biến có kiểu cơ bản, chúng ta sử dụng toán tử &(tên_biến) để truyền địa chỉ của biến cho hàm như trong ví dụ đổi nội dung của biến x và biến y trong hàm swap(&x,&y) sau: 39
41. void swap(int *px, int *py) { int temp; temp = *px; *px = *py; *py = temp; } Con trỏ thông thường được sử dụng trong các hàm phải cho nhiều hơn một giá trị (có thể nói rằng swap cho hai giá trị, các giá trị mới thông qua đối của nó). 2.5.3. Con trỏ và mảng Mảng trong C thực chất là một hằng con trỏ, do vậy, mọi thao tác đối với mảng đều có thể được thực hiện thông qua con trỏ. Khai báo int a[10]; xác định mảng có kích thước 10 phần tử int, tức là một khối 10 đối tượng liên tiếp a[0], a[1], a[9]. Cú pháp a[i] có nghĩa là phần tử của mảng ở vị trí thứ i kể từ vị trí đầu. Nếu pa là con trỏ tới một số nguyên, được khai báo là int *pa; thì phép gán pa = &a[0]; sẽ đặt pa để trỏ tới phần tử đầu của a; tức là pa chứa địa chỉ của a[0]. Bây giờ phép gán x = *pa; sẽ sao nội dung của a[0] vào x. Nếu pa trỏ tới một phần tử của mảng a thì theo định nghĩa pa + 1 sẽ trỏ tới phần tử tiếp theo và pa -i sẽ trỏ tới phần tử thứ i trước pa, pa + i sẽ trỏ tới phần tử thứ i sau pa. Vậy nếu pa trỏ tới a[0] thì *(pa + 1) PTIT sẽ cho nội dung của a[1], pa+i là địa chỉ của a[i] còn *(pa + i) là nội dung của a[i]. Định nghĩa “cộng 1 vào con trỏ” và mở rộng cho mọi phép toán số học trên con trỏ được tăng theo tỉ lệ kích thước lưu trữ của đối tượng mà pa trỏ tới. Vậy trong pa + i, i sẽ được nhân với kích thước của kiểu dữ liệu mà pa trỏ tới trước khi được cộng vào pa. Sự tương ứng giữa việc định chỉ số và phép toán số học trên con trỏ là rất chặt chẽ. Trong thực tế, việc tham trỏ tới mảng được trình biên dịch chuyển thành con trỏ tới điểm đầu của mảng. Kết quả là tên mảng chính là một biểu thức con trỏ. Vì tên mảng là đồng nghĩa với việc định vị phần tử thứ 0 của mảng a nên phép gán pa = &a[0]; cũng có thể viết là 40
42. pa = a; Điều cần chú ý là để tham trỏ tới a[i] có thể được viết dưới dạng *(a + i). Trong khi xử lý a[i], C chuyển tức khắc nó thành *(a + i); hai dạng này hoàn toàn là tương đương nhau. áp dụng phép toán & cho cả hai dạng này ta có &a[i] và (a + i) là địa chỉ của phần tử thứ i trong mảng a. Mặt khác, nếu pa là con trỏ thì các biểu thức có thể sử dụng nó kèm thêm chỉ số: pa[i] đồng nhất với *(pa + i). Tóm lại, bất kì một mảng và biểu thức chỉ số nào cũng đều được viết như một con trỏ. Có một sự khác biệt giữa tên mảng và con trỏ cần phải nhớ đó là : Con trỏ là một biến, nên pa = a và pa ++ đều là các phép toán đúng, còn tên mảng là một hằng chứ không phải là biến nên kết cấu kiểu a = pa hoặc a++ hoặc p = &a là không hợp lệ. Khi truyền một tên mảng cho hàm thì tên của mảng là địa chỉ đầu của mảng, do vậy, tên mảng thực sự là con trỏ. Ta có thể dùng sự kiện này để viết ra bản mới của strlen, tính chiều dài của xâu kí tự. int strlen( char * s) /*cho chiều dài của xâu s*/ { int n; for (n = 0; *s ! = ’\ 0’; s + +) n + +; return(n); } Việc tăng s là hoàn toàn hợp lệ vì s là biến con trỏ; s + + không ảnh hưởng tới xâu kí tự trong hàm gọi tới strlen mà chỉ làm tăng bản sao riêng của địa chỉ trong strlen. Vì các tham biến hình thức trong định nghĩa hàm char s[ ]; và char *s; là hoàn toàn tương đương. Khi truyền một tên mảng cho hàm, hàm có thể coi rằng nó xử líPTIT hoặc mảng hoặc con trỏ là giống nhau. Nếu p và q trỏ tới các thành phần của cùng một mảng thì có thể áp dụng được các quan hệ như = v.v chẳng hạn p < q là đúng, nếu p con trỏ tới thành phần đứng trước thành phần mà q trỏ tới trong mảng. Các quan hệ = = và != cũng áp dụng được. Có thể so sánh một con trỏ với giá trị NULL. Nhưng so sánh các con trỏ trỏ tới các mảng khác nhau sẽ không đưa lại kết quả mong muốn. Tiếp nữa, con trỏ và số nguyên có thể cộng hoặc trừ cho nhau như kết cấu p + n nghĩa là đối tượng thứ n sau đối tượng do p trỏ tới. Điều này đúng với bất kể loại đối tượng nào mà p được khai báo sẽ trỏ tới; trình biên dịch sẽ tính tỉ lệ n theo kích thước của 41
43. các đối tượng do p trỏ tới, điều này được xác định theo khai báo của p. Chẳng hạn trên PC AT, nhân từ tỉ lệ là 1 đối với char, 2 đối với int và short, 4 cho long và float. Phép trừ con trỏ cũng hợp lệ; nếu p và q trỏ tới các thành phần của cùng một mảng thì p - q là số phần tử giữa p và q. Dùng sự kiện này ta có thể viết ra một bản khác cho strlen: /*cho độ dài xâu s*/ int strlen( char *s) { char *p = s; while (*p ! = ’\ 0’) p + +; return(p-s); } Trong khai báo, p được khởi đầu là s, tức là trỏ tới kí tự đầu tiên. Chu trình while, kiểm tra lần lượt từng kí tự xem đã là ‘\ 0’ chưa để xác định cuối xâu. Vì ‘\ 0’ là 0 và vì while chỉ kiểm tra xem biểu thức có là 0 hay không nên có thể bỏ phép thử tường minh. Vậy ta có thể viết lại chu trình trên while (*p) p + +; Do p trỏ tới các kí tự nên p + + sẽ chuyển p để trỏ sang kí tự tiếp theo và p - s sẽ cho số các kí tự đã lướt qua, tức là độ dài của xâu. Ví dụ sau minh họa rõ hơn về phương pháp sử dụng con trỏ. 2.6. Con trỏ với mảng nhiều chiều C không hạn chế số chiều của mảng nhiều chiều mặc dù trong thực tế có khuynh hướng sử dụng mảng con trỏ nhiều hơn. Trong mục này, ta sẽ đưa ra mối liên hệ giữa con trỏ và mảng nhiều. PTIT Khi xử lý với các mảng nhiều chiều, thông thường lập trình viên thường đưa ra khai báo float A[3][3]; hoặc float A[N][N] với N được định nghĩa là cực đại của cấp ma trận vuông mà chúng ta cần giải quyết. Để tạo lập ma trận, chúng ta cũng có thể xây dựng thành hàm riêng : Init_Matrix( float A[N][N], int n); hoặc có thể khởi đầu trực tiếp ngay sau khi định nghĩa: float A[3][3] = { {1 , 2 , 4}, {4 , 8 , 12}, 42
44. {3 , -3 , 0 } } hoặc A[][3] = { {1 , 2 , 4}, {4 , 8 , 12}, {3 , -3 , 0 } } Cả hai cách khởi đầu đều bắt buộc phải có chỉ số cột. Nhưng để thấy rõ được mối liên hệ giữa mảng nhiều chiều và con trỏ, chúng ta phải phân tích kỹ cấu trúc lưu trữ của bảng nhiều chiều. Vì tên của mảng là địa chỉ của mảng đó trong bộ nhớ điều đó dẫn tới những kết quả như sau: Địa chỉ của ma trận A[3][3] là A đồng thời là địa chỉ hàng thứ 0 đồng thời là địa chỉ của phần tử đầu tiên của ma trận: Địa chỉ đầu của ma trận A là A = A[0] = *(A + 0) = & A[0][0] ; Địa chỉ hàng thứ nhất: A[1] = *(A + 1) = &A[1][0]; Địa chỉ hàng thứ i : A[i] = *(A+i) = &A[i][0]; Địa chỉ phần tử A[i][j] = ( *( A+i ) ) + j; Nội dung phần tử A[i][j] = *( *( A+i ) ) + j ); Ví dụ 2.13: Kiểm chứng lại mối quan hệ giữa mảng nhiều chiều với con trỏ thông qua cấu trúc lưu trữ của nó trong bộ nhớ: #include #include void main(void) { PTIT float A[3][3] ; /* khai báo mảng hai chiều gồm 9 phần tử nguyên*/ int i, j; /* Địa chỉ của các hàng*/ for(i=0; i<3; i++) printf(“\n Địa chỉ hàng thứ %d là :%p”, i, A[i]); /* Địa chỉ hàng truy nhập thông qua con trỏ*/ printf(“\n Truy nhập bằng con trỏ :”); for(i=0; i<3; i++) printf(“\n Địa chỉ hàng thứ %d là :%p”, i, *(A+i) ); /*Địa chỉ các phần tử */ for(i=0; i<3;i++){ printf(“\n”); for(j=0;j<3;j++) 43
45. printf(“%10p”,&A[i][j]); } /*Địa chỉ các phần tử truy nhập thông qua con trỏ*/ printf(“\n Truy nhập bằng con trỏ”); for(i=0; i<3;i++){ printf(“\n”); for(j=0;j<3;j++) printf(“%10p”, ( *( A+i ) ) + j ); } getch(); } Kết quả thực hiện chương trình: Địa chỉ hàng thứ 0 = FFD2 Địa chỉ hàng thứ 1 = FFDE Địa chỉ hàng thứ 2 = FFEA Truy nhập bằng con trỏ: Địa chỉ hàng thứ 0 = FFD2 Địa chỉ hàng thứ 1 = FFDE Địa chỉ hàng thứ 2 = FFEA Địa chỉ phần tử A[0][0]= FFD2 Địa chỉ phần tử A[0][1]= FFD6 Địa chỉ phần tử A[0][2]= FFDA Địa chỉ phần tử A[1][0]= FFDE Địa chỉ phần tử A[1][1]= FFE2 Địa chỉ phần tử A[1][2]= FFE6 Địa chỉ phần tử A[2][0]= FFEA Địa chỉ phần tử A[2][1]= FFEE Địa chỉ phần tử A[2][2]= FFF2 Truy nhập bằng con trỏ: PTIT Địa chỉ phần tử A[0][0]= FFD2 Địa chỉ phần tử A[0][1]= FFD6 Địa chỉ phần tử A[0][2]= FFDA Địa chỉ phần tử A[1][0]= FFDE Địa chỉ phần tử A[1][1]= FFE2 Địa chỉ phần tử A[1][2]= FFE6 Địa chỉ phần tử A[2][0]= FFEA Địa chỉ phần tử A[2][1]= FFEE Địa chỉ phần tử A[2][2]= FFF2 Như vậy, truy nhập mảng nhiều chiều thông qua các phép toán của mảng cũng giống như truy nhập của mảng nhiều chiều thông qua con trỏ. C cung cấp cho người sử 44
46. dụng một khai báo tương đương với mảng nhiều chiều. Đó là, thay vì khai báo float A[3][3] ; chúng ta có thể đưa ra khai báo tương đương float (*A)[3]; khai báo một con trỏ kiểu float có thể trỏ tới bảng gồm 3 phần tử float. Như vậy, những hàm được truyền vào các mảng nhiều chiều như : Init_Matrix( float A[N][N], int n); có thể được thay thế bằng: Init_Matrix( float (*A)[N], int n); Dấu (*A) là cần thiết vì dấu [] có thứ tự ưu tiên cao hơn dấu * và khi đó chương trình dịch sẽ hiểu float *A[N] thành một mảng gồm N con trỏ. PTIT 45
47. BÀI TẬP CHƯƠNG 2 2.1. Viết chương trình tính giá trị đa thức P(x) tại điểm x0. 2.2. Viết chương trình tình đạo hàm cấp n của đa thức P(x) bậc n. 2.3. Viết chương trình tính tổng hai đa thức P(x) bậc n và Q(x) bậc m. 2.4. Viết chương trình tính hiệu hai đa thức P(x) bậc n và Q(x) bậc m. 2.5. Viết chương trình tính tích hai đa thức P(x) bậc n và Q(x) bậc m. 2.6. Viết chương trình tính đa thức thương và đa thức phần dư của đa thức P(x) bậc n và Q(x) bậc m. 2.7. Thuật toán cộng. Sử dụng thuật toán cộng xây dựng chương trình cộng hai số nguyên a và b có biểu diễn nhị phân tương ứng là a = (a1, a2. . . , an), b=(b1, b2, . . ., bn), 0 W với Z  U, W  U } . Kí hiệu -> được hiểu là dẫn được. Ta gọi X+ là bao đóng của tập thuộc tính X trên tập phụ thuộc hàm F được xây dựng theo thuật toán đệ qui sau: i) X0 = X ii) Xi = Xi-1  W với Z  U, W  U và Z ->W F 46
48. iii) Nếu Xk = Xk-1 thì X+ = Xk với mọi phép thử trên mỗi phụ thuộc hàm (mỗi phụ thuộc hàm được thử ít nhất một lần mà không bổ xung thêm được thuộc tính mới). Cho file dữ liệu baodong.in được tổ chức như sau: Dòng đầu tiên ghi lại một số tự nhiên N là số các phụ thuộc hàm trong tập phụ thuộc hàm F, dòng kế tiếp là một xâu kí tự ghi lại tập thuộc tính U, N dòng tiếp theo ghi các phụ thuộc hàm, mỗi phụ thuộc hàm được ghi trên một dòng, dòng cuối cùng là tập thuộc tính X  U. Hãy tìm bao đóng của tập phụ thuộc hàm X và ghi lại kết quả vào file Baodong.out. Ví dụ file baodong.in Baodong.out 5 ABCDEFGHIJ ABCDEFGHIJ A -> BCD BC-> CD E -> FGH EF->FGH AE -> IJ AE 2.13. Khoá. Cho lược đồ quan hệ  = trong đó U là tập thuộc tính, F là tập phụ thuộc hàm, K  U. K được gọi là khoá của  = nếu: a) Bao đóng của K bằng U (K+ = U); b) Với mọi thuộc tính A K thì (K\A)+ U. Hãy tìm một khoá của lược đồPTIT quan hệ  = . Dữ liệu vào cho bởi file khoa.in, dòng đầu tiên ghi lại số tự nhiên n là số các phụ thuộc hàm, dòng kế tiếp ghi lại tập thuộc tính U, n dòng tiếp theo ghi lại các phụ thuộc hàm, mỗi phụ thuộc hàm được viết trên một dòng, vế trái và vế phải của mỗi phụ thuộc hàm được phân biệt với nhau bởi một hoặc vài ký tự rỗng. Kết quả ghi lại trong file khoa.out. Ví dụ sau sẽ minh họa cho file khoa.in và khoa.out. khoa.in khoa.out 3 AE ABCDEFGHIJ A BCD E EGH 47
49. AE IJ 2.14. Phủ. Cho lược đồ quan hệ  = và  = . F được gọi là phủ của G + nếu với mọi f: X-> Y F thì X GY và với mọi g: X-> Y G thì X+FY. Hãy kiểm tra tính tương đương của hai tập phụ thuộc hàm F/U và G/U. Dữ liệu vào cho bởi file phu.in, kết quả ghi lại trong file phu.out. 2.15. Phủ tự nhiên. Cho lược đồ quan hệ  = , và tập phụ thuộc hàm G/U. G được gọi là phủ tự nhiên của F nếu: a) G là phủ của F; b) Với mọi f:X Y G thì X Y = ; c) Với mọi X Y, Z W F thì X Z. Hãy tìm một phủ tự nhiên của F. Dữ liệu vào cho bởi file Phutn.in, kết quả ghi lại trong file Phutn.out. 2.16. Phủ không dư. Cho lược đồ quan hệ  = , và tập phụ thuộc hàm G/U. G được gọi là phủ không dư của F nếu: a) G là phủ của F; b) Với mọi g:X Y G thì { G \ g } không là phủ của G. Xuất phát từ một phủ tự nhiên, hãy tìm một phủ không dư của F. Dữ liệu vào cho bởi file phukd.in, kết quả ghi lại trong file phukd.out. 2.17. Cho file dữ liệu dathuc.in được tổ chức như sau: - Dòng đầu tiên ghi lại bốn số nguyên, n, m, xo, l, mỗi số cách nhau bởi một và dấu trống; - Dòng kế tiếp ghi lại n +1 số thực là hệ số của đa thức P(x) bậc n; - Dòng thứ 3 ghi lại m +PTIT 1 số thực là hệ số của đa thức Q(x) bậc m. Hãy viết chương trình đưa kết quả ra màn hình và ghi vào file dathuc.out với những thông tin sau: - Tính giá trị của các đa thức P(x0), Q(x0) ghi ở dòng thứ nhất mỗi số cách nhau một hay và dấu trống; - Tính đạo hàm cấp l <n, l<m của đa thức P(x), Q(x) và ghi vào trong File kết quả ở hai dòng kế tiếp; - Dòng tiếp theo là đa thức tổng R(x) = P(x) + Q(x); - Dòng tiếp theo là đa thức hiệu R(x) = P(x) - Q(x); - Dòng tiếp theo là đa thức tích R(x) = P(x) / Q(x); 48
50. - Hai dòng cuối cùng là đa thức thương và đa thức phần dư của phép chia P(x)/Q(x). Ví dụ về File dathuc.in: 3 2 1 1 1 3 3 1 1 2 1 dathuc.out 8 4 3 6 3 2 2 1 4 5 2 1 2 1 0 1 5 10 10 5 1 1 1 0 0 2.18. Cho ma trận A và cấp m n. Hãy tìm tổng, hiệu của hai ma trận A và B. 2.19. Cho ma trận A cấp m n và ma trận B cấp n m. Hãy tính tích của hai ma trận A và B. 2.20. Cho File dữ liệu matrix.in được tổ chức theo khuôn dạng như sau: - Dòng đầu tiên là một số tự nhiên n là cấp của ma trận vuông A; - n dòng tiếp theo mỗi dòng ghi n số thực. Mỗi số thực được phân biệt với nhau bởi một hoặc vài kí tự trống là các phần tử A[i][j] của ma trận vuông A; Hãy viết chương trình tìmPTIT hàng, cột hoặc đường chéo có tổng các phần tử là lớn nhất. Ghi kết quả hàng, cột hoặc đường chéo vào file matrix.out mỗi phần tử được phân biệt bởi một vài ký tự trống. Ví dụ file matrix.in 3 1 2 4 4 8 12 3 -3 0 file matricx.out 4 8 12 49
51. 2.21. Cho File dữ liệu matrix.in được tổ chức theo khuôn dạng như sau: - Dòng đầu tiên là một số tự nhiên n là cấp của ma trận vuông A; - n dòng tiếp theo mỗi dòng ghi n số thực. Mỗi số thực được phân biệt với nhau bởi một hoặc vài kí tự trống là các phần tử A[i][j] của ma trận vuông A; Tìm định thức của A và ghi lại kết quả vào file matrix.out. Ví dụ file matrix.in 3 1 2 4 4 8 12 3 -3 0 file matrix.out -36 2.21. Cho File dữ liệu matrix.in được tổ chức theo khuôn dạng như sau: - Dòng đầu tiên là một số tự nhiên n là cấp của ma trận vuông A; - n dòng tiếp theo mỗi dòng ghi n số thực mỗi số thực được phân biệt với nhau bởi một hoặc vài kí tự trống là các phần tử A[i][j] của ma trận vuông A; Hãy viết chương trình tìm ma trận nghịch đảo của ma trận vuông A. Ghi lại kết quả vào file matrix.in theo từng dòng. Trong trường hợp ma trận không tồn tại nghịch đảo ghi lại thông báo “Nghịch đảo không tồn tại”. Ví dụ file matrix.in 3 1 2 3 2 5 PTIT3 1 0 8 file matrix.out -40 16 9 13 -5 -3 5 -2 -1 2.23. Cho File dữ liệu matrix.in được tổ chức theo khuôn dạng như sau: - Dòng đầu tiên là một số tự nhiên n là cấp của ma trận vuông A; 50
52. - n dòng tiếp theo mỗi dòng ghi n + 1 số thực mỗi số thực được phân biệt với nhau bởi một hoặc vài kí tự trống là các phần tử A[i][j] của ma trận vuông A và hệ số của vector n thành phần B; Hãy viết chương trình giải hệ phương trình tuyến tính thuần nhất n ẩn AX=B bằng phương pháp khử gaus. Nghiệm của hệ được ghi lại trong file matrix.out trên một dòng. Trong trường hợp hệ suy biến. Ghi lại thông báo “Hệ suy biến”. Ví dụ về file matrix.in 3 1 1 -1 1 2 -1 1 0 3 1 -2 1 file matrix.out 0.33 1.33 0.66 2.24. Ma trận nhị phân là ma trận mà các phần tử của nó hoặc bằng 0 hoặc bằng 1. Đối với ma trận nhị phân người ta định nghĩa các phép hợp, giao, nhân logic và luỹ thừa như sau: - Phép hợp. Cho hai ma trận nhị phân cùng cấp m n , A = { aij }, B = { bij } (i = 1, 2. ., m, j = 1,2, . ., n ). Hợp của A với B cho ta ma trận C = { cij | cij = aij bij ; i =1, 2, . . , m; j= 1, 2, . . , n}. Ví dụ: A = 1 0 1 B= 0 1 0 0 1 0 1 1 0 C = A  B = 1 1 1 1 1 0 - Phép giao. Phép giao của haiPTIT ma trận A = {aij} và B = {bij} cùng cấp m n ho ta một ma trận cùng cấp C = { cij | cij = aij  bij}; i = 1, 2, . . ., m; j = 1, 2, . . ., n. Ví dụ: A = 1 0 1 B= 0 1 0 0 1 0 1 1 0 C = A  B = 0 0 0 0 1 0 - Phép nhân logic. Cho ma trận nhị phân A = {aij} cấp m k và B = {bij } cấp k n. Ma trận C = { cij | cij = (ai1 b1j)  (ai2  b2j)  . . . (aikbkj)} cấp m n được gọi là ma trận tích logic của ma trận A với ma trận B và được ký hiệu là C = AB. Ví dụ: 51
53. 1 0 A = 0 1 B = 1 1 0 1 0 0 1 1 1 1 0 C = A  B = 0 1 1 1 1 0 - Phép luỹ thừa logic bậc r. Luỹ thừa logic bậc r của ma trận vuông nhị phân A, ký hiệu A[r] = A  A A  . . .A (r lần). Bài toán : Cho hai ma trận vuông nhị phân cấp n A = {aij} và B = {bij}. Hãy viết chương trình tính hợp, giao, nhân logic, và luỹ thừa bậc r của A và B. 2.25. Cho một bảng hình vuông gồm 5 x 5 hình vuông nhỏ. Trên mỗi ô ghi một chữ số thập phân như hình vẽ sau: 3 5 1 1 1 5 0 0 3 3 1 0 3 4 3 1 3 4 2 1 1 3 3 1 3 Các chữ số điền vào phải thoả mãn những yêu cầu sau: Yêu cầu 1: 12 số bao gồm năm số năm chữ số theo từng dòng đọc từ trái sang phải, năm số năm chữ số theo từng cột đọc từ trên xuống dưới, hai số năm chữ số theo hai đường chéo đọc từ trái sang phải đều là các số nguyên tố với 5 chữ số có nghĩa. 12 số này không nhất thiết phải khác nhau. Yêu cầu 2: Tổng các chữ số của mỗi số trong 12 số trên đều bằng nhau. Trong ví dụ trên, tổng các chữ số của mỗi số đều bằng 11. Hãy viết chương trình thực hiện các công việc sau: 1- Nhập dữ liệu từ File ngto.in. PTITTrong đó, dòng thứ nhất ghi số là tổng các chữ số của những số cần xây dựng, dòng thứ hai ghi chữ số ở góc bên trái hình vuông. 2- Tìm các lời giải có thể có ứng với dữ liệu vào đã nhập vào file ngto.out . Một lời giải là một mảng 5 x 5 ghi thành 5 dòng mỗi dòng 5 chữ số tương ứng với các hàng của hình vuông, hai lời giải được ghi cách nhau bởi một dòng trống, hai lời giải khác nhau nếu hai hình vuông có ít nhất một ô khác nhau. Trong ví dụ trên, ta có các file input& output như sau: Ngto.in ngto.out 11 3 5 1 1 1 3 5 0 0 3 3 1 0 3 4 3 1 3 4 2 1 52
54. CHƯƠNG 3. DUYỆT VÀ ĐỆ QUI 3.1. Định nghĩa bằng đệ qui Trong thực tế, chúng ta gặp rất nhiều đối tượng mà khó có thể định nghĩa nó một cách tường minh, nhưng lại dễ dàng định nghĩa đối tượng qua chính nó. Kỹ thuật định nghĩa đối tượng qua chính nó được gọi là kỹ thuật đệ qui (recursion). Đệ qui được sử dụng rộng rãi trong khoa học máy tính và lý thuyết tính toán. Các giải thuật đệ qui đều được xây dựng thông qua hai bước: bước phân tích và bước thay thế ngược lại. Ví dụ 3.1. Để tính tổng S(n) = 1 + 2 + . . .+ n, chúng ta có thể thực hiện thông qua hai bước như sau: Bước phân tích: Để tính toán được S(n) trước tiên ta phải tính toán trước S(n-1) sau đó tính S(n) = S(n-1) +n. Để tính toán được S(n-1), ta phải tính toán trước S(n-2) sau đó tính S(n-1) = S(n-2) + n-1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Để tính toán được S(2), ta phải tính toán trước S(1) sau đó tính S(2) = S(1) + 2. Và cuối cùng S(1) chúng ta có ngay kết quả là 1 Bước thay thế ngược lại: Xuất phát từ S(1) thay thế ngược lại chúng ta xác định S(n): S(1) = 1 S(2) = S(1) + 2 PTIT S(3) = S(2) + 3 . . . . . . . . . . . . S(n) = S(n - 1) + n Ví dụ 3.2. Định nghĩa hàm bằng đệ qui Hàm f(n) = n! Dễ thấy f(0) = 1. Vì (n+1) ! = 1 . 2.3 . . . n(n+1) = n! (n+1), nên ta có: f(n+1) = ( n+1) . f(n) với mọi n nguyên dương. Hàm f(n) = an 53
55. Vì a0 = 1; f(n+1) = an+1 = a.an = a. f(n) nên f (n) = a. f(n) với mọi số thực a và số tự nhiên n. Ví dụ 3.3. Tập hợp định nghĩa bằng đệ qui Định nghĩa đệ qui tập các xâu : Giả sử * là tập các xâu trên bộ chữ cái . Khi đó * được định nghĩa bằng đệ qui như sau:  *, trong đó  là xâu rỗng wx * nếu w * và x * Ví dụ 3.4. Cấu trúc tự trỏ được định nghĩa bằng đệ qui struct node { int infor; struct node *left; struct node *right; }; 3.2. Giải thuật đệ qui Một thuật toán được gọi là đệ qui nếu nó giải bài toán bằng cách rút gọn bài toán ban đầu thành bài toán tương tự như vậy sau một số hữu hạn lần thực hiện. Trong mỗi lần thực hiện, dữ liệu đầu vào tiệm cận tới tập dữ liệu dừng. Ví dụ: để giải quyết bài toán tìm ước số chung lớn nhất của hai số nguyên dương a và b với b > a, ta có thể rút gọn về bài toán tìm ước số chung lớn nhất của (b mod a) và a vì USCLN(b mod a, a) = USCLN(a,b). Dãy các rút gọn liên tiếp có thể đạt được cho tới khi đạt điều kiện dừng USCLN(0, a) = USCLN(a, b) = a. Sau đây là ví dụ về một số thuật toán đệ qui thông dụng. Thuật toán 1: Tính an bằng giải thuật đệ qui, với mọi số thực a và số tự nhiên n. double power( float a, int n ){ if ( n ==0) PTIT return(1); return(a *power(a,n-1)); } Thuật toán 2: Thuật toán đệ qui tính ước số chung lớn nhất của hai số nguyên dương a và b. int USCLN( int a, int b){ if (a == 0) return(b); return(USCLN( b % a, a)); } 54
56. Thuật toán 3: Thuật toán đệ qui tính n! long factorial( int n){ if (n ==1) return(1); return(n * factorial(n-1)); } Thuật toán 4: Thuật toán đệ qui tìm kiếm nhị phân: int binary_search( float *A, int x, int i, int j){ int mid = ( i + j)/2; if ( x > A[mid] && i mid) return(binary_search(A, x, i,mid-1); else if (x == A[mid]) return(mid); return(-1); } Thuật toán 5: Thuật toán đệ qui tính số fibonacci thứ n int fibonacci( int n) { if (n==0) return(0); else if (n ==1) return(1); return(fibonacci(n-1) + fibonacci(n-2)); } 3.3. Thuật toán sinh kế tiếp Phương pháp sinh kế tiếp dùng để giải quyết bài toán liệt kê của lý thuyết tổ hợp. Thuật toán sinh kế tiếp chỉ được thực hiện trên lớp các bài toán thỏa mãn hai điều kiện sau: PTIT Có thể xác định được một thứ tự trên tập các cấu hình tổ hợp cần liệt kê, từ đó xác định được cấu hình đầu tiên và cấu hình cuối cùng. Từ một cấu hình bất kỳ chưa phải là cuối cùng, đều có thể xây dựng được một thuật toán để suy ra cấu hình kế tiếp. Tổng quát, thuật toán sinh kế tiếp có thể được mô tả bằng thủ tục genarate, trong đó Sinh_Kế_Tiếp là thủ tục sinh cấu hình kế tiếp theo thuật toán sinh đã được xây dựng. Nếu cấu hình hiện tại là cấu hình cuối cùng thì thủ tục Sinh_Kế_Tiếp sẽ gán cho stop giá trị true, ngược lại cấu hình kế tiếp sẽ được sinh ra. 55
57. Procedure generate; begin stop :=false; while not stop do begin ; Sinh_Kế_Tiếp; end; end; Sau đây chúng ta xét một số ví dụ minh họa cho thuật toán sinh. 3.3.1. Bài toán liệt kê các tập con của tập n phần tử Một tập hợp hữu hạn gồm n phần tử đều có thể biểu diễn tương đương với tập các số tự nhiên 1, 2, . . . n. Bài toán được đặt ra là: Cho một tập hợp gồm n phần tử X = { X1, X2, . ., Xn }, hãy liệt kê tất cả các tập con của tập hợp X. Để liệt kê được tất cả các tập con của X, ta làm tương ứng mỗi tập Y X với một xâu nhị phân có độ dài n là B = { B1, B2, . . , Bn } sao cho Bi = 0 nếu Xi Y và Bi = 1 nếu Xi Y; như vậy, phép liệt kê tất cả các tập con của một tập hợp n phần tử tương đương với phép liệt kê tất cả các xâu nhị phân có độ dài n. Số các xâu nhị phân có độ dài n là 2n. Bây giờ ta đi xác định thứ tự các xâu nhị phân và phương pháp sinh kế tiếp. Nếu xem các xâu nhị phân b = { b1, b2, . . , bn } như là biểu diễn của một số nguyên dương p(b). Khi đó thứ tự hiển nhiên nhất là thứ tự tự nhiên được xác định như sau: Ta nói xâu nhị phân b = { b1, b2, . . , bn } có thứ tự trước xâu nhị phân b’ = { b’1, 4 b’2, . . , b’n } và kí hiệu là b<b’ nếu p(b) < p(b’). Ví dụ với n= 4: chúng ta có 2 = 16 xâu nhị phân (tương ứng với 16 tập con của tập gồm n phần tử) được liệt kê theo thứ tự từ điển như sau: b PTIT p(b) 0 0 0 0 0 0 1 1 0 1 0 2 0 1 1 3 1 0 0 4 1 0 1 5 1 1 0 6 1 1 1 7 56
58. Từ đây ta xác định được xâu nhị phân đầu tiên là 00. .00 và xâu nhị phân cuối cùng là 11 11. Quá trình liệt kê dừng khi ta được xâu nhị phân 1111. Xâu nhị phân kế tiếp là biểu diễn nhị phân của giá trị xâu nhị phân trước đó cộng thêm 1 đơn vị. Từ đó ta nhận được qui tắc sinh kế tiếp như sau: Tìm chỉ số i đầu tiên theo thứ tự i = n, n-1, . ., 1 sao cho bi = 0. Gán lại bi = 1 và bj = 0 với tất cả j>i. Dãy nhị phân thu được là dãy cần tìm Thuật toán sinh xâu nhị phân kế tiếp void Next_Bit_String( int *B, int n ){ i = n; while (bi ==1 ) { bi = 0 i = i-1; } bi = 1; } Sau đây là văn bản chương trình liệt kê các xâu nhị phân có độ dài n: #include #define MAX 100 #define TRUE 1 #define FALSE 0 int Stop, count; void Init(int *B, int n){ int i; for(i=1; i 0 && B[i]){ B[i]=0; i ; } if(i==0 ) Stop=TRUE; 57
59. else B[i]=1; } void Generate(int *B, int n){ int i; Stop = FALSE; while (!Stop) { Result(B,n); Next_Bits_String(B,n); } } void main(void){ int i, *B, n;clrscr(); printf("\n Nhap n=");scanf("%d",&n); B =(int *) malloc(n*sizeof(int)); Init(B,n);Generate(B,n);free(B);getch(); } 3.3.2. Bài toán liệt kê tập con m phần tử của tập n phần tử Bài toán: Cho tập hợp X = { 1, 2, . ., n }. Hãy liệt kê tất cả các tập con m < n phần tử của X. Mỗi tập con m phần tử của X có thể biểu diễn như một bộ có thứ tự a = (a1, a2, , am) thoả mãn 1 <= a1< a2 < <am<=n Trên các tập con m phần tử của X, ta định nghĩa thứ tự của các tập con như sau: Ta nói tập con a = (a1, a2, , am) có thứ tự trước tập a’ = (a’1, a’2, , a’m) theo thứ tự từ điển và kí hiệu a < a’ nếu tìm được chỉ số k sao cho: a1 = a’1 , a2 = a’2 , ak-1 = a’PTITk-1 , ak < a’k Ví dụ X = { 1, 2, 3, 4, 5 }, n = 5, m = 3. Các tập con 3 phần tử của X được liệt kê theo thứ tự từ điển như sau: 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 3 3 4 5 58
60. Như vậy, tập con đầu tiên là 1 , 2, . ., m. Tập con cuối cùng là n-m+1, n-m+2, . ., n. Giả sử ta có tập con chưa phải là cuối cùng (nhỏ hơn so với tập con n-m+1, n-m+2, . ., n), khi đó tập con kế tiếp của a được sinh bởi các qui tắc biến đổi sau: Tìm từ bên phải dãy a1, a2, , am phần tử ai n-m+i, Thay thế ai = ai +1; Thay aj bởi ai + j - i, với j = i +1, i + 2, . ., m. Với qui tắc sinh như trên, chúng ta có thể mô tả bằng thuật toán sau: Thuật toán liệt kê tập con kế tiếp m phần tử của tập n phần tử: void Next_Combination( int *A, int m){ i = m; while ( ai == m-n+i) i = i -1; ai = ai + 1; for ( j = i+1; j #include #define TRUE 1 #define FALSE 0 #define MAX 100 int n, k, count, C[MAX], Stop; void Init(void){ int i; printf("\n Nhap n="); scanf("%d", &n); printf("\n Nhap k="); scanf("%d", &k); for(i=1; i 0 && C[i]==n-k+i) i ; 59
61. if(i>0) { C[i]= C[i]+1; for(j=i+1; j<=k; j++) C[j]=C[i]+j-i; } else Stop = TRUE; } void Combination(void){ Stop=FALSE; while (!Stop){Result(); Next_Combination(); } } void main(void){ clrscr(); Init();Combination();getch(); } 3.3.3. Bài toán liệt kê các hoán vị của tập n phần tử Bài toán: Cho tập hợp X = { 1, 2, . ., n }. Hãy liệt kê tất cả các hoán vị của X. Mỗi hoán vị n phần tử của tập hợp X có thể biểu diễn bởi bộ có thứ tự gồm n thành phần a = (a1, a2, , an) thoả mãn: ai X; i = 1, 2, . ., n; ap aq nếu p q. Trên tập có thứ tự các hoán vị n phần tử của X, ta định nghĩa thứ tự của các hoán vị đó như sau: Hoán vị a = (a1, a2, , an) được gọi là có thứ tự trước hoán vị a’ = (a’1, a’2, , a’n) và kí hiệu a <a’ nếu tìm được chỉ số k sao cho: a1= a’1, a2 = a’2, . ., ak-1=a’PTITk-1, ak <a’k Ví dụ X= { 1, 2, 3} khi đó các hoán vị của 3 phần tử được sắp xếp theo thứ tự từ điển như sau: 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 60
62. Như vậy, hoán vị đầu tiên là 1, 2, . .,n, hoán vị cuối cùng là n, n-1,. .1. Giả sử hoán vị a = (a1, a2, , an) chưa phải là hoán vị cuối cùng, khi đó hoán vị kế tiếp của a được sinh bởi qui tắc sau: Tìm từ phải qua trái hoán vị có chỉ số j đầu tiên thoả mãn aj aj +1 ) j = j -1; k = n; while (aj > ak ) k= k - 1; temp =aj; aj = ak; ak = temp; r = j + 1; s = n; while ( r #define MAX 20 #define TRUE 1 #define FALSE 0 int P[MAX], n, count, Stop;PTIT void Init(void){ int i;count =0; printf("\n Nhap n=");scanf("%d", &n); for(i=1; i<=n; i++) P[i]=i; } void Result(void){ int i;count++; printf("\n Hoan vi %d:",count); for(i=1; i<=n;i++) printf("%3d",P[i]); } 61
63. void Next_Permutaion(void){ int j, k, r, s, temp; j = n-1; while(j>0 && P[j]>P[j+1]) j ; if(j==0) Stop=TRUE; else { k=n; while(P[j]>P[k]) k ; temp = P[j]; P[j]=P[k]; P[k]=temp; r=j+1; s=n; while(r b2 > . . .> bk, và duyệt theo trình tự từ điển ngược. Chẳng hạn với n = 5, chúng ta có thứ tự từ điển ngược của các cách phân chia như sau: 62
64. 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 Như vậy, cách chia đầu tiên chính là n. Cách chia cuối cùng là dãy n số 1. Bây giờ chúng ta chỉ cần xây dựng thuật toán sinh kế tiếp cho mỗi cách phân chia chưa phải là cuối cùng. Thuật toán sinh cách phân chia kế tiếp: void Next_Division(void){ int i, j, R, S, D; i = k; while(i>0 && C[i]==1)i ; if(i>0){ C[i] = C[i]-1; D = k - i +1; R = D / C[i]; S = D % C[i]; k = i; if(R>0){ for(j=i+1; j 0){ k=k+1; C[k] = S; } PTIT } else Stop=TRUE; } Văn bản chương trình được thể hiện như sau: #include #define MAX 100 #define TRUE 1 #define FALSE 0 int n, C[MAX], k, count, Stop; void Init(void){ printf("\n Nhap n="); scanf("%d", &n); 63
65. k=1;count=0; C[k]=n; } void Result(void){ int i; count++; printf("\n Cach chia %d:", count); for(i=1; i 0 && C[i]==1) i ; if(i>0){ C[i] = C[i]-1; D = k - i +1; R = D / C[i]; S = D % C[i]; k = i; if(R>0){ for(j=i+1; j 0){ k=k+1; C[k] = S; } } else Stop=TRUE; } PTIT void Division(void){ Stop = FALSE; while (!Stop){ Result(); Next_Division(); } } void main(void){ clrscr(); Init(); Division(); getch(); } 64
66. 3.4. Thuật toán quay lui (Back track) Phương pháp sinh kế tiếp có thể giải quyết được các bài toán liệt kê khi ta nhận biết được cấu hình đầu tiên của bài toán. Tuy nhiên, không phải cấu hình sinh kế tiếp nào cũng được sinh một cách đơn giản từ cấu hình hiện tại, ngay kể cả việc phát hiện cấu hình ban đầu cũng không phải dễ tìm vì nhiều khi chúng ta phải chứng minh sự tồn tại của cấu hình. Do vậy, thuật toán sinh kế tiếp chỉ giải quyết được những bài toán liệt kê đơn giản. Để giải quyết những bài toán tổ hợp phức tạp, người ta thường dùng thuật toán quay lui (Back Track) sẽ được trình bày dưới đây. Nội dung chính của thuật toán này là xây dựng dần các thành phần của cấu hình bằng cách thử tất cả các khả năng. Giả sử cần phải tìm một cấu hình của bài toán x = (x1, x2, . ., xn) mà i-1 thành phần x1, x2, . ., xi-1 đã được xác định, bây giờ ta xác định thành phần thứ i của cấu hình bằng cách duyệt tất cả các khả năng có thể có và đánh số các khả năng từ 1 . .ni. Với mỗi khả năng j, kiểm tra xem j có chấp nhận được hay không. Khi đó có thể xảy ra hai trường hợp: Nếu chấp nhận j thì xác định xi theo j, nếu i=n thì ta được một cấu hình cần tìm, ngược lại xác định tiếp thành phần xi+1. Nếu thử tất cả các khả năng mà không có khả năng nào được chấp nhận thì quay lại bước trước đó để xác định lại xi-1. Điểm quan trọng nhất của thuật toán là phải ghi nhớ lại mỗi bước đã đi qua, những khả năng nào đã được thử để tránh sự trùng lặp. Để nhớ lại những bước duyệt trước đó, chương trình cần phải được tổ chức theo cơ chế ngăn xếp (Last in first out). Vì vậy, thuật toán quay lui rất phù hợp với những phép gọi đệ qui. Thuật toán quay lui xác định thành phần thứ i có thể được mô tả bằng thủ tục Try(i) như sau: void Try( int i ) { int j; for ( j = 1; j ) { if (i==n) ; else Try(i+1); } } } 65
67. Có thể mô tả quá trình tìm kiếm lời giải theo thuật toán quay lui bằng cây tìm kiếm lời giải sau: Gốc Khả năng chọn x1 Khả năng chọn x2 với x1 đã chọn Khả năng chọn x3 với x1, x2 đã chọn Hình 3.1. Cây liệt kê lời giải theo thuật toán quay lui. 3.4.1. Thuật toán quay lui liệt kê các xâu nhị phân độ dài n Biểu diễn các xâu nhị phân dưới dạng b1, b2, . . ., bn, trong đó bi {0, 1 }. Thủ tục đệ qui Try(i) xác định bi với các giá trị đề cử cho bi là 0 và 1. Các giá trị này mặc nhiên được chấp nhận mà không cần phải thoả mãn điều kiện gì (do đó bài toán không cần đến biến trạng thái). Thủ tục Init khởi tạo giá trị n và biến đếm count. Thủ tục kết quả in ra dãy nhị phân tìm được. Chẳng hạn với n =3 , cây tìm kiếm lời giải được thể hiện như hình 3.2. Gốc PTIT 0 1 0 1 0 1 0 1 0 1 0 1 0 1 000 001 010 011 100 101 110 111 (Hình 3.2. Cây tìm kiếm lời giải liệt kê dãy nhị phân độ dài 3) Văn bản chương trình liệt kê các xâu nhị phân có độ dài n sử dụng thuật toán quay lui được thực hiện như sau: 66
68. #include #include #include #include void Result(int *B, int n){ int i; printf("\n "); for(i=1;i<=n;i++) printf("%3d",B[i]); } void Init(int *B, int n){ int i; for(i=1;i<=n;i++) B[i]=0; } void Try(int i, int *B, int n){ int j; for(j=0; j<=1;j++){ B[i]=j; if(i==n) { Result(B,n); } else Try(i+1, B, n); } } void main(void){ int *B,n;clrscr(); printf("\n Nhap n=");scanf("%d",&n); B=(int *) malloc(n*sizeof(int)); Init(B,n); Try(1,B,n);free(B);PTIT } 3.4.2. Thuật toán quay lui liệt kê các tập con m phần tử của tập n phần tử Biểu diễn tập con k phần tử dưới dạng c1, c2, . ., ck, trong đó 1< c1<c2 . . n . Từ đó suy ra các giá trị đề cử cho ci là từ ci-1 + 1 cho đến n - k + i. Cần thêm vào c0 = 0. Các giá trị đề cử này mặc nhiên được chấp nhận mà không cần phải thêm điều kiện gì. Các thủ tục Init, Result được xây dựng như những ví dụ trên. Cây tìm kiếm lời giải bài toán liệt kê tập con k phần tử của tập n phần tử với n=5, k=3 được thể hiện như trong hình 3.3. 67