Zahl auf Zahlenpalindrom hin überprüfen

[xZise]

Hallo ihr,

wie würdet ihr überprüfen, ob die Zahl ein Zahlenpalindrom ist? Nun ist die "String"-Variante ziemlich langsam (800 - 500 ms für die ersten 1.000.000 Zahlen (die getestet werden)). Wenn man aber die Zahlen bis 2^63-1 (also sozusagen MaxInt64) überprüft, ist man dann mehrere Jahrtausende dabei. Nun ein Teil könnte ausgeschlossen werden, wie zum Beispiel alle mit 0 endenden Zahlen (je nach Definition).

MfG
xZise

[Uwe Raabe]

Wenn du alle Zahlen von 1..MaxInt64 überprüfen willst, hast du somit auch MaxInt64 Überprüfungen vorzunehmen. Nehmen wir nur einmal an, daß eine vertretbare Zeit für diese Aufgabe 1 Tag sei. Dann darf im Schnitt für jede Zahl nur 1/100000000000000000 Sekunde benötigt werden. Nehmen wir weiter an, es gäbe eine Möglichkeit, die Überprüfung einer Zahl mit einem einzigen Prozessortakt auszuführen. Dann brauchen wir bei handelsüblichen Prozessoren (ca. 3GHz) immer noch knapp 36000 Prozessoren, um diese Leistung zu erbringen.

Fazit: Die Aufgabenstellung ist heutzutage mit vertretbarem Aufwand nicht zu lösen!

Wie wärs, wenn du die Palindrome zusammensetzt? Damit schließt tu per Definition schon mal alle Nicht-Palindrome aus. Ob die Laufzeit dadurch aber in einen realistischen Bereich gelangt, weiß ich auch nicht...

[xZise]

Okay das klingt ja schon mal gut und unrealistisch. Aber wir setze ich den Zahlenpalindrome am besten "zusammen"? Außerdem muss sie durch eine beliebige andere Zahl teilbar sein (ohne Rest).

MfG
xZise

[Uwe Raabe]

Zitat:

Zitat von xZise

Aber wir setze ich den Zahlenpalindrome am besten "zusammen"?

- nimm eine beliebige Zahl
- konvertiere in String
- mache eine invertierte Kopie davon (= Reihenfolge der Ziffern umdrehen)
- setze beide zusammen
- in Zahl zurück konvertieren

Zitat:

Zitat von xZise

Außerdem muss sie durch eine beliebige andere Zahl teilbar sein (ohne Rest).

Es hilft ungemein, wenn das Problem nicht scheibchenweise präsentiert wird...

[Apollonius]

Das klingt irgendwie stark nach der Aufgabe vier des aktuellen Bundeswettbewerbs Mathematik.

[Klaus01]

Zitat:

Zitat von xZise

Außerdem muss sie durch eine beliebige andere Zahl teilbar sein (ohne Rest).

Wäre es dann nicht ein Weg alle Vielfachen der beliebigen Zahl
zu prüfen ob denn ein Palindrom vorliegt oder nicht.

Ist eine einstellige Zahl auch schon ein Palindrom?

Grüße
Klaus

[xZise]

Zitat:

Zitat von Apollonius

Das klingt irgendwie stark nach der Aufgabe vier des aktuellen Bundeswettbewerbs Mathematik.

Mag sein. Jemand hatte mich gefragt, ob es möglich wäre, ob alle Palidrome eines vielfachen zu bekommen (z.B. 81). Soweit ich weiß wollte er damit herausbekommen ob irgendwelche Zusammenhänge existieren.

Zitat:

Zitat von Klaus01

[...]Wäre es dann nicht ein Weg alle Vielfachen der beliebigen Zahl
zu prüfen ob denn ein Palindrom vorliegt oder nicht.[...]

Naja das macht er sinn bei Vielfachen > 36.000, WENN der CPU nur ein Takt brauchen würde.

Zitat:

Zitat von xZise

