AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)
Thema durchsuchen
Ansicht
Themen-Optionen

Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

Ein Thema von stoxx · begonnen am 3. Mär 2006 · letzter Beitrag vom 8. Mär 2006
Antwort Antwort
Seite 1 von 3  1 23      
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#1

Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufgabe)

  Alt 3. Mär 2006, 04:27
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]
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Benutzerbild von negaH
negaH

Registriert seit: 25. Jun 2003
Ort: Thüringen
2.950 Beiträge
 
#2

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 06:24
Lass mich mal raten

" m m r t f f f y x x x x x"

müsste

" m f x x x x x x x x x x x"

ergeben ?

Dann ist das einfach. Du arbeitest von vorne nach hinten. Du speicherst den Index an dem der Buchstabe, hier m,f,x im Array gespeichert werden müsste, also m = 1, f = 2, x = 3. Nun brauchst du noch eine Variable die speichert wie oft der aktuell höchste Buchstabe an einem Stück vorkam. Also m = 2, f = 3, x = 5. Bei jedem neuen Buchstaben wird nun ein Zähler auf 1 gesetzt und solange inkrementiert wie der nachfolgende Buchstabe identisch ist. Ist der nachfolgende Buchstabe nicht identisch so vergleichst du diesen Zähle mit dem Zähler des aktuell höchsten Buchstabens. Sollte der Zähler größer sein so passieren zwei Dinge: 1.) im Array am Buchstaben-Index den aktuellen Buschstaben speichern und Buchstaben-Index +1 inkrementieren. 2.) den aktuell höchsten Zähler auf den neuen Wert setzen.

Am Ende hast du ein Array das so assehen würde:

" m f x t f f f y x x x x x"

bei dem aber nur die Werte

" m f x"

von Interesse sind. Die nachfogenden Werte im Array müssen alle mit "x" gefüllt werden.

Gruß Hagen
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#3

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 06:47
Guten Morgen.

Nehmen wir mal an, dass die Beispieldaten korrekt sind. Mit dem angegebenen Algorithmus komme ich dann aber zu dem Ergebnis m2f5. Wo ist mein Denkfehler?

Code:
str  m m r t f f f
cnt  1 2 1 1 1 2 3
rng  6 4 3 2 3 2 1  // corr.
new  m m f f f f f
Hagens Beispiel liefert mir das Ergebnis f5x8:

Code:
str  m m r t f f f y x x x x x
cnt  1 2 1 1 1 2 3 1 1 2 3 4 5
rng  6 4 3 2 7 5 3 2 5 4 3 2 1  // corr.
new  f f f f f x x x x x x x x
str ist der Eingabe-String, cnt ist die fortgeschriebene Häufigkeit des aktuellen Buchstaben, rng ist die Größe des Bereichs und new ist der Ergebnis-String.

Grüße vom marabu
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#4

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 06:55
Zitat von negaH:
Lass mich mal raten

" m m r t f f f y x x x x x"

müsste

" m f x x x x x x x x x x x"

ergeben ?

Hi Du,

Danke .. ich hatte gehofft, dass Du das Problem vielleicht entdeckst.
das ist nicht richtig, denn z.B. x[5] wird berechnet von a[5] bis a[13], also aus der Sequenz f f f y x x x x x.
Da "f" bis zu a[11] der häufigste Buchstabe ist (nämlich 3 mal), ist dessen Länge der Gültigkeit am längsten ( Länge 7)
Es wird im Prinzip so lange gewertet, solange ein Buchstabe der "Sieger" ist.

Ich versuche heute abend mal ein kleines Beispiel auf Buchtstaben zu basteln, das war nur zur veranschaung. Bei mir im Programm ist das Intern alles mit Listen und Zahlen umgesetzt. Da wäre auch viel zu viel drum rum, um da nochwas erkennen zu können.
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#5

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 07:17
Zitat von marabu:
Guten Morgen.

Nehmen wir mal an, dass die Beispieldaten korrekt sind. Mit dem angegebenen Algorithmus komme ich dann aber zu dem Ergebnis m2f5. Wo ist mein Denkfehler?

Code:
str  m m r t f f f
cnt  1 2 1 1 1 2 3
rng  6 4 1 1 3 2 1
new  m m f f f f f
Hagens Beispiel liefert mir das Ergebnis f5x8:

Code:
str  m m r t f f f y x x x x x
cnt  1 2 1 1 1 2 3 1 1 2 3 4 5
rng  6 4 1 1 7 5 3 2 5 4 3 2 1
new  f f f f f x x x x x x x x
str ist der Eingabe-String, cnt ist die fortgeschriebene Häufigkeit des aktuellen Buchstaben, rng ist die Größe des Bereichs und new ist der Ergebnis-String.

