ในปัญหานี้ เราได้รับตัวเลข N งานของเราคือ หาตำแหน่งของตัวเลขที่กำหนดในลำดับตัวเลขที่ประกอบด้วย 4 และ 7 ลำดับที่ประกอบด้วย 4 และ 7 เท่านั้นคือ 4, 7, 44, 47, 74, 77, 444...
มาดูตัวอย่างเพื่อเข้าใจปัญหา
Input
N = 5
Output
74
อธิบาย
ลำดับถึง 5 ตัวคือ 4, 7, 44, 47, 74...
วิธีแก้ปัญหา
วิธีแก้ที่ง่ายคืออิงจากการหา pattern ในลำดับ
ที่นี่ ทุกตำแหน่งคู่จะลงท้ายด้วย 7
และทุกตำแหน่งคี่จะลงท้ายด้วย 4
ดังนั้น เราสามารถหาลำดับได้โดยไปทีละหลักและหาตำแหน่งจากหลักปัจจุบัน
ถ้าหลักปัจจุบันเป็น 4 ตำแหน่งจะอัปเดตเป็น position = (position*2) + 1
ถ้าหลักปัจจุบันเป็น 7 ตำแหน่งจะอัปเดตเป็น position = (position*2) + 2
โปรแกรมแสดงการทำงานของวิธีแก้
ตัวอย่าง
#include <iostream>
using namespace std;
int findNumPosition(string num){
int i = 0, position = 0;
while (num[i] != '\0') {
position *= 2;
if(num[i] == '4')
position += 1;
else
position += 2;
i++;
}
return position;
}
int main() {
string num = "74774";
cout<<"The position of the number in the series is "<<findNumPosition(num);
return 0;
}
ผลลัพธ์
The position of the number in the series is 53
