บทนำ
ลำดับเส้นโค้งมังกร (Dragon Curve Sequence) เป็นลำดับไบนารีแบบอนันต์ ที่เริ่มต้นด้วย 1 และในแต่ละขั้นตอน จะเพิ่ม 1 และ 0 สลับกัน ไปข้างหน้าและข้างหลังของแต่ละสมาชิกในเทอมก่อนหน้า เพื่อสร้างเทอมถัดไป
ตัวอย่างลำดับ
- เทอม 1: 1
- เทอม 2: 110
- เทอม 3: 1101100
- เทอม 4: 110110011100100
เราเริ่มต้นด้วย 1 แล้วเพิ่ม 1 และ 0 สลับกัน หลังจากแต่ละสมาชิกของเทอมก่อนหน้า เมื่อได้เทอมใหม่แล้ว ให้ทำซ้ำขั้นตอนตั้งแต่ 1 ถึง n เพื่อสร้างเทอมถัดไป
ตัวอย่างโค้ด C++
#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]; // นำตัวอักษรจากสตริงเดิม
if (prev == '0') {
temp += one;
prev = one;
} else {
temp += zero;
prev = zero;
}
}
term = temp;
}
return term;
}
int main() {
cout << "4th term of Dragon Curve Sequence: " << dragCurveTerm(4);
return 0;
}
ผลลัพธ์
4th term of Dragon Curve Sequence: 110110011100100
