Programmierwettbewerb Übung

Diskutiere Programmierwettbewerb Übung im Java Basics - Anfänger-Themen Bereich.
T

ToastBrot123

Guten Abend ihr lieben,
meine Schule will so einen Programmierwettbewerb simulieren. Eigentlich habe ich ja paar Grundkenntnisse in Java, aber die folgende Aufgabe sagt mir einfach gar nichts. Es geht um eine Kopfgeldjägerin, die mitHilfe von Druiden Planeten besuchen muss. Das Programm soll nun die Mindestanzahl an notwendigen Druiden bestimmen. Dafür wird eine Textdatei eingelesen mit folgenden Spezifizierung : Die Textdatei beginnt mit einer ganzen Zahl 1 < N < 1000, welche die Anzahl der Planeten festlegt. Die Planeten P werden von 0 bis N -1 durchnummeriert. Die folgenden N Zeilen geben die Hyperraumrouten an. Die i-te dieser Zeilen enthält zuerst die Anzahl der Verbindungen K mit 0<= K <= N-1 vom Planeten i , gefolgt von ganzen Zahlen, welche die Zielplaneten angeben.
Bedingungen : Jeder Planet verfügt über eine Reihe von Portalen. Jedes Portal ist mit einem Portal auf einem anderen Planet verbunden und es darf nur in eine Richtung hin passiert werden ( also ein Portal ist der Eintrittspunkt und der Andere ist der Austrittspunkt). Außerdem muss dieses Netz zyklenfrei sein.

Wäre ich nicht so verzweifelt, hätte ich mir nicht extra einen Account für dieses Forum machen, aber ich hab wirklich gar nichts. Das einzige was mir bei der Aufgabe in den Kopf geht ist, dass das allen sehr Graphen ähnelt ? Aber ich hab echt sonst keinen Ansatz. Wäre absolut dankbar, wenn jemand mir einen Ansatz geben könnte oder mit mir diese Aufgabe durchgeht. Ich weiß nicht, wie starten soll und was wie modelliert werden soll
 
T

ToastBrot123

Wenn es ein Wettbewerb ist, helfe ich sicher nicht schummeln
Du hast das falsch verstanden. Die gestellte Aufgabe ist eine Übungsaufgabe für den Wettbewerb. Logischerweise findet der Wettbewerb unter Aufsicht statt, sonst wäre es naja unnötig xD Schlimmer als solche Aufgaben kann es nicht werden, deswegen haben wir die als Übung mitbekommen
 
L

lennero

Interessante Aufgabe. Kannst du mal einen Ausschnitt von der Inputdatei posten? Wie sieht so ein Input genau aus?

Poste auch mal den genauen Wortlaut der Aufgabe. Was genau ist gesucht und was ist mit "Mindestanzahl der Druiden" gemeint?
 
Zuletzt bearbeitet:
T

ToastBrot123

Interessante Aufgabe. Kannst du mal einen Ausschnitt von der Inputdatei posten? Wie sieht so ein Input genau aus?
Ahja hätte ich am Anfang schon tun sollen. Im Anhang hab ich ein Bild, welches ein "Tipp sein soll". Glaube das hilft zwar echt fürs Verständnis, aber die Umsetzung ist wieder was komplett anderes. Hoffe du kannst mir helfen.
Wie oben geschrieben sieht der Input so aus : "Dafür wird eine Textdatei eingelesen mit folgenden Spezifizierung : Die Textdatei beginnt mit einer ganzen Zahl 1 < N < 1000, welche die Anzahl der Planeten festlegt. Die Planeten P werden von 0 bis N -1 durchnummeriert. Die folgenden N Zeilen geben die Hyperraumrouten an. Die i-te dieser Zeilen enthält zuerst die Anzahl der Verbindungen K mit 0<= K <= N-1 vom Planeten i , gefolgt von ganzen Zahlen, welche die Zielplaneten angeben. "
IMG_1331.jpgIMG_1331.jpg
 
T

ToastBrot123

Was ich noch vergesse hatte zu erwähnen :
Die Druiden müssen von verschiedenen Planeten gleichzeitig starten , kann jedoch von einem Planeten seiner Wahl starten. Aber die Bedingungen von oben müssen eingehalten bleiben.
 
L

lennero

Was ich noch vergesse hatte zu erwähnen :
Die Druiden müssen von verschiedenen Planeten gleichzeitig starten , kann jedoch von einem Planeten seiner Wahl starten. Aber die Bedingungen von oben müssen eingehalten bleiben.
Ohne genauen Wortlaut der Aufgabe sagt mir das nichts. Klingt aber stark nach klassischer Graphtraversierung. Die Inputdatei liefert dir genug Informationen um einen gerichteten Graphen aufzubauen. Das mit den Druiden verstehe ich allerdings nicht.
 
T

ToastBrot123

Ohne genauen Wortlaut der Aufgabe sagt mir das nichts. Klingt aber stark nach klassischer Graphtraversierung. Die Inputdatei liefert dir genug Informationen um einen gerichteten Graphen aufzubauen. Das mit den Druiden verstehe ich allerdings nicht.
Man soll die Mindestanzahl an Druiden angeben, die man braucht, um alle Planeten zu besuchen. Also die Mindestanzahl wird gesucht und anhand vom Bild sieht man ja beim 1. Versuch braucht man mindestens 2 ( einer der von Planet 0 startet und einer der von Planet 3 startet). Damit sind dann alle Planeten besuchbar, da es nur in eine Richtung geht

Bei der 2. sieht man man braucht mindestens 2 für das Kreuz und eben einen für den isolierten. Rückwärts geht ja nicht, wie man den Pfeilen sieht

Aber wie man das umsetzen soll oder kann, weiß ich nicht. Genauso wenig weiß ich der Graph gebaut wird oder wie man den implementiert. Deswegen brauch ich ja Hilfe :(
 
A

AndiE

Man kann das erst mal analysieren:
In der ersten Zeile stehtdie Größe eines Arrays n x n, im ersten Fall n=4
In der nächsten Zeile steht, dass die erste Zeile(für Knoten 0) 0,1,0,0 ist ( nur eine 1 bei Spalte 1)
Dann folgte Zeile Zwei( Für Knoten 1) zu 0,0,1,0
Dann Zeile drei( Für Knoten 2) zu 0,0,0,0
und Zeile vier( Für Knoten 3) zu 0,1,0,0

Für Aufgabe 2 wäre das_

0,0,0,0,0,0
0,0,1,0,0,0
0,0,0,0,1,1
0,0,1,0,0,0
0,0,0,0,0,0
0,0,0,0,0,0

Soweit um 1. Schritt
 
MoxxiManagarm

MoxxiManagarm

Letztlich ist die Mindestanzahl von Druiden doch gleich der Anzahl von Planeten, die nicht Ziel einer Route sind. Also hast du eine Liste von Planeten, eine Liste von Zielplaneten -> die Größe der Differenzliste ist dein Output. Dafür brauch man weder Graphentheorie, noch Objekte. Letztlich ist es nur ein einfaches Zählen beim Einlesen.
 
L

LimDul

Letztlich ist die Mindestanzahl von Druiden doch gleich der Anzahl von Planeten, die nicht Ziel einer Route sind. Also hast du eine Liste von Planeten, eine Liste von Zielplaneten -> die Größe der Differenzliste ist dein Output. Dafür brauch man weder Graphentheorie, noch Objekte. Letztlich ist es nur ein einfaches Zählen beim Einlesen.
Dem wage ich zu widersprechen - das gilt nur, wenn die Routen kreisfrei sind. Wenn ich 3 Planeten (A,B,C) habe und Routen: A->B, B->C, C->A brauche ich trotzdem dafür einen Druiden.
 
T

thecain

Ich vermute du musst die minimal Anzahl an Spanning Trees finden für den Graph
 
MoxxiManagarm

MoxxiManagarm

das gilt nur, wenn die Routen kreisfrei sind.
Bedingungen : Jeder Planet verfügt über eine Reihe von Portalen. Jedes Portal ist mit einem Portal auf einem anderen Planet verbunden und es darf nur in eine Richtung hin passiert werden ( also ein Portal ist der Eintrittspunkt und der Andere ist der Austrittspunkt). Außerdem muss dieses Netz zyklenfrei sein.
Siehe #1, zumindest verstehe ich das so, dass die Bedingung gegeben ist. Was anderes wäre, wenn er diese Bedingung noch sicherstellen muss.

Edit:
Ich bleibe dabei, es ist ein int-Array der Größe n (1. Zeile). Danach wird zeilenweise weiter eingelesen und der Wert an gefundenen Indexen inkrementiert. Wenn du das getan hast wertest du nur noch das int-Array aus. Die Anzahl der benötigten Druiden ist die Anzahl der noch verbliebenen Nullen im Array.
 
Zuletzt bearbeitet:
L

LimDul

Siehe #1, zumindest verstehe ich das so, dass die Bedingung gegeben ist. Was anderes wäre, wenn er diese Bedingung noch sicherstellen muss.

Edit:
Ich bleibe dabei, es ist ein int-Array der Größe n (1. Zeile). Danach wird zeilenweise weiter eingelesen und der Wert an gefundenen Indexen inkrementiert. Wenn du das getan hast wertest du nur noch das int-Array aus. Die Anzahl der benötigten Druiden ist die Anzahl der noch verbliebenen Nullen im Array.
Tja, wenn man die Aufgabenstellung nicht genau liest :) Damit hast du natürlich Recht und ich viel zu kompliziert gedacht.
 
MoxxiManagarm

MoxxiManagarm

Tja, wenn man die Aufgabenstellung nicht genau liest :) Damit hast du natürlich Recht und ich viel zu kompliziert gedacht.
Kein Ding, sowas überliest man ja schnell. Wenn er die Bedingung noch überprüfen müsste, dann müsste er auch zu Graphentheorie übergehen. Man bedenke aber auch, es geht um einen schulischen Wettbewerb. Ich glaube nicht, dass dort bereits Graphentheorie im Mittelpunkt stehen soll. Ich denke sie wollen Schüler einfach für Informatik begeistern. Und das ist ein wunderbares Beispiel für eine Aufgabe, welche erstmal komplex erscheint, sich aber dann erstaunlich leicht lösen lässt. Man muss noch die Abstraktion dieser Sachaufgabe gut hinbekommen, was in meinen Augen der Kernpunkt der Aufgabe ist im Sinne des Wettbewerbs.
 
mrBrown

mrBrown

Letztlich ist die Mindestanzahl von Druiden doch gleich der Anzahl von Planeten, die nicht Ziel einer Route sind. Also hast du eine Liste von Planeten, eine Liste von Zielplaneten -> die Größe der Differenzliste ist dein Output. Dafür brauch man weder Graphentheorie, noch Objekte. Letztlich ist es nur ein einfaches Zählen beim Einlesen.
Mal als Beispiel:
Code:
0 -> 1
|
v
2
Nach deiner Rechnung bräuchte man dann einen?
 
H

httpdigest

Vielleicht noch ein weiteres Beispiel:
Code:
0 -.       .--> 3
    `-> 2 -+--> 4
1 --´      `.-> 5
             `> 6
 
T

ToastBrot123

Vielleicht geht es auch mit Arrays, aber ich hab heute den Tipp bekommen mir Graphen anzuschauen und zu überlegen wie man das implementiert und für die Aufgabe nutzt /: deswegen keine Ahnung ob der Array ansatz es auch tut
 
mihe7

mihe7

Das ist ein Implementierungsdetail. Wichtig ist, dass Du überhaupt erst einmal einen Lösungsansatz hast.
 
Thema: 

Programmierwettbewerb Übung

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben