ในปัญหานี้ เราได้รับตัวเลข N ภารกิจของเราคือ หาตัวเลขตัวที่ n ที่ประกอบด้วยเลขเฉพาะ (2, 3, 5 และ 7) เท่านั้น
ชุดที่ประกอบด้วยเลขเฉพาะเท่านั้น (2, 3, 5, 7) คือ 2, 3, 5, 7, 22, 23, 25, 27, 32, 33...
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input: N = 6 Output: 23
วิธีการแก้ปัญหา
วิธีง่ายในการแก้ปัญหาคือการหาตัวเลขที่ดัชนีที่กำหนด คือการหาพจน์ของชุด สำหรับนี้ เราจะสังเกตชุด
เรามีเลขเฉพาะ 4 ตัวที่แตกต่างกัน ดังนั้นชุดที่สร้างได้สามารถถือเป็นระบบเลขฐานสี่ ในระบบเลขนี้ เรามี 4^x ตัวเลขที่มีความยาว x
ตอนนี้เพื่อแก้ปัญหา เรามีชุดที่เราจะหาความยาวของตัวเลขที่ทำให้สร้างตัวเลขได้ จากนั้นเราจะนับตัวเลขตัวที่ N และพิมพ์ตัวเลขที่ต้องการ
เพื่อหาตัวเลขตัวที่ N โดยใช้ความยาว เราจะนับจากตัวเลขแรกของความยาว (x-1) แล้วนับ N นี้
ตัวอย่าง
โปรแกรมสาธิตการทำงานของวิธีแก้ปัญหาของเรา
#include <iostream> #include <math.h> using namespace std; void findNthNumber(int n){ long x = 1; long lastNum = 0; while (true) { long currNum = lastNum + pow(4, x); if (lastNum < n && currNum >= n) break; x++; lastNum = currNum; } for (int i = 1; i <= x; i++) { for (long j = 1; j <= 4; j++) { if (lastNum + pow(4, x - i) < n) lastNum += pow(4, x - i); else { if (j == 1) cout<<"2"; else if (j == 2) cout<<"3"; else if (j == 3) cout<<"5"; else if (j == 4) cout<<"7"; break; } } } } int main(){ int N = 32; cout<<N<<"th number made of prime digits is "; findNthNumber(N); return 0; }
เอาต์พุต
32th number made of prime digits is 257
