Hey Leute,
ich steh wieder einmal vor einem problem.
Hier erstmal die Aufgabe mit dem dazugehörigen Code:
Implementieren Sie zunächst die Methode greedyPark, die einen Parkplatz für ein Auto der gegebenen Länge finden und besetzen soll. Autofahrer sind ein ungeduldiges Volk, das Parkplätze nach dem Greedy-Algorithmus auswählt. Sie fahren die Straße von Anfang an entlang und parken in der ersten Parklu ̈cke, die groß genug für ihr Auto ist. Die Methode soll also die erste Lücke finden, die mindestens so groß wie das Auto ist. Anschließend sollen alle Felder, die vom Auto belegt werden, durch Aufruf der Methode setOccupied besetzt werden. Beispiel:
Vorher: XX.....XXX...XX
greedyPark(3)
Nachher: XXXXX..XXX...XX
Ich habe jetzt echt Probleme mit der Aufgabe anzufangen...könntet ihr mir da ein paar Denkanstöße geben ?
Also mir ist schon klar, dass ich die Autolänge mit den freien Plätzen vergleichen muss. Aber wie soll ich das so coden ?
ich steh wieder einmal vor einem problem.
Hier erstmal die Aufgabe mit dem dazugehörigen Code:
Implementieren Sie zunächst die Methode greedyPark, die einen Parkplatz für ein Auto der gegebenen Länge finden und besetzen soll. Autofahrer sind ein ungeduldiges Volk, das Parkplätze nach dem Greedy-Algorithmus auswählt. Sie fahren die Straße von Anfang an entlang und parken in der ersten Parklu ̈cke, die groß genug für ihr Auto ist. Die Methode soll also die erste Lücke finden, die mindestens so groß wie das Auto ist. Anschließend sollen alle Felder, die vom Auto belegt werden, durch Aufruf der Methode setOccupied besetzt werden. Beispiel:
Vorher: XX.....XXX...XX
greedyPark(3)
Nachher: XXXXX..XXX...XX
Java:
public class Parking
{
// represents the segments (parking spots) of the road
// true: the segment is free. false: it is occupied
private boolean isFree[];
// generates a road of the given length with random segments being occupied
public Parking(int roadLength)
{
isFree = new boolean[roadLength];
for (int i=1; i<roadLength; ++i)
isFree[i] = Math.random() < 0.7 ? isFree[i-1] : !isFree[i-1];
}
// sets the segment of the given index to "occupied"
public void setOccupied(int index)
{
if (isFree[index])
isFree[index] = false;
else
System.err.println("Position " + index + " was already occupied!");
}
// prints the occupied and free parking spots to the screen
public void printRoad()
{
for (int i=0; i<isFree.length; ++i)
System.out.print(isFree[i] ? "." : "X");
System.out.println();
}
// attempts to park a car of the given length
// chooses the first available space that is large enough
// sets the space to "occupied"
public void greedyPark(int carLength)
{
// TODO: implement greedy parking
}
// attempts to park a car of the given length
// among all available spaces, chooses the smallest one that fits
// sets the space to "occupied"
public void smartPark(int carLength)
{
// TODO: implement smart parking
}
public static void main(String[] args)
{
int roadLength = 100; // length of the road
int numCars = 10; // number of cars trying to park
int minLen = 2; // minimum length of a car
int maxLen = 6; // maximum length of a car
Parking park = new Parking(roadLength);
park.printRoad();
for (int i=0; i<numCars; ++i)
{
// determine random car length
int carLength = (int)(Math.random()*(maxLen-minLen + 1));
carLength += minLen;
System.out.println("Parking a car of length " + carLength);
// try to park it
park.greedyPark(carLength);
park.printRoad();
}
}
}
Ich habe jetzt echt Probleme mit der Aufgabe anzufangen...könntet ihr mir da ein paar Denkanstöße geben ?
Also mir ist schon klar, dass ich die Autolänge mit den freien Plätzen vergleichen muss. Aber wie soll ich das so coden ?