3. Kleine Schwierigkeit mit Arrays: Palindrom ja oder nein?

Kleine Schwierigkeit mit Arrays: Palindrom ja oder nein?

  • V
     

    Für mich ist die Aufgabe gelöst.

    Für mich nicht.

    Ich empfehle bei allen einfachen algorithmischen Problemen, daß man es mit den Fingern plant. Außer, man ist schon so weit, daß man es im Kopf kann.

    Hier heißt das, daß man sich 20 Bit besorgt und trinkt. Es entstehen 20 Kronkorken. Die beschriftet man auf der weichen Innenseite mittels eines Kugelschreibers mit Buchstaben. Eine Auswahl davon legt man in einer Reihe vor sich als zu prüfenden String.

    Wie prüft man diesen String? Wie prüft man ihn als Mensch? Wie prüft man ihn als Mensch, wenn man sich vorstellt, daß man es mit einem so großen String zu tun hat, daß man ihn nicht direkt überschauen kann. Kurzum, wenn man so blöd ist, wie ein Computer?

    Man legt den linken Zeigefinder vor den ersten Buchstaben und den rechten Zeigefinger vor den letzten Buchstaben.
    Schleife solange die Zeigefeiner nicht zusammen sind,
    - schaut man, ob die beiden gezeigten Buchstaben gleich sind.
    - Wenn nein, war es kein Palindrom.
    - Wenn ja, rückt man die Finger um eine Position zusammen und macht mit der Schleife weiter.
    Wenn die Schleife aughört, weil die Zeigefinger sich berühren, war es ein Palindrom.

    Das führt zu zum Beispiel folgendem Code (das meiste geklaut von SeppJ):

    bool ist_palindrom(const string &wort)
{
 int links=0;
 int rechts=wort.size()-1;
 while(links<rechts)
 {
  if(wort[links]!=wort[rechts])
   return false;
  ++links;
  --rechts;
 }
 return true;
}

    Oft entstehen damit saugeile Algorithmen. Welche, die offensichtlich endschnell und sehr einfach sind. Bei einfacheren Problemen nehme ich manchmal die Zifferntasten von ^ bis 9 und stelle sie mir als Array vor, lege die Finger drunter, und operiere im Geiste rum.

    Und dann klappt es bald und ich freue ich mich wie ein Schneekönig.

    0
  • V

    314159265358979 schrieb:

    Ist natürlich richtig, an sowas hab ich gar nicht gedacht, als ich mich bemüht habe, möglichst C++-ischen Code zu schreiben 🙂

    Wie ein Reh vor dem Scheinwerfer. 🕶
    Man muß stets die Implemetierungssprache im Auge behalten, damit es super wird. Aber superer als super muß es nicht werden.

    0
  • 3

    Um mal den Trick von volkard zu klauen:

    #include <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>

int main()
{
        const int n = 42;
        char str[n];

        typedef std::reverse_iterator<const char*> cr_iter;

        while(std::cin.getline(str, n))
        {
                const int length = std::strlen(str);
                std::cout << str << " ist " << std::equal(str, str + length, cr_iter(str + length)) + "kein Palindrom.\n";
        }
}

    http://www.ideone.com/hQW5y
    🤡

    0
  • V

    314159265358979 schrieb:

    Um mal den Trick von volkard zu klauen:

    std::cout << str << " ist " << std::equal(str, str + length, cr_iter(str + length)) + "kein Palindrom.\n";

    Was war daran besser als das schon gesehene

    std::cout << word << " ist " << std::equal(word.begin(), word.end(), word.rbegin()) + "kein Palindrom.\n";

    ?
    Mir fällt nur eine weitere Definition cr_iter auf, daß ich, um den Code zu verstehen, an mehr Ecken zugleich lesen muß. Und daß die Zeilen zufällig genau gleich viele Zeichen haben.

    0
  • 3

    Er wollte es doch mit einem Array haben. Ich dachte mir, mit der Definition kann er es besser lesen. Ich hätte das typedef ansonsten auch weggelassen.

    0
  • V

    314159265358979 schrieb:

    Er wollte es doch mit einem Array haben. Ich dachte mir, mit der Definition kann er es besser lesen. Ich hätte das typedef ansonsten auch weggelassen.

    Achso. Jaklar. Jetzt ist es ein Array. Das hatte ich glatt übersehen.

    0
  • V

    Ich möchte was von Deinem Stoff haben. Meine Adresse haste ja. Weitere Geschäfte per Mail.

    0
  • 3

    Wie bitte? 😃

    0
  • B

    volkard schrieb:

    ?: doch nicht.

    std::cout << word << " ist " << std::equal(word.begin(), word.end(), word.rbegin()) + "kein Palindrom.\n";

    http://ideone.com/5n5T3

    Ich hätt lieber den Stoff von dem hier..
    Meine Fresse hat das gedauert bis ich es gepeilt hab.

    0
  • C

    ⚠ @ 314159265358979

    Und getch() ist auch nicht gerade toll, nimm lieber std::cin.get(); 😉

    Ich verwende getch(); am Ende, damit die Konsole nicht automatisch schließt, wie du dir bestimmt gedacht hast.
    cin.get(); ist eine etwas problematische Wahl.
    cin.get(); liest nämlich sofort die im Puffer verbleibenden Eingaben ein.

    Habe ich also zuvor eine Eingabe getätigt und diese mit Enter bestätigt, so wird ein Zeilenvorschub(Enter-Taste) im Puffer zurückbleiben. Verwende ich nun am Ende cin.get(), so wird der Zeilenvorschub aus dem Puffer automatisch eingelesen und die Konsole schließt sich.
    Ein doppeltes cin.get() würde das Problem natürlich lösen. Ebenfalls ein cin.ignore(); würde ausreichen, welches das letzte Zeichen im Puffer löscht.

    Das ist der Grund, warum ich getch(); wähle. Dieses greift nämlich nicht auf den Puffer zu. Wollte bloß nochmal Stellung dazu nehmen.

    Ansonsten danke ich für die Vorschläge, die hier gegeben wurden. Hab's nun auf viele Varianten versucht. Auch wenn es länger gedauert hat. Es klappt. 😃

    Das Thema kann (meinetwegen) beendet werden.

    0
Anmelden zum Antworten