ในปัญหานี้ เราได้รับจำนวนเต็ม N ซึ่งแสดงถึงชุดของตัวเลขที่ประกอบด้วย 4 และ 7 เท่านั้น
ซีรี่ย์คือ 4, 7, 44, 47, 74, 77, …
ภารกิจคือการค้นหาองค์ประกอบที่ n-th ในชุดที่อนุญาตเพียง 2 หลัก (และ 7)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 4,
ผลลัพธ์
47
คำอธิบาย
The series is: 4, 7, 44, 47, ….
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการสร้างชุดข้อมูลจนถึงเลข N ง่าย ๆ หากตัวเลขปัจจุบันเป็น 7 หลักสุดท้ายของตัวเลขก่อนหน้าและถัดไปคือ 4
ดังนั้น เราจะเริ่มจากตัวเลขที่ 1 และ 2 จากนั้นจึงเข้าสู่องค์ประกอบถัดไป
สำหรับสิ่งนี้ เราจะสร้างชุดอาร์เรย์[n+1]
For index series[1] put 4 For index series[2] put 7
จากนั้นสำหรับค่าต่อเนื่องจนถึง N ให้ค้นหาค่าสำหรับดัชนีที่กำหนด i
If i is odd, series[i] = series[i/2]*10 + 4 If i is even, series[i] = series[i/2]*10 + 7
หลังจากการวนซ้ำ n ครั้ง ให้คืนค่าที่ series[n].
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
int findNthSeriesElement(int N) {
int series[N+1];
series[1] = 4;
series[2] = 7;
for (int i=3; i<=N; i++) {
if (i%2 != 0)
series[i] = series[i/2]*10 + 4;
else
series[i] = series[(i/2)-1]*10 + 7;
}
return series[N];
}
int main() {
int N = 9;
cout<<"The "<<N<<"th element of the array is "<<findNthSeriesElement(N);
return 0;
} ผลลัพธ์
The 9th element of the array is 474
