Bài giảng Kỹ thuật lập trình: Chương 3.2 - Trường Đại học Ngoại ngữ - Tin học TP.HCM

Bài giảng Kỹ thuật lập trình: Chương 3.2 cung cấp cho người đọc những kiến thức như: Kỹ thuật mảng đánh dấu trạng thái; kỹ thuật mảng đếm; phương pháp mảng đếm;...Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Kỹ thuật lập trình: Chương 3.2 - Trường Đại học Ngoại ngữ - Tin học TP.HCM KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tinTrường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)KỸ THUẬTMẢNG ĐÁNH DẤU TRẠNG THÁIKỹ thuật mảng đánh dấu trạng thái• Vấn đề: Trong nhiều bài toán tin học, việc giải quyết bài toán có thể đưa đến việc phải đánh dấu trạng thái (true/fasle) cho tập số tự nhiên {0, 1, 2, … , ? − 1},• Ví dụ: cho ? số A = {0, 1, 2, … , ? − 1}. Các tập con ? của ? có thể biểu diễn ? = {} 0 0 0 0 0 0 0 0 1 2 3 4 5 6 ? = {3} 0 0 0 1 0 0 0 0 1 2 3 4 5 6 3Kỹ thuật mảng đánh dấu trạng thái ? = {2,4} 0 0 1 0 1 0 0 0 1 2 3 4 5 6 ? = {1,2,4} 0 1 1 0 1 0 0 0 1 2 3 4 5 6• Bài toán: Sinh các tập con của tập ? → bài toán đánh dấu trạng thái cho các số 4Kỹ thuật mảng đánh dấu trạng thái• Để đánh dấu số ? có một trong hai trạng thái chúng ta dùng mảng ???? bool[] states = new bool[n]; • Quy ước ???? ? ?ó ??ạ?? ?ℎá? ?????? ? = ቊ ????? ? ?ℎư? ?ó ??ạ?? ?ℎá? 5Kỹ thuật mảng đánh dấu trạng thái• Ý nghĩa giá trị ?????? ? = ????/????? tùy bài toán • ? thuộc tập hợp hay ? không thuộc tập hợp • ? đã xử lý xong hay ? chưa xử lý • ? là số nguyên tố hay ? không là số nguyên tố • ? là vị trí đã xét hay ? là vị trí chưa xét • ? đã đến hay ? chưa đến •… 6Vận dụng• Bài toán: Liệt kê các số nguyên tố • Cho số nguyên ? (1 ≤ ? ≤ 106 ). Viết chương trình liệt kê các số nguyên tố nhỏ hơn hay bằng ?.• Ví dụ 1 • ? = 10 • Các số nguyên tố nhỏ hơn 10: 2, 3, 5, 7• Ví dụ 2 • ? = 20 • Các số nguyên tố nhỏ hơn 20: 2, 3, 5, 7, 11, 13, 17, 19 7Vận dụng• Thuật toán “Eratosthene” • Cấu trúc dữ liệu: dùng một mảng ? để đánh dấu số nào là số nguyên tố, số nào không phải là số nguyên tố. ???? ?ế? ? ?à ?ố ????ê? ?ố ?[?] = ቊ ????? ?ế? ? ?ℎô?? ?ℎả? ?à ?ố ????ê? ?ố• Ý tưởng: • Ban đầu, chúng ta có tập các số {2,3, … , ?} • Tại mỗi bước, chúng ta chọn số nhỏ nhất trong tập (số nhỏ nhất này là số nguyên tố) và bỏ đi các bội của số đó• Cải tiến • Mọi số không nguyên tố có ước số ≤ ? → chúng ta chỉ cần bỏ các bội của số nguyên tố ≤ ? 8Vận dụng• Bài toán: Tìm các tổng • Cho ? gói kẹo được đánh số từ 1 đến ?. Số lượng kẹo trong các gói được cho trong mảng ? = (?1 , ?2 , … , ? ? ) (1 ≤ ? ≤ 200 và 0 ≤ ? ? ≤ 1000). Một số gói kẹo có thể gôm lại thành một phần và số kẹo trong một phần là tổng số kẹo trong của các gói trong phần đó. Hãy cho biết các loại tổng khác nhau của các phần• Ví dụ: ? = (2,5,4). Ta có 7 phần có tổng khác nhau là • 2 = ?1 • 4 = ?3 • 5 = ?2 • 6 = ?1 + ?3 • 7 = ?1 + ?2 • 9 = ?2 + ?3 • 11 = ?1 + ?2 + ?3 9Vận dụng• Cấu trúc dữ liệu: dùng một mảng ???? để đánh dấu tổng nào có thể được tạo ra từ dãy số. ???? ?ế? ? ?à ?ổ?? đượ? sinh ?? ????[?] = ቊ ????? ?ế? ? ?ℎô?? ?ℎả? ?à ?ổ?? đượ? sinh ??• Ý tưởng: • Xét từng số ?[?] • Với số ?[?], xét các tổng ? đã được sinh ra (xét ? từ lớn đến nhỏ) nếu ????[? + ?[?]] = ????? thì ???? ? + ? ? = ???? 10Kỹ thuật mảng đánh dấu trạng thái• Ngoài mảng bool[], trong C# cung cấp cho chúng ta lớp BitArray để xử lý mảng các bit, có thể dung thay thế cho mảng bool[]• Tạo đối tượng BitArray BitArray bits = BitArray(n);• Một số properties Tên Ý nghĩa Count Lấy số phần trong BitArray Length Lấy/Thiết lập số phần tử trong BitArray Item[Int32] Lấy/Thiết lập giá trị bit tại vị trí cho trước 11Kỹ thuật mảng đánh dấu trạng thái• Một số methods Tên Ý nghĩa And(BitArray) Thực hiện phép toán bitwise And Not() Đảo ngược các giá trị bit Or(BitArray) Thực hiện phép toán bitwise Or SetAll(Boolean) Thiết lập tất cả các bit giá trị cho trước Xor(BitArray) Thực hiện phép toán bitwise Xor ...