Bài toán Dãy số nguyên (Đề thi Tin học trẻ)

Dãy số nguyên

Bài toán – Dãy số nguyên (Dành cho học sinh THCS)

Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:

1234567891011121314…..  (1)

Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?

Em hãy làm bài này theo hai cách: Cách 1 dùng suy luận logic và cách 2 viết chương trình để tính toán và so sánh hai kết quả với nhau.

Tổng quát bài toán trên: Chương trình yêu cầu nhập số K từ bàn phím và in ra trên màn hình kết quả là số nằm ở vị trì thứ K trong dãy (1) trên. Yêu cầu chương trình chạy càng nhanh càng tốt.

Giải và cài đặt bài toán Dãy số nguyên

Cách 1: Suy luận logic

Để tìm số ở vị trí thứ K trong dãy số tự nhiên trên, ta có thể sử dụng một số tính chất của dãy số đó.

Nhận xét: Mỗi lần đếm đến số 9, số chữ số của các số từ 1 đến 9 trong dãy tăng lên 1. Ví dụ: số 1-9 có 9 số, số 10-99 có 90 số, số 100-999 có 900 số, và tiếp tục.

Với quy luật này, ta có thể tính xem số ở vị trí thứ K sẽ nằm trong khoảng bao nhiêu chữ số của dãy số tự nhiên. Sau đó, từ khoảng đó ta có thể tính được số cụ thể là bao nhiêu.

Cách 2: Viết chương trình tính toán

Để viết chương trình tính toán số ở vị trí thứ K trong dãy số tự nhiên, ta có thể sử dụng ngôn ngữ lập trình Python hoặc C++.

Cài đặt bài toán dãy số nguyên với Python

Dưới đây là một ví dụ về cách viết chương trình trong Python:

def find_number_at_position_K(K):
    # Khởi tạo số đang đếm là 1
    num = 1
    # Khởi tạo số chữ số của số đang đếm là 1
    num_digits = 1

    while True:
        # Nếu K nằm trong khoảng số chữ số của num hiện tại
        if K <= num_digits:
            # Chuyển số num thành chuỗi
            num_str = str(num)
            # Trả về chữ số ở vị trí K - 1 trong chuỗi num_str
            return int(num_str[K-1])
        else:
            # Nếu K không nằm trong khoảng số chữ số của num hiện tại
            # Cộng thêm số chữ số của num hiện tại vào K
            K -= num_digits
            # Tăng giá trị của num lên 1
            num += 1
            # Nếu num có 10 chữ số mới tăng số chữ số của num lên 1
            if num == 10**num_digits:
                num_digits += 1

# Nhập giá trị K từ bàn phím
K = int(input("Nhập giá trị K: "))
# Tìm số ở vị trí K trong dãy số tự nhiên
result = find_number_at_position_K(K)
# In kết quả
print("Số ở vị trí thứ", K, "là:", result)

Bạn có thể chạy đoạn mã trên với giá trị K nhập từ bàn phím để xem kết quả. Chương trình sẽ in ra số ở vị trí thứ K trong dãy số tự nhiên.

Cài đặt bài toán dãy số nguyên với C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    int K;
    cout << "Nhap vao vi tri K: ";
    cin >> K;

    string sequence = "";
    int current_num = 1;

    // Tạo dãy số tự nhiên
    while (sequence.length() < K) {
        sequence += to_string(current_num);
        current_num++;
    }

    // In ra số nằm ở vị trí thứ K
    cout << "So o vi tri " << K << " trong day la: " << sequence[K - 1] << endl;

    return 0;
}

Đoạn mã trên sẽ yêu cầu người dùng nhập vào một số nguyên K, sau đó sẽ tạo dãy số tự nhiên từ 1 đến K và in ra số nằm ở vị trí thứ K trong dãy đó. Lưu ý là vị trí trong chuỗi được tính từ 0, nên chúng ta phải trừ đi 1 để lấy giá trị chính xác. Đoạn mã này sẽ hoạt động nhanh chóng với dữ liệu nhỏ, tuy nhiên với K lớn thì có thể gặp phải vấn đề hiệu năng. Để tối ưu hóa hiệu năng, có thể sử dụng cách tính toán trực tiếp để tìm giá trị tại vị trí K mà không cần tạo dãy số tự nhiên hoàn chỉnh. Tuy nhiên, cách này sẽ phức tạp hơn và cần tính toán đúng kỹ thuật để tránh tràn số. Có thể áp dụng các thuật toán số học hoặc đại số để giải quyết vấn đề này. Ngoài ra, cách 1 dùng suy luận logic cũng sẽ đưa ra kết quả chính xác và nhanh chóng với mọi giá trị của K, tuy nhiên cần phải có kỹ năng suy luận và tính toán logic cao hơn.

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 *