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:

  1. Teile Helfer 1 Aufgabe 1 zu
  2. Hat er noch Zeit für die nächste Aufgabe ? Wenn ja, teile sie ihm zu und wiederhole 2.
  3. Helfer 1 ist nun ausgelastet

 

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:

  1. h=1
  2. Für alle Aufgaben n arbeite 2.1. und 2.2. ab:
    1. Teile Helfer h Aufgabe n zu
    2. Wenn er ausgelastet ist, nehme nächsten Helfer h+1.

 

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