196-algorithm

Урок 20 из 20 курса Математические головоломки на Coddy.

Если мы возьмем 38, перевернем и сложим, 38 + 83 = 121, что является палиндромом.

Не все числа образуют палиндромы так быстро. Например,

37 + 73 = 110
110 + 11 = 121

То есть числу 37 потребовалось две итерации, чтобы стать палиндромом.

Другой пример, начиная с 249:

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

Предполагается, что числа-палиндромы, такие как 11, 343, становятся палиндромами за ноль итераций.

Возьмите любое положительное целое число, переверните его цифры и прибавьте к исходному числу. Это операция процесса «переверни и сложи». Теперь повторяйте процедуру с полученной суммой до тех пор, пока не будет получено число-палиндром. Эта процедура быстро приводит к получению палиндромов для большинства целых чисел.

Число, которое никогда не образует палиндром в процессе «переверни и сложи», называется числом Лишрел. Первые несколько чисел, для которых неизвестно, образуют ли они палиндромы, — «кандидаты в числа Лишрел» — это 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Задание

Средне

Хотя это еще никто не доказал, некоторые числа в десятичной системе счисления, такие как 196, никогда не образуют палиндром. Для целей этого испытания мы будем считать число числом Лишрела, пока не доказано обратное. Каждое число меньше десяти тысяч либо (i) становится палиндромом менее чем за пятьдесят итераций, либо (ii) никто, обладая всеми существующими вычислительными мощностями, до сих пор не смог привести его к палиндрому.

Напишите функцию isLychrel, которая принимает положительное целое число меньше 10000 и возвращает количество итераций, необходимых для того, чтобы оно стало палиндромом.

Верните -1 в случае, если прошло более пятидесяти итераций.

Попробуйте сами

#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;
}