Autor |
Beitrag |
MungoPower
Hält's aus hier
Beiträge: 10
|
Verfasst: Do 01.10.09 18:54
Moin moin.
Ich weiß, dass es bereits einige Beiträge zu diesem Thema gibt, aber so ganz verstehen tu ich es noch nicht -.-
- Ich habe einen array[1..12] of string mit jeweils einem Buchstaben, z.B. array[1] := 'J';
- In einem weiteren Feld kann der Benutzer ein Wort eingeben, dass kürzer ist, als 12 Buchstaben
- Ich möchte nun wissen, ob dieses Wort mit den Buchstaben aus dem ersten Array gelegt wurde
Mein Ansatz:
- Zweites Wort in einem Array verwandeln
- arrays vergleichen, wenn also z.B. array1[1] = array2[4] ist, dann macht er weiter, wenn nicht, nicht
Wie gehtn das möglichst schonend? Ich könnte das nur mit 12 if-anweisungen in ner for schleifen...
Moderiert von Narses: 2. Frage entfernt.
Viele Grüße
MungoPower
Moderiert von Narses: Titel geändert.
|
|
platzwart
      
Beiträge: 1054
Erhaltene Danke: 78
Win 7, Ubuntu 9.10
Delphi 2007 Pro, C++, Qt
|
Verfasst: Do 01.10.09 19:35
MungoPower hat folgendes geschrieben : | Moin moin.
2tes Problem:
Ich möchte den array1 zufällig sortieren, nicht alphabetisch oder so wie immer in den tutorials...
|
Wenn ich mich nicht täusche, dann ist "zufälliges Sortieren" = nicht sortiert?!?
Zum ersten Teil: Müssen die 12 Buchstaben in einem Array sein, oder darf man die auch als Zeichenkette aneinander hängen?
_________________ Wissenschaft schafft Wissenschaft, denn Wissenschaft ist Wissenschaft, die mit Wissen und Schaffen Wissen schafft. (myself)
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Do 01.10.09 20:35
Du willst also überprüfen, ob ein Array B eine Permutation eines anderen Arrays A ist. Am einfachsten, allerdings nur in O(n²), funktioniert das so:
- Du brauchst ein drittes, gleichgroßes Boolean-Array C, vorbelegt mit False
- Für jedes Element aus A: Suche ein Element aus B, das damit übereinstimmt und dessen zugehöriger (= gleicher Index) Wert in C False ist. Falls gefunden, setze den Wert in C auf True, ansonsten bist du schon fertig.
- Genau wenn C nur True beinhaltet, ist es eine Permutation
_________________ >λ=
|
|
MungoPower 
Hält's aus hier
Beiträge: 10
|
Verfasst: Do 01.10.09 21:49
Zitat: | Wenn ich mich nicht täusche, dann ist "zufälliges Sortieren" = nicht sortiert?!? |
Ähm ja, ich meine eigentlich die Buchstaben einfach willkürlich vertauschen, so dass da statt ANGSBUDE eben BUNDESTAG steht.
Zu 1.
Es ist ja keine richtige Permutation, weil das 2te Wort kürzer ist als das erste. Ich will also z.B. prüfen, ob "TAG" in "BUNDESTAG" enthalten ist.
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Do 01.10.09 22:02
MungoPower hat folgendes geschrieben : | Es ist ja keine richtige Permutation, weil das 2te Wort kürzer ist als das erste. |
Achso, quasi die Permutation einer Kombination. Wenn du das kleinere Array als A nimmst, C auf die Größe von B setzt und den letzten Schritt weg lässt, sollte mein Algorithmus trotzdem passen.
_________________ >λ=
|
|
MungoPower 
Hält's aus hier
Beiträge: 10
|
Verfasst: Do 01.10.09 22:13
Danke für eure Mühen, ich hab eindlich eine Lösung gefunden..
Ich poste gleich, wie ichs gemeint hab, mom
|
|
Jann1k
      
Beiträge: 866
Erhaltene Danke: 43
Win 7
TurboDelphi, Visual Studio 2010
|
Verfasst: Do 01.10.09 23:32
Andere Idee:
Ich sortiere beide Arrays (geht denke ich mit maximal O(n log n)) und vergleiche dann beide bis zum Ende vom kürzeren, sind die beiden Arrays bis zum Abbruch gleich ist die Eingabe okay.
|
|
Kha
      
Beiträge: 3803
Erhaltene Danke: 176
Arch Linux
Python, C, C++ (vim)
|
Verfasst: Fr 02.10.09 00:18
[B;C] und [A;B;C] sind sortiert, sie haben trotzdem nicht den gleichen Anfang  .
Edit: Wenn du das allerdings weiter denkst, kommst du zu dem linearen Algorithmus, den ich im Kopf und auch schonmal implementiert habe: Beide Arrays werden jeweils nach gleichen Elementen gruppiert und die Größen der Gruppen festgehalten. Aus [A;B;B;C;B;A] würde beispielsweise [(A,2);(B,3);(C,1)]. Dann muss nur noch überprüft werden, ob die Größe jeder Gruppe im kleineren Array A kleiner als die der entsprechenden Gruppe in B ist. Sortieren ist nicht nötig, deswegen geht auch O(n).
_________________ >λ=
|
|
MungoPower 
Hält's aus hier
Beiträge: 10
|
Verfasst: Fr 02.10.09 18:23
Also, hab einfach so gemacht:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| procedure TForm1.BtTauschenClick(Sender: TObject); var zufallszahl1, zufallszahl2, d : Integer; hilfsstring, wort, wort2 : string; begin for d := 1 to 4 do begin zufallszahl1 := (random(Length(EdAnzeige.Text))+1); //EdAnzeige.Text soll umsortiert werden zufallszahl2 := (random(Length(EdAnzeige.Text))+1); wort := EdAnzeige.Text; wort2 := EdAnzeige.Text; hilfsstring := EdAnzeige.Text[zufallszahl1]; wort[zufallszahl1] := wort[zufallszahl2]; wort[zufallszahl2] := wort2[zufallszahl1]; EdAnzeige.Text := wort; end; end; |
Das ist zwar ein bissel unschön, aber ich fands einfach
Lg,
MungoPower
|
|
|