mikrocontroller.net

Forum: PC-Programmierung Hilfe bei dieser Aufgabe


Autor: Marvin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Muss man bei dem Wettbewerb nicht so eine Bestätigung unterschreiben,
dass man die Aufgaben selbstständig gelöst hat? ;-)

Autor: Jan (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Marvin: Ich würde es auch so machen.

Mfg Jan

Autor: Marvin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mh, damit kann ich natürlich viel anfangen...

Marvin

Autor: daniel (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: HT (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: thomas (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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?

Autor: Marvin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Moi (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hab davon kein Plan, aber ist die Basis nicht eine einfache Modulo 
Operation, ähnlich wie sie bei einer CRC Berechnung verwendet wird?!

Autor: Denker (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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... >:->

Autor: Frank L. (hermastersvoice)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: tztztz (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;).

Autor: HT (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...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.

Autor: a! (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.