| |
| Autor |
 1000 Euro in genau 10 Scheinen legen |
|
KiliZahl
Neu 
Dabei seit: 16.02.2018
Mitteilungen: 2
 |  Themenstart: 2018-02-16
|
Hallo.
Meine Tochter (3.Klasse) hat folgende Hausaufgaben:
Finde 10 Möglichkeiten 1000 Euro aus genau 10 Scheinen zu legen.
Wir sind nur auf 4 Lösungen gekommen.
1. 10 x 100 Euro
2. 8 x 50 Euro + 100 Euro + 500 Euro
3. 5 x 20 + 4 x 100 + 500
4. 2 x 10 + 4 x 20 + 2 x 50 + 100 + 200
Hat jemand weitere Ideen? Da gibt es doch sicher einen Trick . Danke
|
 Profil
|
wladimir_1989
Senior 
Dabei seit: 23.12.2014
Mitteilungen: 1688
Wohnort: Freiburg
| Beitrag No.1, eingetragen 2018-02-16
|
Hallo KiliZahl und willkommen auf dem Matheplaneten,
deine vier Lösungen enthalten aber jeweils nur 10 Scheine und keine 19.
lg Wladimir
|
Profil
|
PrinzessinEinhorn
Senior
Dabei seit: 23.01.2017
Mitteilungen: 2625
 | Beitrag No.2, eingetragen 2018-02-16
|
@Wladimir:
Das ist ein Tippfehler. Es ist so gemeint wie im Thementitel. Daher mit 10 Scheinen.
@Kilizahl: Eure vierte Lösung passt leider nicht.
|
Profil
|
wladimir_1989
Senior
Dabei seit: 23.12.2014
Mitteilungen: 1688
Wohnort: Freiburg
| Beitrag No.3, eingetragen 2018-02-16
|
@Prinzessin: Danke, ist mir auch gerade aufgefallen.
@KiliZahl eine weitere Kombination: 1 mal 500, 2 mal 200, 4 mal 20 1 mal 10 2 mal 5
lg Wladimir
|
Profil
|
Orthonom
Wenig Aktiv
Dabei seit: 02.09.2010
Mitteilungen: 574
| Beitrag No.4, eingetragen 2018-02-16
|
Wie wärs mit 4*200, 1*100 und 5*20?
|
Profil
|
Orthonom
Wenig Aktiv 
Dabei seit: 02.09.2010
Mitteilungen: 574
| Beitrag No.5, eingetragen 2018-02-16
|
Wie wärs mit 1*500, 2*200,1*50,1*20,1*10 und 4*5?
|
Profil
|
mint
Ehemals Aktiv
Dabei seit: 20.05.2011
Mitteilungen: 554
| Beitrag No.6, eingetragen 2018-02-16
|
Hi,
man kann das ganze auch etwas systematischer angehen: ausgehend von der 10*100 Lösung, kann man eine weiter produzieren, in dem man einen 100er durch zwei 50er ersetzt, und dafür dann noch zwei weitere 100er durch einen 200er ersetzt. Man kann sich verschiedene Ersetzungen überlegen, die sowohl die Gesamtsumme als auch die Anzahl der Scheine unverändert lässt.
Viele Grüße
mint
[Die Antwort wurde nach Beitrag No.3 begonnen.]
|
Profil
|
Kuestenkind
Senior
Dabei seit: 12.04.2016
Mitteilungen: 2570
| Beitrag No.7, eingetragen 2018-02-16
|
\quoteon(2018-02-16 17:22 - KiliZahl im Themenstart)
Da gibt es doch sicher einen Trick.
\quoteoff
Huhu,
ich kenne mich mit Grundschuldidaktik nicht wirklich aus, aber ich denke, hier soll einfach die Addition "intelligent" geübt werden. Ich denke nicht, dass ein Drittklässler hier irgendein Trick erkennen soll (aber kann). Sinn der Aufgabe ist es wohl viele Additionsaufgaben möglichst schnell eben im Kopf durchzuführen und ein "Gefühl" für Zahlen zu bekommen.
Gruß,
Küstenkind
PS: 7 mal 100 , 1 mal 200 und 2 mal 50 tut es wohl auch.
[Die Antwort wurde nach Beitrag No.4 begonnen.]
|
Profil
|
Orthonom
Wenig Aktiv
Dabei seit: 02.09.2010
Mitteilungen: 574
| Beitrag No.8, eingetragen 2018-02-16
|
Wie wärs mit 2*5, 2*10, 1*20, 1*50, 2*100, 1*200 und 1*500.
EineLösung in der jeder Schein mindestens einmal vorkommt.
Man kann sich selber einen Algorithmus basteln, wie man auf alle
Lösungen kommt oder aber einfach kreativ sein.
Gruß Orthonom
[Die Antwort wurde nach Beitrag No.5 begonnen.]
|
Profil
|
KiliZahl
Neu
Dabei seit: 16.02.2018
Mitteilungen: 2
| Beitrag No.9, vom Themenstarter, eingetragen 2018-02-16
|
Vielen Dank für die vielen Antworten in so kurzer Zeit! Und sorry, ja die 19 war tatsächlich ein Schreibfehler:-)
|
Profil
|
GrafZahl
Senior
Dabei seit: 22.04.2003
Mitteilungen: 1456
Wohnort: Leverkusen, D
 | Beitrag No.10, eingetragen 2018-02-16
