196-algorithm

Lektion 20 von 20 im Kurs Mathematische Rätsel von Coddy.

Wenn wir 38 nehmen, die Ziffern umkehren und addieren, 38 + 83 = 121, was ein Palindrom ist.

Nicht alle Zahlen ergeben so schnell Palindrome. Zum Beispiel:

37 + 73 = 110
110 + 11 = 121

Das heißt, 37 benötigte zwei Iterationen, um zu einem Palindrom zu gelangen.

Ein weiteres Beispiel, beginnend mit 249:

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

Bei Palindromzahlen wie 11 oder 343 wird davon ausgegangen, dass sie in null Iterationen zum Palindrom werden.

Nehmen Sie eine beliebige positive Ganzzahl, kehren Sie die Ziffern um und addieren Sie sie zur ursprünglichen Zahl. Dies ist die Operation des Umkehr-und-Addier-Verfahrens (reverse-and-add process). Wiederholen Sie nun den Vorgang mit der so erhaltenen Summe, bis eine Palindromzahl erreicht wird. Dieses Verfahren führt bei den meisten Ganzzahlen schnell zu Palindromzahlen.

Eine Zahl, die durch das Umkehr-und-Addier-Verfahren niemals ein Palindrom bildet, wird als Lychrel-Zahl bezeichnet. Die ersten Zahlen, von denen nicht bekannt ist, dass sie Palindrome erzeugen, sogenannte „Lychrel-Kandidaten“, sind 196, 295, 394. [https://mathworld.wolfram.com/196-Algorithm.html]

Aufgabe

Mittel

Obwohl es bisher noch niemand bewiesen hat, erzeugen einige Zahlen im Dezimalsystem, wie 196, niemals ein Palindrom. Für die Zwecke dieser Herausforderung nehmen wir an, dass eine Zahl eine Lychrel-Zahl ist, bis das Gegenteil bewiesen wurde. Jede Zahl unter zehntausend wird entweder (i) in weniger als fünfzig Iterationen zu einem Palindrom, oder (ii) niemandem ist es bisher mit der gesamten verfügbaren Rechenleistung gelungen, sie auf ein Palindrom abzubilden.

Schreiben Sie eine Funktion isLychrel, die eine positive Ganzzahl kleiner als 10000 erhält und die Anzahl der Iterationen zurückgibt, die benötigt werden, um ein Palindrom zu werden.

Geben Sie -1 zurück, falls mehr als fünfzig Iterationen vergangen sind.

Probier es selbst

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