Dãy Dragon Curve là một dãy nhị phân vô hạn. Nó bắt đầu bằng 1, và ở mỗi bước, nó lần lượt thêm 1 và 0 trước và sau mỗi phần tử của số hạng trước để tạo thành số hạng tiếp theo.
Các số hạng đầu tiên
- Số hạng 1: 1
- Số hạng 2: 110
- Số hạng 3: 1101100
- Số hạng 4: 110110011100100
Chúng ta bắt đầu từ "1", sau đó thêm "1" và "0" xen kẽ sau mỗi phần tử của số hạng trước. Khi số hạng mới được tạo ra trở thành số hạng hiện tại, lặp lại các bước từ 1 đến n để tạo ra các số hạng tiếp theo.
Ví dụ minh họa
#include <iostream>
using namespace std;
string dragCurveTerm(int n) {
string term = "1";
for (int i = 2; i <= n; i++) {
string temp = "1";
char prev = '1', zero = '0', one = '1';
for (int j = 0; j < term.length(); j++) {
temp += term[j]; // lấy ký tự từ chuỗi gốc
if (prev == '0') {
temp += one;
prev = one;
} else {
temp += zero;
prev = zero;
}
}
term = temp;
}
return term;
}
int main() {
cout << "Số hạng thứ 4 của dãy Dragon Curve: " << dragCurveTerm(4);
return 0;
}
Kết quả
Số hạng thứ 4 của dãy Dragon Curve: 110110011100100