Grüße vom marabu

In meinem Beispiel hast Du ein wenig Recht, das zweite m von Dir ist richtig ( wenn man die Häufigkeit von eins mit beachtet) kleiner Fehler von mir.
Die Tabellen ( oder Zustände) sind nur für die Berechnung von einem einzigen Schritt korrekt. Das ist das blöde daran.
Bei sowas wird es dann interessant, und man muss jeden Schritt berechnen ... , m m r t f f f y m m x x x x
überleg .... ich glaub ich mach erstmal ein kleines Code Beispiel ... ich glaube nämlich, ich habs doch falsch erklärt, es gibt nämlich noch einen Schwellwert. Mit der Häufigkeit von 1 macht das nämlich keinen Sinn. .. Wieder die vielen Knoten im Gehirn ....
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#6

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 08:34
Wichtig ist, dass du den Algorithmus genau wiedergibst, sonst wird das nichts mit der Hilfe. Ich habe ihn mal mit meinem momentanen Kenntnisstand implementiert - Komplexität O(n).

marabu
Angehängte Dateien
Dateityp: dpr demo_849.dpr (1,5 KB, 4x aufgerufen)
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#7

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 16:24
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
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#8

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 17:28
Hallo.

Zitat von stoxx:
Der Algorithmus ist aber eigentlich richtig beschrieben.
Dann stimmen die Beispielergebnisse aber nicht.

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 f f f f f

seq:  m m r t f f f a a
cnt:  1  2  1  1  1  2  3  1  2
rev:  2  1  1  1  3  2  1  2  1
rng:  6  4  3  2  5  4  2  2  1
res:  m f f f f f a a a
Habe eine Fassung meines Programms angehängt, welche die Kontrolltabellen ausgibt, wenn man einen Dateinamen als Aufrufparameter mitgibt. Die Verarbeitungsschleife wird mit einer leeren Sequenz abgebrochen.

Zitat von stoxx:
Hier der Quelltext, der sagt vielleicht mehr als tausend Worte.
Die Redensart gilt nicht immer - nichtmal für jedes Bild.

Woher hast du eigentlich den Algortihmus? Gibt es eine authentische Beschreibung? Oder kannst du etwas über die zugrunde liegende Aufgabenstellung verraten?

Nachdenkliche Grüße vom marabu
Angehängte Dateien
Dateityp: dpr demo_830.dpr (2,3 KB, 1x aufgerufen)
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#9

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 19:41
Zitat:
Dann stimmen die Beispielergebnisse aber nicht.
jaaa ... Maßgeblich ist der Quelltext, das soll rauskommen.
Mein Quelltext hab ich so gestaltet, dass man ihn gut debuggen kann und sieht was rauskommt, und mit welchen Werten er arbeitet.
Die Aufgabentellung ist kein Lehrbuchbeispiel, sondern eine Problem aus meiner eigenen Praxis.

Dein Beispiel ist da auch nicht richtig:

Zitat:
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 f f f f f
richtig ist: (also genau die gleiche Sequenz als ergebnis)

Zitat:
seq: m m r t f f f
res: m m r t f f f




als drittes Result kommt bei Dir f raus, stimmt aber nicht, da kommt ein r hin.
das deswegen.

das "r" errechnet sich aus aus r t f f f

(5 Buchstaben) .. das r hat bis einschließlich dem dritten Buchstaben die größte Häufigkeit (von eins) , bzw wird sie nicht durch eine andere Häufigkeit übertrofffen, erst mit dem 4 Buchstaben erlangt das F den obersten Rang. Da dann nur noch ein f danach kommt, ist die länge von r = 3 und f = 2 .. somit fällt die entscheidung für r

also m m r .. dann weiter ...

oder aber auch als neues Beisiel:

Zitat:
seq: m m r t f f f a
res: m m r f f f f a
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#10

Re: Algorithmus Laufzeitverhalten Knoten im Kopf (Knobelaufg

  Alt 3. Mär 2006, 20:01
Peinlich - ich habe ein Gleichheitszeichen vergessen:

Delphi-Quellcode:
// ...
  // calculate result
  for i := High(seq) downto 0 do
  begin
    if (i = High(seq)) or (rng[i] >= maxRange) then // muss natürlich >= sein !
// ...
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 f f f f
Und immer noch O(n). Den Hintergrund magst du nicht aufdecken? Schade.

marabu
Angehängte Dateien
Dateityp: dpr demo_120.dpr (2,3 KB, 7x aufgerufen)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23      


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 21:29 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz