Geldwechsler

30.01.2021, 16:27

Dopap

Geldwechsler

ich habe auf der Bank nachgefragt auf wie viele Arten Sie mir meinen 100 Euro Schein ohne Cent Münzen wechseln können...

Danach hingesetzt und nach dem Koeffizienten von $\begin{eqnarray*} x^{100} \end{eqnarray*}$ im Polynom

$\begin{eqnarray*} \left(1+\sum_{k=1}^{100} x^k\right)\cdot \left(1+\sum_{k=1}^{50} x^{2k}\right)\cdot \left(1+\sum_{k=1}^{20} x^{5k}\right)\cdot \left(1+\sum_{k=1}^{10} x^{10k}\right)\cdot \left(1+\sum_{k=1}^{5} x^{20k}\right) \left(1+\sum_{k=1}^{2} x^{50k}\right)\cdot \left(1+\sum_{k=1}^{1} x^{100k}\right) \end{eqnarray*}$

gesucht.
Leider stieg der TR schon bei den 5 Euro Scheinen aus.

Gibt es da nicht was Effektiveres?

30.01.2021, 18:19

HAL 9000

Auf diesen Beitrag antworten »

1) Du traust $\begin{eqnarray*} x^0=1 \end{eqnarray*}$ nicht? Könnte deine Formel in der Schreibweise vereinfachen.

2) Du kannst die Summen auch durch Reihen ersetzen. Ist womöglich keine rechnerische Vereinfachung, sieht in der Formel aber hübscher aus:

$\begin{eqnarray*} \frac{1}{\left(1-x\right)\left(1-x^2\right)\left(1-x^5\right)\left(1-x^{10}\right)\left(1-x^{20}\right)\left(1-x^{50}\right)\left(1-x^{100}\right)} \end{eqnarray*}$

3) Wie man solche Koeffizienten rekursiv berechnet - vermutlich rechenzeit- und kapazitätsschonender, als es ein CAS mit Polynommultiplikation tut - hatte ich ja oben im Primzahlwürfel-Thread demonstriert.

--------------------------------------------

Ok, Berechnungsskizze für das vorliegende Problem:

Münzwerte $\begin{eqnarray*} (m_k)_{k=1,\ldots,7} = (1,2,5,10,20,50,100) \end{eqnarray*}$

$\begin{eqnarray*} A(k,s) \end{eqnarray*}$ ... Anzahl Münzkombinationen der Münzsorten $\begin{eqnarray*} 1\ldots k \end{eqnarray*}$ mit Summe $\begin{eqnarray*} s \end{eqnarray*}$

Dann ist

$\begin{eqnarray*} A(k,s) = \sum_{i=0}^{\left\lfloor \frac{s}{m_k}\right\rfloor} A\left(k-1,s-im_k\right) \end{eqnarray*}$

mit Start $\begin{eqnarray*} A(0,s)=\delta_0(s) \end{eqnarray*}$ . Klar, im Fall von $\begin{eqnarray*} m_1=1 \end{eqnarray*}$ (wie hier) könnte man auch mit

$\begin{eqnarray*} A(1,s) = \begin{cases} 1 &\;\mbox{für}\;s\geq 0\\ 0 &\;\mbox{für}\;s< 0\end{cases} \end{eqnarray*}$

starten - ich wollte es nur möglichst allgemein halten. Augenzwinkern

$\begin{eqnarray*} A(7,100) = 4563 \end{eqnarray*}$

30.01.2021, 20:24

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 1+\sum\limits_{i=1}^{\frac{n}{m} } x^{m\cdot i}=\frac{x^{n+m} -1}{x^{m} -1} \end{eqnarray*}$

Geht das?

31.01.2021, 23:50

Dopap

Auf diesen Beitrag antworten »

nicht immer lustig, meist zu allgemein, aber sehr schön, dass das rekursive Vorgehen beim Geldwechseln verständlicher wurde.

Konnte somit das Programm "A" in RPN schreiben ebenfalls mit $\begin{eqnarray*} A(7,100)=4563 \end{eqnarray*}$ . Laufzeit = 12 min. [A(5,100)=4111 zum Vergleich]
'A':

$\begin{eqnarray*} \rm \langle \to k \, s \, \langle \, 0 \, \,IF\, \,k\, 1 == s\, \, 0\,\geq \, AND\,\, THEN \, 1\,+ \, \rm ELSE \\ \rm \, 0 \, s\,\,m \, k\, GET \, DIV \, FOR \, i \, k\,1\,k \,1\,-\,s\,m\,k\, GET\, \, i \,* \, -\,{\color{red}A}\,+ \,NEXT \,END\,\rangle\rangle<br /> \end{eqnarray*}$

das kann man, wenn man will, stufenweise algebraisch schreiben z.B. statt m k GET wie gewohnt 'm(k)' oder z.B.
'IFTE(bedingung,then_Term,else_Term)'. Letztlich geht es ohne Programmzeilen was mir aber zu pingelig wird.
--------------------
Diese Rekursionen lassen sich bestimmt mit dem PC ziemlich weit treiben.

Meine Idee war und ist aber, den Geldscheinwert derart in die Höhe zu treiben bis der PC aufgibt.
Keine Ahnung wo das ungefähr sein könnte.

Um danach mittels der unendlichen Reihen, $\begin{eqnarray*} \sum_{k=0}^\infty x^{kg}=\frac {1}{(1-x^g)}\qquad g\in m \end{eqnarray*}$ ,

die irgendwie? noch mathematisch bearbeitet werden müssten -

um damit auch $\begin{eqnarray*} A(7,10^{50}) \end{eqnarray*}$ oder auch $\begin{eqnarray*} A(9,10^{50}) \end{eqnarray*}$ für einen Geldschein von $\begin{eqnarray*} 10^{50} \end{eqnarray*}$ Euro bestimmen zu können.

Bin dabei ein klein wenig optimistischer wie diese Bemerkung:

Zitat:

Original von HAL 9000

2) Du kannst die Summen auch durch Reihen ersetzen. Ist womöglich keine rechnerische Vereinfachung, sieht in der Formel aber hübscher

mal sehen...

01.02.2021, 10:41

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Konnte somit das Programm "A" in RPN schreiben ebenfalls mit $\begin{eqnarray*} A(7,100)=4563 \end{eqnarray*}$ . Laufzeit = 12 min.

Diese exorbitante Zeit lässt mich vermuten, dass du die Rekursion

$\begin{eqnarray*} A(k,s) = \sum_{i=0}^{\left\lfloor \frac{s}{m_k}\right\rfloor} A\left(k-1,s-im_k\right) \end{eqnarray*}$

so direkt implementiert hast, d.h., ohne Zwischenspeicherung der "alten" Werte? Organisiert man das ganze hingegen so

Zitat:

Schritt $\begin{eqnarray*} j \end{eqnarray*}$ : Berechne $\begin{eqnarray*} A(j,r) \end{eqnarray*}$ für $\begin{eqnarray*} r=0,1,\ldots,s \end{eqnarray*}$ aus den zwischengespeicherten Werten $\begin{eqnarray*} A(j-1,0),\ldots,A(j-1,s) \end{eqnarray*}$ .

und das sukzessive für $\begin{eqnarray*} j=1,\ldots,k \end{eqnarray*}$ , dann sollte das in Sekundenbruchteilen abgehandelt sein, selbst auf lahmer Hardware und Interpretersprache (na Ok, bei Interpretern vielleicht doch ein paar Sekunden).

Zum Vergleich:

Matlab-MuPad (auch keine Riese hinsichtlich Rechengeschwindigkeit) benötigt mit dieser Zwischenspeicherungsmethode für $\begin{eqnarray*} A(10,1000)=32\,7631\,322 \end{eqnarray*}$ (entspricht der Zusammenstellung von 100 Euro bis zur Aufsplittung 10ct) ungefähr 3 Sekunden. Für $\begin{eqnarray*} A(13,10000)=7\,089\,628\,318\,292\,845 \end{eqnarray*}$ (das wäre die 1ct-Auflösung dieser 100 Euro) sind es dann aber auch schon etwas über 4 Minuten.

EDIT: Wert A(13,10000) nunmehr korrigiert.

01.02.2021, 14:45

Dopap

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 'A': \rm \langle \to k \, s \, \langle \, \overbrace{0}^{erster\,Summand} \, \,IF\, \,k\, 1 == s\, \, 0\,\geq \, AND\,\, THEN \, 1\,+ \, \rm ELSE \\ \rm \underbrace {\, 0 \, s\,\,m \, k\, GET \, DIV \, FOR \, i }_{\rm Start\, Summenschleife} \underbrace{\,k \,1\,-}_{\rm Argument1\,von\, A}\underbrace {\,s\,m\,k\, GET\, \, i \,* \, -\,}_{\rm Argument2\,von\, A}\,\,{\color{red}A}\,+ \,\underbrace {NEXT}_{\rm Schleifenende } \,END\,\rangle\rangle<br /> \end{eqnarray*}$

RPN muss man eben lesen können Augenzwinkern

Stimmt, rein rekursiver Aufruf mit 2 Argumenten von A.

mMn werden reichlich unvollendete Schleifen mit reichlich vielen Aufrufen im ELSE in den stack gestellt
bis ein Aufruf auf THEN trifft.
Das könnte den Speicher ( 200 kB ) und die Zeit strapazieren, andererseits sind 75 MHz auf einem Interpreter wahrlich nicht viel.

Hab' die Türme von Hanoi früher mal ähnlich geschrieben. Schon nach 30s kam die erste Vertauschung, danach circa alle 2 Sekunden die Nächste und weiter so für die folgenden ca. 2E+19s ~ 650 Mrd Jahre.

01.02.2021, 17:04

HAL 9000

Auf diesen Beitrag antworten »

Aus sportlichem Ehrgeiz wollte ich jetzt mal noch messen, wie lange man mit vernünftigem C++-Code benötigt, diese Anzahl zu berechnen.

Unter Verwendung von 64Bit-Integer für die Anzahlwerte $\begin{eqnarray*} A(k,s) \end{eqnarray*}$ dauert die Berechnung von obigem $\begin{eqnarray*} A(13,10000)=7\,089\,628\,318\,292\,845 \end{eqnarray*}$ nur noch ca. 50ms, und das als Single-Thread-Applikation. Augenzwinkern

EDIT: Verwendet man Datentyp mpz_class (ganze Zahlen beliebiger Größe) statt 64Bit-Integer, so verlängert sich die Rechenzeit auf 650ms.

Dafür ist man mit mpz_class aber in der Lage, die Bastion 500-Euro-Schein zu nehmen, d.h. die Anzahl der Wechselmöglichkeiten bis hinab zum 1ct-Stück zu bestimmen:

$\begin{eqnarray*} A(15,50000) = 33\,263\,329\,898\,033\,135\,692\,339 \end{eqnarray*}$ (75 Binärstellen), Rechenzeit ca. 16 Sekunden.

So, diese Darstellungen jetzt alle mal auslegen, und Dopap ist für die nächste Billion Jahre beschäftigt - vorausgesetzt, er schafft 1000 Wechselmöglichkeiten pro Sekunde. Kann er ja nach den 650 Milliarden Jahren für den Hanoi-Turm machen. Big Laugh

01.02.2021, 23:34

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

$\begin{eqnarray*} A(15,50000) = 33\,263\,329\,898\,033\,135\,692\,339 \end{eqnarray*}$ (75 Binärstellen), Rechenzeit ca. 16 Sekunden. Big Laugh

Wow beeindruckend!

Habe auch etwas experimentiert:

1.) mit Fließ-komma geht es 4 x schneller als beim exakten rationalen Zahlentyp.
2.) die Simulationssoftware auf dem LAPTOP ist in der höchsten Stufe 40 x schneller als das Original.

aber, trotz der 3.3E22 Möglichkeiten für 15 Geldeinheiten in 16s gebe ich noch nicht auf.

Lehrer

Das Ziel * ist und bleibt eine mathematische "Formel" die das C++ zur Schnecke degradiert.

Zur Not muss dann halt ein GOOGOL- Schein ( 1.E100 oder zehn Sexdezilliarden ) gewechselt werden.

Zur Vorbereitung erst einmal die Münzen auf amerikanisch $\begin{eqnarray*} m=\{ 1,5,10,25,50,100\} \rm cent ; \quad k=6 \end{eqnarray*}$ umgestellt.

Ein Test vorab, $\begin{eqnarray*} A_{\rm USA}(6,100)=293 \end{eqnarray*}$

(*) der Mensch braucht Ziele. 30 Jahre lang im 3 Band Billard vergeblich versucht einen Generaldurchschnitt
von 1.0 zu erreichen. Es reichte dann nur zu ~ 0.65 unglücklich

02.02.2021, 09:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
Lehrer

Das Ziel * ist und bleibt eine mathematische "Formel" die das C++ zur Schnecke degradiert.

Na klar, man muss sich ambitionierte Ziele setzen. Augenzwinkern

Neue Frage »

Antworten »

Geldwechsler

Verwandte Themen