Aufgabe 2: Partyvorbereitungen
Vorüberlegungen
Katrin Käfer soll versuchen, die Aufgaben der Reihe nach zu verteilen. Dabei beauftragt sie jeden Helfer mit soviel Aufgaben, wie er schafft.
Etwas formaler gestaltet sich ihre Vorgehensweise für den 1.Helfer wie folgt:
Mit dem 2.Helfer soll nun genauso verfahren werden, allerdings soll er nicht wieder bei Aufgabe 1 anfangen. Auch Helfer h soll sich dem gleichen Algorithmus unterziehen. So formuliere ich allgemeiner:
Nun zeige ich, daß auch die 3.Anforderung erfüllt wird:
Ein beliebiger Helfer h hat die Aufgaben r bis s mit dem Zeitaufwand tr+tr+1+...+ts zu bewältigen. Für seine Gesamtzeit Th, in der er helfen kann, gilt:
(1) Th >= tr + tr+1 + ... + ts
Weiter gilt nach obigem Algorithmus:
(2) Th < tr + tr+1 + ... + ts + ts+1
Aber für die Helfer h und h+1 gilt:
(3) Th +T h+1 >= tr + tr+1 + ... + ts + ts+1
Da alle Helfer die gleiche Arbeitszeit zur Verfügung haben, ist T=Th und T=T h+1:
(4) 2T >= tr + tr+1 + ... + ts + ts+1
Somit kann man folgende Gleichung bei einer Auslastung x aufstellen:
aus (1) und (4): 2xT = tr + tr+1 + ... + ts + ts+1, 1 < 2x <= 2
Dies läßt den Schluß zu, daß 2 Helfer stets mehr Arbeit erfüllen, als 1 Helfer es könnte. Daraus folgt, daß jeder einzelne Helfer im Durchschnitt zu mehr als 50% ausgelastet ist. Der beste Fall würde eine Arbeitsdauer von 100% der zur Verfügung stehenden Zeit pro Helfer erreichen. Dadurch wird klar, daß mein Verfahren im ungünstigsten Fall mindestens halb so gut wie ein optimales funktioniert. Somit werden höchstens doppelt so viele Helfer benötigt, wie im besten Fall nötig wären.
Am gegebenen Beispiel kann man das leicht überprüfen (in den Helfer-Spalten sind die einzelnen Aufgaben gleich aufsummiert):
Aufgabe |
Dauer |
Helfer h1 |
Helfer h2 |
Helfer h3 |
1 |
45 |
45 |
||
2 |
45 |
90 |
||
3 |
45 |
135 |
||
4 |
45 |
180 |
||
5 |
45 |
225 |
||
6 |
45 |
270 |
||
7 |
45 |
45 |
||
8 |
165 |
210 |
||
9 |
105 |
105 |
Es sind 3 Helfer notwendig, die 270 Minuten, 210 Minuten bzw. 105 Minuten arbeiten. Eine optimale Lösung würde nur (270+210+105):300=1,95 d.h. 2 Helfer benötigen (es gibt keine teilbaren Helfer). Meine Strategie braucht nur 1,5mal soviel und liegt damit voll im Bereich des gewünschten.
Die eben benutzte Gleichung ist von theoretischer Natur, da die Aufgaben nicht teilbar sind. Jedoch findet man durch Probieren eine Lösung, die tatsächlich eine Lösung nur 2 Helfern benötigt:
Aufgabe |
Dauer |
Helfer h1 |
Helfer h2 |
1 |
45 |
45 |
|
2 |
45 |
90 |
|
3 |
45 |
135 |
|
4 |
45 |
45 |
|
5 |
45 |
90 |
|
6 |
45 |
135 |
|
7 |
45 |
180 |
|
8 |
165 |
300 |
|
9 |
105 |
285 |
Es gibt sicher auch Verfahren, die ohne Durchprobieren aller Kombinationen die jeweils optimale Lösung finden. Ich denke dabei besonders an die Graphentheorie. Allerdings ist mein Verfahren extrem einfach zu verstehen und implementieren. Dies schlägt sich auch in der Ausführungsgeschwindigkeit nieder.
Abschließend möchte ich mich dem Verständnis des Wortes Helfer zuwenden. Da Katrin Käfer selbst mitarbeitet, sehe ich sie selbst auch als Helfer an. Somit muß man von der berechneten Helferanzahl immer 1 subtrahieren, um die Anzahl der hinzuzuziehenden Freunde zu ermitteln.
Bedienung
Alle Zeitangaben sind in Zeiteinheiten zu verstehen. Dieser variabel nutzbare Begriff erlaubt die Benutzung von Sekunden, Minuten, Stunden usw. und ist damit flexibel verwendbar. Da die Zeiteinheit für die Berechnung ganz und gar unwichtig ist, wird im weiteren Verlauf darauf auch kein Wert gelegt.
Zuerst muß die Arbeitszeit pro Person eingegeben werden. Dies ist nötig, um eine zu große Aufgabendauer abzufangen. Man sollte diese Arbeitszeit auch nur noch ändern, wenn die Liste leer ist. Danach kann man die jeweilige Dauer einer Aufgabe eintippen. Durch Druck auf Enter wird sie automatisch am Anfang der Liste hinzugefügt. Im Bildschirmauszug ist dies für das gegebene Beispiel getan worden. Beide Eingabefelder lassen nur numerische Werte zu.
Der Text über dem Aufgabendauer-Eingabefeld zählt die Nummer der nächsten Aufgabe mit, ist also um 1 größer als die Anzahl der in der Liste enthaltenen Elemente.
Wenn man Zufall aktiviert, wird die Liste mit 10.000 Zufallsaufgaben im Bereich von 1 bis 20 Zeiteinheiten gefüllt und die Arbeitszeit auf 25 gestellt. Da dieser Vorgang etwas länger dauert, wird im Zufallsbutton die Nummer der gerade bestimmten Aufgabe ausgegeben. Eine vorher bestehende Liste wird entfernt. Allerdings wird noch keine Berechnung der benötigten Helfer durchgeführt. Dies muß separat durch Berechen geschehen.
Mit Neu kann man die Liste löschen. Ebenfalls werden beide Eingabefelder auf 0 gesetzt. Es wird keine Sicherheitsabfrage durchgeführt.
Die eigentlich wichtigste Funktion erfüllt Berechnen. Damit wird der oben beschriebene Algorithmus ausgeführt. In einem Infofenster werden dann die Anzahl der benötigten Helfer und ihre durchschnittliche Arbeitsdauer ausgegebenen.
Programmdokumentation
Da jede ListBox nicht nur den sichtbaren Teil speichert, sondern auch pro Element einen Datenwert zuläßt, werden die jeweiligen Aufgabendauern dort hinterlegt. Somit spare ich mir eine extra Datenstruktur.
Ich werde mich im folgenden nur auf die beiden Methoden beschränken, die der Lösung der Aufgabenstellung dienen. Dazu gehören:
void OnRandom();
void OnCalc();
OnRandom
Um bei jedem Programmstart andere Zufallszahlen zu erhalten, wird auf Grundlage der aktuellen Zeit der Startwert des Zufallsgenerator neu bestimmt. Dies ähnelt der Funktionsweise von Randomize unter Pascal. Danach wird die Arbeitszeit ausgegeben.
Eine Schleife durchläuft die Elemente 1 bis 9.999. Dabei wird jedesmal eine Zufallszahl im Bereich von 1 bis 20 nach folgender Formel ermittelt:
Zufallszahl = Ganzzahl(rand()*20)+1
Da aber rand() Zahlen im Bereich von –215 bis +215-1 liefert und nicht von 0 bis 19, muß eine Konvertierung vorgenommen werden. Das Produkt liegt nun im gewünschten Bereich und wird durch Addition von 1 auf 1 bis 20 verändert.
Die Zufallszahl wird sowohl numerisch als auch in Zeichenkettenform an das Ende der Liste angefügt. Alle 100 Durchläufe wird der Zufallsbutton mit der Laufvariable aktualisiert, um dem Benutzer eine Programmaktivität zu verdeutlichen.
Das 10.000.Element wird genau wie alle 9.999 vorherigen ermittelt. Der einzige Unterschied liegt in der Visualisierung, da alle Bildschirmelemente an die neue Liste angepaßt werden müssen. Theoretisch könnte ich das mit allen 10.000 so tun, allerdings leidet die Geschwindigkeit erheblich darunter.
Abschließend wird auch der Zufallsbutton in den Ursprungszustand zurückversetzt.
OnCalc
Es wird gleich zu Beginn überprüft, ob die Liste mit Elementen gefüllt ist und eine gültige Arbeitszeit eingegeben wurde. Gegebenfalls erfolgt ein Abbruch mit entsprechender Fehlermeldung.
Die Idee ist, nicht ein Feld für alle Helfer aufzubauen, sondern in einer einzelnen Variable nur einen einzelnen Helfer zu betrachten. Ist dieser mit Aufgaben versorgt, wende ich mich dem nächsten zu und verwerfe die genauen Daten des bisherigen.
Also existiert nur eine Variable nAufgabenEinerPerson. Ich summiere die Gesamtaufgabenzeit in nAufgabenSumme. Die Anzahl der benötigten Helfer steht in nPersonen. Da mindestens eine Person notwendig ist, wird mit 1 initialisiert.
In einer Schleife werden alle Aufgaben durchlaufen. Nachdem die Aufgabendauer geholt wurde, erhöht sich die Gesamtaufgabenzeit. Weiterhin überprüft die Routine, ob der aktuelle Helfer diese Aufgabe noch zeitlich bewältigen kann. Ist dies nicht der Fall, wird der nächste herangezogen und sie diesem zugeteilt.
Abschließend gibt das Programm auf dem Bildschirm die benötigte Anzahl an Helfern und ihre durchschnittliche Arbeitszeit aus. Letzteres ist das arithmetische Mittel aller Aufgabenzeiten, d.h. nAufgabenSumme : nPersonen.
Beispiele
Unter Vorüberlegungen wurde das gegebene Beispiel bereits ausführlich gelöst. Trotzdem hier in Kurzfassung: Es werden 3 Personen benötigt, die im Durchschnitt 195 Minuten arbeiten.
Der geforderte Zufallsgenerator wurde 5mal angewandt, um Streuungen zu minimieren:
Durchlauf |
Anzahl Personen |
Durchschnittliche Arbeitszeit |
1 |
5593 |
18 |
2 |
5590 |
18 |
3 |
5656 |
18 |
4 |
5599 |
18 |
5 |
5566 |
18 |
Der Mittelwert beträgt 5601 Personen bei einer Maximalabweichung von 55 (Durchlauf 3), was etwas weniger als 1% entspricht.
Quelltext
ZWEI.H
#include "resource.h" // IDs der Resourcen einbinden
class CZweiApp : public CWinApp // Basisklasse des Fensters
{
public:
virtual BOOL InitInstance(); // Programmstart überladen
};
class CZweiDlg : public CDialog // Dialogklasse
{
public:
CZweiDlg(CWnd* pParent = NULL); // Konstruktor
enum { IDD = ID_DIALOG }; // ID der Resource
protected:
virtual BOOL OnInitDialog(); // Dialogstart
virtual void OnOK(); // bei Druck von ENTER
afx_msg void OnAdd(); // Hinzufügen eines Elementes
afx_msg void OnRandom(); // Zufallserzeugung
afx_msg void OnNew(); // Liste löschen
afx_msg void OnCalc(); // Berechnung
afx_msg void OnAbout(); // Programminfo
afx_msg void OnClose(); // Programmende
DECLARE_MESSAGE_MAP() // Messagehandler deklarieren
};
ZWEI.CPP
#include <afxwin.h> // MFC-Definitionen einbinden
#include "zwei.h" // Headerfile einbinden
CZweiApp ZweiApp; // Programmklasse statisch erzeugen
virtual BOOL CZweiApp::InitInstance() // Programmstart überladen
{
Enable3dControls(); // 3D-Look
CZweiDlg dlg; // Dialog statisch erzeugen
m_pMainWnd = &dlg; // Dialog als Fenster festhalten
dlg.DoModal(); // Dialog modal ausführen
return FALSE;
}
BEGIN_MESSAGE_MAP(CZweiDlg, CDialog) // alle Messages weiterleiten
ON_BN_CLICKED(ID_BUTTON_ADD, OnAdd)
ON_BN_CLICKED(ID_BUTTON_RANDOM, OnRandom)
ON_BN_CLICKED(ID_BUTTON_NEW, OnNew)
ON_BN_CLICKED(ID_BUTTON_CALC, OnCalc)
ON_BN_CLICKED(ID_BUTTON_ABOUT, OnAbout)
ON_WM_CLOSE()
END_MESSAGE_MAP()
CZweiDlg::CZweiDlg(CWnd* pParent) : CDialog(IDD, pParent)
{ // Konstruktor
} // keine Variablen zu initialisieren
virtual BOOL CZweiDlg::OnInitDialog() // Dialogstart
{
CDialog::OnInitDialog(); // zur Basisklasse weiterleiten
OnNew(); // Liste löschen
((CEdit*)GetDlgItem(ID_EDIT_ARBEITSZEIT))->SetFocus();
// Focus auf Arbeitszeitfeld setzen
return FALSE; // Focus von Win95 nicht verändern
}
virtual void CZweiDlg::OnOK() // bei Druck von ENTER
{
OnAdd(); // neue Aufgabendauer hinzufügen
}
void CZweiDlg::OnAdd() // Hinzufügen eines Elementes
{
int nArbeitsZeit = GetDlgItemInt(ID_EDIT_ARBEITSZEIT,NULL,FALSE);
// neue Arbeitszeit holen
if (nArbeitsZeit==0) // muß größer 0 sein
{
MessageBox("Bitte zuerst die Arbeitszeit eingeben.","Problem",MB_OK|MB_ICONSTOP);
return; // Fehlermeldung, abbrechen
}
int nEingabe = GetDlgItemInt(ID_EDIT_AUFGABE,NULL,FALSE);
// neue Aufgabendauer holen
if (nEingabe>nArbeitsZeit) // Aufgabendauer zu groß ?
{
MessageBox("Keine Aufgabe darf größer als die Arbeitszeit sein.","Problem",MB_OK|MB_ICONSTOP);
return; // Fehlermeldung, abbrechen
}
if (nEingabe>0) // Aufgabendauer muß größer 0 sein
{
char cConvert[40];
sprintf(cConvert, "%i", nEingabe); // in Zeichenkette umwandeln
CListBox* pBox = (CListBox*)GetDlgItem(ID_LISTBOX);
pBox->InsertString(0,cConvert); // an erster Stelle in die Liste einfügen
pBox->SetItemData(0,nEingabe);
sprintf(cConvert, "Dauer der Aufgabe %i:", pBox->GetCount()+1);
SetDlgItemText(ID_TEXT_AUFGABE, cConvert);
// Textfeld über Aufgabendauer anpassen
}
else
MessageBox("Eine Aufgabendauer von 0 ist nicht zulässig !","Problem",MB_OK|MB_ICONSTOP);
// Fehlermeldung
}
void CZweiDlg::OnRandom() // Zufallserzeugung
{
#define MinAufgabenZeit 1 // Konstanten definieren
#define MaxAufgabenZeit 20
#define ArbeitsZeit 25
#define AnzahlAufgaben 10000
#define GetRandom (((unsigned int)rand()*MaxAufgabenZeit)/32768+MinAufgabenZeit)
// Makro zur einfachen Ermittlung
// einer Zufallsaufgabendauer
srand(clock()); // Zufallsgenerator initialisieren
SetDlgItemInt(ID_EDIT_ARBEITSZEIT, ArbeitsZeit, FALSE);
// Arbeitszeit anzeigen
CListBox* pBox = (CListBox*)GetDlgItem(ID_LISTBOX);
for (int Lauf=0; Lauf<AnzahlAufgaben-1; Lauf++)
{
int nNeueAufgabe = GetRandom; // Zufallszahl
char cConvert[40];
sprintf(cConvert, "%i", nNeueAufgabe); // in Zeichenkette umwandeln
pBox->InsertString(0,cConvert); // an erster Stelle einfügen
pBox->SetItemData(0,nNeueAufgabe);
if (Lauf%100==0) // Anzeige der Laufvariable
{ // im Zufallsbutton, aber nicht zu oft
char cConvert[6];
sprintf(cConvert, "%i", Lauf);
SetDlgItemText(ID_BUTTON_RANDOM, cConvert);
}
}
int NeueAufgabe = GetRandom; // letzter Durchlauf als Nachahmung
// einer Benutzereingabe
SetDlgItemInt(ID_EDIT_AUFGABE, NeueAufgabe, FALSE);
OnAdd();
SetDlgItemInt(ID_EDIT_AUFGABE, 0, FALSE);
SetDlgItemText(ID_BUTTON_RANDOM, "&Zufall");// Zufallsbutton wiederherstellen
#undef MinAufgabenZeit // Konstanten entfernen
#undef MaxAufgabenZeit
#undef ArbeitsZeit
#undef AnzahlAufgaben
}
void CZweiDlg::OnNew() // Liste löschen
{
CListBox* pBox = (CListBox*)GetDlgItem(ID_LISTBOX);
pBox->ResetContent(); // Liste löschen
SetDlgItemText(ID_TEXT_AUFGABE, "Dauer der Aufgabe 1:");
// Textfeld anpassen
}
void CZweiDlg::OnCalc() // Berechnung
{
CListBox* pBox = (CListBox*)GetDlgItem(ID_LISTBOX);
int nAufgabenAnzahl = pBox->GetCount(); // Anzahl Elemente bestimmen
if (nAufgabenAnzahl==0) // Abbruch bei leerer Liste
{
MessageBox("Noch keine Aufgaben eingegeben.","Problem",MB_OK|MB_ICONSTOP);
return;
}
int nArbeitsZeit = GetDlgItemInt(ID_EDIT_ARBEITSZEIT,NULL,FALSE);
// Arbeitszeit holen
if (nArbeitsZeit==0) // Abbruch bei ungültiger Dauer
{
MessageBox("Noch keine Arbeitszeit eingegeben.","Problem",MB_OK|MB_ICONSTOP);
return;
}
int nPersonen = 1; // min. 1 Person nötig
int nAufgabenEinerPerson = 0; // noch keine Aufgaben verteilt
int nAufgabenSumme = 0;
for (int Lauf=0; Lauf<nAufgabenAnzahl; Lauf++)
// alle Aufgaben durchlaufen
{
int nAufgabe = pBox->GetItemData(Lauf); // nächste Aufgabe holen
nAufgabenSumme += nAufgabe; // Gesamtsumme bilden
if (nAufgabenEinerPerson+nAufgabe > nArbeitsZeit)
// ist Person überfordert ?
{
nPersonen++; // nächste Person anfordern
nAufgabenEinerPerson = 0;
}
nAufgabenEinerPerson += nAufgabe; // Aufgabe zuteilen
}
char cInfo[80];
sprintf(cInfo, "Es werden %i Personen benötigt, die im Durchschnitt %i Zeiteinheiten arbeiten",
nPersonen, nAufgabenSumme/nPersonen);
MessageBox(cInfo, "Ergebnis", MB_OK|MB_ICONINFORMATION);
// Anzahl Personen und durchschnittliche
// Arbeitszeit ausgeben
}
void CZweiDlg::OnAbout() // Programminfo
{
MessageBox("geschrieben von Stephan Brumme\nin Watcom C++ 10.6 mit MFC 3.2","Über...",MB_OK|MB_ICONINFORMATION);
}
void CZweiDlg::OnClose() // Programmende
{
if (MessageBox("Wirklich beenden ?","Ende",MB_YESNO|MB_ICONQUESTION)==IDYES)
// Sicherheitsabfrage
CDialog::OnClose();
}
ZWEI.DLG
100 DIALOG FIXED IMPURE 24, 35, 185, 144
STYLE DS_MODALFRAME | DS_3DLOOK | DS_CENTER | DS_CENTERMOUSE | WS_OVERLAPPED | WS_CAPTION | WS_VISIBLE | WS_SYSMENU
CAPTION "Aufgabe 2"
FONT 8, "Helv"
BEGIN
CONTROL "0", 102, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 10, 20, 75, 12
CONTROL "&Hinzu", 105, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 10, 40, 75, 14
CONTROL "&Zufall", 107, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 10, 60, 75, 14
CONTROL "", 106, "LISTBOX", LBS_STANDARD | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_VSCROLL | WS_TABSTOP, 100, 40, 75, 93
CONTROL "&Berechnen", 109, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 10, 100, 75, 14
CONTROL "&Neu", 108, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 10, 80, 75, 14
CONTROL "Dauer der Aufgabe:", 101, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 10, 10, 86, 8
CONTROL "Arbeitszeit pro Person:", 103, "STATIC", SS_LEFT | WS_CHILD | WS_VISIBLE, 100, 10, 75, 8
CONTROL "0", 104, "EDIT", ES_LEFT | ES_AUTOHSCROLL | ES_NUMBER | WS_CHILD | WS_VISIBLE | WS_BORDER | WS_TABSTOP, 100, 20, 75, 12
CONTROL "&Autor", 110, "BUTTON", BS_PUSHBUTTON | WS_CHILD | WS_VISIBLE | WS_TABSTOP, 10, 120, 75, 14
END
RESOURCE.H
#define ID_DIALOG 100
#define ID_TEXT_AUFGABE 101
#define ID_EDIT_AUFGABE 102
#define ID_TEXT_ARBEITSZEIT 103
#define ID_EDIT_ARBEITSZEIT 104
#define ID_BUTTON_ADD 105
#define ID_LISTBOX 106
#define ID_BUTTON_RANDOM 107
#define ID_BUTTON_NEW 108
#define ID_BUTTON_CALC 109
#define ID_BUTTON_ABOUT 110