Autor |
Beitrag |
Christian S.
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Mo 15.12.08 01:54
Hallo!
Da es in der Shoutbox eine kleine Diskussion zum Abgabeformat gegeben hat, hier nicht gerade ein Tipp, sondern eine Klarstellung. Für das im Rätsel gegebene Beispiel sähe die Abgabe so aus:
Quelltext
Viele Grüße
Christian
_________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
Klabautermann
Beiträge: 6366
Erhaltene Danke: 60
Windows 7, Ubuntu
Delphi 7 Prof.
|
Verfasst: Mi 17.12.08 22:05
Hallo,
für diejenigen unter euch die mit der Aufgabe dieser Woche noch ihre Probleme haben hier ein kleiner Hinweis:
- An Weihnachten sehe ich die ganze Verwandschaft wieder. Mein Vater ist da, er freut sich bestimmt mich, seinen Sohn, wieder zu sehen. Und mein Opa ist auch da. Der freut sich auch meinen Vater, seinen Sohn, wieder zu sehen.
Viel Spaß beim weiter Programmieren!
|
|
Narses
Beiträge: 10182
Erhaltene Danke: 1255
W10ent
TP3 .. D7pro .. D10.2CE
|
Verfasst: Mo 22.12.08 01:07
Moin!
Die Lösung des Gewinnspiels ist auf mehrere Arten möglich. Wer nicht faul ist, kann´s sogar nur mit einem Blatt Papier und Stift rauskriegen. Deshalb geben wir mal einfach nur die Lösung an:
Quelltext 1:
| A,B,C,G,H,K,L,N,O,S,U,Y |
cu
Narses
_________________ There are 10 types of people - those who understand binary and those who don´t.
|
|
Wolle92
Beiträge: 1296
Windows Vista Home Premium
Delphi 7 PE, Delphi 7 Portable, bald C++ & DirectX
|
Verfasst: Mo 22.12.08 01:11
Gut, immerhin richtig, und falls jemand noch andere Unit-Listen basteln will und das ausprobieren will, hier mein Script:
eicke92.ei.ohost.de/...laere_referenzen.php
_________________ 1405006117752879898543142606244511569936384000000000.
|
|
Tilman
Beiträge: 1405
Erhaltene Danke: 51
Win 7, Android
Turbo Delphi, Eclipse
|
Verfasst: Mo 22.12.08 01:12
Narses hat folgendes geschrieben : | Die Lösung des Gewinnspiels ist auf mehrere Arten möglich. Wer nicht faul ist, kann´s sogar nur mit einem Blatt Papier und Stift rauskriegen. |
Stimmt, ich muss aber zugeben dass ich bis ich da sgemerkt habe es schon rekursiv implementiert hatte.
_________________ Bringe einen Menschen zum grübeln, dann kannst du heimlich seinen Reis essen.
(Koreanisches Sprichwort)
|
|
Xentar
Beiträge: 2077
Erhaltene Danke: 2
Win XP
Delphi 5 Ent., Delphi 2007 Prof
|
Verfasst: Mo 22.12.08 01:16
Hab's händisch in einer Textdatei gelöst.
War sogar gar nicht mal soo schwer, 20 Minuten oder so.
_________________ PROGRAMMER: A device for converting coffee into software.
|
|
Arne K.
Beiträge: 112
C# (VS 2008 Professional)
|
Verfasst: Mo 22.12.08 01:18
Also ist deine Lösung richtig, immerhin! Dein Programm ist aber trotzdem fehlerhaft
Es findet nämlich auch Verweise in Units, die keine Verweise enthalten.
Deine Lösung bei D z.B.:
D => A => C => L => E => K => I => K => R => U => A => H => G => R => O => N => G => O => B => N => V => S => Y => E =>
An der Stelle K => R ist (u.A.) ein Fehler, denn die Unit R referenziert nicht die Unit U. Sie referenziert selbst gar keine Unit, wie es die Aufgabenstellung klärt. Dadurch kamen auch deine utopisch langen Ketten zustande, über die ich mich so gewundert habe
|
|
Wolle92
Beiträge: 1296
Windows Vista Home Premium
Delphi 7 PE, Delphi 7 Portable, bald C++ & DirectX
|
Verfasst: Mo 22.12.08 01:22
stimmt, ich hab die rücksprünge in der rekursion nicht beachtet, hab aber keine Lust, das noch zu ändern...
_________________ 1405006117752879898543142606244511569936384000000000.
|
|
Regan
Beiträge: 2157
Erhaltene Danke: 72
Java (Eclipse), Python (Sublimetext 3)
|
Verfasst: Mo 22.12.08 01:25
|
|
jaenicke
Beiträge: 19285
Erhaltene Danke: 1743
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Mo 22.12.08 01:54
Ja, dann poste ich auch natürlich wieder mein Lösungsprogramm, ich finde die rekursive Variante immer noch am elegantesten, deshalb poste ich mal die.
Grundsätzlich ist das Problem bei der Geschwindigkeit das Auslesen des Memoinhalts. Das dauert im Vergleich zum Algorithmus ewig (Weil nicht TStringList sondern TMemoStrings als Klasse Verwendung findet, und die ist leider relativ langsam.).
Zeitaufwand der ersten Version vielleicht 10-15 Minuten, dann noch etwas mehr für den Rest.
Einloggen, um Attachments anzusehen!
|
|
Tilman
Beiträge: 1405
Erhaltene Danke: 51
Win 7, Android
Turbo Delphi, Eclipse
|
Verfasst: Mo 22.12.08 02:17
Ich poste mal nur den Screenshot meines Programms, machen tun die ja doch alle das gleiche, aber ich habe bei meinem Angegeben dass es immer den kürzesten String ausgeben soll, daher zum Vegrleich.
"Easy" startete übrigens die einfache Variante, mit der man es auch auf Papier hätte lösen können, die andern Buttons beziehen sich nur auf das Konsolen Fenster um da einige Sachen auszugeben.
Einloggen, um Attachments anzusehen!
_________________ Bringe einen Menschen zum grübeln, dann kannst du heimlich seinen Reis essen.
(Koreanisches Sprichwort)
|
|
jaenicke
Beiträge: 19285
Erhaltene Danke: 1743
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Mo 22.12.08 03:24
Ja, bei mir wird nur die erste zirkuläre Referenz einer Unit ausgegeben, alle weiteren werden nicht mehr gesucht. (Was man aber sehr einfach ändern könnte, indem man die Abbrüche entfernt.)
Zunächst hatte die erste Version noch ca. 1 ms gebraucht, und da hab ich dann ein wenig Pointerspielerei betrieben. Trotzdem komme ich auf 140 Mikrosekunden, wenn ich jedesmal aus dem Memo auslese oder auf 40 Mikrosekunden, wenn ich aus einer TStringList jedesmal lese. Das ist auch in dem eben geposteten Programm drin, aber ich kanns ja auch mal direkt posten: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74:
| type PStrings = ^TStrings;
function TfrmMain.GetCircularReferences(uLines: PStrings): string; var UnitData, CurPointer, Visited: PBoolean; function CheckCircular(uChar, uCheck: Integer): Boolean; var i: Integer; begin Result := False; if PBoolean(Integer(Visited) + uCheck)^ then Exit; PBoolean(Integer(Visited) + uCheck)^ := True; for i := 65 to 90 do if PBoolean(Integer(UnitData) + uCheck * 90 + i)^ and ((uChar = i) or CheckCircular(uChar, i)) then begin Result := True; Exit; end; end; var i, j, LineCount: Integer; Line: string; Chars: PByte; begin Result := ''; GetMem(UnitData, 8100); FillMemory(UnitData, 8100, 0); LineCount := uLines^.Count; GetMem(Chars, LineCount); for i := 0 to LineCount - 1 do begin Line := uLines^[i]; Chars^ := Ord(Line[1]); CurPointer := PBoolean(Integer(UnitData) + Chars^ * 90); Inc(Chars); j := 3; while j <= Length(Line) do begin PBoolean(Integer(CurPointer) + Ord(Line[j]))^ := True; Inc(j, 2); end; end; Dec(Chars, LineCount);
GetMem(Visited, 90); for i := 0 to LineCount - 1 do begin CurPointer := PBoolean(Integer(UnitData) + Chars^ * 90); for j := 65 to 90 do if PBoolean(Integer(CurPointer) + j)^ then begin FillMemory(Visited, 90, 0); if (j = Chars^) or CheckCircular(Chars^, j) then begin Result := Result + Chr(Chars^) + ','; Break; end; end; Inc(Chars); end; FreeMem(Visited, 90); Dec(Chars, LineCount);
FreeMem(Chars, LineCount); FreeMem(UnitData, 8100);
if Length(Result) > 0 then Result := Copy(Result, 1, Length(Result) - 1) else Result := 'keine Funde'; end; | Wobei das PStrings gar nicht nötig wäre, es ist ja ohnehin ein Objekt, aber so passt es zum Rest.
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 22.12.08 09:00
Hi
Ja, es lies sich definitiv leichter mit Stift und Papier lösen. Dummerweise habe ich mich dabei vertan und die unit S falsch weggestrichen Ansonsten stimmt meine Lösung überein.
Was lernt man daraus: Vor dem Absenden doppelt prüfen
mfG,
_________________ Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)
|
|
jaenicke
Beiträge: 19285
Erhaltene Danke: 1743
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Mo 22.12.08 09:20
Hidden hat folgendes geschrieben : | Ja, es lies sich definitiv leichter mit Stift und Papier lösen. Dummerweise habe ich mich dabei vertan und die unit S falsch weggestrichen |
Naja, vom Zeitaufwand her ist es etwa identisch. Der Unterschied ist eben, dass es bei einem Programm keine Fehler gibt.
Und ich hab die erste Version einfach runtergeschrieben, kompiliert und funktionierte, wie gesagt, vielleicht 10 Minuten (unterbrochen durch Posts und so, also in Realtime etwas mehr).
Wenn man dann nicht noch hergeht und die Lösung schöner und dann auch noch performanter macht hält sich der Aufwand ziemlich in Grenzen.
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Mo 22.12.08 09:33
Ich möchte hier mal eine andere Methode vorstellen, das Problem zu lösen. Die bisherigen basieren ja auf einer Tiefen- oder Breitensuche durch den Graphen. Ich bestimme die die "Transitive Hülle" des Graphen und gebe am Ende die Schleifen (u,u) aus. Ist zwar nicht die theoretisch eleganteste Möglichkeit, aber sehr übersichtlich implementierbar:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52:
| type TAdjazenzMatrix = Array['A'..'Z', 'A'..'Z'] of Integer;
var Namen : Array[1..22] of String = ( 'ARCHER','BLAKE','CYLONS','DALEK','FARGO','GKAR','HUGO','JANEWY','KIRK','LUKE','MCKAY', 'NOG','OBIVAN','PICARD','QUARK','SYLAR','TEALC','UHURA','WHO','XENA','YAR','ZAPHOD');
A: TAdjazenzMatrix;
procedure InitMatrix; var i, j: Char; n, l, iName: Integer; begin for i := 'A' to 'Z' do for j := 'A' to 'Z' do A[i,j] := 0;
for n := 1 to 22 do begin l := length(Namen[n]); for iName := 2 to l do A[Namen[n][1], Namen[n][iName] ] := 1; end; end;
procedure TransitiveHull; var k,i,j: Char; begin for k := 'A' to 'Z' do for i := 'A' to 'Z' do for j := 'A' to 'Z' do begin if (A[i,j] = 0) and (A[i,k]=1) and (A[k,j] = 1) then A[i,j] := 1 end; end;
function GetCircles: String; var c: Char; begin result := ''; for c := 'A' to 'Z' do if A[c,c] = 1 then result := result + c + ','; end;
procedure TForm1.FormCreate(Sender: TObject); begin InitMatrix; TransitiveHull; Edit1.Text := GetCircles; end; | Und es ist auch ohne Tricks sehr schnell.
_________________ We are, we were and will not be.
|
|
jaenicke
Beiträge: 19285
Erhaltene Danke: 1743
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Mo 22.12.08 09:37
Ja, so ähnlich sah meine nicht rekursive Variante auch aus, allerdings war die nicht so schnell, weshalb ich die wieder verworfen habe.
Wenn ich mir das so ansehe habe ich es mir dabei unnötig kompliziert gemacht, deine Version ist einfacher.
Eigentlich ist es ja auch klar so. Naja, hinterher ist man immer schlauer.
|
|
GTA-Place
Beiträge: 5248
Erhaltene Danke: 2
WIN XP, IE 7, FF 2.0
Delphi 7, Lazarus
|
Verfasst: Mo 22.12.08 10:05
War einfach zu lösen: Erstmal in einer einfachen Schleife alle Units rausgeworfen, die nie aufgerufen werden oder die es nicht gibt. Musste man mehrmals durchjagen, dann waren glaub weniger als 10 Units übrig. K:K streicht man weg. Und dann denkt man an Mathematik und fängt mit Ersetzen an. Hab ich zum Beispiel A:R,C,H,R (R war glaub auch nicht dabei, bin mir grad nicht sicher), dann ersetzt man überall (das geht im Texteditor per Hand ) in den anderen Strings das A durch A,R,C,H (das A muss dabei bleiben). Und schon hat man am Ende einen langen String, aus dem man per Schleife alle doppelten Einträge entfernt, dann noch sortiert und fertig.
_________________ "Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)
|
|
AdrianK
Beiträge: 56
Kubuntu 9.04 Jaunty
Mono 2.4 + MonoDevelop 2.0; Qt Creator
|
Verfasst: Mo 22.12.08 11:25
Juhu! Habs auch richtig...
Die Aufgabe habe ich gelöst, indem ich die ganze Unitliste in einen Graphen geschrieben habe (hatte zufälliger Weise am selben Tag den MSDN Webcast über die Graphentheorie gesehen... ) und dann mittels Breitensuche die Kanten des Graphen so lange verfolgte bis ich alle Knoten besucht hatte, oder wieder "zurückgekommen" bin -> Zirkuläre Referenz
@Edit: Bin ich denn der einzige der's mit C# gemacht hat?
Einloggen, um Attachments anzusehen!
Zuletzt bearbeitet von AdrianK am Mo 22.12.08 14:12, insgesamt 1-mal bearbeitet
|
|
baka0815
Beiträge: 489
Erhaltene Danke: 14
Win 10, Win 8, Debian GNU/Linux
Delphi 10.1 Berlin, Java, C#
|
Verfasst: Mo 22.12.08 12:52
Ich hatte es als Konsolenversion gebaut, aber den Quellcode hab' ich nicht mehr gespeichert. Weiß also noch nicht, ob ich's richtig habe.
|
|
AdrianK
Beiträge: 56
Kubuntu 9.04 Jaunty
Mono 2.4 + MonoDevelop 2.0; Qt Creator
|
Verfasst: Mo 22.12.08 12:56
meine Lösung ist auch ne Konsolenversion...
|
|
|