Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

[stoxx]

Ich hab hier ein problem, was ich irgend´wie nicht zufriedenstellend lösen kann und da ich schon einen Knoten im Kopf habe, wollte ich einfach mal fragen.
Ich möchte es mal formulieren.
Ich habe es im Gefühl, dass es da eine schnellere Lösung geben muss, aber komm nicht so recht drauf,... vielleicht täuscht mich auch mein Gefühl.
Das Verfahren hätte normalerweise ein Laufzeitverhalten das proportional zu : n * (n-k) ist
Ziel wäre aber die proportionalität zu n.



ich habe n - Elemente, die auf folgende Art und Weise folgendes Ergebnis liefern sollen.
Ich möchte es mal an einem Beispiel mit 7 Elementen demonstrieren

a ist das gegebene Array und x das Ergebnis Array, dass genauso groß ist wie a.

Delphi-Quellcode:

var a, x : array[1..7] of char;

a[1]  a[2]  a[3]  a[4]  a[5]  a[6]  a[7]  
m     m     r     f     f     f     a

Als Ergebnis soll rauskommen:

x[1]  x[2]  x[3]  x[4]  x[5]  x[6]  x[7] 
m     m     f     f     f     f     a

Pseudocode:

Delphi-Quellcode:

n := 7;

for i := 0 to 6 do
begin
    
    x[n-i] := 
    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.
              
end;

Und zwar ... hmmm , ist nicht einfach zu formulieren.

der Witz an der Sache ist, dass x[1] den Buchstaben "m" erhält. und zwar im letzten Schritt (im siebten Schleifendurchlauf bei i = 6 )
Bei jedem Schritt i muss man von vorn bis hinten alle Werte durchsehen.
Bei i = 3 zum Beispiel fängt man bei a[3] an und hört bei a[7] auf um x[3] zu berechnen/zu ermitteln.

Im siebten und letzten Schritt passiert folgndes. ( i= 6 )
Ich gehe in 7 Schritten von a[1] bis a[7]

dabei für j := 1 bis 7
j = 1 -> a[1] -> m kommt einmal vor und erstreckt sich über größten bereich der Länge 1
j = 2 -> a[2] kommt hinzu -> m kommt 2 mal vor und erstreckt sich über einen Bereich der Lange 2
j = 3 -> a[3] kommt hinzu -> m ist immernoch der häufigste Buchstabe ( zweimal) und erstreckt sich nun über einen Bereich von a[1] bis a[3] ... also hat die Bereichsgröße von 3
j = 4 -> a[4] kommt hinzu -> m erstreckt sich nun über einen Bereich von 4, nämlich von a[1] bis a[4]

usw.

bei j = 7 entscheidet sich dann, was in x[1] ( i = 6) eingetragen wird.
nämlich "m", weil "m" sich über einen Bereich von 6 erstreckt. Genauer von a[1] bis a[6].
Da kommt es nämlich als Buchstabe am häufigsten vor, nämlich 2 mal. Buchstabe "f" auch, aber damit "f" das "m" ablösen kann muss es dreimal vorkommen.
Das geschieht bei j = 7, dann ist "f" am Häufigsten, erstreckt sich aber nur über einen Bereich von eins.
Nämlich von a[7] bis a[7]. Da kommmt es dreimal vor. ( mehr als "m").
Obwohl "f" 3 mal vorkommt, also öfter als "m", wird in x[1] "m" eingetragen. Da Länge des Bereichs von "m" 6 beträgt.

r fällt in dem Ergebnisarray ganz raus,

ach heije .......



Jetzt ist die große Frage, wie man das berechnen könnte, in einem Rutsch von hinten nach vorn in 7 Schritten, ohne wieder bei jedem Schritt nach hinten gehen
zu müssen um die Zählung neu anzufangen.

Es ist zulässig, sich irgendwas zu indizieren, da sich a1 bis a7 nicht ändern. Irgendwann kommt a8 hinzu, da wird das Ergebnisarray komplett neu berechnet. Aber habe noch keine Ideen.

*grübel
[edit=SirThornberry]Da ausversehen der Zitieren-Button anstelle des Edit-Buttons verwendet wurde enstanden 2 Beiträge. Somit wurden der erste Beitrag gelöscht und bei dem zitierten (geänderten Beitrag) die Zitiat-Tags entfernt. Mfg, SirThornberry[/edit]