Hallo, ich möchte am Bundeswettbewerb Informatik teilnehemen. Die meisten Aufgaben sind ja sehr leicht und lassen sich schnell lösen. Die einzige Aufgabe, die ich noch nicht gelöst habe ist Aufgabe 4. Ich glaube das ist mit Abstand die schwierigste Aufgabe. Mein Ansatz ist einfach alle verschiedene Möglichkeiten, die der Mann da gehen kann durchzugehen. Das würde sich dann Brute Force nennen. Aber das kann es ja wohl nicht sein, dass dauert wahrscheinlich auch viel zu lange, wenn es mal 100 Teekücken geben würde... Marvin Hier die Aufgabe: Aufgabe 4: Kreisrund Hugo Langbein ist stolzer Vater zweier M¨adchen, die den Betriebskindergarten seiner Firma besuchen. F¨ur den Tagesausflug des Kindergartens hat er sich bereit erkl¨art, bei den Kollegen die Elternbeitr¨age einzusammeln. Aber, oh weh, er hat es vergessen! Jetzt ist nur noch wenig Zeit. Man sollte meinen, Hugo k¨onnte nun schnell bei seinen Kollegen vorbeischauen und das Vers¨aumte nachholen. Doch das ist nicht so einfach: Hugo arbeitet bei der Kreisrund AG, deren Mitarbeiter extrem arbeitsw¨utig sind. Sie wollen auf keinen Fall w¨ahrend der Arbeitszeit gest¨ort werden. Zum Gl¨uck f ¨ur Hugo sind seine Kollegen aber auch sehr durstig: Jeder Mitarbeiter hat eine pers¨onliche Teezahl, die seinen Teezyklus beschreibt: Jemand mit Teezahl t trinkt alle t Minuten in einer Teek¨uche einen Tee und beginnt damit genau t Minuten nach dem Arbeitsbeginn. Der Arbeitsbeginn ist f ¨ur alle gleich. Die Kreisrund AG befindet sich im obersten Stockwerk eines ringf¨ormigen Geb¨audes. Die Teek¨uchen liegen in gleichen Abst¨anden auf dem Flur und sind nummeriert. Die erste und letzte Teek¨uche sind benachbart. Um Tee zu trinken, geht ein Mitarbeiter immer zur selben Teek¨uche. Hugo erinnert sich an die Elternbeitr¨age genau zum Arbeitsbeginn und ist gerade in Teek¨uche 1. Wenn er sofort mit dem Einsammeln beginnt, k¨onnte er es vielleicht noch schaffen. Damit er einen Kollegen in dessen Teek¨uche trifft, muss Hugo gleichzeitig mit ihm ankommen, oder dort schon auf ihn warten. Hugo braucht 20 Sekunden von einer Teek¨uche zu einer benachbarten. Das Bezahlen geht sehr schnell, so dass man sagen kann, es kostet Hugo keine Zeit.
Muss man bei dem Wettbewerb nicht so eine Bestätigung unterschreiben, dass man die Aufgaben selbstständig gelöst hat? ;-)
in jedem Forum eine Aufgabe lösen lassen und schon hat man gewonnen :) mit so einer Einstellung ist man zum BWL Studium predestiniert >Hugo Langbein ist stolzer Vater zweier M¨adchen, die den >Betriebskindergarten seiner Firma >besuchen. .. einfach von deren Lohn das Geld abziehen :-^^ es steht auch nirgends wieviel Kinder ein Mitarbeiter hat.
Hallo Marvin, brute force bedeutet, alle denkbaren Möglichkeiten durchzurechnen. Die damit verbundene Komplexität kann schnell zu hoch werden. Denke darüber nach, welche Möglichkeiten einer Vereinfachung es gibt. Außerdem kann es sinnvoll sein, aus einem komplexen Prblem mehrere kleine zu machen - Stichwort Rekursion. Gruß HT
>Hugo erinnert sich an die Elternbeiträge genau zum Arbeitsbeginn und >ist gerade in Teeküche das würde ja bedeuten, Hugo hat die Teezahl 0 und würde den ganzen Tag die Teeküche nicht verlassen. Wieso wurde er noch nicht gefeuert???? ok, spass beiseite. Soll t eine Ganzzahl sein? Was soll das Ziel dieser Aufgabe sein? Sollst du eine Ablauf erstellen, der das bestmögliche Vorgehen beschreibt?
Danke für die doch kommenden Antworten. Ziel der Aufgabe soll sein, herauszufinden ob oder ob nicht Herr Langbein es in einer bestimmten Zeitspanne noch schaffen kann. Wenn es möglich ist, soll der Weg angegeben werden. Marvin
Hab davon kein Plan, aber ist die Basis nicht eine einfache Modulo Operation, ähnlich wie sie bei einer CRC Berechnung verwendet wird?!
>Ziel der Aufgabe soll sein, herauszufinden ob oder ob nicht Herr >Langbein es in einer bestimmten Zeitspanne noch schaffen kann. Ja er kann es in einer BESTIMMTEN Zeitspanne noch schaffen... >:->
Mir stellt sich eine ganz andere Frage. Warum will man an einem Wettbewerb teilnehmen wenn Einem dazu die Grundlagen fehlen? Wäre es da nicht sinnvoller an einem Preisauschreiben in der Bildzeitung teilzunehmen? Die Eingangsvoraussetzungen dafür dürfen marvinkompatibler sein...
Erste Frage: welche Angaben fehlen in der Aufgabenstellung: Die Gesamtzahl der Kollegen ist nicht erwähnt. Ob die Teezahlen lückenlos und z.B. bei 1 oder 2 beginnend vorhanden sind - damit ergäbe sich mit einer (auch nicht vorgegebenen) maximalen Tagesarbeitszeit wenigstens eine Obergrenze. "Persönliche" Teezahl würde ich interpretieren als nur je einmal vorhanden, auch das ist nicht sicher. Die Anzahl der Teeküchen fehlt.
In dem obigen Zitat fehlt einfach der letzte Absatz, damit wird die Aufgabenstellung klarer http://www.bwinf.de/uploads/media/bwinf271-aufgabenblatt.pdf "Hilf Hugo und schreibe ein Programm, das Hugo sagt, ob und, falls ja, wie er es innerhalb der ihm verbleibenden Zeit noch schaffen kann, das Geld einzusammeln. Als Eingabe erhält dein Programm Hugos Zeitlimit in Sekunden, die Anzahl der Teeküchen und eine Liste der Elternkollegen mit ihren Teezahlen und Teeküchennummern. Beispiele für Eingabedaten findest du unter http://www.bwinf.de/aufgaben/material . Teste dein Programm mit diesen und eigenen Daten und dokumentiere die Ergebnisse." http://www.bwinf.de/index.php?id=457
Das heißt, mit Erhalt der Liste ist die Belegung aller Teeküchen für den ganzen Tag vollständig vorgegeben. "Leerminuten" sind möglichst zu vermeiden. Sprünge zu weiter entfernten Teeküchen kosten Zeit, Hugo sollte nur die nächsten drei benachbarten links und rechts besuchen, die kann er in einer Minute erreichen. Ob es dazu eine geschlossene Lösung gibt? Ich vermute, man muß wie ein Schachprogramm alle möglichen Züge durchprobieren und nach "Zugstärke" bewerten, eventuell nur erfolgversprechendere Züge weiterverfolgen.
Wie es scheint ist es nicht die erste Aufgabe, bei der "Marvin" Hilfe braucht. Aufgabe 3 mit den Gebirkszügen, wurde hier auch schon erfragt. Vielleicht können "wir" ja als Forum direkt dran teilnehmen das nächste mal ;).
...ich habe es mal ausprobiert. Es lässt sich ein Algorithmus finden wenn man überlegt, welche Besuche überhaupt stattfinden und die dann in eine sinnvolle Reihenfolge bringt. Für die Umsetzung habe ich 100 Codezeilen benötigt. Die Lösung werde ich natürlich nicht online stellen, aber ich denke, ein Hinweis ist ok.
@HT: 100 Zeilen? Für eine optimale Lösung? Ich brauche wesentlich mehr und weiss dazu nicht mal sicher, ob die Lösung in jedem Falle optimal ist.. Im ersten "Durchlauf" ist sie das sicher, aber sobald der "Offset" durch die Intervallverschiebung hinzu kommt, bin ich mir nicht mehr so ganz sicher.. Wäre an einem Lösungsaustausch interessiert, wie kann ich dich erreichen? LG
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.