พิมพ์ตัวเลขเป็นสตริงของ 'A' และ 'B' ตามลำดับพจนานุกรมในภาษา C++

ในปัญหานี้ เราได้รับหมายเลข 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