Bài toán – Chữ số thứ N
Khi viết các số tự nhiên tăng dần từ 1, 2, 3,… liên tiếp nhau, ta nhận được một dãy các chữ số thập phân vô hạn, ví dụ: 1234567891011121314151617181920…
Yêu cầu: Hãy tìm chữ số thứ N của dãy số vô hạn trên.
Dữ liệu vào từ file ‘Number.inp’ gồm một số dòng, mỗi dòng ghi một số nguyên dương N (N<109).
Kết quả ra file ’Number.out’, với mỗi số N đọc được từ file Number.inp, ghi trên dòng tương ứng chữ số thứ N của dãy.
Ví dụ:
Number.inp |
Number.out |
5 10 54 |
5 1 3 |
Thuật toán
Để tìm chữ số thứ N của dãy số vô hạn trên, ta cần thực hiện các bước sau:
- Tìm xác định đoạn nào trong dãy số chứa chữ số thứ N. Để làm điều này, ta sử dụng công thức sau:
- Số lượng chữ số của các số tự nhiên có dạng 1, 2, 3, …, 9 là 9, 90, 900, 9000, …, 9 x 10^(k-1), với k là số lượng chữ số của số đó.
- Với N được cho, ta sẽ xác định được số tự nhiên có dạng x và chữ số thứ y trong số đó bằng cách tính: x = ceil((N – 9 – 90 x 2 – 900 x 3 – … – 9 x 10^(k-2) x (k-1)) / k) + 10^(k-1) – 1 y = (N – 9 – 90 x 2 – 900 x 3 – … – 9 x 10^(k-2) x (k-1) – 1) % k
- Trong đó, ceil(x) là phép làm tròn x lên thành số nguyên gần nhất.
- Tìm chữ số thứ y trong số tự nhiên x. Để làm điều này, ta sẽ chuyển số tự nhiên x thành chuỗi, sau đó lấy ký tự ở vị trí y.
Với mỗi số N được đọc từ file ‘Number.inp’, ta sẽ thực hiện các bước trên để tìm chữ số thứ N và ghi kết quả vào file ‘Number.out’.
Cài đặt bài toán với Python
import math
def get_digit(n):
# Tính số lượng chữ số của số tự nhiên chứa chữ số thứ N
k = 1
while True:
count = 9 * 10**(k-1) * k
if n <= count:
break
n -= count
k += 1
# Tìm số tự nhiên chứa chữ số thứ N
x = math.ceil(n / k) + 10**(k-1) - 1
# Tìm chữ số thứ y trong số tự nhiên x
y = (n - 1) % k
digit = int(str(x)[y])
return digit
# Đọc dữ liệu từ file input
with open('Number.inp', 'r') as f:
data = f.read().splitlines()
# Ghi kết quả vào file output
with open('Number.out', 'w') as f:
for n in data:
digit = get_digit(int(n))
f.write(str(digit) + '\n')
Cài đặt bài toán với C++
#include <bits/stdc++.h>
using namespace std;
int get_digit(int n) {
// Tính số lượng chữ số của số tự nhiên chứa chữ số thứ N
int k = 1;
while (true) {
int count = 9 * pow(10, k-1) * k;
if (n <= count) {
break;
}
n -= count;
k++;
}
// Tìm số tự nhiên chứa chữ số thứ N
int x = ceil((double)n / k) + pow(10, k-1) - 1;
// Tìm chữ số thứ y trong số tự nhiên x
int y = (n - 1) % k;
int digit = stoi(to_string(x).substr(y, 1));
return digit;
}
int main() {
ifstream fin("Number.inp");
ofstream fout("Number.out");
int n;
while (fin >> n) {
int digit = get_digit(n);
fout << digit << "\n";
}
fin.close();
fout.close();
return 0;
}
Trong đó, hàm get_digit(n)
nhận vào một số nguyên n
và trả về chữ số thứ n
. Hàm này thực hiện hai bước chính:
- Tìm số tự nhiên
x
chứa chữ số thứn
bằng cách tính toán dựa trên số lượng chữ số của các số tự nhiên và chữ số thứn
. - Tìm chữ số thứ
y
trong số tự nhiênx
bằng cách chuyểnx
thành chuỗi, sau đó lấy ký tự ở vị tríy
.
Trong hàm main()
, chúng ta đọc dữ liệu từ file Number.inp
, thực hiện các truy vấn và ghi kết quả vào file Number.out
. Cuối cùng, đóng các file đang mở và kết thúc chương trình.