C H U ỖI.
G iớ i t h i ệ u v à ví d ụ
Chuỗi là một danh sách các phần tử có tính tới trật tự. Chuỗi được dùng trong toán học theo nhiều cách. Chúng có thể dùng để biểu diễn nghiêm trong các bài toán đếm, nó cũng là một cấu trúc dữ liệu quan trọng trong khoa học máy tính.
Định nghĩa
• Một cách hình thức: Một chuỗi {an} được chỉ định bẳng một hàm tạo f:S→A
với S⊆N (thường S=N hay S=N－{0}) và một tập A.
• Nếu f là một hàm taọu cho chuỗi {an}, khi đó n∈S, thì ký tự cũng được coi
là một phần tử thứ n của S
Ví dụ:
• Nhiều khi ta viết “a1, a2, …” thay cho {an}, để cho tập chỉ ra được rõ ràng
• Một ví dụ về chuỗi vô hạn:
– Xét chuỗi {an} = a1, a2, …, trong đó (∀n≥1) an= f(n) = 1/n.
– Do vậy {an} = 1, 1/2, 1/3, …
• Xét thêm chuỗi {bn} = b0, b1, … trong đó bn = (－1)n.
• {bn} = 1, －1, 1, －1, …
• Như vậy là lặp lại! {bn} là một chuỗi vô hạn 1 và －1
N h ận d ạ n g c h u ỗ i
Một bài toán hay gặp trong toán học rời rạc là tìm ra công thức hay luật tổng quát cho một chuỗi được đưa ra. Trong một số trường hợp, chỉ một số ít các phần tử đầu được biết, mục tiêu là phải xác định được chuỗi. Ngay cả khi một số phần tử đầu không xác định được toàn bộ chuỗi (điều này là do có rất nhiều các chuỗi bắt đầu với bất kỳ một hữu hạn phần tử), nó cũng sẽ giúp phỏng đoán được. Khi có được phỏng đoán, chúng ta cần phải tìm cách chứng minh tính đúng đắn của nó.
Trong quá trình tìm ra luật của chuỗi từ những các phần tử ban đầu, hãy cố gắng tìm ra các đặc điểm chung của chúng. Sau đây là một số câu hỏi giúp cho quá trình tìm kiếm dễ dàng hơn:
Chuỗi có bị lặp lại không? Tức là các giá trị giống nhau có xảy ra nhiều lần
trên một hàng không?
Các phần tử có đạt được từ các phần tử trước bằng cách thêm vào cùng một
giá trị hay giá trị đó có phụ thuộc thêm vào vị trí của chuỗi hay không?
Các phần tử có đạt được từ các phần tử trước bằng cách nhân vào cùng một
giá trị cụ thể hay giá trị đó phụ thuộc thêm vào vị trí của chuỗi hay không?
Các phần tử có đạt được từ các phần tử trước bằng cách kết hợp một số các
phần tử trước hay không?
Có chu kỳ nào giữa các phần tử không?
• Ví dụ: Tìm sồ tiếp theo?
– 1,2,3,4,…
– 1,3,5,7,9,…
– 2,3,5,7,11,...
– 1, 2, 2, 3, 3, 3, 4,4, 4, 4, ...
– 5, 11, 17, 23, 29, 35, 41, 47, 53, 59, ...
– 1, 7, 25, 79, 241, 727, 2185, 6559, 19681, 59047
• Khi bài toán yêu cầu tìm ra hàm tổng quát mà chỉ bằng một số các phần tử của chuỗi thì đây là yêu cầu không thực sự rõ ràng. Bởi vì có thể có vô số các hàm giống nhau một số các phần tử đầu
• Chúng ta phải ngầm định là tìm hàm đơn giản nhất, tuy nhiên chúng ta nên hiểu hàm thế nào là đơn giản? Chúng ta có thể định nghĩa đơn giản là không phức tạp, tuy nhiên nó đòi hỏi nhiều những kiến thức mà chúng ta không thể thảo luận ở đây. Do vậy câu hỏi thực sự vẫn chưa có câu trả lời xác đáng.
C h u ỗi ( S tri n g)
• Trong modul này thì “chuỗi hữu hạn có dạng a1, a2, …, an”, tuy nhiên đôi
khi chúng ta cũng nói tới chuỗi vô hạn.
• Chuỗi cũng thường được xét giới hạn trong các bảng chữ cái alphabet, đôi
khi chỉ là 0 và 1.
• Độ dài của chuỗi là số phần tử của chuỗi đấy.
• Coi Σ là tập hữu hạn các ký tự, ví dụ như bảng alphabet.
• Một chuỗi s trên alphabet Σ là bất kỳ chuỗi {si} ký tự nào, si∈Σ.
• Nếu a, b, c, … là các ký tự, chuỗi s = a, b, c, … có thể được viết abc
…(không có dấu phẩy).
• Nếu s là một chuỗi hữu hạn và t là một chuỗi, khi ta nối s với t, viết là st, là một chuỗi mới bao gồm các ký tự của s, theo sau là ccs ký tự của t
• Độ dài |s| của một chuỗi hữu hạn s là số ký tự của nó.
• Nếu s là một chuỗi và n∈N, sn ký hiệu n chuỗi s nối liên tiếp nhâu.
• ε ký hiệu là một chuỗi rỗng, độ dài bằng 0.
• Nếu Σ là bảng alphabet và n∈N,
Σn {s | s là một chuỗi trên Σ có độ dài n}, và
Σ* {s | s là một chuỗi hữu hạn trên Σ}.
| Một số dãy hay gặp | |
| Phần tử thứ n | 10 phần tử đầu |
| n2 | 1, 4, 9, 16, 25, 36, 49, 64, 81, 100,... |
| n3 | 1, 8, 27, 64, 125, 216, 343, 512, 729, 1000,... |
| n4 | 1, 16, 81, 256, 625, 1296, 2401, 4096, 6561, 10000,... |
| 2n | 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,... |
| 3n | 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049,... |
| n! | 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800,.. |