Hallo!
Ich habe zwei Listen:
A 1
B 2
C 1
D 3
E 0
F 0
(natürlich deutlich länger)
(Anzahl gleich Summe aller Zahlen in der 1. Liste)
AB:
AD:
AC:
AF:
BD:
BC:
ED:
Jetzt muss hinter jede Zeile der zweiten Liste ein Buchstabe stehen. Dabei dürfen aber die in der ersten Liste genannten Limits nicht unterschritten werden.
1700 Einträge hat die erste Liste,
2700 die zweite.
Bei dem Beispiel möchte ich dann z.B. diese Ausgabe:
AB: B
AD: D
AC: C
AF: A
BD: D
BC: B
ED: D
Wenn das Limit 0 ist, muss der andere Buchstabe ausgewählt werden. Der zweite eindeutige Fall ist, wenn das Limit der Anzahl der offenen Listeneinträge, in dem der Buchstabe vorkommt, entspricht.
Die Datenstruktur habe ich wie folgt interpretiert:
$limits[X][0] Limit
$limits[X][1] Buchstabe
$limits[X][2] Anzahl der Vorkommnisse
$limits[X][3] Quotient Limit durch Anzahl
$verbindung[X][0] erster Buchstabe
$verbindung[X][1] zweiter Buchstabe
$verbindung[X][2] Lösung
In der ersten Liste wird angegeben, wie oft der jeweilige Buchstabe als Lösung in der zweiten Reihe existieren darf.
Die Aufgabenstellung ist:
Jeder Schüler hat ein individuelles Limit an Aufgaben, die er erledigen muss (limits.txt). Jede Zeile in der Datei aufgaben.txt stellt eine Aufgabe da, die entweder der eine, oder der andere Schüler bearbeiten muss. Finden Sie eine Lösung, bei der kein Schüler zu viele oder zu wenig Aufgaben bearbeiten muss. Geben Sie dazu für jede Zeile an, welcher Schüler die Aufgabe zugeteilt bekommen soll.
Also z.B.:
Tom 1
Peter 2
Lisa 0
Tom Peter : Peter
Lisa Peter : Peter
Tom Lisa : Tom
Zuerst kann man die eindeutigen Fälle bestimmen: Wenn das Limit 0 ist (bei jeder Festlegung wird aktuallisiert), muss der andere Name ausgewählt werden. Der zweite eindeutige Fall ist, wenn das Limit der Anzahl der offenen Listeneinträge, in dem der Name vorkommt, entspricht (z.B. Peter, 2 Einträge, Limit 2).
meine Datenstruktur:
$limits[X][0] Limit
$limits[X][1] Name des Schülers
$limits[X][2] Anzahl der Aufgaben
$limits[X][3] Quotient Limit durch Aufgabenanzahl
$verbindung[X][0] erster Name
$verbindung[X][1] zweiter Name
$verbindung[X][2] wird bearbeitet von...
Ziel ist es, das jeder sich an sein Limit hällt und nicht mehr oder weniger zu bearbeiten hat. Jede Namenskombination kommt nur ein mal vor.
Ich habe es nach dem Verfahren hierversucht
[autoit]Global $fertig = False
[/autoit][autoit][/autoit][autoit]Func loesungfinden($nr)
While $fertig == False
$erfolg = Suchen($nr, 0)
If $erfolg == -1 Then
$erfolg = Suchen($nr, 1)
EndIf
If $erfolg == 1 Then
If $fertig == True Then Return True
If loesungfinden($nr + 1) == True Then
Return True
Else
loeschen($nr)
If Suchen($nr, 1) == -1 Then
loeschen($nr)
Else
If loesungfinden($nr + 1) == True Then Return True
EndIf
EndIf
EndIf
loeschen($nr)
Return False
WEnd
EndFunc ;==>loesungfinden
loesungfinden(0)
Aber leider funktioniert das nicht, das endet in einer Dauerschleife:
.....
### 374:0 # 401
### 375:0 # 402
### 376:0 # 403
### 377:0 # 404
### 378:1 # 405
### 379:0 # 406
### 380:0 # 407
### 381:0 # 408
### 382:1 # 409
0 sind bei beiden übrig 383
0 sind bei beiden übrig 383
###bereits leer###
zurück: 382
### 382:1 # 410
0 sind bei beiden übrig 383
0 sind bei beiden übrig 383
###bereits leer###
zurück: 382
zurück: 381
### 381:1 # 411
### 382:0 # 412
0 sind bei beiden übrig 383
0 sind bei beiden übrig 383
###bereits leer###
zurück: 382
### 382:1 # 413
### 383:0 # 414
### 384:1 # 415
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:1 # 416
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
### 383:0 # 417
### 384:1 # 418
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:1 # 419
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
zurück: 382
zurück: 381
zurück: 380
### 380:1 # 420
### 381:0 # 421
### 382:0 # 422
0 sind bei beiden übrig 383
0 sind bei beiden übrig 383
###bereits leer###
zurück: 382
### 382:1 # 423
### 383:0 # 424
### 384:1 # 425
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:1 # 426
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
### 383:0 # 427
### 384:1 # 428
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:1 # 429
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
zurück: 382
zurück: 381
### 381:1 # 430
### 382:0 # 431
### 383:0 # 432
### 384:1 # 433
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:1 # 434
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
### 383:0 # 435
### 384:1 # 436
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:1 # 437
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
zurück: 382
### 382:1 # 438
### 383:0 # 439
### 384:0 # 440
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:0 # 441
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
### 383:0 # 442
### 384:0 # 443
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
### 384:0 # 444
0 sind bei beiden übrig 385
0 sind bei beiden übrig 385
###bereits leer###
zurück: 384
zurück: 383
zurück: 382
zurück: 381
zurück: 380
zurück: 379
### 379:1 # 445
### 380:0 # 446
### 381:0 # 447
### 382:1 # 448
0 sind bei beiden übrig 383
0 sind bei beiden übrig 383
###bereits leer###
zurück: 382
### 382:1 # 449
0 sind bei beiden übrig 383
0 sind bei beiden übrig 383
###bereits leer###
zurück: 382
zurück: 381
### 381:1 # 450
zurück: XXX = Eintrag wieder gelöscht
### XXX:Y # 449 = Eintrag XXX für Y. Schüler festgelegt
0 sind bei beiden übrig: Limit bei beiden Schülern mitlerweile auf 0
Alles anzeigen
Vorher werden alle eindeutigen Fälle bereits zugeordnet und gelöscht, diese kommen also im gesammten Array nicht mehr vor.
Die Funktion suchen(ID, Nr) überprüft erst, ob mitlerweile ein eindeutiger Fall (bei mehreren Fehler) vorliegt und teilt dann entsprechend zu (auch zum anderen, wenn nötig, also zum 1. anstatt 0. wie aufgerufen). Beinem uneindeutigem Fall wird nach dem übergebenen Parameter entschieden.
Die Funktion löschen(ID) löscht den Eintrag wieder.
Mir ist die Laufzeit relativ egal, hauptsache die Aufgabe ist gelöst, kann auch ruhig 2 Stunden dauern.
Ich bin jetzt schon seit Tagen am Rumprobieren, aber irgendwie bekomme ich es nicht hin.
Es wäre sehr nett, wenn mir da jemand helfen könnte!
Vielen Dank!