Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

[stoxx]

Zitat von marabu:

Wichtig ist, dass du den Algorithmus genau wiedergibst
marabu

das hab ich jetz beim erstellen des Beispiels auch gemerkt. Also hier der Algorithmus mit Komplexitet n * (n-k)
O(n^2) ist das dann wohl ?

Ich habe mich in meinem Einführungsbeispiel vertan. Der Algorithmus ist aber eigentlich richtig beschrieben.
Es ist im Prinzip eine Bestimmung irgendeines Maxwertes zweimal hintereinander.

für mmrtfff kommt immernoch mmrtfff raus.
Interessant wird es erst, wenn man hinter diese Sequenz zum Beispiel anfängt den Buchstaben a anzufügen.

also z.B. mmrtfffaa

da kommmt raus. mmfffffaa



Hier der Quelltext, der sagt vielleicht mehr als tausend Worte.

Delphi-Quellcode:

type


TDatenMaxCount = record
  Buchstabe : Char;
  Count : Integer;
  StartIndex: Integer;
  MaxLen : Integer;
end;


TDatenSieger = record
  Buchstabe : Char;
  MaxLen: Integer;
end;


//==============================================================================

function ermittle(Sequenz : String)  : char;
var loop, charindex : Integer;
    CountArray : array[0..255] of Integer;
    Sieger : TDatenSieger;
    MaxCount : TDatenMaxCount;

begin

for loop := 0 to high(CountArray)  do
  CountArray[loop] := 0;


MaxCount.Buchstabe := Sequenz[1];
Maxcount.Count := 1;
MaxCount.StartIndex := 1;
MaxCount.MaxLen := 1;

Sieger.Buchstabe := MaxCount.Buchstabe;
Sieger.MaxLen := 1;



for loop := 2 to length(Sequenz) do
begin
   charindex :=  ord(Sequenz[loop]);
   inc(CountArray[charindex]);



   if charindex = ord(maxCount.Buchstabe)then
   begin
       inc(MaxCount.Count);
   end else
   begin
       // Eventuell Neuen Count Max bestimmen

       if CountArray[charindex] > MaxCount.Count then
       begin
          MaxCount.Count := CountArray[charindex];
          MaxCount.StartIndex := loop;
          MaxCount.Buchstabe := char(charIndex);
       end;

   end; // if else

   // wird solange erhöht, bis der nächste Maxcount an dessen stelle kommt
    MaxCount.MaxLen := loop - MaxCount.StartIndex;

   // Längen Maximum .. Sieger bestimmen
   // aktueller Maxcount kann den Sieger übertreffen

   if MaxCount.MaxLen > Sieger.MaxLen then
   begin
       Sieger.Buchstabe := MaxCount.Buchstabe;
       Sieger.MaxLen := MaxCount.MaxLen;

   end;


end;  // for

result := Sieger.Buchstabe;

end; // function ermittle

//==============================================================================

procedure TForm2.Button1Click(Sender: TObject);
var Eingabe, ausgabe, st : String;
    i, len : Integer;
begin


Eingabe := 'mmrtfff';
ausgabe := '';
len := length(Eingabe);


for i := 0 to len -1  do
begin
    st := copy(Eingabe, len -i, i+1);
    ausgabe := Ermittle(st) + ausgabe;
end; // for


showmessage(ausgabe);




end;  // buttonclick