Bài toán chuỗi vô hạn các chữ số
Từ một số có 3 chữ số cho trước người ta xây dựng chuỗi vô hạn các chữ số theo cách sau: lấy tổng 3 chữ số cuối cùng của chuỗi và điền tổng nhận được vào cuối chuỗi. Ví dụ, với số ban đầu là 123 ta có chuỗi vô hạn bắt đầu là 12361181091010, còn với số 971 ta có 971179171715. . . Dãy số tìm được có thể coi như là phần thập phân của một số có phần nguyên bằng 0.
Yêu cầu: Xác định chữ số thứ N trong phần thập phân của số A cho trước.
Dữ liệu: Vào từ file văn bản SUM.INP:
– Dòng thứ nhất chứa một số nguyên A có 3 chữ số,
– Các dòng tiếp theo: mỗi dòng chứa một số nguyên N ( 1 ≤ N < 10100).
Kết quả: Đưa ra file văn bản SUM.OUT các chữ số tìm được, mỗi số trên một dòng.
Thuật toán
Để giải bài toán này, ta có thể sử dụng thuật toán sau đây:
- Tìm chu kỳ của chuỗi số bằng cách tính tổng của 3 chữ số cuối cùng của chuỗi và thêm nó vào cuối chuỗi. Lặp lại quá trình này cho đến khi tìm được một chu kỳ.
- Tính phần nguyên của N khi chia cho độ dài của chu kỳ. Điều này sẽ cho ta biết số lần chu kỳ được lặp lại trước khi đến chữ số thứ N.
- Tính vị trí của chữ số N trong chuỗi số.
- Trả về chữ số tương ứng.
Cài đặt bài toán với Python
def find_cycle_length(num):
"""
Tìm độ dài của chu kỳ
"""
visited = {}
remainder = 0
i = 1
while True:
remainder = (remainder * 10 + num) % 1000
if remainder in visited:
return i - visited[remainder]
visited[remainder] = i
i += 1
def get_digit(num, n):
"""
Trả về chữ số thứ n của số num
"""
return int(str(num)[n - 1])
def main():
# Đọc dữ liệu từ file input
with open("SUM.INP", "r") as f:
num = int(f.readline())
n_values = [int(line.strip()) for line in f.readlines()]
# Tìm độ dài của chu kỳ
cycle_length = find_cycle_length(num)
# Xử lý từng giá trị của n
result = []
for n in n_values:
# Tính phần nguyên của n khi chia cho độ dài của chu kỳ
cycle_count = (n - 1) // cycle_length
# Tính vị trí của chữ số trong chu kỳ
position = (n - 1) % cycle_length
# Tìm chữ số tương ứng
digit = get_digit(num, position + 1)
# Nếu n vượt quá độ dài của chuỗi, chữ số tương ứng là 0
if n > cycle_length * 100:
digit = 0
# Thêm chữ số vào kết quả
result.append(str(digit))
# Ghi kết quả vào file output
with open("SUM.OUT", "w") as f:
f.write("\n".join(result))
Cài đặt bài toán với C++
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
// Tính độ dài của chu kỳ
int find_cycle_length(int num) {
int visited[1000] = {};
int remainder = 0;
int i = 1;
while (true) {
remainder = (remainder * 10 + num) % 1000;
if (visited[remainder]) {
return i - visited[remainder];
}
visited[remainder] = i;
i++;
}
}
// Trả về chữ số thứ n của số num
int get_digit(int num, int n) {
string num_str = to_string(num);
return num_str[n - 1] - '0';
}
int main() {
freopen("SUM.INP", "r", stdin);
freopen("SUM.OUT", "w", stdout);
int num, n;
cin >> num;
int cycle_length = find_cycle_length(num);
while (cin >> n) {
int cycle_count = (n - 1) / cycle_length;
int position = (n - 1) % cycle_length;
int digit = get_digit(num, position + 1);
if (n > cycle_length * 100) {
digit = 0;
}
cout << digit << endl;
}
return 0;
}