Außerdem muss sie durch eine beliebige andere Zahl teilbar sein (ohne Rest).

Es hilft ungemein, wenn das Problem nicht scheibchenweise präsentiert wird...[/quote]
Naja ich wollte EIGENTLICH nur wissen, wie man schnell ermittelt ob die Zahl n ein Palindrom ist. Dass sie noch ein vielfaches einer Zahl ist hätte ich selber hinbekommen. Erst nachdem du mir zeigtest, wie lange das dauert, habe ich gedacht, dass man da etwas rausholen könnte.

MfG
xZise

[himitsu]

isses wirklich so schwer?

müßten doch alle 6- und 5-stelligen Zahlenpalindroms zur Basis 10 sein?
(andere Stellenanzahlen analog)

Delphi-Quellcode:

Var i: Integer;

For i := 1 to 999 do
  If i mod 10 <> 0 Then
    Memo1.Lines.Add(Format('%d%d%d%.3d', [i mod 10, i div 10 mod 10, i div 100 mod 10, i]));
For i := 1 to 999 do
  If i mod 10 <> 0 Then
    Memo1.Lines.Add(Format('%d%d%.3d', [i mod 10, i div 10 mod 10, i]));

Zitat:

Zitat von Wiki

Zahlenpalindrome bzw. Palindromzahlen sind Zahlen, deren Zahlensystemdarstellung von vorne und hinten gelesen den gleichen Wert hat, z. B. 1331 oder 742247

aber wieso dann?

Zitat:

Zitat von xZise

Außerdem muss sie durch eine beliebige andere Zahl teilbar sein (ohne Rest).

bzw ist das überhaupt möglich? :gruebel:

[edit]
na toll, kaum macht man mal nebenbei noch was, schreiben Andere och sowas ... nur früher -.-°

[add]
billige Lösung ... und dann noch die anderen Stellenanzahlen durchgehn

Zitat:

ob alle Palidrome eines vielfachen zu bekommen (z.B. 81).

Delphi-Quellcode:

For i := 1 to 999 do
  If i mod 10 <> 0 Then Begin
    If (i + i mod 10 * 100000 + i div 10 mod 10 * 10000 + i div 100 mod 10 * 1000) mod 81 = 0 Then
      Memo1.Lines.Add(Format('%d%d%d%.3d', [i mod 10, i div 10 mod 10, i div 100 mod 10, i]));
    If (i + i mod 10 * 10000 + i div 10 mod 10 * 1000) mod 81 = 0 Then
      Memo1.Lines.Add(Format('%d%d%.3d', [i mod 10, i div 10 mod 10, i]));
  end;

[Cyf]

Zitat:

Zitat von Apollonius

Das klingt irgendwie stark nach der Aufgabe vier des aktuellen Bundeswettbewerbs Mathematik.

War auch schon dabei, was über Teilbarkeitsregeln von mir zu geben, aber dann ist mir durch den Kopf, dass das bestimmt sowas ist, weil mans eigentlich nur für Wettbewerbe braucht (und diese nunmal in der Regel selbstständig oder in Gruppen zu bearbeiten sind). Dachte erst an Informatik, aber wenn da mitlerweile die Aufgaben der 2ten Runde raus wären, wüsste ich das schon. :)
Ein Programm nützt hier zwar recht wenig, da es nur nachweist, dass es Palindrome gibt, die die Bedingung erfüllen, dass steht aber auch schon in der Aufgabe (ebenso eigentlich wie man ein solches Palindrom bastelt) und ist kein Beweis dafür.
Dennoch sollte der Nachweis von sowas bei laufenden Wettbewerben nicht diskutiert werden.

[xZise]

Wie gesagt liefere ich damit ja keine Lösung sondern nur eine Anzahl von Palindromen.

Zu himitsu: Hmmm ... 98 mod 10 ist doch ungleich 0 oder? Aber das ist doch kein Palindrom?

MfG
xZise