intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:29

Thêm vào BST
Báo xấu
13
lượt xem 6
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1. KỸ THUẬT LẬP TRÌNH CƠ BẢN Khoa Công nghệ thông tin Trường Đại học Ngoại ngữ - Tin học TP.HCM (HUFLIT)
  2. KỸ THUẬT MẢNG ĐÁNH DẤU TRẠNG THÁI
  3. Kỹ 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 3
  4. Kỹ 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ố 4
  5. Kỹ 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 𝑡𝑟𝑢𝑒 𝑖 𝑐ó 𝑡𝑟ạ𝑛𝑔 𝑡ℎá𝑖 𝑠𝑡𝑎𝑡𝑒𝑠 𝑖 = ቊ 𝑓𝑎𝑙𝑠𝑒 𝑖 𝑐ℎư𝑎 𝑐ó 𝑡𝑟ạ𝑛𝑔 𝑡ℎá𝑖 5
  6. Kỹ 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 •… 6
  7. Vậ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 7
  8. Vậ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ố ≤ 𝒏 8
  9. Vậ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 9
  10. Vậ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ì 𝑡𝑜𝑛𝑔 𝑘 + 𝑎 𝑖 = 𝑡𝑟𝑢𝑒 10
  11. Kỹ 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 11
  12. Kỹ 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 12
  13. KỸ THUẬT MẢNG ĐẾM
  14. Vấn đề lưu trữ • Vấn đề lưu trữ dãy số Cho dãy số 𝑎 = (𝑎0 , 𝑎1 , … , 𝑎 𝑛−1 ). Hãy tìm cách lưu trữ dãy 𝑎 hiệu quả • Về bộ nhớ • Về thời gian xử lý • Nguyên tắc cơ bản • Lưu trữ càng ít, xử lý càng nhanh • Lưu trữ có trật tự, xử lý nhanh hơn 14
  15. Vấn đề lưu trữ • Giới hạn bộ nhớ của ứng dụng trên Windows 64-bit • Ứng dụng 32-bit (default) • Stack: 1 𝐺𝐵 int[] a = new int[500000000]; → 2 𝐺𝐵 • Heap: 𝟐 𝑮𝑩 • Ứng dụng 64-bit • Stack: 1 𝐺𝐵 int[] a = new int[1000000000]; → 4 𝐺𝐵 • Heap: 𝟖 𝑻𝑩 • Phân tích: Đặc trưng của dãy 𝑎 = (𝑎0 , 𝑎1 , … , 𝑎 𝑛−1 ) • Số lượng phần tử: 𝑛 • Đặc điểm giá trị các phần tử: 𝑎 𝑖 • Thứ tự của các 𝑎 𝑖 15
  16. Phương pháp lưu trữ chuẩn • Cách chuẩn • Đặt tuần tự các phần tử 𝑎 = (𝑎0 , 𝑎1 , … , 𝑎 𝑛−1 ) vào trong một mảng 𝐴[𝑛] 𝐴[0] = 𝑎0 𝐴[1] = 𝑎1 ... 𝐴[𝑛 − 1] = 𝑎 𝑛−1 • Nhận xét • Đây là cách lưu trữ rất tự nhiên • Chúng ta đặt trực tiếp các phần tử vào từng ô của 𝐴 16
  17. Phương pháp lưu trữ chuẩn • Ví dụ 1: 𝑎 = (9, 5, 3, 2,6,5,3) 𝐴[… ] 9 5 3 2 6 5 3 • Ví dụ 2: 𝑎 = (3,3, 3, 4,2,4,3) 𝐴[… ] 3 3 3 4 2 4 3 17
  18. Phương pháp lưu trữ chuẩn • Ưu điểm • Đơn giản, dễ hiểu • Lưu được các 𝑎 𝑖 có miền giá trị lớn • Biết được vị trí ban đầu của các phần 𝑎 𝑖 trong dãy 𝑎 • Khuyết điểm • Khi 𝑎 chứa các giá trị bằng nhau, vẫn lưu mỗi giá trị một ô riêng 18
  19. Phương pháp mảng đếm • Cách khác • Tạo một mảng 𝑐𝑜𝑢𝑛𝑡[… ] chứa các giá trị đếm (counters) • Mỗi số 𝑥 trong dãy 𝑎 được đếm vào trong mảng 𝑐𝑜𝑢𝑛𝑡[… ]: bằng cách tăng giá trị đếm (trong mảng 𝑐𝑜𝑢𝑛𝑡[… ]) ở vị trí có 𝑖𝑛𝑑𝑒𝑥 bằng 𝑥 𝑎0 𝑎1 𝑎2 𝑎3 𝑎4 𝑎5 𝑎6 0 0 2 3 2 3 2 𝑐𝑜𝑢𝑛𝑡[… ] 𝟐 𝟎 𝟑 𝟐 𝟎 𝟏 𝟐 𝟑 19
  20. Phương pháp mảng đếm • Nhận xét • Mỗi số chúng ta không lưu trực tiếp giá trị vào mảng, mà chúng ta lưu số lần xuất hiện của số đó • Tận dụng sự giống nhau của các giá trị 𝑎 𝑖 để tiết kiệm bộ nhớ • Nếu 𝑎 𝑖 ∈ {0,1, … , 𝑚} thì kích thước mảng đếm là: 𝑚 + 1 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2