Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

**stoxx**

Code:

			seq:   m  m  r  t  f  f  f

cnt:   1  2  1  1  1  2  3

rev:   2  1  1  1  3  2  1

rng:   6  4  3  2  3  2  1

res:   m  m  r  [color=#ff003f][size=18][b]F[/b][/size][/color]  f  f  f

das F ist falsch.

Das PRoblem ist, die Tabelle die Du verwendest, ist nur für den ersten Buchstaben gültig.
Die Fortgeschriebenen Häufigkeiten sind nur gültig, wenn man den ersten Buchstaben berechnen will.
Wenn man den zweiten Buchstaben berechnet, dann gelten ja andere fortgeschriebenen Häufigkeiten.
(Ob man bei meinem Algorithmus von vorn oder von hinten anfängt, ist egal)

in meinem Beispiel könnte man auch von vorn berechnen:

markieren

Delphi-Quellcode:

			for i := 0 to len -1  do 

begin 

    st := copy(Eingabe, i+1, len -i); 

    ausgabe :=  ausgabe +  Ermittle(st) ; 

end; // for

anstatt:

markieren

Delphi-Quellcode:

			for i := 0 to len -1  do 

begin 

    st := copy(Eingabe, len -i, i+1); 

    ausgabe := Ermittle(st) + ausgabe; 

end; // for

Das ist egal.

Ich dachte halt nur, wenn man von hinten anfängt, könnte man eventuell schon ergebnisse nutzen .. irgendwie .. vielleicht halt.
Also eventuell ..

**marabu**

Das von dir als falsch markierte f ergibt sich doch aus der Tatsache, dass der Bereich für das t in der Eingabesequenz an der betrachteten Stelle die Größe 2 hat (das erste f kann ), während das f als einzige relevante Alternative die Bereichsgröße 3 besitzt. Nach der Beschreibung deines Algorithmus qualifiziert der größere Bereich den "Sieger" - ergo wird das t vom f verdrängt. Hast du die Spielregeln geändert?

Außerdem kann ich deine Aussage zu meinen Hilfsvektoren cnt bzw. rev nicht nachvollziehen - vielleicht bin ich einfach schon zu müde. Auf jeden Fall nährt sich der Knobelcharakter deiner Aufgabe aus der individuellen Art, mit der du eine klare Formulierung des Algorithmus vermeidest. Vielleicht wird alles klarer, wenn du einmal die Bereichsgrößen darstellst. Stimmen denn die Angaben in meinem Vektor rng? Oder liegt da schon das Verständigungsproblem?

marabu

**stoxx**

Zitat von marabu:

Das von dir als falsch markierte f ergibt sich doch aus der Tatsache, dass der Bereich für das t in der Eingabesequenz an der betrachteten Stelle die Größe 2 hat (das erste f kann ), während das f als einzige relevante Alternative die Bereichsgröße 3 besitzt. Nach der Beschreibung deines Algorithmus qualifiziert der größere Bereich den "Sieger" - ergo wird das t vom f verdrängt. Hast du die Spielregeln geändert?

Außerdem kann ich deine Aussage zu meinen Hilfsvektoren cnt bzw. rev nicht nachvollziehen - vielleicht bin ich einfach schon zu müde. Auf jeden Fall nährt sich der Knobelcharakter deiner Aufgabe aus der individuellen Art, mit der du eine klare Formulierung des Algorithmus vermeidest. Vielleicht wird alles klarer, wenn du einmal die Bereichsgrößen darstellst. Stimmen denn die Angaben in meinem Vektor rng? Oder liegt da schon das Verständigungsproblem?

marabu

das t wird vom f "noch" nicht verdrängt.

t wird von 4 bis 7 berechnet

t -> t ist einmal vorhanden, t hat Spannweite von 1
tf -> t ist einmal vorhanden, t hat Spannweite von 2
f ist einmal vorhanden, f hat Spannweite von 1

tff - f wird am häufigsten, Spannweite von 1 !! ab hier fängt die Zählung an für f (siehe Definition ganz oben)
t ist einmal vorhanden, Spannweite immer noch 2

tfff t hat immernoch die Spannweite von 2
f hat nun auch die Spannweite von 2 (ist aber noch nicht größer als die von t) .. daher ist der Sieger immer noch t

ich weiß, dass das Problem schwierig zu beschreiben ist. das sind Häufigkeitszählungen, aber das wird Dir nicht viel nützen.

Zitat:

Stimmen denn die Angaben in meinem Vektor rng?

Die Vektoren hab ich mir schon nicht mehr angeschaut, weil die fortlaufende Häufigkeitszählung falsch ist.
siehe das Beispiel. Weiß nicht so recht, was Dein Algo macht.
Denn die fortlaufenden Häufigkeit ist zur Berechnung des ersten Buchstaben eine andere, als wenn man den vierten Buchstaben berechnen würde.

markieren

Code:

			seq:   f  m  m  r  t  f  f  f 

cnt:   1  1  2  1  1  [color=#ff003f][b]1 2 3 [/b][/color] 

rev:   1  2  1  1  1  3  2  1 

rng:   2  6  4  3  2  3  2  1 

res:   m  m  m  r  f  f  f  f

**x000x**

Moin moin,
ich habe auch mal versucht da durchzusteigen... Wie folgt habe ich
es verstanden:

markieren

Code:

			___________________________________________________

1.

      _____4______

     |            |

 |f  m| m  r  t  f |f  f |          = x[0] = m (4)

 |____|            |_____|

   2                 2

___________________________________________________

2.

                       _1

                      |  |

  f |m  m  r  t  f  f |f           = x[1] = m (6)

    |_________________|

             6

___________________________________________________

3.

                    __2__

                   |     |

  f  m |m  r  t  f |f  f |         = x[2] = m (4)

       |___________|

             4

___________________________________________________

4.

                    __2__

                   |     |

  f  m  m |r  t  f |f  f |         = x[3] = r (3)

          |________|

              3

___________________________________________________

5.

                    __2__

                   |     |

  f  m  m  r |t  f |f  f |         = x[4] = t (da t >= f)

             |_____|

                2

___________________________________________________

6, 7 und 8.

  f  m  m  r  t |f  f  f |         = x[5..7] = f

                |________|

                     f

___________________________________________________

Ergebnis: m m m r t f f f

Sollte ich nicht daneben liegen, ergeben sich 2 Fragen:
1. Warum kommst du in deinem letzten Beitrag auf x[4] = f ?
2. Was ist mit dem Fall unter Punkt 1 bei einer Arraylänge n? Würden die F am ende
als neuer "Abschitt" gesehen werden?

Sollte ich daneben liegen... naja, ist halt schon spät

**marabu**

Guten Morgen.

Zitat von stoxx:

ab hier fängt die Zählung an für f

Erst durch diese Erklärung fällt mir auf, dass sich bei meiner Implementierung angrenzende Bereiche überlappen. Ich muss noch eine kleine Änderung an der abschließenden Berechnungsschleife einführen:

zusammenfalten · markieren

Delphi-Quellcode:

			// ...

  // calculate result

  for i := High(seq) downto 0 do

  begin

    maxRange := rng[i];

    maxSymbol := seq[i];

    for j := i + maxRange to High(seq) do

      if (j = i) or (rng[j] > maxRange) then

      begin

        maxSymbol := seq[j];

        maxRange := rng[j];

      end;

    Result[Succ(i)] := maxSymbol;

  end;

// ...

Die als falsch eingestuften "Häufigkeitszählungen" in meinem Programm sind übrigens gerade der Schlüssel zur Umstellung der Laufzeitkomplexität auf O(n).

Schönes Wochenende

marabu

**stoxx**

Hi x000x !

Deine Darstellung ist richtig !

Danke !
Das hast Du komplett richtig verstanden, so soll es sein, weil die Darstellung so gut war, hab ich es mal für das Beispiel

a a b b c c a a gemacht.

markieren

Code:

			1.

 |a  a  b  b  c  c  a  a |      = x[0] = a (8)

 |_______________________|

             8

___________________________________________________

2.               5

           ______________

          |              |

  a |a  b |b  c  c  a  a |      = x[1] = b (5)

    |_____|         

       2  

___________________________________________________

3.

  a  a |b  b  c  c  a  a |      = x[2] = b (6)

       |_________________|

                6

___________________________________________________

4.                    

                 ___3____                                  

                |        |                           

  a  a  b |b  c |c  a  a |      = x[3] = c (3)

          |_____|                                         

             2                                      

___________________________________________________

5.

  a  a  b  b |c  c  a  a |      = x[4] = c (4)

             |___________|                                      

                  4                                 

___________________________________________________

6.

                       _1_                            

                      |   |                          

  a  a  b  b  c |c  a |a  |     = x[5] = c (2)

                |_____|                                   

                   2                                

___________________________________________________

7.

  a  a  b  b  c  c |a  a |      = x[6] = a (2)

                   |_____|                                

                      2                             

___________________________________________________

2.

  a  a  b  b  c  c  a |a |      = x[7] = a (1)

                      |__|                             

___________________________________________________

Ergebnis: a b b c c c a a

Deine Fragen:

Zitat:

1. Warum kommst du in deinem letzten Beitrag auf x[4] = f ?

Das ist ja das falsche Beispiel von marabu, Deins ist richtig.

Zitat:

2. Was ist mit dem Fall unter Punkt 1 bei einer Arraylänge n? Würden die F am ende
als neuer "Abschitt" gesehen werden?

zu einer Länge von n kommen wir ja, wenn wir weitere Elemente anfügen. Bei jedem neuen Element muss die gesamte Berechnung neu durchgeführt werden.
Oder aber eben irgendeine intelligente andere Lösung ...

Hi Marabu,

Mit Deinem Code kommt bei a a b b c c a a als falsches Ergebnis: a c b b c c a a raus, ist das jetzt nur noch ein kleiner Fehler oder stimmt die Logik nicht ?

Danke an Euch !

**marabu**

Hallo stoxx,

Zitat:

Mit Deinem Code kommt bei a a b b c c a a als falsches Ergebnis: a c b b c c a a raus, ist das jetzt nur noch ein kleiner Fehler oder stimmt die Logik nicht ?

bist du sicher, dass dein Ergebnis stimmt? Meine Interpretation deiner Regeln ergibt etwas anderes:

markieren

Code:

			___________________________________________________

4.                   

                 __2__                                 

                |     |                           

  a  a  b |b  c |c  a |a |      = x[3] = b (2) (da b >= c)

          |_____|     |__|                                    

             2          1                           

___________________________________________________

marabu

PS: Kompliment von mir an x000x für die gelungene Semigrafik.

**stoxx**

Hi Marabu,

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.
Da kein anderer Buchstabe bis zum Ende dreimal vorkommt, bleibt c der Sieger bis zum Schluß. Das meinte ich ja damit, dass die Häufigkeitszählungen immer neu gemacht werden müssen.

Zitat:

Es ist der Buchstabe mit folgenden Eigenschaften:
1. Derjenige, der von vorn durchgegangen (von x[n-i] bis x[n]) sich über
den größten bereich erstreckt.
Der Bereich für einen Buchstaben ist definiert:
Er beginnt ab dem Index, wo der betreffende
Buchstabe am häufigsten vorkommt.
und endet bei dem Index , wo ein anderer neuer Buchstabe dessen Häufigkeit übertrifft.

**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:

zusammenfalten · markieren

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:

markieren

Code:

			___________________________________________________

5.

                    __2__

                   |     |

  f  m  m  r |t  f |f  f |         = x[4] = t (da t >= f)

             |_____|

                2

___________________________________________________

marabu

**stoxx**

Zitat:

Die Häufigkeit eines Buchstaben dient nur zur Abgrenzung der Bereiche und nicht als Kriterium für den "Sieger".

richtig

Zitat:

Häufigkeit - nach meiner Auffassung ist das übrigens die Länge der längsten Teilkette im untersuchten Abschnitt.

mit Häufigkeit ist die Anzahl der Vorkommen eines Buchstaben gemeints.

Zitat:

ist das übrigens die Länge der längsten Teilkette im untersuchten Abschnitt

ähm, nochmal, versteh ich nicht ..

Zitat:

eliminiere ich durch folgende Korrektur:

aber es funktioniert doch immernoch nicht
Ich mach Dir ungern Vorschriften, da Du Dir die Mühe gemacht hast und Dir wirklich mal Quellcode überlegt hast.
Dafür bin ich Dir unheimlich dankbar.
Deswegen sorry, aber warum nimmst Du nicht einfach mal meinen Quelltext, kompiliest ihn und schaust ob Dein Programm dasselbe rechnet.
Das tut es nämlich nicht.
für aabbccaa kommt bei Dir jetzt auch aabbccaa raus ... jetzt ist noch ein richtig grober fehler drin.
Denke aber immernoch, dass Du das Problem anders verstanden hast, als ich wollte.
Wo siehst Du in dem Beispiel ein Widerspruch ?

für die Berechnung ist relevant

tfff

und da ist t über einen Bereich von 2 gültig;
und f über einen Bereich von 2.
Da aber f noch nicht über einen Bereich von 3 Gültigkeit hatte, somit ist t noch der Sieger.
hmmmmm .. fragend anschau ...
(richtigerweise müsste die Begründung aber heißen, da f <= t )

markieren

Code:

			5.

                    __2__

                   |     |

  f  m  m  r |[color=#ff003f]t[/color]  f |f  f |         = x[4] = t (da t >= f)

             |_____|

                2

___________________________________________________