Fun-Soft - Programmierforum

Autor

Thread - Seiten: [ 1 ] > 2 <

010
01.05.2007, 23:46 Uhr
ao

(Operator)

Zitat von Suba Esel:

Die Länge ist nicht unbedingt entscheidend, da ja die Leerzeichen nicht zählen.
Beispiel oben:

Zitat:

"Alles wird gut" -> "Lustiger Wald"

Die beiden Strings sind unterschiedlich lang, weil verschieden viele Leerzeichen da sind. Trotzdem sind sie ein Anagramm.

Na ja, vor dem Messen latürnich die Leerzeichen, Satzzeichen und alles, was nicht mitgemessen werden darf, rausschmeißen. Dachte, das versteht sich von selbst.

ao

Dieser Post wurde am 02.05.2007 um 08:42 Uhr von ao editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

011
04.05.2007, 19:41 Uhr
Lensflare

Zitat:

@Lensflare: Irgendwie funktioniert dein Code bei mir nicht, gibt bei mir immer nein aus.
Kannst du mir bitte auch sagen warum du -65 rechnest, steh da gerade etwas aufm Schlauch ;-)

Weil der buchstabe 'A' auf der ASCII Tabelle die Stelle 65 hat.
um jetzt die Mengen aller Buchstaben in das array mit 26 elementen packen zu können, muss man 65 von der stelle des Buchstaben 'A' abziehen. Man beginnt also mit 0 für A, dann 1 für B, usw...
Man könnte auch schreiben -'A' statt -65

zum Problem mit den Leerzeichen und unterschiedlich langen strings:

C++:

#include <stdio.h>
#include <ctype.h>

bool anagramm(char *s1, char *s2)
{
  int a1[26];
  int a2[26];

  bool b = true;

  for(int i=0; i<26; i++)
  {
    a1[i] = 0;
    a2[i] = 0;
  }

  while(*s1 != '\0')
  {
    if(isalpha(*s1))
      a1[toupper(*s1)-65]++;

    s1++;
  }

  while(*s2 != '\0')
  {
    if(isalpha(*s2))
      a2[toupper(*s2)-65]++;

    s2++;
  }

  for(int i=0; i<26; i++)
  {
    if(a1[i] != a2[i])
      b = false;
  }

  return b;
}

int main()
{
  if(anagramm("Alles wird gut","Lustiger Wald"))
    printf("ja");
  else
    printf("nein");

  getchar();
}

so sollte es gehen.
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)

Dieser Post wurde am 04.05.2007 um 19:48 Uhr von Lensflare editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

012
05.05.2007, 10:19 Uhr
FloSoft
Medialer Over-Flow
(Administrator)

hmm ich würde fast sagen, das ganze wär schneller wenn man:

die strings dupliziert (damit man sie nicht ändert), dann sortiert, und dann vergleicht. dürfte die laufzeit etwas drücken (zumindest bei langen "sätzen")
--
class God : public ChuckNorris { };

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

013
06.05.2007, 05:05 Uhr
0xdeadbeef
Gott
(Operator)

Ich denke da an etwas in der Art:

C++:

static __inline__ void count_letters(unsigned buf[26], char const *s) {
  memset(buf, 0, 26 * sizeof(unsigned));

  for(; *s; ++s) {
    if(isalpha(*s) {
      ++buf[tolower(*s) - 'a'];
    }
  }
}

_Bool anagramm(char const *s1, char const *s2) {
  unsigned letters1[26], letters2[26];

  count_letters(letters1, s1);
  count_letters(letters2, s2);

  return memcmp(s1, s2, 26 * sizeof(unsigned)) == 0;
}

...prinzipiell sehe ich aber keinen schnelleren Algorithmus. Das Duplizieren der Strings ändert nichts am Rechenaufwand des Buchstabenzählens, und kostet nur unnötig Zeit.

In C++ das _Bool durch bool ersetzen, und am besten sowieso das ganze mit std::strings machen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 06.05.2007 um 05:08 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

014
06.05.2007, 22:30 Uhr
0xdeadbeef
Gott
(Operator)

Wobei...heh, in dieser Form sollte das wohl wegen Lokalisierung (Umlaute etc) eher so heißen:

C++:

#define CHAR_VALUES (1 << CHAR_BIT)

static __inline__ void count_letters(unsigned buf[CHAR_VALUES], char const *s) {
  memset(buf, 0, CHAR_VALUES * sizeof(unsigned));

  for(; *s; ++s) {
    if(isalpha(*s) {
      ++buf[tolower(*s)];
    }
  }
}

_Bool anagramm(char const *s1, char const *s2) {
  unsigned letters1[CHAR_VALUES], letters2[CHAR_VALUES];

  count_letters(letters1, s1);
  count_letters(letters2, s2);

  return memcmp(s1, s2, CHAR_VALUES * sizeof(unsigned)) == 0;
}

Da steckt dann zwar prinzipiell noch Optimierungspotential drin, aber...es dürfte schwer sein, das für alle locales anders handzuhaben.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 06.05.2007 um 22:33 Uhr von 0xdeadbeef editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: [ 1 ] > 2 < [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: