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.