Algorytm 196

Lekcja 20 z 20 w kursie Zagadki matematyczne w Coddy.

Jeśli weźmiemy 38, odwrócimy kolejność cyfr i dodamy, otrzymamy 38 + 83 = 121, czyli liczbę palindromiczną.

Nie wszystkie liczby tak szybko stają się palindromami. Na przykład:

37 + 73 = 110
110 + 11 = 121

Oznacza to, że liczba 37 potrzebowała dwóch iteracji, aby otrzymać palindrom.

Inny przykład, zaczynając od 249:

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

Zakłada się, że liczby palindromiczne, takie jak 11 i 343, stają się palindromami w zerowej liczbie iteracji.

Weź dowolną dodatnią liczbę całkowitą, odwróć kolejność jej cyfr i dodaj ją do liczby początkowej. To działanie nazywa się procedurą odwracania i dodawania. Następnie powtarzaj tę procedurę, używając otrzymanej sumy, aż uzyskasz liczbę palindromiczną. Procedura ta szybko prowadzi do uzyskania liczb palindromicznych w przypadku większości liczb całkowitych.

Liczbę, która nigdy nie staje się palindromem w wyniku procedury odwracania i dodawania, nazywa się liczbą Lychrela. Pierwsze kilka liczb, o których nie wiadomo, czy tworzą palindromy, czyli „kandydatów na liczby Lychrela”, to 196, 295 i 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Wyzwanie

Średni

Chociaż nikt jeszcze tego nie udowodnił, niektóre liczby w systemie dziesiętnym, takie jak 196, nigdy nie tworzą palindromu. Na potrzeby tego wyzwania założymy, że liczba jest liczbą Lychrela, dopóki nie zostanie udowodnione inaczej. Każda liczba mniejsza niż dziesięć tysięcy albo (i) stanie się palindromem w mniej niż pięćdziesięciu iteracjach, albo (ii) nikomu, pomimo całej dostępnej mocy obliczeniowej, nie udało się dotąd przekształcić jej w palindrom.

Napisz funkcję isLychrel, która przyjmuje dodatnią liczbę całkowitą mniejszą niż 10000 i zwraca liczbę iteracji potrzebnych do uzyskania palindromu.

Zwróć -1, jeśli minie więcej niż pięćdziesiąt iteracji.

Spróbuj swoich sił

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