Dãy số tổng bình phương chữ số (Sum of Digit Squares)

Bài toán

Ứng với mỗi số tự nhiên x, ta có số tự nhiên f(x) bằng tổng bình phương các chữ số của x. Từ x ta xây dựng dãy (Xn) như sau:

X1 = x ; X2 = f(X1) ; X3 = f(X2) ; …; Xi = f(Xi – 1)    với   1 <= I <= n

Ví dụ: 

            x = 12 ta có dãy: 12; 5; 25; 29; 85; 89; 145; 42; 20; 4; 16; 37; 58; 89

            x = 4 ta có dãy: 4; 16; 37; 58; 89; 145; 42; 20; 4

Viết chương trình nhập vào từ bàn phím số tự nhiên x và in ra màn hình dãy (Xn)

Dữ liệu vào: Số tự nhiên x.

Dữ liệu ra: In ra màn hình dãy (Xn)

Thuật toán

Để giải bài toán này, ta sẽ sử dụng vòng lặp để tính toán giá trị của từng phần tử trong dãy cho đến khi nào tìm được phần tử có giá trị trùng với một phần tử đã xuất hiện trước đó. Khi đó, ta sẽ dừng vòng lặp và in ra dãy (Xn) từ đầu đến phần tử trùng lặp đó.

Cài đặt bài toán với Python

def sum_of_digit_squares(num):
    sum = 0
    while num > 0:
        digit = num % 10
        sum += digit ** 2
        num //= 10
    return sum

x = int(input("Nhap vao so tu nhien x: "))
sequence = [x]
while True:
    next_num = sum_of_digit_squares(sequence[-1])
    if next_num in sequence:
        break
    sequence.append(next_num)

for i in range(len(sequence)):
    print(sequence[i], end=" ")

Cài đặt bài toán bằng C++

#include <iostream>
#include <vector>
using namespace std;

int sum_of_digit_squares(int num) {
    int sum = 0;
    while (num > 0) {
        int digit = num % 10;
        sum += digit * digit;
        num /= 10;
    }
    return sum;
}

int main() {
    int x;
    cout << "Nhap vao so tu nhien x: ";
    cin >> x;
    vector<int> sequence;
    sequence.push_back(x);
    while (true) {
        int next_num = sum_of_digit_squares(sequence.back());
        if (find(sequence.begin(), sequence.end(), next_num) != sequence.end()) {
            break;
        }
        sequence.push_back(next_num);
    }
    for (int i = 0; i < sequence.size(); i++) {
        cout << sequence[i] << " ";
    }
    return 0;
}

Trong chương trình này, ta sử dụng một vector để lưu trữ các phần tử trong dãy (Xn). Ta bắt đầu bằng cách thêm x vào vector, sau đó sử dụng vòng lặp while để tính toán từng phần tử tiếp theo trong dãy bằng cách gọi hàm sum_of_digit_squares().

Nếu phần tử mới tính được không trùng với bất kỳ phần tử nào trong vector, ta sẽ thêm nó vào vector và tiếp tục vòng lặp. Nếu phần tử mới tính được đã xuất hiện trước đó trong vector, ta sẽ dừng vòng lặp bằng cách sử dụng lệnh break.

Cuối cùng, ta sử dụng một vòng lặp for để in ra từng phần tử trong vector (Xn).