|
\quoteon(2018-02-16 18:05 - Orthonom in Beitrag No. 8)
Wie wärs mit 2*5, 2*10, 1*20, 1*50, 2*100, 1*200 und 1*500.
EineLösung in der jeder Schein mindestens einmal vorkommt.
Man kann sich selber einen Algorithmus basteln, wie man auf alle
Lösungen kommt oder aber einfach kreativ sein.
Gruß Orthonom
[Die Antwort wurde nach Beitrag No.5 begonnen.]
\quoteoff
Streng genommen, die einzige Lösung, in der jeder Schein mindestens einmal vorkommt( bei einer Gesamtanzahl von 10)
MfG
Graf Zahl
|
Profil
|
mint
Ehemals Aktiv
Dabei seit: 20.05.2011
Mitteilungen: 554
| Beitrag No.11, eingetragen 2018-02-16
|
Es gibt übrigens insgesamt 25 Zerlegungen die den Kriterien entsprechen :-)
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
 | Beitrag No.12, eingetragen 2018-02-16
|
\quoteon(2018-02-16 19:09 - mint in Beitrag No. 11)
Es gibt übrigens insgesamt 25 Zerlegungen die den Kriterien entsprechen :-)
\quoteoff
Exakt, nämlich
$[[100, 100, 100, 100, 100, 100, 100, 100, 100, 100],
[200, 100, 100, 100, 100, 100, 100, 100, 50, 50],
[200, 200, 100, 100, 100, 100, 50, 50, 50, 50],
[200, 200, 200, 100, 50, 50, 50, 50, 50, 50],
[200, 200, 200, 100, 100, 100, 50, 20, 20, 10],
[200, 200, 200, 200, 50, 50, 50, 20, 20, 10],
[200, 200, 200, 200, 100, 20, 20, 20, 20, 20],
[200, 200, 200, 200, 100, 50, 20, 10, 10, 10],
[200, 200, 200, 200, 100, 50, 20, 20, 5, 5],
[500, 100, 50, 50, 50, 50, 50, 50, 50, 50],
[500, 100, 100, 100, 50, 50, 50, 20, 20, 10],
[500, 100, 100, 100, 100, 20, 20, 20, 20, 20],
[500, 100, 100, 100, 100, 50, 20, 10, 10, 10],
[500, 100, 100, 100, 100, 50, 20, 20, 5, 5],
[500, 200, 50, 50, 50, 50, 50, 20, 20, 10],
[500, 200, 100, 50, 50, 20, 20, 20, 20, 20],
[500, 200, 100, 50, 50, 50, 20, 10, 10, 10],
[500, 200, 100, 50, 50, 50, 20, 20, 5, 5],
[500, 200, 100, 100, 20, 20, 20, 20, 10, 10],
[500, 200, 100, 100, 50, 10, 10, 10, 10, 10],
[500, 200, 100, 100, 50, 20, 10, 10, 5, 5],
[500, 200, 200, 20, 20, 20, 10, 10, 10, 10],
[500, 200, 200, 20, 20, 20, 20, 10, 5, 5],
[500, 200, 200, 50, 10, 10, 10, 10, 5, 5],
[500, 200, 200, 50, 20, 10, 5, 5, 5, 5]]$
Edit: Falls es jemanden interessiert, nachfolgend auch noch mein Maple-Programm dazu. Es basiert auf einer Breitensuche auf einem Wurzelbaum mit der Wurzel [[]], also einer Liste bestehend nur aus der leeren Liste, wobei zu noch unvollständigen Listen jeweils ein neues Element aus der Liste G der Geldbeträge hinzugefügt wird, welches einerseits nicht größer als das letzte Listenelement, andererseits aber auch nicht zu klein ist, sodass damit überhaupt noch eine Lösung entstehen kann (s.u.).
Andere Vorschläge der Implementierung wären durchaus interessant, auch wenn die Rechenzeit (auf meinem Rechner 16ms oder sogar darunter!) schwer zu unterbieten sein dürfte. Denkbar wäre z.B. auch eine doppelte Rekursion über b und n, was dann möglicherweise ein sehr kurzes Programm ergeben könnte.
\sourceon Maple
geld:=proc(n:=10,b:=1000)
local a,g,G:=[5,10,20,50,100,200,500],s,S:=[[]],T,X:=[];
do
T:=[];
for s in S do
a:=add(s_,s_ in s);
if nops(s)>n or a>b then next end if;
if a=b then
if nops(s)=n then X:=[op(X),s] end if;
next
end if;
for g in G do
if (s=[] or g<=s[-1]) and a+(n-nops(s))*g>=b then
T:=[op(T),[op(s),g]]
end if;
end do
end do;
S:=T; if S=[] then return X end if
end do
end:
\sourceoff
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.13, eingetragen 2018-02-17
|
Ich habe mein letztes Posting noch um mein Programm, mit dem ich die dort angegebene Lösung ermittelt hatte, ergänzt. Wie gesagt wäre ich persönlich sehr an alternativen Programmen bzw. auch Algorithmen zu dem angesprochenen Thema interessiert, soferne sie nicht allzu sehr auf brute force hinauslaufen, d.h., der Rechenaufwand dafür noch einigermaßen akzeptabel bleibt. :-D
|
Profil
|
gonz
Senior 
Dabei seit: 16.02.2013
Mitteilungen: 4743
Wohnort: Harz
 | Beitrag No.14, eingetragen 2018-02-17
