Wie heute morgen schon angedroht hab ich hier nochmal ein kleines Rätselchen, welches mir letztendlich meine Mittagspause geraubt hat :) --- Ihr steht vor einem 100-stöckigen (für die Harten unter euch: n-stöckigen) Hochhaus und habt ein Säckchen voll Murmeln. Ihr möchtet herausfinden aus welchem Stock ihr die Murmeln maximal werfen könnt ohne dass sie zerbersten. Dazu wollt ihr aber maximal 2 Murmeln opfern. Wieviel Versuche braucht man minimal mindestens um eine sichere Antwort geben zu können? Wie sähe eine Strategie aus um die Worst-Case Versuchsanzahl zu minimieren? --- Beispielstrategie um den Sachverhalt zu veranschaulichen: Ich beginne im ersten Stock und gehe immer einen Stock nach oben bis eine Murmel kaputtgeht. Worst-Case: 100 Versuche (die Murmel überlebt auch Etage 100)
Sukzessive Approximation. Scheitert aber an der Suche nach der weggerollten Murmel (==> es sind mehr als 2 Murmeln notwendig) und wegen des Polizeieinsatzes.
Variante 1: Murmel Nr.1 aus dem 100. Stock werfen. Überlebt sie, genügt der eine Versuch. Ansonsten mit der zweiten Murmel von ganz unten anfangen. best case 1 Versuch, worst case 100 Versuche. Variante 2: Murmel Nr.1 aus dem 50. Stock werfen. Im Überlebensfall nach oben vorarbeiten. Ansonsten mit der zweiten Murmel von ganz unten anfangen. best case 2 Versuche, worst case 51 Versuche.
Icke ®. schrieb: > Variante 2: > Murmel Nr.1 aus dem 50. Stock werfen. Im Überlebensfall nach oben > vorarbeiten. Ansonsten mit der zweiten Murmel von ganz unten anfangen. > best case 2 Versuche, worst case 50 Versuche. Diese Variante kann man noch optimieren, in dem man die erste Murmel aus dem 33 Stock wirft. Geht sie kaputt, fängt man mit der anderen von ganz unten an. Bleibt sie ganz, wirft man sie aus dem 66. Im worst case also 34 Versuche.
Ich würde von unten Anfangen und alle 10 Stockwerke eine Murmel fallen lassen. Wenn die Mumel bei einem Stockwerk kaputt gehen sollte, dann nehme ich die zweite Murmel und Taste mich vom letzten Zehnerstockwerk in einser-Schritten weiter. Wenn dann die zweite Murmel kaputt geht, weiss ich genau welches Stockwerk es ist. Wenn ich mich nicht verhauen habe sind 19 Würfe der worst case.
Was stört euch an den schon genannten (implizit - aber welcher Ingenieur kennt die Arbeitsweise von ADC nicht?) 7 Versuchen?
Denk aber dran, dass dein ADC bei zu oft Comparator=1 in Rauch aufgeht.
Ich sehe aber ein Problem mit der Intervallhalbierung. Angenommen nur im ersten und zweiten Stock bleibt die Murmel ganz, dann habe ich mehr kaputt gemacht, bis ich die Lösung hätte... edit oh hab was überlesen, hat keinen Bezug auf die Vorherigen Varianten, aber Intervallhalbierung ist trotzdem doof ;)
John Drake schrieb: > Was stört euch an den schon genannten (implizit - aber welcher Ingenieur > kennt die Arbeitsweise von ADC nicht?) 7 Versuchen? Nichts stört daran, aber kannst du auch eine Strategie liefern die das leistet und nicht gegen die Voraussetzungen verstößt? Ansonsten habe ich schon 19 gelesen, wer bietet weniger? :)
D. I. schrieb: > Ansonsten habe ich schon 19 gelesen, wer bietet weniger? :) 14 Wenn man die Abstände zwischen den Stockwerken, aus denen man die Murmel zunächst fallen lässt, nicht konstant wählt, sondern absteigend (14., 27., 39,...).
J.-u. G. schrieb: > 14 Ja, das dürfte die richtige Lösung zu sein. Oder allgemein:
War leider noch auf dem Nachhauseweg, als du die Lösung gepostet hast ;-) @D. I.: Klasse Rätsel! Wo nimmst du die Dinger immer nur her?
J.-u. G. schrieb: > D. I. schrieb: >> Ansonsten habe ich schon 19 gelesen, wer bietet weniger? :) > > 14 > > Wenn man die Abstände zwischen den Stockwerken, aus denen man die Murmel > zunächst fallen lässt, nicht konstant wählt, sondern absteigend (14., > 27., 39,...). Jup das ist korrekt. Yalu X. schrieb: > @D. I.: > > Klasse Rätsel! Wo nimmst du die Dinger immer nur her? Internet und Bücher :) Naja ums etwas zu präziser auszudrücken: Im wesentlichen Artikel, Literatur, Erfahrungsberichte, etc. die sich unter anderem damit beschäftigen was einem in großen US IT Unternehmen so in Vorstellungsgesprächen unter die Räder kommt. Und da ich viele davon selbst erst das erste Mal gehört habe und ich auch regelmäßiger Konsument dieses Forums bin, ist es oft so, dass die meisten von euch sie auch noch nicht kennen. Ich finds interessant auf was für unterschiedliche Ansätze die Leute kommen und in letzter Instanz dann immer deine mathematischen Begründungen. ;) Dir würd ich blindlings zutrauen, dass du ohne weiteres den technisch / algorithmischen Part solcher Interviews wuppen würdest. Das von gestern und heute waren aus der Reihe "15 BANNED Google Interview Questions That Will Make You Feel Stupid" Die Rätsel die ich vor geraumer Zeit mal gestellt habe kamen mir während des Studiums so entgegen. Z.B. das mit dem Hüteratespiel ;)
Würde es dir was aus machen, noch ein paar mehr Rätsel online zu stellen? Ich finde die sehr spannend!
Mike Mike schrieb: > Würde es dir was aus machen, noch ein paar mehr Rätsel online zu > stellen? Ich finde die sehr spannend! Ne macht mir nix aus ;) Ein paar Alte kannste auch noch finden wenn du Off-topic nach meinem Nick und irgendwas mit rätsel suchst oder so. Aber hier hab ich noch nen Low-Brainer als Absacker: Gegeben ist ein 8x8 Schachbrett bei dem 2 gegenüberliegende Ecken herausgeschnitten werden. Ist es möglich das Brett mit 31 Dominosteinen (2x1 Größe) zu bedecken, so dass alle Felder bedeckt sind? Wenn ja gib ne Konfiguration an, wenn nein warum nicht? @Yalu: Ich hätte da noch ein relatives heftiges Programmierproblem an dem ich selbst noch hadere, Interesse? (Die Knoblerehre gebietet es mir nicht in die Musterlösung zu schauen...) Edit: Falls es auch andere interessiert: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3914
Also ich denke jetzt mal, ich muss das nicht unbedingt mit einem 8x8 Feld machen, da ich theoretisch gesehen die Mitte mit einem rechteckigen Klotz füllen könnte. Könnte aber jetzt schon ein Denkfehler sein. Wenn ich das ganze mit einem 4x4 Feld versuche, bleibt bei jeder Möglichkeit immer ein "T" Stück übrig, also sage ich mal es geht nicht.
Mike Mike schrieb: > Wenn ich das ganze mit einem 4x4 Feld versuche, bleibt bei jeder > Möglichkeit immer ein "T" Stück übrig, also sage ich mal es geht nicht. Kannst dus auch stichhaltig begründen? Denn nur weil es für 4x4 nicht geht, induziert ja nicht zwingend, dass es nicht für 8x8 oder 1000x1000 gehen könnte.
Meine Überlegung ist: Egal wie ich eine Wand fülle (wegen der ungeraden Blockzahl), es beeinflusst die nebenliegenden Seiten so, dass es "nicht aufgeht", das heißt, es bleibt immer ein 1x1 Feld, das ja irgendwie auch abgedeckt werden will. Lege ich nun einen Block drauf, sorgt es wiederum dafür, dass ich irgendwann wieder bei einem 1x1 Block lande. Solange, bis eben zwei 1x1 Felder übrig bleiben, die sich Diagonal gegenüberliegen. Ich arbeite an etwas Stichhaltigem, lass mir noch bisschen zeit ;)
Ich habe es! Ein Dominostein wird auf das Schachbrett gelegt. Egal wie ich ihn lege, die eine Hälfte liegt auf einem schwarzem Feld und die andere auf einem weißen! Und genau da ist der Knackpunkt. Die Beiden Felder die an den Ecken entfernt werden, haben die gleiche Farbe. D.h. genau, das eben zwei gleichfarbige Felder übrigbleiben, und da kann ich keinen Dominostein drauflegen, da ein Dominostein auf zwei verschiedenfarbigen Feldern liegen muss.
Sehr gut, so ist es. :) "Der stolze Moment bei dem man selbstständig auf eine Lösung kommt" Wenn du jetzt noch 5 handelsübliche Würfel so aufeinander stapelst, dass die Summe der Augenzahlen auf allen 4 Säulenseiten gleich ist, dann kann mas für heute gut sein lassen :)
Eher der Moment in dem man sich auf die Stirn klatscht, weil es so trivial ist. Habe verschiedene Ansätze gehabt, mit verschiedenen Anordnungen der Steine und habe damit versucht zu beweisen, warum es nicht "aufgeht". Aber jetzt bin ich schlauer ;) edit Rätzel in Arbeit, moment
Wenn ich mich nicht verrechnet habe, geht das glaube ich nicht. Wir sehen uns eine Seite an. Die Obere Würfelzahl wäre a, die nächste b, bis zur letzten, e. Dann wäre die Summe a+b+c+d+e Jeweils gegenüberliegende Würfelzahlen haben den Wert 7-Augenzahl D.h. wir haben die Gleichung
1 | a+b+c+d+e = 7-a + 7-b + 7-b + 7-c + 7-d + 7-e |
2 | |
3 | a+b+c+d+e = -a + -b + -b + -c + -d + -e + 35 |
4 | |
5 | 2*(a+b+c+d+e) = 35 |
6 | |
7 | a+b+c+d+e = 17,5 |
Da Augenzahlen und damit auch die Summer der Augenzahlen nur ganze Zahlen sein können, geht es nicht!
Jawohl, genug für heute. Wenn mir wieder eins in die Finger kommt werde ich das Forum nochmal malträtieren. Ansonsten kannst du dich ebenfalls an der Programmieraufgabe versuchen.
Gerne, nur her damit;) Schickst mir ne PN wenn du magst.
D. I. schrieb: > Ansonsten kannst du dich ebenfalls an der Programmieraufgabe versuchen. hab grad versucht mich anzumelden, aber ich krieg keine mail von denen. Im Spamfilter isses auch nicht hängen geblieben. Habs auch mit 2 unterschiedlichen Mai-Accounts probiert. Wollte eigentlich nur versuchen rauszufinden, in welchen Sprachen man die Lösuingen Posten kann. An sich klingt das nich so wahnsinnig kompliziert. Aufhänger sind die Schwarzen Ecken. Ich würde durch das Feld gehen und schauen, wie viele korrekte Möglichkeiten es für jedes schwarze Feld gibt, das Teil zu plazieren. Die Felder mit 1 können direkt entfernt werden. Das ganze solange wiederholen (Wiederholung jeweils auf direkt beeinflusste Umgebung beschränken), bis keine mehr entfernt werden können. irgenwdwann wird man raten müssen. weiter also per Backtracking. Aktuelles Feld und Entscheidung auf einen Stack und rechnen. Im Fehlerfall letzte Entscheidung vom Stack herstellen und einen anderen Weg ausprobieren. Gibts da Speicherbeschränkungen? in simplester Implementierung schlägt ein Speicherstand mit 250.000B zu Buche. Ist schon recht viel. Optimieren ließe sich das auf 62.500 (2bit pro feld, 4 pro Byte) oder mit extrem ekligen Zugriffen 50.000 (5 Felder pro Byte). Für eine Speicherung und zum nicht drauf arbeiten ist es aber fast egal. Theoretisch könnte man hier noch weiter komprimieren, da die weißen Felder weniger Information tragen, als schwarz oder leer. Als Quickcheck könnte man schauen, - ob es genau doppelt so viele weiße wie schwarze gibt - ob an jedes weiße mindestens 1 schwarzes (4er nachbarschaft) angrenzt - ob an jedes schwarze mindestens 2 (4er nachbarschaft) weiße angrenzen - ob es nicht mehr als 2 aufeinanderfolgende schwarze gibt (hor und vert). Ich vermute das Feld sollte sich relativ schnell ausdünnen. bin aber zu faul, das jetzt zu implementieren. kannst du es ja mal den Rahmen (also das einparsen und grundlegendste Feld-Struktur) posten.
Vlad Tepesch schrieb: > hab grad versucht mich anzumelden, aber ich krieg keine mail von denen. > Im Spamfilter isses auch nicht hängen geblieben. Ach, du auch nicht? Dann liegt's also nicht daran, dass ich mich evtl. bei der E-Mail-Adresse vertippt habe. > Wollte eigentlich nur versuchen rauszufinden, in welchen Sprachen man > die Lösuingen Posten kann. Es scheinen die gleichen wie bei http://uva.onlinejudge.org zu sein. Dort sind wählbar:
1 | - ANSI C 4.5.3 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE |
2 | |
3 | - JAVA 1.6.0 - Java Sun JDK |
4 | |
5 | - C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE |
6 | |
7 | - PASCAL 2.4.0 - Free Pascal Compiler |
> Die Felder mit 1 können direkt entfernt werden. > irgenwdwann wird man raten müssen. weiter also per Backtracking. > Ich vermute das Feld sollte sich relativ schnell ausdünnen. Ich schätze, das hat D. I. auch schon probiert. Wenn aber bei den über 500²/3 möglichen schwarzen Feldern nur jedes 1000ste nicht direkt ent- fernt werden kann, müssen mehr als 10²⁴ Varianten durchprobiert werden.
Vlad Tepesch schrieb: > hab grad versucht mich anzumelden, aber ich krieg keine mail von denen. > Im Spamfilter isses auch nicht hängen geblieben. Habs auch mit 2 > unterschiedlichen Mai-Accounts probiert. Yalu X. schrieb: > Ach, du auch nicht? Dann liegt's also nicht daran, dass ich mich evtl. > bei der E-Mail-Adresse vertippt habe. Habe es gerade eben auch mal mit meiner gmail-Adresse versucht und sofort den Link per Mail erhalten. Vielleicht gabs in der Nacht ein Problem? Auf jeden Fall kann man resend machen, dann sollte sie kommen. Titel: "ACM-ICPC Live Archive - Your Registration is Pending Approval" und nach klicken vom Link Titel: "ACM-ICPC Live Archive - New User Details" Yalu X. schrieb: > Ich schätze, das hat D. I. auch schon probiert. Wenn aber bei den über > 500²/3 möglichen schwarzen Feldern nur jedes 1000ste nicht direkt ent- > fernt werden kann, müssen mehr als 10²⁴ Varianten durchprobiert werden. Bei 500x500 brauch ich den Ansatz nicht mal probieren um zu wissen, dass das nicht klappen wird :) Mein bisheriger Ansatz war bipartites Matching / maximaler Fluss, aber das gab Time-Limit was bei sovielen Knoten leider fast schon klar war >.< Yalu X. schrieb: > Es scheinen die gleichen wie bei http://uva.onlinejudge.org zu sein. > Dort sind wählbar: Das stimmt, ist dasselbe System, im Live Archive landen allerdings nur die Aufgaben der vergangenen ICPC Regionals und World Finals.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.