Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

[marabu]

Hi stoxx,

Zitat von stoxx:

das Ergebnis stimmt, denn bei der x[3] Berechnung (seit x000x beginnt die Zählung bei Null, achtung !) wird: b c c a a herangezogen und da kommt "c" zweimal drin vor.

ich halte mich lieber an die Beschreibung des Algorithmus, die du zitierst und hoffe, dass da kein Fehler drin ist. Darin steht, dass die Dimensionierung des Bereiches eines Buchstaben diesen für die Besetzung der Stelle qualifiziert. Die Häufigkeit eines Buchstaben dient nur zur Abgrenzung der Bereiche und nicht als Kriterium für den "Sieger".

Häufigkeit - nach meiner Auffassung ist das übrigens die Länge der längsten Teilkette im untersuchten Abschnitt. Leider ist diese Definition so nicht aus der Beschreibung des Algorithmus zu entnehmen. Ein Testfall wäre die Sequenz aabcaccc.

Allerdings zeigt mir dein Beispiel mit der Sequenz aabbccaa, dass ich die Bereichsüberlappung noch nicht ganz ausgeschaltet habe. Das falsche c auf der zweiten Stelle eliminiere ich durch folgende Korrektur:

Delphi-Quellcode:

// ...
  // calculate result
  for i := High(seq) downto 0 do
  begin
    maxRange := rng[i];
    maxSymbol := seq[i];
    j := i + maxRange;
    while j <= High(seq) do
    begin
      if (j = i) or (rng[j] > maxRange) then
      begin
        maxSymbol := seq[j];
        maxRange := rng[j];
      end;
      Inc(j, rng[j]);  // hic salta
    end;
    Result[Succ(i)] := maxSymbol;
  end;
// ...

Wegen der Sprünge habe ich die FOR Schleife durch eine WHILE Schleife ersetzt.

Zitat von stoxx:

Da kein anderer Buchstabe bis zum Ende dreimal vorkommt, bleibt c der Sieger bis zum Schluß.

Steht das nicht im Widerspruch zu dem hier:

Code:

___________________________________________________
5.
                    __2__
                   |     |
  f  m  m  r |t  f |f  f |         = x[4] = t (da t >= f)
             |_____|
                2
___________________________________________________

marabu