CHƯƠNG VIII
CHUYÊN ĐỀ DÃY CON.
A. LÝ THUYẾT:
- Dãy con là dãy các phần tử liên tục thuộc một dãy có trước (dãy mẹ) thỏa mãn một tính chất nào đó.
- Để quản lí một dãy con cần một chỉ số (nơi bắt đầu dãy con) và độ dài của dãy.
- Một cách quản lí khác là chỉ số đầu và chr số cuối.
- Để xây dựng một dãy con cần:
- Xây dựng giá trị ban đầu.
- Duyệt qua các phần tử của dãy, Nếu:
- Thỏa điều kiện, tăng độ dài thêm 1 ngược lại:
- Nếu dãy con đang xét cần lưu thì: Lưu lại độ dài, chỉ số đầu dãy, Xác định lại độ dài, chỉ số đầu của dãy mới.
- Nếu dãy con đang xét không cần lưu thì: Xác định lại độ dài, chỉ số đầu của dãy mới.
- Để duyệt qua tất cả các dãy con của một dãy gồm n số ta dùng thuật toán vét cạn sau:
For i:= 1 to n
For j:= 1 to n-i+1 Xét dãy con bắt đầu từ vị trí thứ i có độ dài j.
Chia sẻ với bạn bè của bạn: |