Thuật toán 196

Bài học 20 trên 20 trong khóa học Câu đố toán học của Coddy.

Nếu lấy 38, đảo ngược rồi cộng, ta có 38 + 83 = 121, đây là một số đối xứng.

Không phải số nào cũng tạo thành số đối xứng nhanh như vậy. Ví dụ:

37 + 73 = 110
110 + 11 = 121

Tức là, phải qua hai lần lặp thì 37 mới tạo thành số đối xứng.

Một ví dụ khác, bắt đầu với 249:

249+942=1191
1191+1911=3102
3102+2013=5115.

Các số đối xứng như 11, 343 được xem là tạo thành số đối xứng sau 0 lần lặp.

Lấy một số nguyên dương bất kỳ, đảo ngược các chữ số rồi cộng với số ban đầu. Đây là thao tác của quy trình đảo ngược rồi cộng. Sau đó, lặp lại quy trình với tổng vừa thu được cho đến khi có một số đối xứng. Quy trình này nhanh chóng tạo ra số đối xứng với hầu hết các số nguyên.

Một số không bao giờ tạo thành số đối xứng qua quy trình đảo ngược rồi cộng được gọi là số Lychrel. Một số số đầu tiên chưa biết có tạo ra số đối xứng hay không, gọi là các số “ứng viên Lychrel”, là 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Thử thách

Trung bình

Dù chưa ai chứng minh được điều này, một số số trong hệ thập phân, như 196, không bao giờ tạo thành số đối xứng. Trong thử thách này, ta sẽ giả định một số là số Lychrel cho đến khi có bằng chứng ngược lại. Mọi số nhỏ hơn mười nghìn hoặc sẽ (i) trở thành số đối xứng trong ít hơn năm mươi lần lặp, hoặc (ii) cho đến nay, dù có sử dụng toàn bộ năng lực tính toán hiện có, vẫn chưa ai tìm được cách biến số đó thành số đối xứng.

Viết hàm isLychrel nhận một số nguyên dương nhỏ hơn 10000 và trả về số lần lặp cần để số đó trở thành số đối xứng.

Trả về -1 nếu đã quá năm mươi lần lặp.

Tự làm thử

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"

int main() {
    int n;
    if (scanf("%d", &n) != 1) n = 0;
    int r = isLychrel(n);
    printf("%d\n", r);
    return 0;
}