Der Gegenstand der vorliegenden Erfindung ist zunächst ein
Verfahren zum Kassieren mindestens einer Geldsumme mittels
einer Kombination von Geldmünzen, die aus einer Gesamtmenge
verfügbarer Münzen herausgegriffen werden.
Ein solches Verfahren findet insbesondere bei
Zahlvorrichtungen Verwendung, auf die man bei automatischen Vorrichtungen
und insbesondere bei öffentlichen Telefonapparaten oder
Münzfernsprechern trifft.
Bei diesen Apparaten wirft der Benutzer eine bestimmte Anzahl
von Geldstücken in die Kassiervorrichtung des
Münzfernsprechers ein, die die einzuziehende Summe, in diesem Fall den
Betrag für die Verbindung, berücksichtigt und bestimmte
Geldstücke in die Kasse des Münzfernsprechers und die anderen in
eine Schale lenkt, wo sie der Benutzer wieder zu sich nimmt.
Das bei Münzfernsprechern am häufigsten verwendete Verfahren
ist dem Fachmann unter dem Begriff Kassierverfahren "mit dem
Strom" bekannt. Hat der Benutzer bei diesem Verfahren zum
Herstellen seiner Verbindung eine bestimmte Anzahl von Münzen
eingeworfen, die als eine Gesamtmenge verfügbarer Münzen
bezeichnet werden können, dann wird das Kassieren je nach der
Ankunft der Gebührenimpulse für die Verbindung durchgeführt,
wobei die Münzen mit dem geringsten Wert zunächst eingezogen
werden, dann die Münzen mit einem höheren Wert, usw.
Allerdings weist ein solches Verfahren zwei Nachteile auf. Der
erste liegt darin, daß die Gefahr besteht, daß der
Gesamtbetrag der zur Kasse geleiteten Münzen sehr viel höher als die
tatsächlich einzuziehende Summe ist. Dies passiert
beispielsweise dann, wenn nur noch ein Zehn-Franc-Stück verfügbar ist
und der Benutzer nur noch eine Verbindungszeit benötigt, die
im wesentlichen einer Gebühreneinheit, also weniger als einem
Franc, entspricht.
In diesem Fall betragen die effektiven Kosten für diese
Einheit für den Benutzer 10 Franc. Dem Verfahren "mit dem Strom"
fehlt damit eine Genauigkeit bezüglich des tatsächlich
eingezogenen Betrags. Der zweite Nachteil dieses Verfahrens
besteht darin, daß das Verhältnis zwischen dem Betrag und dem
Volumen aller Münzen in der Kasse gering ist, da stets die
kleinen Münzen zuerst herausgegriffen werden. Dies ist
insbesondere ein Nachteil für automatische Apparate wie
Münzfernsprecher, denn ist die Kasse voll und kann sie keine neuen
Münzen mehr aufnehmen, dann funktioniert der Apparat nicht
mehr. Dadurch wird es erforderlich, die Kasse von oft
benutzten Apparaten häufig zu leeren, was einen Zwang darstellt.
Im übrigen ist aus dem Dokument US-A-4 192 972 ein Verfahren
nach dem Oberbegriff von Anspruch 1 bekannt.
Dieses Verfahren ermöglicht es, daß der Benutzer nur den
genauestmöglichen Betrag zu bezahlen braucht, wobei er die
Anzahl und den Wert der Münzen kennt, die er in den Apparat
eingeworfen hat. Dagegen ermöglicht es nicht die Optimierung
der Auswahl der einzuziehenden Münzen, so daß das
geringstmögliche Volumen erhalten wird.
Aus dem Dokument FR-A-2 402 980 ist auch eine Vorrichtung
bekannt, die darauf abzielt, das geringstmögliche Volumen von
Münzen einzuziehen, aber das Problem des richtigen
eingezogenen Betrags wird dort nicht angegangen.
Die vorliegende Erfindung zielt darauf ab, die oben
beschriebenen Nachteile zu beheben, indem sie ein neues Verfahren
bereitstellt, das das Kassieren des richtigstmöglichen
Betrags ermöglicht, und es darüberhinaus mittels bestimmter
zusätzlicher Merkmale erlaubt, das Volumen der eingezogenen
Münzen zu optimieren.
Zu diesem Zweck liegt der Gegenstand der Erfindung in einem
Verfahren nach Anspruch 1.
Das Verfahren der Erfindung ermöglicht es, eine Vielzahl von
Kombinationen zu bestimmen, die den richtigstmöglichen Betrag
aufweisen.
Vorteilhaft
- berechnet man das Volumen jeder Kombination, die den am
nächsten kommenden Betrag aufweist,
- bestimmt man unter den berechneten Volumina das geringste
Volumen und
- zieht man eine der Kombinationen ein, die dieses geringste
Volumen aufweist.
Das Volumen der in der Kasse befindlichen Münzen ist damit
reduziert.
Ferner
- bestimmt man vorteilhaft eine erste Kombination, indem man
wie folgt verfährt:
- man ordnet im Verlauf einer ersten Schrittfolge der ersten
Kombination eine Anzahl verfügbarer Münzen mit dem höchsten
Wert zu, indem man folgendermaßen vorgeht:
- man klassifiziert die Werte der verfügbaren Münzen in einer
vom ersten, dem höchsten, bis zum letzten, dem geringsten,
abnehmenden Weise;
- man bestimmt die maximale Anzahl verfügbarer Münzen mit dem
ersten Wert, deren um den Wert einer Münze des letzten Wertes
verringerter Betrag kleiner ist als der Betrag der
einzuziehenden Summe;
- man berechnet einen ersten Betrag, der dem Betrag aller
verfügbaren Münzen, verringert um den Betrag aller
verfügbaren Münzen mit dem ersten Wert, entspricht;
- man berechnet einen zweiten Betrag, der dem Betrag der
einzuziehenden Summe, verringert um den Betrag der maximalen
Anzahl von Münzen mit dem ersten Wert, entspricht;
- man vergleicht den ersten Betrag mit dem zweiten Betrag,
und
- man ordnet der ersten Kombination eine Anzahl von Münzen
mit dem ersten Wert zu, die der maximalen Anzahl entspricht,
wenn der erste Betrag größer ist als der zweite Betrag oder
mit diesem übereinstimmt, und die im umgekehrten Fall der um
eine Einheit erhöhten maximalen Anzahl entspricht;
- man ordnet im Verlauf einer zweiten Schrittfolge der ersten
Kombination eine Anzahl verfügbarer Münzen mit dem in bezug
auf den höchsten Wert nächstkleineren Wert zu, indem wie beim
ersten Schritt vorgegangen wird, jedoch ausgehend von einem
Satz verfügbarer Münzen, von dem alle Münzen mit dem höchsten
Wert ausgeschlossen sind, sowie unter Zugrundelegung einer
einzuziehenden Summe, deren Betrag um den Betrag der Münzen,
die bereits der ersten Kombination zugeordnet worden ist,
verringert ist; und
- man ordnet auf diese Weise im Verlauf aufeinanderfolgender
Schrittfolgen, die analog zu den vorausgehenden Schrittfolgen
sind, der ersten Kombination die Anzahl verfügbarer Münzen
jeden Werts zu, und zwar bis zur letzten Schrittfolge, in
deren Verlauf man die maximale Anzahl bestimmt, ohne ihren
Betrag um den Wert einer Münze der letzten Wertkategorie zu
vermindern;
- man bestimmt eine zweite Kombination, indem man wie bei der
ersten Kombination vorgeht, jedoch ausgehend von einem Satz
verfügbarer Münzen, von dem alle Münzen mit dem höchsten Wert
ausgeschlossen sind;
- man bestimmt eine dritte Kombination, indem man wie bei der
ersten und der zweiten Kombination verfährt, jedoch ausgehend
von einem Satz verfügbarer Münzen, von dem alle Münzen mit
dem höchsten Wert und dem nächstkleineren ausgeschlossen
sind; und
- man verfährt so bis zur letzten Kombination, die man allein
unter Zugrundelegung der verfügbaren Münzen mit dem
geringsten Wert erhält, oder solange, bis am Ende einer der
Schrittfolgen die einzuziehende Summe, verringert um den
Betrag der Münzen, die bereits einer Kombination zugeordnet
sind, gleich Null oder negativ wird.
Von einem solchen Verfahren zur Bestimmung von
Münzkombinationen läßt sich sagen, daß man wirklich ein
richtigstmögliches Kassieren erhält, dessen Volumen darüberhinaus sehr
gering ist, denn es ist festzustellen, daß die ersten
bestimmten Kombinationen vor allem bezüglich des Münzvolumens
optimal sind, während die letzten vor allem bezüglich des Betrags
optimal sind. Die Vielzahl von auf diese Weise bestimmten
Kombinationen ermöglicht dann also eine gute Auswahl.
Der Gegenstand der Erfindung liegt auch in einer
Kassiervorrichtung zur Durchführung des oben beschriebenen Verfahrens.
Die vorliegende Erfindung ist leichter dank der folgenden
Beschreibung der bevorzugten Durchführung des Verfahrens der
Erfindung sowie der bevorzugten Ausführungsform der
Vorrichtung der Erfindung unter Bezugnahme auf die beigefügten
Zeichnungen zu verstehen; darin zeigen
Fig. 1 schematisch eine Kassiervorrichtung nach der
Erfindung;
Fig. 2 ein Flußdiagramm der von der Rechenschaltung der
Vorrichtung von Fig. 1 erfüllten Aufgaben;
Fig. 3 ein detaillierteres Flußdiagramm zur Aufgabe der
Bestimmung der Vielzahl von Kombinationen aus dem
Flußdiagramm von Fig. 2, und
Fig. 4 genauer die Aufgabe der Bestimmung einer Kombination
aus dem Flußdiagramm von Fig. 3.
Nun wird eine automatische Kassiervorrichtung beispielsweise
für einen öffentlichen Telefonapparat oder einen
Münzfernsprecher beschrieben. Diese Vorrichtung ist zum Einziehen
einer Geldsumme D oder der "Schuld", in diesem Fall also
dem Betrag, der dem Preis für die Verbindung entspricht, die
der Benutzer gerade beendet hat, mit Hilfe einer Kombination
von Geldmünzen, die aus einer Gesamtmenge verfügbarer Münzen
oder einem "Vorrat" herausgegriffen werden, also den Münzen,
die vom Benutzer zu diesem Zweck in den Münzfernsprecher
eingeworfen worden sind.
Genauer läßt sich nämlich sagen, daß die Vorrichtung
wenigstens die der Schuld entsprechende Geldsumme einzieht, denn
stellt sich heraus, daß ein Teil der verfügbaren Münzen nicht
so kombiniert werden kann, daß der Gesamtbetrag dieses Teils
gleich dem Betrag der Schuld ist, dann zieht die Vorrichtung
eine Kombination mit einem etwas höheren Betrag ein.
Unter Bezugnahme auf Fig. 1 weist die Kassiervorrichtung
zunächst eine Einrichtung 2 zum Bestimmen des Werts jeder in
eine Einwurföffnung 22 eingeworfenen Münze auf, mit der sie
versehen ist. Die Einrichtung 2 ist auch mit einem Ausgang
für die Münzen versehen, der hier mit einer Speichergleitbahn
4 versehen ist. Die Speichergleitbahn 4 steht mit einer
Leiteinrichtung 5 in Verbindung, die mit einem Schieber 51 für
zwei Positionen versehen ist und es ermöglicht, jede Münze
entweder zu einer Schale 7 zu leiten, wo sie der Benutzer
wieder aufnehmen kann, oder zu der Kasse 6 des
Münzfernsprechers.
Die Einrichtung 2 zum Bestimmen des Werts jeder Münze ist
eine Schaltung eines bekannten Typs, die mit einem Ausgang
versehen ist, an dem hier ein digitales elektrisches Signal
VA verfügbar ist, um die Tatsache, daß eine Münze die
Einrichtung 2 durchquert hat, sowie deren Wert anzugeben. Das
Signal VA wird an einen Eingang einer Rechenschaltung 3, hier
an einen Mikroprozessor, angelegt. Der Mikroprozessor 3
erhält auch an einem weiteren Eingang ein digitales Signal D,
das für die geschuldete Summe steht und von dem
Einheitenzähler 1 stammt, mit dem der Münzfernsprecher versehen ist. Der
Mikroprozessor 3 ist schließlich mit einem Binärausgang
versehen, der ein Signal C zur Steuerung des Schiebers 51 der
Lenkeinrichtung 5 abgibt.
Die eben beschriebene Einrichtung funktioniert wie folgt.
Der Benutzer wirft zunächst eine bestimmte Anzahl von Münzen
in die Öffnung 22, die nach ihrem Durchgang in der Gleitbahn
4 gespeichert werden und damit die Gesamtmenge verfügbarer
Münzen 8a, 8b, 8c und 8d bildet, die in Fig. 1 dargestellt
sind. Im folgenden wird angenommen, daß die Münzen nach ihrem
Wert Wa, Wb, Wc oder Wd vier unterschiedlichen Typen
angehören können, in Frankreich beispielsweise 5 F, 2 F, 1 F und
0,5 F. Die Einrichtung 2 bestimmt beim Durchgang den Wert
jeder der verfügbaren Münzen, und der Mikroprozessor
speichert diese Werte sowie die Reihenfolge, in der die Münzen
durchlaufen, und bestimmt die Anzahl der für jeden Wert
verfügbaren Münzen. Der Mikroprozessor 3 kennt damit die
Zusammensetzung ZUS des Vorrats an verfügbaren Münzen, die durch
die Anzahl na verfügbarer Münzen mit dem Wert Wa die Anzahl
nb verfügbarer Münzen mit dem Wert Wb definiert ist, usw.
Dies wird notiert:
ZUS = (Wa, na; Wb; nb; Wc, nc; Wd, nd) (1)
Darüberhinaus wird hier der Einfachkeit halber angenommen:
Wa > Wb > Wc > Wd (2)
Der Mikroprozessor 3 berechnet hier den Betrag aller
verfügbaren Münzen, d. h. des Vorrats nach der Formel
S = na Wa + nb Wb + ncWc + ndWd (3).
Nach dem Einwerfen einer ausreichenden Menge von Münzen ist
der Benutzer auf bekannte Weise berechtigt, die Verbindung
herzustellen, in deren Verlauf die Einheiten von dem Zähler 1
gezählt werden. Während der Verbindung vergleicht der
Mikroprozessor 3 den Betrag D für die Verbindung mit dem Betrag S
des Vorrats. Nähert sich der Betrag D, der sich dann im Laufe
der Zeit erhöht, dem Betrag S, dann wird der Benutzer davon
benachrichtigt. Er kann dann die Verbindung unterbrechen oder
neue Münzen einwerfen, in welchem Fall der Mikroprozessor
einen neuen, höheren Betrag S des Vorrats berechnet. Hat der
Benutzer also seine Verbindung beendet, dann ist der
einzuziehende oder geschuldete Betrag D damit kleiner als der
Betrag S des Vorrats. Dem ist nicht so, wenn die Verbindung
gewaltsam durch den Münzfernsprecher unterbrochen worden ist,
da der Benutzer die Verbindung nicht selbst unterbrochen oder
neue Münzen vor dem Unterbrechungszeitpunkt eingeworfen hat,
zu dem D gleich S wird. In diesem Fall ist das Problem des
Kassierens offensichtlich geregelt.
In den anderen, den häufigsten Fällen bestimmt, sobald der
Benutzer seine Verbindung beendet hat, der Mikroprozessor 3,
der also die Zusammensetzung des Vorrats S und der
geschuldeten Summe D gespeichert hat, aus einer Vielzahl von möglichen
Kombinationen der Münzen des Vorrats die genaueste und am
wenigsten voluminöse Kombination als die einzuziehende
Kombination, was weiter unten besser zu verstehen ist. Der
Mikroprozessor 3, der im übrigen die Reihenfolge gespeichert hat,
in der die Münzen durchgelaufen sind, und damit die
Reihenfolge, in der sie in der Gleitbahn 4 angeordnet sind, steuert
dann über ein Signal C und den Schieber 51 das Kassieren der
der einzuziehenden Kombination zugeordneten Münzen in der
Kasse 6 oder die Rückgabe von dieser Kombination nicht
zugeordneten Münzen über die Schale 7 zu dem Benutzer.
Unter Bezugnahme auf Fig. 2 werden nun die verschiedenen, von
dem Mikroprozessor 3 erfüllten Aufgaben beschrieben.
Zunächst bestimmt der Mikroprozessor 3 im Verlauf eines
Schritts 10 eine Vielzahl von unterschiedlichen Kombinationen
von verfügbaren Münzen. Jede Kombination wird auf eine später
genauer beschriebene Weise so bestimmt, daß ihr Betrag etwas
größer als der Betrag der einzuziehenden Summe oder der
Schuld D oder gleich dieser ist. In Fig. 3, die die im
Verlauf des Schritts 10 erfüllte Aufgabe zerlegt, wird im
Verlauf des Schritts 100 ausgehend von allen verfügbaren Münzen
eine erste Kombination K&sub1; bestimmt. Dann werden im Verlauf
eines Schritts 200 aus dem Vorrat der verfügbaren Münzen alle
Münzen mit dem höchsten Wert ausgeschlossen, hier die Münzen
mit dem Wert Wa in einer Anzahl na. Dann wird im Verlauf
eines neuen Durchgangs durch den Schritt 100 ausgehend von
diesem verringerten Vorrat eine zweite Kombination K&sub2; bestimmt.
Daraufhin werden im Verlauf eines neuen Durchgangs durch den
Schritt 200 alle Münzen mit dem höchsten Wert aus dem Vorrat
ausgeschlossen, die nun die Münzen mit dem Wert Wb in einer
Anzahl nb sind. Dann wird im Verlauf eines neuen Durchgangs
durch den Schritt 100 eine dritte Kombination K&sub3; bestimmt,
usw. Bei dem vorliegenden Beispiel, wo vier Werte von Münzen
Wa, Wb, Wc und Wd angenommen wurden, sind damit im Prinzip
vier Kombinationen K&sub1;, K&sub2;, K&sub3; und K&sub4; bestimmt.
Schließlich berechnet der Mikroprozessor 3, wieder unter
Bezugnahme auf Fig. 2, im Verlauf eines Schritts 20 den Betrag
jeder Kombination. Selbstverständlich ist es möglich, daß
zwei unterschiedliche Kombinationen den gleichen Betrag
aufweisen. So läßt sich ein Betrag B&sub1; für die Kombination K&sub1;
finden, ein für die Kombinationen K&sub2; und K&sub3; identischer
Betrag B&sub2; und ein Betrag B&sub3; für die Kombination K&sub4; finden.
Daraufhin wird im Verlauf eines Schritts 30 durch den
Mikroprozessor 3 der der einzuziehenden Summe D am nächsten
kommende Betrag bestimmt. Es handelt sich nämlich hier um den
geringsten Betrag, da der Betrag einer Kombination,
beispielsweise der Betrag M2, stets größer oder gleich dem
Betrag D ist.
Dann berechnet der Mikroprozessor 3 im Verlauf eines Schritts
40 das Volumen jeder Kombination, die den am nächsten
kommenden Betrag aufweist. Demnach handelt es sich hier um die
Volumina VO&sub2; und VO&sub3; der Kombinationen K&sub2; und K&sub3; mit dem Betrag
B&sub2;. Die Volumina jedes verschiedenen Typs von Münzen sind im
Speicher des Mikroprozessors 3 gespeichert, um die Berechnung
des Volumens der Kombinationen zu ermöglichen.
Dann bestimmt der Mikroprozessor 3 im Verlauf eines Schritts
50 das geringste Volumen, z. B. VO&sub3;.
Daraufhin steuert der Mikroprozessor 3 die Einrichtung 5 im
Verlauf eines Schritts 60 so, daß die Kombination K&sub3; mit dem
geringsten Volumen sowie, selbstverständlich, der am nächsten
liegende Betrag eingezogen wird.
Unter Bezugnahme auf Fig. 4 werden nun die verschiedenen, von
dem Mikroprozessor 3 im Verlauf des Schritts 100 von Fig. 3,
dem Schritt des Bestimmens einer Kombination beschrieben.
Zunächst ordnet der Mikroprozessor 3 im Verlauf eines ersten
Durchgangs durch eine Schrittfolge 1010 bis 1140 der
Kombination eine bestimmte Anzahl von verfügbaren Münzen mit dem
höchsten Wert zu. Unter der Annahme, daß die zu bestimmende
Kombination die erste K&sub1; ist, handelt es sich um Münzen mit
dem Wert Wa. Ist die zu bestimmende Kombination die zweite,
dann sind natürlich die verfügbaren Münzen mit dem höchsten
Wert diejenigen mit dem Wert Wb, usw.
Im Verlauf des Schritts 1010 klassifiziert der Mikroprozessor
die Werte der verfügbaren Münzen in abnehmender Weise vom
ersten WA, dem höchsten, bis zum letzten WN, dem geringsten,
usw. Die Klassifizierung lautet also wie folgt, wenn der
Mikroprozessor die erste Kombination bestimmt, sowie mit den
über die Werte Wa, Wb, Wc und Wd gestellten Hypothesen:
WA = Wa WB = Wb WC = Wc und WN = WD = Wd (4)
Bestimmt aber der Mikroprozessor die zweite Kombination, dann
ist die Klassifizierung wie folgt
WA = Wb WB = Wc und WN = WC = Wd (5)
Im Verlauf der Schritte 1020 bis 1050 und 1070, über die
Schleife 1090, bestimmt der Mikroprozessor 3 die maximale
Anzahl, in diesem Fall die Anzahl (n-x) verfügbarer Münzen
mit dem ersten Wert WA, deren Betrag, verringert um den Wert
WN einer Münze mit dem letzten Wert, kleiner als der Betrag D
der einzuziehenden Summe ist. Noch einfacher bestimmt der
Mikroprozessor 3 die höchste Anzahl (n-x) so, daß der
folgenden Beziehung genügt ist:
(n-x) WA - WN < D (6)
Dafür bestimmt der Mikroprozessor 3 zunächst im Verlauf des
Schritts 1020 die Anzahl n von Münzen mit dem Wert WA und
initialisiert im Verlauf eines Schritt 1030 eine ganze
Variable x auf dem Wert Null.
Dann bestimmt er im Schritt 1040, ob der erste Wert WA gleich
dem letzten Wert WN ist. Beim ersten Durchgang, der aktuell
beschrieben wird, ist dies nicht der Fall, und er berechnet
im Verlauf des Schritts 1050 eine Größe A wie:
A = (n-x) WA - WN (7)
Im Verlauf des Schritts 1070 vergleicht er die Größe A mit
dem Betrag D, und ist die Größe A größer als oder gleich
diesem Betrag, dann erhöht er im Verlauf des Schritts 1090 x um
eine Einheit und beginnt erneut die Schritte 1040, 1050 und
1070 mit diesem neuen Wert von x.
Man kann also sagen, daß der Mikroprozessor 3 nach Versuch
und Irrtum ausgehend von einer Gesamtzahl n verfügbarer
Münzen mit dem ersten Wert WA vorgeht, einer Gesamtzahl, die er
Einheit für Einheit bis zu der gesuchten maximalen Anzahl (n-x)
verringert.
Ist diese maximale Anzahl (n-x) bestimmt, dann berechnet der
Mikroprozessor 3 im Verlauf des Schritts 1080 einen ersten
Betrag E gleich dem Betrag S aller verfügbaren Münzen,
verringert um den Betrag aller verfügbaren Münzen mit dem ersten
Wert WA, d. h. einen Betrag E wie:
E = S - n WA (8)
Es ist zu bemerken, daß dieser Betrag E den Betrag der
verfügbaren Münzen darstellt, die nicht den ersten Wert WA
aufweisen, d. h. den Betrag, der verfügbar bleibt, um den
einzuziehenden Rest zu begleichen, wenn angenommen wird, daß eine
bestimmte Anzahl von Münzen mit dem ersten Wert WA eingezogen
worden ist, und man sich an diese Anzahl hält.
Dann berechnet der Mikroprozessor 3 im Verlauf des Schritts
1100 einen zweiten Betrag G, der gleich dem Betrag D der
einzuziehenden Summe ist, der um den Betrag der maximalen Anzahl
von Münzen mit dem ersten Wert WA verringert ist, d. h. einen
Betrag G wie:
G = D - (n-x) WA (9)
Es ist zu bemerken, daß dieser Betrag G den einzuziehenden
Rest darstellt, wenn angenommen wird, daß eine Anzahl von
Münzen mit dem ersten Wert WA eingezogen worden ist, die
gleich der maximalen Anzahl (n-x) ist.
Der Mikroprozessor vergleicht dann im Verlauf des Schritts
1110 den ersten Betrag E mit dem zweiten Betrag G.
Ist der erste Betrag E größer als der zweite Betrag G, dann
ist es offensichtlich möglich, eine Anzahl (n-x) von Münzen
mit dem ersten Wert einzuziehen, da es der restliche Vorrat
mit dem Betrag E erlaubt, den einzuziehenden Rest mit dem
Betrag G abzudecken. So ordnet der Mikroprozessor der
Kombination, die er gerade bestimmt, und im Verlauf des Schritts
1130 eine der maximalen Anzahl (n-x) gleiche Anzahl p von
Münzen mit dem Wert WA zu, also
p = n-x (10)
Ist der erste Betrag E kleiner als der zweite Betrag G, dann
ordnet der Mikroprozessor im Verlauf des Schritts 1120 der
Kombination eine Anzahl p von Münzen mit dem Wert WA zu, die
gleich der um eine Einheit erhöhten maximalen Anzahl (n-x)
ist, also:
p = n-x + 1 (11)
Der erste Durchgang durch die Schrittfolge 1010 bis 1140 ist
praktisch beendet, wobei eine Anzahl p von Münzen mit dem
ersten Wert WA, d. h. hier dem Wert Wa, der Kombination
zugeordnet ist.
Im Verlauf des Schritts 1140 bereitet der Mikroprozessor 3 den
zweiten Durchgang durch die Folge 1010 bis 1140 vor, indem er
eine neue Gesamtmenge verfügbarer Münzen bestimmt, von der
alle Münzen mit dem höchsten Wert Wa ausgeschlossen sind,
also hier mit einer Zusammensetzung ZUS wie:
ZUS = (Wb, nb; Wc, nc; Wd, nd) (12)
und mit einem Betrag S gleich:
S = nb Wb + nc Wc + nd Wd (13)
Im Verlauf des Schritts 1140 bestimmt der Mikroprozessor 3
den neuen Betrag der einzuziehenden Summe, der gleich dem
einzuziehenden Rest ist, wenn die p Münzen mit dem Wert WA
eingezogen worden sind, also:
D = D - p WA (14)
Im Verlauf des zweiten Durchgangs durch die Schrittfolge 1010
bis 1040 wird der Mikroprozessor dann der Kombination eine
bestimmte Anzahl verfügbarer Münzen mit dem in bezug auf den
höchsten Wert Wa nächstkleineren Wert zuordnen, also hier dem
Wert Wb.
Es ist zu bemerken, daß die Klassifizierung nach dem zweiten
Durchgang durch den Schritt 1010 wie folgt ist:
WA = Wb WB = Wc und WN = WC = Wd (15)
Ein dritter Durchgang durch die Schrittfolge 1010 bis 1040
ermöglicht es dem Mikroprozessor 3, der Kombination eine
bestimmte Anzahl von Münzen mit dem Wert Wc zuzuordnen, und
hier ermöglicht es ein vierter und letzter Durchgang der
Kombination eine bestimmte Anzahl von Münzen mit dem Wert Wd
zuzuordnen.
Allerdings ist zu bemerken, daß der Mikroprozessor 3 beim
letzten Durchgang durch die Schrittfolge 1010 bis 1040 die
maximale Anzahl bestimmt, ohne deren Betrag um den Wert WN
einer Münze mit dem letzten Wert zu verringern. Beim letzten
Durchgang ist die Klassifizierung nach dem Schritt 1010
nämlich notwendigerweise wie folgt:
WA = WN = Wd (16)
Dem Schritt 1040 folgt dann der Schritt 1060, und die
berechnete Größe A ist dann, wie sich in Fig. 4 ergibt:
A = (n-x) WA (17)
Natürlich ist bei dem Flußdiagramm von Fig. 4 auf eine aus
Gründen der einfacheren Darstellung nicht gezeigte Weise der
Übergang zu "Ende" vorgesehen, sobald die neue, im Verlauf
des Schritts 1140 nach der Beziehung (14) berechnete Schuld D
Null oder negativ wird.
Um die Gedanken festzuhalten, wird nun ein konkretes Beispiel
beschrieben. Es sei angenommen:
Wa = 5 F, Wb = 2 F, Wc = 1 F, Wd = 0,5 F (18)
Es wird angenommen, daß die Gesamtmenge der verfügbaren
Münzen eine Münze mit 5 F, 3 Münzen mit 2 F und 2 Münzen mit 0,5
F beinhaltet. Daraus ergibt sich also:
ZUS = (5 F, 1; 2 F, 3; 0,5 F, 2) (19)
S = 12 F (20)
Es wird angenommen, daß der Betrag D der geschuldeten Summe
beträgt:
D = 6,50 F (21)
Dann wird ausgehend von den in den obengenannten Beziehungen
19, 20 und 21 gegebenen ZUS, S und D eine erste Kombination
K&sub1; bestimmt.
Im Verlauf eines ersten Durchgangs werden nacheinander
bestimmt:
- Schritt 1010 : WA = 5 F WB = 2 F WN = WC = 0,5 F
- Schritte 1020-1070 : n-x = 1
- Schritt 1080 : E = 7 F
- Schritt 1100 : G = 1,50 F
- Schritt 1130 : p = 1
(eine Münze mit 5 F wird also der Kombination K&sub1; zugeordnet)
- Schritt 1140 : S = 7 F D = 1,50 F
Im Verlauf eines zweiten Durchgangs werden dann nacheinander
bestimmt:
- Schritt 1010 : WA = 2 F WN = WC = 0,5 F
- Schritte 1020-1070 : n-x = 0
- Schritt 1080 : E = 1 F
- Schritt 1100 : G = 1,50 F
- Schritt 1120 : p = 1
(eine Münze mit 2 F wird also der Kombination K&sub1; zugeordnet)
- Schritt 1140 : S = 1 F D = -0,5 F
Da der geschuldete Rest negativ wird, geht man über zu
"Ende".
Die erste Kombination K&sub1; beinhaltet also eine Münze mit 5 F
sowie eine Münze mit 2 F, und ihr Betrag ist 7 F.
Zur Bestimmung einer zweiten Kombination K&sub2; werden aus der
Gesamtmenge der verfügbaren Münzen diejenigen mit dem
höchsten Wert ausgeschlossen, hier also die Münze mit 5 F. Es
wird also von ZUS und S wie folgt ausgegangen:
ZUS = (2 F, 3; 0,5 F, 2) (22)
S = 7 F (23)
Dabei wird der dem der Beziehung (21) entsprechende Betrag D
behalten, also:
D = 6,50 F (21)
Im Verlauf eines ersten Durchgangs werden nacheinander
bestimmt:
- Schritt 1010 : WA = 2 F WN = WC = 0,5 F
- Schritte 1020-1070 : n-x = 3
- Schritt 1080 : E = 1 F
- Schritt 1100 : G = 0,5 F
- Schritt 1130 : p = 3
(drei Münzen mit 2 F werden also der Kombination K&sub2;
zugeordnet)
- Schritt 1140 : S = 1 F D = 0,5 F
Im Verlauf eines zweiten Durchgangs werden nacheinander
bestimmt:
- Schritt 1010 : WA = WN = 0,5 F
- Schritte 1020-1070 : n-x = 0 (über den Schritt 1060)
- Schritt 1080 : E = 0 F
- Schritt 1100 : G = 0,5 F
- Schritt 1120 : p = 1
(eine Münze mit 0,5 wird also der Kombination K&sub2; zugeordnet)
- Schritt 1140 : S = 0 D = 0
Da der geschuldete Rest Null wird, geht man zu "Ende" über.
Die zweite Kombination K&sub2; weist also drei Münzen mit 2 F und
eine Münze mit 0,5 F auf, und ihr Betrag ist 6,50 F.
Es ist hier nicht möglich, eine dritte oder eine vierte
Kombination zu bestimmen, denn sind die Münze mit 5 F und die
Münzen mit 2 F aus der Gesamtmenge des verfügbaren Vorrats
ausgeschlossen, dann deckt der verfügbare Betrag nicht mehr
die Schuld.
In diesem Fall ist die einzuziehende Kombination nach dem
Flußdiagramm von Fig. 2 die Kombination K&sub2;&sub1; da ihr Betrag
gleich der einzuziehenden Summe ist. Bei diesem, absichtlich
einfach gewählten Beispiel stellt sich nicht die Frage nach
dem Volumen der Kombination, da nur eine Kombination mit dem
geringsten Betrag bestimmt wird.
Natürlich ist der Bereich der vorliegenden Anmeldung nicht
auf den Fall beschränkt, bei dem die Münzen in vier
Wertkategorien aufgeteilt werden, und die Erfindung ist
selbstverständlich auf den Fall einer beliebigen Anzahl von Werten
anwendbar.