Foren » 39. Bundeswettbewerb Informatik

• Danniv Arnon

  

  • 5 Beiträge
   

  19. November 2020 15:20:11 CET

  Muss man bei der Wichtelaufgabe ein Programm entwickeln, was immer zu 100 % die beste Verteilung ermittelt? Dafür müsste der Computer ja alle Möglichkeiten durchgehen, was schwer umzusetzen ist, da für n Kinder in einer Datei !n Verteilungen existieren.

• Jonathan Busch

  

  • 66 Beiträge
   

  19. November 2020 15:34:06 CET

  Man muss nicht immer (bei vielen Problemen sogar niemals) alle Möglichkeiten durchgehen. Das kann man sich wie folgt überlegen:

  Person 1 wünscht sich Geschenke A, B und C (in der Reihenfolge)

  Person 2 wünscht sich Geschenke B, C und A

  Person 3 wünscht sich Geschenke C, A und B

  Wenn man nun als erste Möglichkeit versucht, allen Personen ihren ersten Wunsch zu erfüllen (was in 3 erfüllten ersten Wünschen resultiert), weiß man, dass man eine optimale Verteilung gefunden hat, da es nicht mehr als 3 erfüllte erste Wünsche geben kann (da es nicht mehr Personen gibt). Diese optimale Verteilung hat man also gefunden, ohne alle Möglichkeiten durchprobiert zu haben.

  Wenn man einen guten Algorithmus entwickeln will, ist das Ziel, sich solche Gedanken zu machen und zu beweisen, dass das Verfahren trotzdem korrekt ist.

• Danniv Arnon

  

  • 5 Beiträge
   

  19. November 2020 15:55:28 CET

  Hallo und erstmal danke für die Antwort.

  Aber wenn mehrere Spieler denselben Erst- und Zweitwunsch haben ist es halt sehr schwer zu entscheiden wer das eine Geschenk nun bekommen soll, da man nicht alle möglichen Ausgangsmöglichkeiten kennt.

• Jonathan Busch

  

  • 66 Beiträge
   

  19. November 2020 21:50:21 CET

  Es können trotzdem sehr viele Ausgangsmöglichkeiten ausgeschlossen werden. Das genaue (möglichst effiziente) Verfahren auszuarbeiten, macht letztlich die Schwierigkeit der Aufgabe aus.

• Wolfgang Pohl

  

  • 391 Beiträge
   

  20. November 2020 15:59:43 CET

  Genau - und damit sind auch genug hilfreiche Hinweise zur Aufgabe gegeben. ;-)