Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Rekursionsgleichung aufstellen

Rekursionsgleichung aufstellen

Universität / Fachhochschule

Sonstiges

Tags: Sonstig

wemsor aktiv_icon

18:20 Uhr, 26.05.2018

Hallo! Wir befassen uns aktuell mit dem Münzwechselproblem und sollen folgende Aufgabe lösen:

Gesucht ist die minimale Anzahl an Münzen die wir brauchen um den Betrag

b

auszuzahlen. Unsere Münzen haben den Wert

w_{1}, ..., w_{n}

.

Nun sollen wir eine Rekursionsgleichung für die minimale Anzahl an Münzen

M (i, j)

finden um den Betrag

j \in {0, ..., b}

auszuzahlen wobei nur die Münzen

w_{1}, ..., w_{i}

mit

i \in {1, ..., n}

genutzt werden dürfen. Wie häufig wir jede Münze benutzen ist egal.

Kann mir wer helfen wie ich vorgeben kann?
LG

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich benötige bitte nur das Ergebnis und keinen längeren Lösungsweg."

ledum aktiv_icon

22:17 Uhr, 26.05.2018

Hallo
weiss man denn irgendetwas über die

w_{i},

damit man

b = 1

zahlen kann muss

w_{1} = 1,

also kann man

b = n

auszahlen mit

n \cdot w_{1},

falls man

w 2

als nächst größeren kenn kann man möglichst viele

w 1

durch

w 2

ersetzen usw.
besser
anderer Weg; die

w_{i}

seien geordnet,

w_{i} < w_{k}

für

i < k

dievidiere

b

durch das größte

w_{i} < b

mit Rest, den Rest entsprechend weiter verarbeiten.
Gruß ledum

anonymous

07:31 Uhr, 27.05.2018

Hallo
Ich lese mir den Text nochmals und nochmals durch, und verbleibe doch ein wenig in Zweifel.
Lasst uns erst mal klar werden, wie die etwas verklausulierte Aufgabe überhaupt zu verstehen ist.

Da ist einmal von einem Betrag "b" die Rede, und einmal von einem Betrag "j" .(?)
So wie's geschrieben ist, müsste man annehmen, dass

' j'

nur ein Teilbetrag von

' b'

ist.

Ich will mal den Begriff "Münzwerte" einführen oder verdichten.
"Unsere Münzen haben den Wert

w_{1}, . .

, w_{n}

".
Um ein Beispiel aus dem europäischen Währungsraum zu nutzen:
Der Euro wird in den Münzwerten
1ct ; 2ct ; 5ct ; 10ct ; 20ct ; 50ct ; 1€ ; 2€
gehandelt.
Das wären also 8 Münzwerte.

Aufgabenverständnis 1:
Ich lese mir den Aufgabentext nochmals und nochmals durch. Ich halte es für möglich, dass das so zu verstehen ist, dass wir möglichst wenige Münzwerte nutzen sollen.
Dann ist in einer Kondition, in der wir eine 1ct Münze zur Verfügung haben, möglich, dass wir jeden Betrag mit nur einem Münzwert bezahlen können, nämlich mit der 1ct Münze - auch wenn wir die dazu Schubkarren-weise nutzen müssten.
Denn "Wie häufig wir jede Münze benutzen ist egal."

Aufgabenverständnis 2:
Ich lese mir den Aufgabentext nochmals und nochmals durch. Ich halte es für möglich, dass das so zu verstehen ist, dass wir möglichst wenige Münzen nutzen sollen.
Das ist nicht nur die naheliegende Spontanvermutung, das scheint auch das Verständnis von dir, Ledum, zu sein, weil wir dieses Problem ja auch aus dem Alltag kennen.

Dann ist aber der Lösungsvorschlag von Ledum nicht unbedingt das Optimum.
Dann ist die Aufgabe höchst wahrscheinlich nur iterativ lösbar.
Beispiel:
Wir haben die Münzwerte:

w_{1} = 1

w_{2} = 7

w_{3} = 9

und den Betrag

b = 49

.

Gemäß Ledums Vorschlag würde man also erstmal

>

die größtmögliche Münze versuchen, die 9-er Münze, die passt 5-mal um den Teilbetrag

45

zu erzielen, Restbetrag: 4.

>

dann die nächst größere Münze versuchen, die 7-er Münze, die passt offensichtlich nicht.

>

dann die nächst größere Münze versuchen, die 1-er Münze, die passt noch 4-mal.

>

Zusammenfassung: wir haben 9 Münzen genutzt.

Unschwer ersichtlich ist aber (das Beispiel ist ja so hingetrimmt), dass iterativ die Aufgabe natürlich auch mit nur
7 Münzen zu je den Werten

w_{2} = 7

lösbar ist.

ermanus aktiv_icon

07:39 Uhr, 27.05.2018

Hallo,
hier noch ein "übersichtlicheres" Gegenbeispiel:
3 Münzwerte: 1, 4, 6.
Dann ist 8=4+4=6+1+1.
Gruß ermanus

anonymous

07:45 Uhr, 27.05.2018

Hallo wemsor, hast du den Original-Aufgabentext angeboten?
Wenn nein - kannst du das noch klärend nachholen?

wemsor aktiv_icon

13:26 Uhr, 27.05.2018

Ja natürlich.
Es werden nur Münzen mit den Werten

w_{1}, ..., w_{n}

aus den natürlichen Zahlen verwendet

(n \in ℕ)

. Wir wollen die kleinste Anzahl an Münzen bestimmen, die benötigt wird, um den Betrag

b

auszuzahlen

(b \in ℕ)

. Gib dafür eine Rekursionsgleichung für die minimale Anzahl Münzen

M (i, j)

an, um den Betrag

j

mit

j \in {0, ..., b}

auszuzahlen, wobei nur die Münzen mit den Weten

w_{1}, ..., w_{i}

für

i \in {1, ..., n}

benutzt werden dürfen. Jeder Münztyp darf beliebig oft verwendet werden.

anonymous

15:06 Uhr, 27.05.2018

Hallo

Ich nehme an, dein ursprünglicher Zusatz
"Wie häufig wir jede Münze benutzen ist egal."
stammt demnach aus deiner Feder, dient eher der Verwirrung, und sollten wir fortan besser ignorieren.

Ferner verstehe ich aus dem Aufgabentext, dass eher das

\Rightarrow

Aufgabenverständnis_2
gemeint ist.
Sind wir uns einig?

Roman-22

16:40 Uhr, 27.05.2018

>

hier noch ein "übersichtlicheres" Gegenbeispiel:
Ja, bekanntermaßen findet der von ledum vorgeschlagene greedy-Algorithmus bestenfalls ein lokales Minimum, selten aber das globale.
Schlimmer sogar - er kann versagen, obwohl eine Lösung existiert.
ZB: Münzwerte 2 und

5;

Betrag

11

.
Der greedy Algorithmus findet nach

5 + 5 + . .

. keine Lösung, die aber mit

5 + 2 + 2 + 2

existiert.

Allerdings ist es so, dass so gut wie alle gängigen real existierenden Währungen so gestückelt sind, dass mit dem greedy-Algorithmus das globale Minimum gefunden werden kann.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1428338

1428214

	Status: nicht eingeloggt	Noch nicht registriert?