Foren » 34. BwInf

• nicht mehr angemeldetes Mitglied

  
   

  2. September 2015 20:50:58 CEST

  Hi,
  
  Ich habe eine kurze Frage zu "Kassiopeias Weg": Ist der Startpunkt, wo es gerade am günstigsten ist, frei wählbar oder soll das Programm für ein gegebenes Feld und einen gegebenen Startpunkt den Weg finden?
  
  Im Beispiel gibt es mit dem Startpunkt (4|3) ja eine Lösung, mit (5|4) zum Beispiel aber nicht.
  
  Viele Grüße,
  Felix
• Thomas Leineweber

  

  • 230 Beiträge
   

  2. September 2015 22:30:58 CEST

  Ich würde das als geklärt sehen, wenn die Beispieleingaben auf der Webseite vorhanden sind. Dann kannst Du ja sehen, ob eine Startposition mit enthalten ist oder nicht.
• nicht mehr angemeldetes Mitglied

  
   

  2. September 2015 23:10:56 CEST

  [blockquote]Thomas Leineweber said:
  Ich würde das als geklärt sehen, wenn die Beispieleingaben auf der Webseite vorhanden sind. Dann kannst Du ja sehen, ob eine Startposition mit enthalten ist oder nicht.[/blockquote]
  
  Das stimmt. Was ist es denn voraussichtlich soweit? Wenn man noch in den nächsten Tagen damit rechnen könnte, würde ich nämlich bis dahin noch warten, bis ich die Aufgabe anfange.
• Wolfgang Pohl

  

  • 391 Beiträge
   

  3. September 2015 15:57:49 CEST

  Die Materialseite zur 1. Runde des 34. BwInf steht jetzt bereit und damit auch die Beispieleingaben für "Kassiopeia" und "Kassiopeias Weg".
  Dieser Beitrag wurde am 3. September 2015 15:58:34 CEST von Wolfgang Pohl bearbeitet
• nicht mehr angemeldetes Mitglied

  
   

  3. September 2015 21:21:05 CEST

  Ah, danke. Der Startpunkt ist also gegeben.
• Wolfgang Pohl

  

  • 391 Beiträge
   

  3. September 2015 22:24:50 CEST

  Genau. In Aufgabe 1 war das ja auch im Text angedeutet. "… von ihrem Startpunkt aus", also nicht "… von einem beliebigen Startpunkt aus".
• nicht mehr angemeldetes Mitglied

  
   

  9. September 2015 19:45:41 CEST

  Verlangt der Operator "Löse [Junoiraufgabe 1]" eine separate Implementierung der Lösung?
  Dieser Beitrag wurde am 9. September 2015 19:45:54 CEST von nicht mehr angemeldetes Mitglied bearbeitet
• Fritz Windisch

  

  • 58 Beiträge
   

  9. September 2015 21:07:32 CEST

  Die Grundidee des "lösen"s schlägt sich weiter unten in der Aufgabenstellung nieder, wo es heißt, man soll sein bisheriges Programm erweitern. Es wäre also sinnvoll, die JA2 zuerst zu lösen, da man sowieso zur Berechnung des Wegs in A1 herausfinden muss, ob überhaupt alle Blätter erreichbar sind.
  
  MfG. Fritz
  Dieser Beitrag wurde am 9. September 2015 21:13:27 CEST von Fritz Windisch bearbeitet
• Simon Pohmann

  

  • 3 Beiträge
   

  16. Oktober 2015 17:46:25 CEST

  Mein Programm muss zur Berechnung des Weges in A1 nicht herausfinden, ob alle Blätter erreichbar sind. Muss ich trotzdem einen entsprechenden Algorithmus zum Lösen von Junioraufgabe 1 schreiben?
• Wolfgang Pohl

  

  • 391 Beiträge
   

  17. Oktober 2015 10:15:31 CEST

  [blockquote]Simon Pohmann said:
  Mein Programm muss zur Berechnung des Weges in A1 nicht herausfinden, ob alle Blätter erreichbar sind. Muss ich trotzdem einen entsprechenden Algorithmus zum Lösen von Junioraufgabe 1 schreiben?[/blockquote]
  
  Im Prinzip ja, aber Junioraufgabe 2. Die erste Teilaufgabe von Aufgabe 1 lautet: "Löse zunächst die Junioraufgabe 2."
  
  In der zweiten Teilaufgabe heißt es: "Erweitere dein Programm". Auch wenn die Algorithmen nicht aufeinander aufbauen, können möglicherweise andere Elemente der Lösung und Implementierung der ersten Teilaufgabe in der zweiten weiter verwendet werden.
  
• Henrik Schlüter

  

  • 2 Beiträge
   

  17. Oktober 2015 19:34:11 CEST

  Ich nehme an, man muss jeden möglichen Weg von Kassiopeia untersuchen. Dann gibt es beim ersten Schritt typischerweise 4, bei jedem weiteren Schritt 3 Möglichkeiten. Bei einem Weg von 20 Schritten sind das 4,6 Milliarden Möglichkeiten. Braucht der Computer 1 ms pro Weg, sind das 54 Tage Rechenzeit. Oder habe ich einen Denkfehler?
• Felix Roth

  

  • 38 Beiträge
   

  18. Oktober 2015 15:18:51 CEST

  Das wäre ein Brute Force Ansatz. Solche Lösungen sind beim BWInf-Team erfahrungsgemäß nicht sehr beliebt (insbesondere wenn die Laufzeit für die vorgegebenen Beispiele unzumutbar ist), du solltest überlegen/suchen, ob du noch eine bessere findest... Brute Force gibt bestimmt keine volle Punktzahl.
• Tim Weiland

  

  • 17 Beiträge
   

  18. Oktober 2015 19:30:06 CEST

  Ich will euch ja nur ungern den Spaß verderben, aber das ist meiner Meinung nach schon eine Lösungsdiskussion und demnach unfair für die Teilnehmer, die hier nicht vorbeischauen.
• Wolfgang Pohl

  

  • 391 Beiträge
   

  19. Oktober 2015 13:50:23 CEST

  [blockquote]Tim Weiland said:
  Ich will euch ja nur ungern den Spaß verderben, aber das ist meiner Meinung nach schon eine Lösungsdiskussion und demnach unfair für die Teilnehmer, die hier nicht vorbeischauen.[/blockquote]
  
  Sehe ich ähnlich. Derart konkrete Zahlen, wie Henrik sie angegeben hat, gehören nicht hierher. Wobei Angaben, die auf Brute Force hindeuten, wohl am wenigsten problematisch sind, weil einfach nicht hilfreich. ;-)
  
  Felix' Hinweis ist aber recht genereller Natur und von daher passend; so ähnlich würde ich auf eine Anfrage per Mail auch antworten.