โจทย์
เราต้องการหาจำนวนหลักของตัวเลขลำดับที่ n ที่ประกอบด้วยเลข 1, 2, 3, และ 4 เท่านั้น
ลำดับของตัวเลขด้วย 4 หลักดังกล่าวคือ
1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24...
เราต้องการหาจำนวนหลักของตัวเลขลำดับที่ n จากลำดับข้างต้น หากสังเกตรูปแบบอย่างละเอียด จะพบว่า
- มี 4 ตัวเลขที่มี 1 หลัก
- มี 16 ตัวเลขที่มี 2 หลัก
- รูปแบบต่อไปเป็นกำลังของ 4
มาดูตัวอย่าง
อินพุต
7
เอาต์พุต
2
ตัวเลขลำดับที่ 7 ในลำดับคือ 13 และมี 2 หลัก
อัลกอริธึม
- กำหนดตัวเลข n
- กำหนดตัวแปร 2 ตัว หนึ่งเก็บผลลัพธ์ อีกตัวเก็บผลรวมตัวเลขในลำดับ
- สร้างลูปที่เพิ่มตัวแปรวนรอบด้วยกำลังของ 4
- บวกจำนวนปัจจุบันเข้าไปในตัวแปรผลรวม
- ถ้าผลรวมมากกว่าหรือเท่ากับ n ให้หยุดลูป
- เพิ่ม 1 เข้าไปในผลลัพธ์ เนื่องจากชุดตัวเลขถัดไปจะมีหลักมากกว่าชุดก่อนหน้า 1 หลัก
- คืนค่าผลลัพธ์
การนำไปใช้งาน
ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน C++
#include <bits/stdc++.h>
using namespace std;
int getDigitsCount(int n) {
int i, result = 1, sum = 0;
for (i = 4; ; i *= 4) {
sum += i;
if (sum >= n) {
break;
}
result += 1;
}
return result;
}
int main() {
int n = 57;
cout << getDigitsCount(n) << endl;
return 0;
}
ผลลัพธ์
หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้
3
