Ta cần tìm số chữ số trong số thứ n gồm bốn chữ số 1, 2, 3, 4 đã cho.
Chuỗi có bốn chữ số trên như sau
1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24 ...
Ta cần tìm số chữ số của số thứ n từ dãy số trên. Nếu bạn quan sát kỹ mô hình này, bạn sẽ tìm thấy những điểm sau.
-
Có 4 số có chữ số 1.
-
Có 16 số có chữ số 2.
-
Mô hình tiếp tục như các lũy thừa của 4.
Hãy xem một ví dụ
Đầu vào
7
Đầu ra
2
Số thứ 7 trong dãy là 13 và số chữ số trong đó là 2.
Thuật toán
- Khởi tạo số n.
- Khởi tạo hai biến, một để lưu trữ kết quả và một biến khác để lưu tổng cộng các số trong chuỗi.
- Tạo một vòng lặp để tăng biến lặp lại bằng lũy thừa của 4.
- Thêm số hiện tại vào biến tổng.
- Nếu tổng lớn hơn n thì ngắt vòng lặp.
- Thêm 1 vào kết quả vì tập hợp số tiếp theo sẽ có thêm một chữ số so với tập hợp số trước đó.
- Trả lại kết quả.
Thực hiện
Sau đây là cách thực hiện thuật toán trên trong 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;
} Đầu ra
Nếu bạn chạy đoạn mã trên, thì bạn sẽ nhận được kết quả sau.
3