Trong bài toán này, chúng ta được cung cấp một số nguyên N, biểu thị một dãy số chỉ bao gồm 4 và 7.
Chuỗi là 4, 7, 44, 47, 74, 77,…
Nhiệm vụ là tìm phần tử thứ n trong một dãy chỉ được phép có 2 chữ số (và 7).
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
N = 4,
Đầu ra
47
Giải thích
The series is: 4, 7, 44, 47, ….
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là tạo chuỗi cho đến số thứ N. Thật đơn giản, nếu chữ số cuối cùng của số hiện tại là 7. Khi đó chữ số cuối cùng của các số trước đó và số tiếp theo là 4.
Vì vậy, chúng tôi sẽ bắt đầu từ số 1 và số 2, sau đó chuyển sang phần tiếp theo.
Đối với điều này, chúng tôi sẽ tạo một chuỗi mảng [n + 1].
For index series[1] put 4 For index series[2] put 7
Sau đó, đối với các giá trị liên tiếp cho đến N, hãy tìm các giá trị của chỉ số i đã cho,
If i is odd, series[i] = series[i/2]*10 + 4 If i is even, series[i] = series[i/2]*10 + 7
Sau n lần lặp, trả về giá trị tại chuỗi [n].
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The 9th element of the array is 474