Autor |
Beitrag |
jfheins
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: So 20.12.15 18:19
Die letzten Rätsel fand' ich ganz gut
Str8ts hat sich etwas gezogen und ich hatte nebenbai Paint.net offen, damit ich auf frühere Stände zurückgehen konnte. Immer, bevor ich etwas raten musste, habe ich einen Screenshot gemacht und eingefügt. Nach und nach ließ sich dann alles lösen.
Die Kugel war ähnlich, aber gefühlt einfacher. In einen Screenshot den Weg zurückverfolgen und dann wieder abfahren. Meistens gab es nur eine Möglichkeit, von der die Kugel kommen konnte
Das Rätsel von heute hat mir noch am besten gefallen. Schlecht zu raten, man muss etwas überlegen und kann es dann aber bspw. mit Excel aber auch per Hand lösen
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: So 20.12.15 19:07
jfheins hat folgendes geschrieben : | Die letzten Rätsel fand' ich ganz gut |
Auch das mit der Kugel im Irrgarten?
Das gefällt mir jedenfalls hervorragend!
Vielleicht kann unser Mathematiker sogar ein eigenes Programm oder ein Modul in seinem Alpha-Programm anbieten, das noch viel mehr solcher Kugel-Lösungsmöglichkeiten hat.
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 20.12.15 19:11
Hallo,
Delphi-Laie hat folgendes geschrieben : | Vielleicht kann unser Mathematiker sogar ein eigenes Programm oder ein Modul in seinem Alpha-Programm anbieten, das noch viel mehr solcher Kugel-Lösungsmöglichkeiten hat. |
Gibt es doch schon.
siehe www.entwickler-ecke....ewtopic.php?t=113784
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Für diesen Beitrag haben gedankt: Delphi-Laie
|
|
Delphi-Laie
Beiträge: 1600
Erhaltene Danke: 232
Delphi 2 - RAD-Studio 10.1 Berlin
|
Verfasst: So 20.12.15 19:17
Danke, das war mir entfallen, jetzt erinnere ich mich.
Die Spiele dort sind aber etwas kleiner als die Herausforderungen der letzten beiden Weihnachtskalender?!
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: So 20.12.15 20:18
Hallo,
die Auflösung vom gestrigen Kugelrätsel:
Mit der Bezeichnung l=left, d=down, r=right, u=up ist die kürzeste Zugfolge:
Zitat: | ldruludlurdrulululdrurdldrdlu |
oder als Bild
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Mo 21.12.15 01:35
Hmm, nachdem ich jetzt über Weihnachten bei meinen Eltern bin muss ich feststellen dass das WLAN hier etwas wacklig ist.
Die Aufgabe von heute habe ich gelöst, aber im falschen Moment war gerade das Internet weg. D.h., ich hab eine Schneeflocke aber keinen Eintrag in der Liste bei www.entwickler-ecke....es/ags2015/index.php
Muss ich das Rätsel ein zweites Mal lösen?
_________________ 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)
|
|
Narses
Beiträge: 10182
Erhaltene Danke: 1255
W10ent
TP3 .. D7pro .. D10.2CE
|
Verfasst: Mo 21.12.15 10:21
Moin!
Hidden hat folgendes geschrieben : | Muss ich das Rätsel ein zweites Mal lösen? |
Ja, leider.
cu
Narses
_________________ There are 10 types of people - those who understand binary and those who don´t.
Für diesen Beitrag haben gedankt: Hidden
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 21.12.15 15:31
Hallo,
hier die Auflösung für Wichtel Willys Problem, den Eisbären zu umgehen.
Da er nur waagerecht nach rechts, senkrecht nach oben und diagonal von links unten nach rechts oben laufen kann, liegt hier ein gerichteter Graph von W nach A vor.
Für ein einzelnes Quadrat ABCD mit Diagonale gilt dann:
Ist a die Anzahl der Möglichkeiten nach A zu gelangen, b die nach B und c die nach C, so gibt es genau d = a+b+c Möglichkeiten nach D zu gelangen.
Es ist offensichtlich, dass man von B und C nur auf einem Weg nach D kommt, damit ist die Gesamtzahl b+c. Von A kann man auch nur auf eine Art nach D gelangen, nämlich diagonal. Die Wege A->B->D und A->C->D sind nicht mehr zu berücksichtigen, da diese schon bei den Möglichkeiten b und c eingerechnet sind. D.h., insgesamt d = a+b+c.
Beginnt man nun links unten im Graphen und berechnet für die rechte obere Ecke jedes Quadrates die Summe der dahinführenden Wege (3, bzw. wenn der Eisbär stört 2), so erhält man
Willy kann also auf 152 verschiedenen Wegen zum Weihnachtsmann gelangen, ohne gefressen zu werden.
Beste Grüße
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 21.12.15 15:48
Hallo,
warum einfach, wenn es auch kompliziert mittels Rekursion geht:
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:
| program KeinEisbaerBitte; type tdw = record dx,dy : NativeInt; end;
const maxX = 4; maxY = 4; Eisbaerpos :tdw = (dx:2;dy:2); Startpos :tdw = (dx:0;dy:0); EndPos :tdw = (dx:maxX;dy:MaxY); delta : array[0..2] of tdw = ((dx:1;dy:0),(dx:0;dy:1),(dx:1;dy:1)); var solution : NativeInt;
procedure NextStep(ps:tdw); var i : integer; newPos : tdw; begin For i := 0 to 2 do Begin with delta[i] do Begin newpos.dx := ps.dx+dx; newpos.dy := ps.dy+dy; end; with newPos do Begin IF (dx=Eisbaerpos.dx) AND (dy=Eisbaerpos.dy)then continue; IF (dx>maxx) or (dy>maxy)then continue; IF (dx=EndPos.dx) AND (dy=EndPos.dy)then Begin inc(solution); end else NextStep(newPos); end; end; end;
Begin solution := 0; NextStep(Startpos); writeln('Es gibt ',solution,' Wege'); end. |
Ausgabe Es gibt 152 Wege
Gruß Horst
EDIT:
ich habe das BREAK bei der Erreichung des Enpunktes, ehemals Zeile 35, auskommentiert.
Es funktioniert hier nur, weil die DeltaWerte passend angeordnet sind.Wenn Delta [0] und Delta[2] getauscht wären, ginge es nicht..
Zuletzt bearbeitet von Horst_H am Mo 21.12.15 21:00, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Mathematiker, ub60
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 21.12.15 16:47
Hallo Horst,
Horst_H hat folgendes geschrieben : | warum einfach, wenn es auch kompliziert mittels Rekursion geht: |
Sehe ich nicht so, im Gegenteil. Ich finde deine Lösung sehr gut!
Mein Versuch, es mit dem Computer rechnen zu lassen, gibt nämlich schief.
Ich habe jetzt schnell deine Routine in ein sehr einfaches Programm eingebaut, mit dem man in einem Gitter bis 10 x 10 und verschiedene Eisbärorte die Anzahl der Wege berechnen kann. Da kann man sicher noch einiges mehr basteln, z.B. mehrere Eisbären, aus anderen Gründen gesperrte Wege, usw. usf...
Beste Grüße und Danke für die Routine
Mathematiker
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
Physli
Hält's aus hier
Beiträge: 7
MacOS, Win 10
|
Verfasst: Mo 21.12.15 18:45
|
|
jackle32
Beiträge: 183
Erhaltene Danke: 7
Win7
Delphi XE5 Starter, RAD Studio XE7 Pro
|
Verfasst: Mo 21.12.15 22:12
Hallo zusammen,
hab gestern auch mal wieder die Rekursion genutzt hier mal meine Lösung:
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:
| procedure TForm1.Button1Click(Sender: TObject); var freq, startTime, endTime: int64; begin self.Funktionsaufrufe := 0; Wege := 0; QueryPerformanceFrequency(freq); QueryPerformanceCounter(startTime);
self.PunktPruefen(XSTART, YSTART); self.LabeledEdit1.Text := IntToStr(self.Funktionsaufrufe); self.LabeledEdit2.Text := IntToStr(self.Wege);
QueryPerformanceCounter(endTime);
self.LabeledEdit3.Text := IntToStr((endTime-startTime)*1000000 div freq)+ ' us'; self.LabeledEdit4.Text := IntToStr(freq); end;
function TForm1.PunktPruefen(x, y: integer): integer; var gueltig, endpunkt, baer: boolean; begin Inc(self.Funktionsaufrufe);
baer := (x = XBAER)and(Y = YBAER); endpunkt:= (x = XMAX) and (y = YMAX);
if not (baer or endpunkt) then begin if x < XMAX then self.PunktPruefen(x+1,y); if y < YMAX then self.PunktPruefen(x,y+1); if ((y < YMAX) and (x < XMAX)) then self.PunktPruefen(x+1,y+1); end;
if endpunkt then Inc(self.Wege);
result := 0; end; |
Hab auch mal etwas an der Performance gespielt, daher auch die Zeitmessung.
Und ich habe mal wieder festgestellt, dass mit optimiertem Code doch einiges an Zeit zu gewinnen ist.
Anfänglich hatte ich etwas über 1300 Rekursive aufrufe, in der Endversion sind es nur um die 450 und dem entsprechend natürlich auch kürzere Laufzeiten. (Ja ich weiß is hier mit Kanonen auf Spatzen geschossen, da die rekursive Funktion sowieso nicht viel macht).
Gruß,
Jack
P.S. Vielen Dank an Mathematiker für die vielen tollen Ideen und die hervorragende Umsetzung.
_________________ Es gibt keine dummen Fragen, nur dumme Antworten.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Mo 21.12.15 22:54
Hallo,
gerade ist die Version mit mehreren zufällig positionierten Eisbären fertig.
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: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94:
| program KeinEisbaerBitte; type tdw = record dx,dy : NativeInt; end;
const maxX = 12; maxY = 12; Startpos :tdw = (dx:0;dy:0); ZielPos :tdw = (dx:maxX;dy:MaxY);
var chkFld : array[0..MaxX+1,0..MaxY+1] of byte; Waystack : array[0..maxx+maxy] of tdw; solution : NativeInt;
procedure InitChkfld(n: NativeInt); const symbols = '.ZS_B'; var x,y : NativeInt; Begin Fillchar(chkFld,Sizeof(chkFld),#0); For x := 0 to MaxX+1 do chkFld[x,MaxY+1] := 3; For y := 0 to MaxY do chkFld[MaxX+1,y] := 3; with ZielPos do chkFld[dx,dy] := 1; with StartPos do chkFld[dx,dy] := 2; repeat x := random(Maxx+1); y := random(Maxy+1); IF chkFld[x,y] = 0 then chkFld[x,y] := 4; dec(n) until n<= 0; For y := MaxY downto 0 do Begin For x := 0 to MaxX do write(symbols[chkfld[x,y]+1]); writeln; end; end;
procedure NextStep(idx:NativeInt); forward;
procedure Check(idx:NativeInt);inline;Begin with WayStack[idx+1] do case chkFld[dx,dy] of 0:NextStep(idx+1); 1:inc(solution); end; end;
procedure NextStep(idx:NativeInt); begin with WayStack[idx+1] do begin dx := WayStack[idx].dx+1; dy := WayStack[idx].dy+0; end; Check(idx); with WayStack[idx+1] do begin dx := WayStack[idx].dx+0; dy := WayStack[idx].dy+1; end; Check(idx); with WayStack[idx+1] do begin dx := WayStack[idx].dx+1; dy := WayStack[idx].dy+1; end; Check(idx); end;
Begin InitChkfld(50); solution := 0; WayStack[0] := StartPos; NextStep(0); writeln('Es gibt ',solution,' Wege'); end. |
Quelltext 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:
| 12x12 mit 50 zufälligen Bären: B.........B.Z .....B.B...BB .........BB.B .B........B.B .B...B..B.B.. ....B..BB.... .B..BBB.....B .......BB.... B.B.B...B.... .....B......B ...B.B.BB.... ......BBBBB.. S..........B. Es gibt 30480 Wege -------------------------- 12x12 ohne Baeren ............Z 10x ............. S............ Es gibt 251595969 Wege real 2.510s -------------------------- 10x10 ohne Baeren Es gibt 8097453 Wege real 0m0.081s |
Wirklich alle Wege abzuklappern ist für grössere Abmessungen schier unmöglich.
Gruß Horst.
Für diesen Beitrag haben gedankt: Mathematiker
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Mo 21.12.15 23:17
Hallo Horst,
schöne Lösung für viele "Eisbären". Ich baue noch eine Variante zusammen, bei der Eisbären grafisch mit der Maus gesetzt und entfernt werden.
Horst_H hat folgendes geschrieben : | Wirklich alle Wege abzuklappern ist für grössere Abmessungen schier unmöglich. |
Die Gesamtzahl der Wege wird durch die Delannoy-Zahlen bestimmt. Die Delannoy-Zahlen werden definiert durch:
D(a,b) = D(a-1,b) + D(a,b-1) + D(a-1,b-1)
wobei D(0,0) = 1 ist. Das ist die von mir oben gegebene Erklärung für das Lösen per Hand.
Diese Zahlen geben die Anzahl der möglichen Wege vom Punkt (0,0) zum Punkt (a,b) an, wenn ausschließlich Schritte (1,0), (0,1) und (1,1) möglich sind.
Für die ersten Delannoy-Zahlen D(n,n) ergibt sich für n = 0,1,2,3,…
1, 3, 13, 63, 321, 1683, 8989, 48639, 265729, 1462563, 8097453, 45046719, 251595969, 1409933619, 7923848253, 44642381823, 252055236609, 1425834724419, 8079317057869, 45849429914943, 260543813797441, …
d.h., die Werte wachsen extrem schnell. n=13 mit einer guten Billion geht vielleicht noch, aber dann wird es schwierig.
Beste Grüße
Mathematiker
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
|
|
ub60
Beiträge: 762
Erhaltene Danke: 127
|
Verfasst: Di 22.12.15 01:21
Ich habe das Ganze mal ein wenig weitergerechnet, und es geht doch enorm aufwärts.
Immerhin geht es noch bis n=27 gut.
Für Interessenten:
Quelltext 1: 2: 3: 4: 5: 6:
| 22: 1482376214227923 23: 8443414161166173 24: 48141245001931263 25: 274738209148561921 26: 1569245074591690083 27: 8970232353223635949 |
Ab 9,2*10^18 ist es dann sogar für Int64 zu viel, aber dann gäbe es ja noch die Langzahlarithmetik ...
ub60
PS: Rechenzeit etwa 5 Mikrosekunden
|
|
Mathematiker
Beiträge: 2622
Erhaltene Danke: 1447
Win 7, 8.1, 10
Delphi 5, 7, 10.1
|
Verfasst: Do 24.12.15 01:00
Hallo und frohe Weihnachten,
heute ist der letzte Tag des EE-Adventsgewinnspiels 2015.
Ich möchte mich bei euch für die Teilnahme bedanken und hoffe, ihr hattet etwas Spaß und Freude. Besonderer Dank geht an Narses. Nur durch seine Arbeit war das AGS möglich.
Die Gewinner werden in den nächsten Tagen durch Narses bekanntgegeben. Allen, die eine der wertvollen AGS-Tassen gewinnen werden , möchte ich jetzt schon gratulieren.
Das heutige Rätsel ist zum ruhigen Ausklang wieder ein einfaches Puzzle.
Ich wünsche euch schöne Festtage, viele Geschenke und natürlich auch einen guten Rutsch ins Neue Jahr.
Steffen
Einloggen, um Attachments anzusehen!
_________________ Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein
Für diesen Beitrag haben gedankt: Christian S., Hidden, Horst_H, klassiknerd, Narses, Ralf Jansen, ub60
|
|
Physli
Hält's aus hier
Beiträge: 7
MacOS, Win 10
|
Verfasst: Do 24.12.15 08:52
Frohe Weihnachten euch allen
|
|
harryp
Beiträge: 52
Erhaltene Danke: 9
Win 8.1
Delphi 7, XE8
|
Verfasst: Do 24.12.15 10:23
Vielen Dank an den Mathematiker und alle anderen Beteiligten für die Rätsel, die es in den vergangenen Tagen zu lösen galt.
Respekt an alle, die es geschafft haben alle Aufgaben zu lösen.
Euch allen ein schönes Weihnachtsfest und nen guten Rutsch ins neue Jahr.
|
|
Hidden
Beiträge: 2242
Erhaltene Danke: 55
Win10
VS Code, Delphi 2010 Prof.
|
Verfasst: Do 24.12.15 11:10
Frohe Weihnchten!
--
(Was ich noch fragen wollte: Können wir die Offline-Version allgemein verfügbar machen, nachdem die letzte Einsendung da ist? Ich würde das eine oder andere Rätsel sicher noch ein paar Mal besuchen, und nicht unbedingt immer mit Internetverbindung.)
_________________ 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)
|
|
mandras
Beiträge: 430
Erhaltene Danke: 107
Win 10
Delphi 6 Prof, Delphi 10.4 Prof
|
Verfasst: Do 24.12.15 14:13
Auch von mir
F R O H E W E I H N A C H T E N
an alle hier.
|
|
|