Bài toán Chữ số thứ N

Sinh vien hoc lap trinh

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:

  1. 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.
  1. 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:

  1. 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.
  2. Tìm chữ số thứ y trong số tự nhiên x bằng cách chuyển x 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.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *