Hallo,
ich habe dieses Jahr am Bundewettbewerb Informatik teilgenommen. Eine der Aufgaben habe ich nicht geschafft komplett richtig zu lösen (trotz stundenlangem Suchen und Probieren) und würde jetzt wo der Wettbewerb bewertet ist (ich habe immerhin noch 3/5 Punkten bekommen) gerne wissen wo der Fehler liegt.
Daher würde ich mich freuen wenn sich ein profi mal mein Programm anschauen würde auch wenn es vielleicht ein paar Minuten dauert sich in die Aufgabe einzuarbeiten.
Die Aufgabe kurz zusammengefasst:
Ziel ist es, gültige Anmeldelisten zu einer Veranstaltung zu generieren (hier Tutorien). Jeder Tutor soll genau ein Tutorium leiten. Den Studenten sollen aber zur Anmeldung ein Termin mehr ausgegeben werden als wirklich stattfindet damit der Termin mit den geringsten Anmeldungen gestrichen werden kann
Das Problem liegt darin dass nicht jeder Tutor an jedem Termin zur Verfügung steht.
Eine Anmeldeliste ist also gültig wenn jeder der Termine gestrichen werden könne und trotzdem für die übrigen Termine je ein Tutor zur Verfügung stellt.
Das Programm soll nun aus t möglichen Terminen und n Tutoren eine gültige Anmeldeliste aus n+1 Terminen ausgeben.
Hier ein Link zu der kompletten Aufgabe
Zu meiner Lösung:
Mit einem ersten Backtracking werden alle Teilmengen (n+1) der möglichen Termine gebildet.
Ein zweites Backtracking prüft dann die gültigkeit der Anmeldeliste, indem immer ein Termin gestrichen wird und anschließend versucht wird jedem Termin einen Tutor zuzuordnen.
Hier der Quellcode:
Also grundsätzlich funktioniert es auch, wenn ich das korrekte Beispiel auf Gültigkeit überprüfe wird es richtig angezeigt, wenn ich die nicht gültige Anmeldeliste angebe wird sie auch korrekt als nicht gültig angezeigt.
Will ich aber zu dem Beispiel eine Anmeldeliste ausgeben, bekomme ich eine Fehlerhafte (Termin 1, 2, 5, 4, 6) ausgegeben. Gebe ich diese jedoch wiederum zur Überprüfung an, wird sie wieder korrekt als falsch ausgegeben.
Bei simplen Eingaben funktioniert die Ausgabe einer Anmeldeliste auch.
Vielen Dank schonmal wenn sich jemand die Zeit nimmt sich das anzuschauen
ich habe dieses Jahr am Bundewettbewerb Informatik teilgenommen. Eine der Aufgaben habe ich nicht geschafft komplett richtig zu lösen (trotz stundenlangem Suchen und Probieren) und würde jetzt wo der Wettbewerb bewertet ist (ich habe immerhin noch 3/5 Punkten bekommen) gerne wissen wo der Fehler liegt.
Daher würde ich mich freuen wenn sich ein profi mal mein Programm anschauen würde auch wenn es vielleicht ein paar Minuten dauert sich in die Aufgabe einzuarbeiten.
Die Aufgabe kurz zusammengefasst:
Ziel ist es, gültige Anmeldelisten zu einer Veranstaltung zu generieren (hier Tutorien). Jeder Tutor soll genau ein Tutorium leiten. Den Studenten sollen aber zur Anmeldung ein Termin mehr ausgegeben werden als wirklich stattfindet damit der Termin mit den geringsten Anmeldungen gestrichen werden kann
Das Problem liegt darin dass nicht jeder Tutor an jedem Termin zur Verfügung steht.
Eine Anmeldeliste ist also gültig wenn jeder der Termine gestrichen werden könne und trotzdem für die übrigen Termine je ein Tutor zur Verfügung stellt.
Das Programm soll nun aus t möglichen Terminen und n Tutoren eine gültige Anmeldeliste aus n+1 Terminen ausgeben.
Hier ein Link zu der kompletten Aufgabe
Zu meiner Lösung:
Mit einem ersten Backtracking werden alle Teilmengen (n+1) der möglichen Termine gebildet.
Ein zweites Backtracking prüft dann die gültigkeit der Anmeldeliste, indem immer ein Termin gestrichen wird und anschließend versucht wird jedem Termin einen Tutor zuzuordnen.
Hier der Quellcode:
Java:
import java.util.*;
class Tutoren
{
static void loesche(int[] verf, int index)
{
verf[index] = 0;
}
static void einfuegen(int[] verf, int merke)
{
verf[merke] = 1;
}
static void anmeldeliste(int[] verf, int n, int t, int[][] tutoren)
{
int j;
Integer zahl = null;
boolean gefunden, gefunden2;
int stelle = 1;
int merke = 0;
int[] reihe = new int[t+1];
int[] neueReihe = new int[t+1];
do {
j = merke;
gefunden = false;
do {
j++;
if (j>t) {
break;
} // end of if
if (verf[j] == 1) {
zahl = j;
gefunden = true;
} // end of if
} while (gefunden == false);
if (gefunden == true) {
reihe[stelle] = zahl;
merke = 0;
loesche(verf, j);
stelle++;
if (stelle > t) {
stelle = stelle-1;
merke = reihe[stelle];
einfuegen(verf, merke);
gefunden2 = true;
for (int i = 1; i<n+2; i++) {
neueReihe[reihe[i]] = 1;
if ((i > 1) && (reihe[i] < reihe[i-1])) {
gefunden2 = false;
break;
} // end of if
} // end of for
if (gefunden2) { //wenn eine Kombination gefunden wurde wird die Gültigkeit überprüft
if (gueltig(neueReihe, tutoren, n, t)) {
break;
} // end of if
} // end of if
} // end of if
} // end of if
else {
stelle = stelle - 1;
if (stelle > 0) {
merke = reihe[stelle];
einfuegen(verf, merke);
} // end of if
} // end of if-else
} while (stelle != 0 );
if (stelle == 0) {
System.out.println("Keine Anmeldeliste gefunden");
} // end of if
}
static boolean gueltig(int[] verf, int[][] tutoren, int n, int t)
{
int stelle;
int merke;
int[] reihe = new int[n+2];
//Die Verfügungsmenge wird zur Speicherung in ein weiteres Array übertragen
int[] verfm = new int[t+1];
for (int i = 1 ; i<t+1; i++) {
if (verf[i] == 1) {
verfm[i] = 1;
} // end of if
} // end of for
Integer zahl = null;
int j;
int k = 0;
boolean gefunden;
boolean geloescht;
Integer geloeschteZahl = null;
do {
geloescht = false;
//Die Verfügungsmenge wird wieder aufgefüllt
for (int i = 1; i<t+1; i++) {
if (verfm[i] == 1) {
verf[i] = 1;
} // end of if
} // end of for
//Ein Termin wird gelöscht, anschließend überprüft ob allen übrigen Terminen ein Tutor zugeordnet werden kann
do {
k++;
if (verf[k] == 1) {
loesche(verf, k);
geloeschteZahl = k;
geloescht = true;
} // end of if
} while (! geloescht && k<t );
stelle = 1;
merke = 0;
do {
j = merke;
gefunden = false;
do {
j++;
if (j>t) {
break;
} // end of if
if (verf[j] == 1) {
if (tutoren[stelle][j] == 1) {
zahl = j;
gefunden = true;
} // end of if
} // end of if
} while (gefunden == false);
if (gefunden == true) {
reihe[stelle] = zahl;
merke = 0;
loesche(verf, j);
stelle++;
if (stelle > n) {
break;
} // end of if
} // end of if
else {
stelle = stelle - 1;
if (stelle > 0) {
merke = reihe[stelle];
einfuegen(verf, merke);
} // end of if
} // end of if-else
} while (stelle != 0 );
if (stelle == 0) {
return false;
} // end of if
else {
einfuegen(verf, k);
} // end of if-else
} while (k<t);
reihe[n+1] = geloeschteZahl;
System.out.println();
for (int i = 1; i<n+2; i++) {
System.out.print("Termin "+reihe[i] + " ");
} // end of for
return true;
}
public static void main(String [] arg)
{
Scanner s = new Scanner(System.in);
System.out.println("Anzahl Tutoren");
int n = s.nextInt();
System.out.println("Anzahl möglicher Termine");
int t = s.nextInt();
System.out.println();
int verfuegbar;
int tutoren[][] = new int[n+1][t+1];
int termineverf[] = new int[t+1];
for (int i = 1; i<n+1; i++) {
for (int j = 1; j<t+1; j++) {
System.out.println("Tutor " + i + " verfügbar an Termin " + j + "? (1/0)");
verfuegbar = s.nextInt();
System.out.println();
if (verfuegbar == 1) {
tutoren[i][j] = 1;
} // end of if
else {
tutoren[i][j] = 0;
} // end of if-else
} // end of for
} // end of for
System.out.println("Anmeldeliste ausgeben (1) oder Anmeldeliste überprüfen (2)?");
int auswahl = s.nextInt();
switch (auswahl) {
case 1 :
for (int i = 1; i<t+1; i++) {
termineverf[i] = 1;
} // end of for
anmeldeliste(termineverf, n, t, tutoren);
break;
case 2 :
for (int i = 1; i<n+2; i++) {
System.out.println("Index von Termin " + i + " der Anmeldeliste eingeben");
termineverf[s.nextInt()] = 1;
System.out.println();
} // end of for
if (gueltig(termineverf, tutoren, n, t)) {
System.out.println("Gültige Anmeldeliste");
} // end of if
else {
System.out.println("Anmeldeliste ungültig");
} // end of if-else
break;
default:
} // end of switch
}
}Also grundsätzlich funktioniert es auch, wenn ich das korrekte Beispiel auf Gültigkeit überprüfe wird es richtig angezeigt, wenn ich die nicht gültige Anmeldeliste angebe wird sie auch korrekt als nicht gültig angezeigt.
Will ich aber zu dem Beispiel eine Anmeldeliste ausgeben, bekomme ich eine Fehlerhafte (Termin 1, 2, 5, 4, 6) ausgegeben. Gebe ich diese jedoch wiederum zur Überprüfung an, wird sie wieder korrekt als falsch ausgegeben.
Bei simplen Eingaben funktioniert die Ausgabe einer Anmeldeliste auch.
Vielen Dank schonmal wenn sich jemand die Zeit nimmt sich das anzuschauen
