ในปัญหานี้ เราได้รับหมายเลข N หน้าที่ของเราคือสร้างโปรแกรมเพื่อ พิมพ์ตัวเลขเป็นสตริงของ 'A' และ 'B' ตามลำดับพจนานุกรม
การแสดงตัวเลขทั้งหมดเป็นสตริงของ 'A' และ 'B' คือ
1 =อา
2 =ข
3 =AA
4 =AB
5 =BA
6 =บีบี
7 =AAA
8 =AAB
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล: ไม่มี =12
ผลลัพธ์: แบ๊บ
แนวทางการแก้ปัญหา
สตริงของ 'A' และ 'B' คล้ายกับเลขฐานสอง ในการหาสตริง เราจะหาความยาวของสตริงก่อน โดยใช้ข้อเท็จจริงว่ามีตัวเลข 2 ตัวยาว 1 (ถึงขนาด 2), 4 ตัวยาว 2 (ถึงขนาด 6), 8 ตัวยาว 3 (ยาวถึงขนาด) 14). หลังจากหาความยาวแล้ว เราก็ต้องหาตัวอักษรของสตริง โดยการอัปเดตความยาวที่เหลืออยู่ซ้ำๆ เมื่อเราเพิ่มตัวเลขลงในสตริง อักขระจะพิจารณาจากการเปรียบเทียบ N กับ (2^(ความยาวที่เหลือ)) ถ้า N น้อยกว่าอักขระปัจจุบันคือ 'B' มิฉะนั้น อักขระนั้นจะเป็น 'A' หลังจากการวนซ้ำแต่ละครั้ง เราจะลดความยาวลง 1 และหากอักขระเป็น 'B' จะอัปเดต N และลดความยาวลง num
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
#include<math.h>
using namespace std;
int findStringLength(int M) {
int stringLen = 1;
while((pow(2, stringLen + 1) - 2) < M) {
stringLen++;
}
return stringLen;
}
void printNumString(int N) {
int stringLen, num, stringNumber;
stringLen = findStringLength(N);
stringNumber = N - (pow(2, stringLen) - 2);
while (stringLen) {
num = pow(2, stringLen - 1);
if (num < stringNumber) {
cout<<"B";
stringNumber -= num; }
else {
cout<<"A";
}
stringLen--;
}
}
int main() {
int N = 47;
cout<<"The number as sting of 'A' and 'B' in lexicographic order is ";
printNumString(N);
return 0;
} ผลลัพธ์
The number as sting of 'A' and 'B' in lexicographic order is BAAAA
