1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#!/usr/bin/env python3
# Beispiel hier einfügen
#Beispiel =
#"5,23; 4,41; 3,33; 13,13; 9,12; 4,38; 6,34; 5,37; 4,11; 3,74; 10,62"
#"4,14; 3,63; 3,92; 7,95; 5,23; 3,30; 4,86; 15,06"
#"6,96; 5,06; 3,77; 3,95; 3,91; 3,54; 4,26; 4,03; 5,43; 4,04; 4,43; 4,12; 2,78"
# das Beispiel wird geparst
#Beispiel = [float(j.replace(",", ".")) for j in Beispiel.split("; ")]
Beispiel = [6] * 9 + [1] * 6
# vorgegebene Konstanten in Meter umgerechnet
Faehrenlaenge = 20
Faehrenbreite = 3
Abstand = 0.3
# `abfolge`: Eine Liste mit Längen von Autos
# gibt ein dict zurück, welches "anzahl" und "länge" aller Autos enthält
# im Verlauf der Funktion wird `abfolge` um die verladenen Fahrzeuge geleert
def strategie_a(abfolge):
# `faehre` hält die Anzahl an Fahrzeugen und deren Gesamtlänge in einem dict
faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite}
while len(abfolge):
success = False
# Fahrzeuge werden aus der Schlange gepopt
fahrzeug = abfolge.pop()
# jetzt wird das Fahrzeug möglichst weit links eingeordnet
for j in range(Faehrenbreite):
# dazu wird bei allen Parkreihen überprüft, ob das Fahrzeug passt
if fahrzeug + faehre["länge"][j] < Faehrenlaenge - Abstand * (faehre["anzahl"][j] - 1):
faehre["länge"][j] += fahrzeug
faehre["anzahl"][j] += 1
print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + str(j))
success = True
break
if success == False:
print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
# ...und abfahren
break
# Wichtig: in `faehre["länge"][x]` ist der Abstand nicht einberechnet
return faehre
# siehe `strategie_a`
def strategie_b(abfolge):
faehre = {"anzahl": [0] * Faehrenbreite, "länge": [0] * Faehrenbreite}
j = 0
while len(abfolge):
success = False
fahrzeug = abfolge.pop()
# Fahrzeuge werden möglichst gleichmäßig von links nach rechts verteilt
for k in range(Faehrenbreite):
l = j + k
if l >= Faehrenbreite:
l -= Faehrenbreite
if fahrzeug + faehre["länge"][l] < Faehrenlaenge - Abstand * (faehre["anzahl"][l] - 1):
faehre["länge"][l] += fahrzeug
faehre["anzahl"][l] += 1
print(str(fahrzeug) + " wurde eingeordnet in Reihe " + str(l))
success = True
break
if success == False:
print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
break
j += 1
if j == Faehrenbreite:
j = 0
return faehre
print("\n=== Strategie A ===\n")
print(strategie_a(Beispiel[:]))
print("\n=== Strategie B ===\n")
print(strategie_b(Beispiel[:]))
|
