Bài toán Tìm số khép kín
Ta quy ước:
– Các chữ số 1, 2, 3, 5, 7 có 0 đường khép kín
– Các chữ số 0, 4, 6, 9 có 1 đường khép kín
– Chữ số 8 có 2 đường khép kín
Viết chương trình tính tổng số đường khép kín của một số nguyên dương n (n < 1010)
Dữ liệu vào từ file KHEPKIN.INP
– Dòng đầu tiên ghi số n
Kết quả ra file KHEPKIN.OUT
– Dòng đầu tiên ghi tổng số đường khép kín tính được.
Thuật toán giải bài toán tìm số khép kín
Để giải quyết bài toán này, ta có thể sử dụng phương pháp chia số n thành các chữ số riêng lẻ và đếm số đường khép kín của mỗi chữ số đó. Sau đó, ta cộng tổng số đường khép kín của các chữ số lại với nhau để tính tổng số đường khép kín của số n.
Để tính số đường khép kín của mỗi chữ số, ta có thể sử dụng một bảng tra cứu đơn giản, trong đó lưu trữ số đường khép kín tương ứng với mỗi chữ số. Sau đó, ta chỉ cần tra cứu số đường khép kín tương ứng với mỗi chữ số trong bảng này.
Cài đặt bài toán tìm số khép kín với Python
# Đọc số n từ file input
with open('KHEPKIN.INP', 'r') as f:
n = int(f.readline().strip())
# Bảng tra cứu số đường khép kín của các chữ số
digits = {
'0': 1,
'1': 0,
'2': 0,
'3': 0,
'4': 1,
'5': 0,
'6': 1,
'7': 0,
'8': 2,
'9': 1,
}
# Tính tổng số đường khép kín của số n
total = 0
for digit in str(n):
total += digits[digit]
# Ghi kết quả ra file output
with open('KHEPKIN.OUT', 'w') as f:
f.write(str(total))
Cài đặt bài toán tìm số khép kín với C++
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
// Mở file input
ifstream infile("KHEPKIN.INP");
// Đọc số n từ file input
int n;
infile >> n;
// Bảng tra cứu số đường khép kín của các chữ số
int digits[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
// Tính tổng số đường khép kín của số n
int total = 0;
string str_n = to_string(n);
for (int i = 0; i < str_n.length(); i++) {
int digit = str_n[i] - '0';
total += digits[digit];
}
// Mở file output và ghi kết quả vào file output
ofstream outfile("KHEPKIN.OUT");
outfile << total;
// Đóng file input và output
infile.close();
outfile.close();
return 0;
}