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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# getestet mit Python 2.7.8 und 3.4.2
'''Stellt zwei Strategien zur Lösung der Fähre-Füllen-Aufgabe'''
BEISPIEL = []
BEISPIEL.append(
"5,23; 4,41; 3,33; 13,13; 9,12; 4,38; 6,34; 5,37; 4,11; 3,74; 10,62")
BEISPIEL.append(
"4,14; 3,63; 3,92; 7,95; 5,23; 3,30; 4,86; 15,06")
BEISPIEL.append("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
for j in range(len(BEISPIEL)):
BEISPIEL[j] = [float(k.replace(",", ".")) for k in BEISPIEL[j].split("; ")]
# 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
def strategie_a(vabfolge):
'''Sortiert eine Abfolge von Fahrzeugen möglichst weit links ein'''
abfolge = vabfolge[:]
# `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 k in range(FAEHRENBREITE):
# dazu wird bei allen Parkreihen überprüft, ob das Fahrzeug passt
if fahrzeug + faehre["länge"][k] < \
FAEHRENLAENGE - ABSTAND * (faehre["anzahl"][k] - 1):
faehre["länge"][k] += fahrzeug
faehre["anzahl"][k] += 1
print(str(fahrzeug) + " wurde eingeordnet in die Reihe " + \
str(k))
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(vabfolge):
'''Sortiert eine Abfolge von Fahrzeugen möglichst gleichmäßig ein'''
abfolge = vabfolge[:]
faehre = {"anzahl": [0] * FAEHRENBREITE, "länge": [0] * FAEHRENBREITE}
spalte = 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):
diese_spalte = spalte + k
if diese_spalte >= FAEHRENBREITE:
diese_spalte -= FAEHRENBREITE
if fahrzeug + faehre["länge"][diese_spalte] < FAEHRENLAENGE \
- ABSTAND * (faehre["anzahl"][diese_spalte] - 1):
faehre["länge"][diese_spalte] += fahrzeug
faehre["anzahl"][diese_spalte] += 1
print(str(fahrzeug) + " wurde eingeordnet in Reihe " + \
str(diese_spalte))
success = True
break
if success == False:
print("Das Fahrzeug " + str(fahrzeug) + " hat nicht mehr gepasst")
break
spalte += 1
if spalte == FAEHRENBREITE:
spalte = 0
return faehre
if __name__ == "__main__":
print("\n=== Strategie A ===\n")
print(strategie_a(BEISPIEL[0][:]))
print("\n=== Strategie B ===\n")
print(strategie_b(BEISPIEL[0][:]))
|