|
PS.: Ich nehme an, dass der Algo den ich angepeilt habe genau der von weird codierte ist
Da es mir nicht um eine Optimierung der Laufzeit ging, habe ich es relativ platt nach etwa folgendem Schema programmiert:
Alle Kombinationen von 10 Scheinen, die 1000 ergeben findet man, indem man
1x500 + Alle Kombinationen von 9 Scheinen, die 500 ergeben,
und
1x200 + Alle Kombinationen von 9 Scheinen, die 800 ergeben, und keine 500er enthalten,
und
1x100 + Alle Kombinationen von 9 Scheinen, die 900 ergeben und weder "500"er noch "200" er enthalten ( davon gibt es genau eine, nämlich 10x100).
( der größte Schein muss 100 sein, da 10x50 < 1000 ist und es entsprechend keine Kombinationen gibt, die weder 500 noch 200 noch 100 enthalten )
ich glaube man sieht wie es weitergeht. Wenn man davon ausgehen, dass sich über die 10 Scheine die Anzahl der Wege im Mittel zB verfünffacht, der letzte Schein festliegt, sowie der erste eben nur zwei zu untersuchende Varianten zuläßt, wäre man bei unter einer Million Zweige.
Ich habe dann weil es ja schon ein Ergebnis gab das Ganze nicht mehr fertiggemacht. Der Algo ist natürlich "Brute force" und wahrscheinlich einfach das erste, was einem so einfällt :)
Das Verfahren wäre natürlich auch dafür geeignet, die geforderte Anzahl an Kombinationen manuell auszuknobeln...
Grüsse
gonz
|
Profil
|
nullptr
Ehemals Aktiv
Dabei seit: 17.12.2016
Mitteilungen: 62
| Beitrag No.15, eingetragen 2018-02-17
|
Die Anzahl der Möglichkeiten kann man mit dynamischer Programmierung über den Geldbetrag und die Anzahl der Scheine ausrechnen.
Im folgenden Programm ist $dp[n][k]$ die Anzahl der Möglichkeiten, $n$ Euro mit genau $k$ Scheinen zu bezahlen. Dabei werden erst nur 5-Euro-Scheine, dann auch 10-Euro-Scheine, 20-Euro-Scheine, ... betrachtet und immer mindestens ein Schein benutzt.
\sourceon C++
int gsize = 7;
int g[gsize] = { 5, 10, 20, 50, 100, 200, 500 };
int maxn = 1000, maxk = 10;
int dp[maxn + 1][maxk + 1];
fill(dp[0], dp[0] + (maxn + 1) * (maxk + 1), 0);
dp[0][0] = 1;
for (int i = 0; i < gsize; ++i) {
for (int n = g[i]; n <= maxn; ++n) {
for (int k = 1; k <= maxk; ++k) {
dp[n][k] += dp[n - g[i]][k - 1];
}
}
}
cout << dp[maxn][maxk] << endl; // 25
\sourceoff
Interessant wäre, ob es einen viel effizienteren Algorithmus (Laufzeit nicht proportional zu $n$, sondern z.B. zu $\log{n}$) gibt. Wenn man das Problem in diesem Thread leicht verändert (nicht genau $k$ Scheine, sondern höchstens $k$ Scheine), dann sieht es nicht danach aus. Das change-making problem ist nämlich NP-schwer und wir könnten das kleinstmögliche $k$ mit einer Binärsuche in Zeit $\mathcal{O}(\log{n})$ finden.
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.16, eingetragen 2018-02-17
|
@gonz
Vielen Dank für deinen Beitrag! Der von dir beschriebene Algorithmus macht meiner Meinung nach von einer doppelten Rekursion nach der Anzahl $n$ der Scheine und dem Geldbetrag $b$ Gebrauch. In Maple würde das so wie unten aussehen und liefert dann auch wieder in 15ms das gleiche Ergebnis wie zuvor. Allerdings ist das Programm etwa gleich lang geblieben und ohne die option remember, mit der es sich Maple das Ergebnis von früheren rekursiven Aufrufen merkt, wäre es auch mit 37.5 s erheblich langsamer. Insgesamt ist es also keine Verbesserung gegenüber meinem Programm in #12.
\sourceon Maple
argent:=proc(n:=10,b:=1000)
option remember;
local g,G:=[5,10,20,50,100,200,500],s,S,T:=[];
if n=1 then
if b in G then return [[b]] else return [] end if
end if;
for g in G do
if g>=b then next end if;
S:=argent(n-1,b-g);
for s in S do
if g>s[-1] then next end if;
if g+add(s_,s_ in s)=b then T:=[op(T),[op(s),g]] end if
end do
end do;
return T
end:
\sourceoff
@nullptr
Auch du benutzt ja offensichtlich den rekursiven Zugang, allerdings dann nur für die Berechnung der Anzahl Lösungen und nicht für die Lösungen selber, was jetzt nicht allzuviel aufwändiger gewesen wäre wie das obige Programm zeigt. Interessant auch deine Anmerkungen zur Komplexität von diesem und ähnlichen Problemen. Vielen Dank auch dir!
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4743
Wohnort: Harz
| Beitrag No.17, eingetragen 2018-02-18
|
\quoteon(2018-02-17 21:37 - weird in Beitrag No. 16)
Der von dir beschriebene Algorithmus macht meiner Meinung nach von einer doppelten Rekursion nach der Anzahl $n$ der Scheine und dem Geldbetrag $b$ Gebrauch.
\quoteoff
Ja, wobei ich auch die bisher festgelegte Aufteilung für die ersten Scheine mitgebe, einmal um am Ende die Folge komplett ausgeben zu können, wenn im letzten Rekursionsschritt erkannt wird, dass sie gültig ist, und auch, da der nächste auszuwählende Schein nicht grösser sein soll als der letzte schon festgelegte. Durch diese Bedingung wird auch erreicht, dass jede Lösung nur einmal gefunden wird. Vielleicht mache ich das ganze doch dann mal fertig ist ein kleines nettes C Programm.
Grüsse erstmal und einen schönen Sonntag
gonz
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.18, eingetragen 2018-02-18
|
\quoteon(2018-02-18 09:58 - gonz in Beitrag No. 17)
Ja, wobei ich auch die bisher festgelegte Aufteilung für die ersten Scheine mitgebe, einmal um am Ende die Folge komplett ausgeben zu können, wenn im letzten Rekursionsschritt erkannt wird, dass sie gültig ist, und auch, da der nächste auszuwählende Schein nicht grösser sein soll als der letzte schon festgelegte. Durch diese Bedingung wird auch erreicht, dass jede Lösung nur einmal gefunden wird. Vielleicht mache ich das ganze doch dann mal fertig ist ein kleines nettes C Programm.
\quoteoff
Vielleicht täusche ich mich, aber ich glaube genau in meinem Programm in #16 genau das gemacht zu haben, was du oben beschrieben hast. Aber ja, schreib noch deine eigene Programmversion, damit man das noch besser vergleichen kann. ;-)
Ich selbst habe in der Zwischenzeit auch noch eine weitere Version geschrieben, von der ich hoffe, dass sie vor allem die Kombinatoriker, welche gerne mit erzeugenden Funktionen arbeiten, so entzücken wird, dass sie hörbar mit der Zunge schnalzen wie bei der Verkostung eines besonders edlen Tropfen Weines, zumal auch die Rechenzeit noch durchaus akzeptabel ist. :-D
\sourceon Maple
zaster:=proc(n:=10,b:=1000)
local g,G:=[5,10,20,50,100,200,500],p:=1,s;
for g in G do
p:=rem(p*add((s[g]*y^g*x)^k,k=0..floor(b/g)),x^(n+1),x);
p:=rem(p,y^(b+1),y)
end do;
limit(limit(p/x^n,x=infinity)/y^b,y=infinity)
end:
t:=time():zaster(10,1000);(time()-t)*'s'
4 2
s[5] s[10] s[20] s[50] s[200] s[500]
2 4 2
+ s[5] s[10] s[50] s[200] s[500]
2 2 2
+ s[5] s[10] s[20] s[50] s[100] s[200] s[500]
2 4 2
+ s[5] s[10] s[20] s[200] s[500]
2 2 3
+ s[5] s[20] s[50] s[100] s[200] s[500]
2 2 4
+ s[5] s[20] s[50] s[100] s[500]
2 2 4
+ s[5] s[20] s[50] s[100] s[200]
5 2
+ s[10] s[50] s[100] s[200] s[500]
4 3 2
+ s[10] s[20] s[200] s[500]
3 3
+ s[10] s[20] s[50] s[100] s[200] s[500]
3 4
+ s[10] s[20] s[50] s[100] s[500]
3 4
+ s[10] s[20] s[50] s[100] s[200]
2 4 2
+ s[10] s[20] s[100] s[200] s[500]
2 5
+ s[10] s[20] s[50] s[200] s[500]
2 3 3
+ s[10] s[20] s[50] s[100] s[500]
2 3 4
+ s[10] s[20] s[50] s[200]
2 3 3
+ s[10] s[20] s[50] s[100] s[200]
5 2 5 4
+ s[20] s[50] s[100] s[200] s[500] + s[20] s[100] s[500]
5 4 8
+ s[20] s[100] s[200] + s[50] s[100] s[500]
6 3 4 4 2
+ s[50] s[100] s[200] + s[50] s[100] s[200]
2 7 10
+ s[50] s[100] s[200] + s[100]
3.735 s
\sourceoff
Was die Ausgabe betrifft, so sollte diese meiner Meinung nach "self-explanatory" sein. Das Polynom in den Variablen $s[5],s[10],...,s[500]$ repräsentiert mit seinen 25 Monomen genau die 25 Lösungen, wobei man z.B. das erste Monom als die Lösung $[5,5,5,5,10,20,50,200,200,500]$ interpretieren muss.
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4743
Wohnort: Harz
| Beitrag No.19, eingetragen 2018-02-18
|
Ja, ich denke auch dass wir genau das gleiche machen. Trotzdem der Vollständigkeit halber...
\sourceon C
#include
#define N 10
#define S 1000
int festgelegt[N];
#define scheinzahl 7
int scheine[scheinzahl]={5,10,20,50,100,200,500};
void ausgabe() {
int loop;
for (loop=N-1;loop>=0;loop--)
printf("%i,",festgelegt[loop]);
printf("\n");
}
void do_next_schein(int betrag, int anzahl, int max_schein) {
int now_schein;
for (now_schein=max_schein;now_schein>=0;now_schein--) {
if (anzahl==1) {
if (scheine[now_schein]==betrag) {
// passt und habe fertig
festgelegt[0]=scheine[now_schein];
ausgabe();
}
} else {
if (betrag>scheine[now_schein]) {
festgelegt[anzahl-1]=scheine[now_schein];
do_next_schein(betrag-scheine[now_schein],anzahl-1,now_schein);
}
}
}
}
int main() {
do_next_schein(S,N,scheinzahl-1);
}
\sourceoff
Ausgabe ( Zeit habe ich nicht gemessen, die Ergebnisse werden quasi instantan ausgeworfen )
\sourceon plain ascii text
500,200,200,50,20,10,5,5,5,5,
500,200,200,50,10,10,10,10,5,5,
500,200,200,20,20,20,20,10,5,5,
500,200,200,20,20,20,10,10,10,10,
500,200,100,100,50,20,10,10,5,5,
500,200,100,100,50,10,10,10,10,10,
500,200,100,100,20,20,20,20,10,10,
500,200,100,50,50,50,20,20,5,5,
500,200,100,50,50,50,20,10,10,10,
500,200,100,50,50,20,20,20,20,20,
500,200,50,50,50,50,50,20,20,10,
500,100,100,100,100,50,20,20,5,5,
500,100,100,100,100,50,20,10,10,10,
500,100,100,100,100,20,20,20,20,20,
500,100,100,100,50,50,50,20,20,10,
500,100,50,50,50,50,50,50,50,50,
200,200,200,200,100,50,20,20,5,5,
200,200,200,200,100,50,20,10,10,10,
200,200,200,200,100,20,20,20,20,20,
200,200,200,200,50,50,50,20,20,10,
200,200,200,100,100,100,50,20,20,10,
200,200,200,100,50,50,50,50,50,50,
200,200,100,100,100,100,50,50,50,50,
200,100,100,100,100,100,100,100,50,50,
100,100,100,100,100,100,100,100,100,100,
\sourceoff
|
Profil
| | Folgende Antworten hat der Fragensteller vermutlich noch nicht gesehen. |
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.20, eingetragen 2018-02-18
|
@gonz
Ja, dürfte sehr ähnlich meinem Programm in #16 mit der doppelten Rekursion sein. Schade, dass ein Zeitvergleich nicht möglich war.
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4743
Wohnort: Harz
| Beitrag No.21, eingetragen 2018-02-18
|
och, das lässt sich ja noch machen :) werd mal heute abend die zeit stoppen :)
Es gibt auch sicher noch Verbesserungen, zB dass der Restbetrag kleiner oder gleich dem Produkt aus max. zu nutzendem Schein und der verbleibenden Scheinzahl sein muss, genauso wie man aufhören kann, wenn die verbleibende Summe kleiner als das 5-fache der verbleibenen Scheinzahl ist. Da kann ich gleich mal nachmessen ob und was das noch bringt.
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4743
Wohnort: Harz
| Beitrag No.22, eingetragen 2018-02-18
|
Ok, die Laufzeit des Programms ist ( auf einem handelsüblichen Server ) kleiner als 0.2 ms. Durch die oben schon angedachte Verbesserung
anstatt bisher:
if (betrag>scheine[now_schein]) {
nun:
if (betrag>=scheine[now_schein]+scheine[0]*(anzahl-1))
if (betrag<=scheine[now_schein]*anzahl)
verringert sich die Laufzeit auf 0.12 ms, von denen ein Grossteil für die Ausgabe der gefundenen Daten draufgeht, das eigentliche Rechenwerk braucht weniger als 0.01 ms. Die Zeit für die Ausgaben ist bei mir recht hoch, da sie über ein remote terminal erfolgt.
Die Änderung bewirkt, dass der aktuell verbliebene Betrag nicht höher sein kann, als durch Auffüllen der verbleibenden Scheine mit dem gewählten Anfangsschein möglich wäre, und nicht kleiner sein darf, als man durch Auffüllen mit dem gewählten Schein und nachfolgend lauter 5ern erreichen kein.
Eine nette Sache das Ganze :)
Grüsse
gonz
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4743
Wohnort: Harz
| Beitrag No.23, eingetragen 2018-02-18
|
Noch ein Nachtrag:
Ich habe einfach mal zählen lassen, wie oft die Funktion do_next_schein aufgerufen wird, und bin auf 150 gekommen ( mit der Version ohne die oben genannte Verbesserung waren es 6601 mal). Das ist ziemlich optimal, das Programm steuert offenbar recht direkt auf die Lösungen zu. Ich denke entsprechend nicht, dass man den Algo noch sehr verbessern kann.
Grüsse
gonz
|
Profil
|
weird
Senior
Dabei seit: 16.10.2009
Mitteilungen: 5301
| Beitrag No.24, eingetragen 2018-02-18
|
@gonz
Ja, wie erwartet lässt sich das dann natürlich bei einem optimierten Algorithmus, implementiert in C und das vermutlich auch noch auf einem sehr schnellen Rechner, dann nicht mehr toppen! Danke, dass du nun auch noch meinem Wunsch nach einer Zeitmessung nachgekommen bist. ;-)
|
Profil
|
digerdiga
Wenig Aktiv
Dabei seit: 15.11.2006
Mitteilungen: 1389
| Beitrag No.25, eingetragen 2018-02-18
|
Hallo ihr,
Ich hab mal große Teile gelöscht, weil es doch etwas umständlich war.
Letztendlich war es nichts anderes als Folgendes:
Die Gleichung
\[ 5n_5 + 10n_{10} + 20n_{20} + 50n_{50} + 100n_{100} + 200n_{200} + 500n_{500} - 1000 = 0 \]
soll über $\IN$ unter der Nebenbedingung
\[ n_5 + n_{10} + n_{20} + n_{50} + n_{100} + n_{200} + n_{500} - 10 = 0 \]
gelöst werden. Auflösen Letzterer nach $n_5$ und einsetzen in Erstere liefert zunächst
\[ 5n_{10} + 15 n_{20} + 45n_{50} + 95 n_{100} + 195n_{200} + 495n_{500} = 950 \]
also
\[ \begin{pmatrix} n_5 \\ n_{10} \\ n_{20} \\ n_{50} \\ n_{100} \\ n_{200} \\ n_{500} \end{pmatrix} = \begin{pmatrix} -180 + 2 n_{20} + 8n_{50} + 18n_{100} + 38n_{200} + 98n_{500} \\ 190 - 3n_{20} - 9n_{50} - 19n_{100} - 39n_{200} - 99n_{500} \\ n_{20} \\ n_{50} \\ n_{100} \\ n_{200} \\ n_{500} \end{pmatrix}
\]
und man muss genau $11 \cdot 11 \cdot 11 \cdot 6 \cdot 2 = 15972$ Fälle durchgehen, also letztlich brute force...31ms
Alternativ hab ich mir die Frage gestellt, ob man das Problem als Pivotverfahren formulieren kann (und die Lösungen dann iterativ durchgeht), oder geht das nur für Optimierungen?
[Die Antwort wurde nach Beitrag No.20 begonnen.]
|
Profil
|
| KiliZahl wird per Mail über neue Antworten informiert. |
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
