004 – Größtes Palindrom als Produkt aus zwei dreistelligen Zahlen

 

Eine palindromische Zahl ist eine Zahl, die von vorne und von hinten gelesen gleich ist. Beispiel: 10298689201

Die größte palindromische Zahl, die das Produkt aus zwei zweistelligen Zahlen bildet, ist 91\cdot 99=9009.

Finde die größte palindromische Zahl, die ein Produkt aus zwei dreistelligen Zahlen ist!

Lösung

Als einfachste Lösung stellen wir eine Matrix auf, in denen alle Produkte von 100*100 bis 999*999 berechnet werden. Diese Matrix schreiben wir dann in einen Vektor, den wir in einer Schleife durchlaufen. Jedes Element wird getestet, ob es größer als das größte gefundene Palindrom ist. Ist es das, so wird geprüft, ob das Element selbst ein Palindrom ist. Gegebenenfalls wird das größte gefundene Palindrom durch das aktuelle Element ersetzt.

Die Prüfung, ob eine Zahl ein Palindrom ist, erfolgt dabei wie folgt:
Die Ziffern werden mit einer Modulo-Operation in einen Vektor geschrieben. Von diesem Vektor mit n Ziffern wird jeweils die i-te mit der n+1-i-ten verglichen:

v1 = 100 : 999;
v2 = 100 : 999;
m = v1' * v2;
v = m( : );

max_pali = 1;

for it = 1 : length(v)
    zahl = v(it);

    if (zahl > max_pali)
        zahl_vec = mod(zahl, 10);
        zahl = floor(zahl / 10);

        while zahl > 0
            zahl_vec = [zahl_vec mod(zahl, 10)];
            zahl = floor(zahl / 10);
        end

        palindrom = 1;

        for ziffer = 1 : length(zahl_vec) / 2
            if (zahl_vec(ziffer) ~= zahl_vec(length(zahl_vec) + 1 - ziffer))
                palindrom = 0;
            end
        end

        if palindrom == 1
            max_pali = v(it);
        end
    end
end

max_pali

Das Ergebnis ist 906609.
Rechenzeit: 0.563708 Sekunden

Möglichkeit 2

Die Matrix, die wir oben aufgestellt haben, ist symmetrisch. Es reicht also, (etwa) die Hälfte ihrer Elemente zu prüfen, nämlich entweder die obere rechte, oder die untere linke Dreiecksmatrix. Dies realisieren wir mit zwei verschachtelten Schleifen. Außerdem ist es besser, von oben nach unten zu iterieren. Dann kann abgebrochen werden, wenn das Produkt kleiner als das größte gefundene Palindrom ist, da alle folgenden Produkte noch kleiner werden:

max_pali = 0;

for a = 999 : -1: 100
    for b = 999 : -1: a
        zahl = a * b;
        if zahl <= max_pali
            break;
        end

        zahl_vec = mod(zahl, 10);
        zahl = floor(zahl / 10);

        while zahl > 0
            zahl_vec = [zahl_vec mod(zahl, 10)];
            zahl = floor(zahl / 10);
        end

        palindrom = 1;
        for ziffer = 1 : length(zahl_vec) / 2
            if (zahl_vec(ziffer) ~= zahl_vec(length(zahl_vec) + 1 - ziffer))
                palindrom = 0;
            end
        end

        if palindrom == 1
            max_pali = a * b;
        end % Ende if
    end % Ende Schleife b
end % Ende Schleife a

max_pali

Rechenzeit: 0.032040 Sekunden, der Algorithmus ist also um den Faktor 17 schneller!

Möglichkeit 3

Nun steigen wir wieder in die analytische Betrachtung des Problems ein. Wir wissen, dass das gesuchte Palindrom 6 Ziffern hat. Das folgt daraus, dass es höchstens 6 Ziffern haben kann (999*999=998001), und dass das Palindrom 111111 = 777*143 schon 6 Stellen hat.

Daraus folgt:

p = 100000x+10000y+1000z+100z+10y+x

p = 100001x+10010y+1100z

p = 11\left( {9091x+910y+100z} \right)

Da 11 eine Primzahl ist, muss sie also entweder in a oder in b als Primfaktor vorkommen. Mit dieser Information können wir in Abhängigkeit von a bestimmen, welche Werte für b getestet werden müssen:

max_pali = 0;

for a = 999 : -1 : 100
	if mod(a, 11) == 0
        b = 999;
        db = 1;
	else
        b = 990; % größte Zahl <= 999, die durch 11 teilbar ist
        db = 11; % es muss nur jede 11-te Zahl geprüft werden
    end
    while b > a
        zahl = a * b;
        if zahl <= max_pali
            break;
        end

        zahl_vec = mod(zahl, 10);
        zahl = floor(zahl / 10);

        while zahl > 0
            zahl_vec = [zahl_vec mod(zahl, 10)];
            zahl = floor(zahl / 10);
        end

        palindrom = 1;
        for ziffer = 1 : length(zahl_vec) / 2
            if (zahl_vec(ziffer) ~= zahl_vec(length(zahl_vec) + 1 - ziffer))
                palindrom = 0;
            end
        end

        if palindrom == 1
            max_pali = a * b;
        end % Ende if

        b = b - db;
    end % Ende Schleife b
end % Ende Schleife a

max_pali

Rechenzeit: 0.005169 Sekunden.

M3 ist um den Faktor 109 schneller als M1.
M3 ist um den Faktor 6,2 schneller als M2.

Man könnte nun noch den Algorithmus zur Überprüfung der Palindrom-Eigenschaft verbessern, dies bringt aber keine großen Geschwindigkeitssteigerungen mehr.

Ähnliche Artikel

1 Kommentar zu “004 – Größtes Palindrom als Produkt aus zwei dreistelligen Zahlen”

stevanie heins

man blickt hier nicht mehr ganz durch…
ich würde als verbesserungsvorschlag es deutlicher machen.

Kommentar verfassen