Die Mathe-Redaktion - 20.06.2018 05:47 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktAnmeldung MPCT Juli
ListenpunktFormeleditor fedgeo
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 277 Gäste und 6 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von viertel GrafZahl
Schulmathematik » Stochastik und Kombinatorik » 1000 Euro in genau 10 Scheinen legen
Druckversion
Druckversion
Antworten
Antworten
Autor
Schule 1000 Euro in genau 10 Scheinen legen
KiliZahl
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 16.02.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
wladimir_1989
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.12.2014
Mitteilungen: 1072
Aus: Freiburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
PrinzessinEinhorn
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2017
Mitteilungen: 1337
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
wladimir_1989
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.12.2014
Mitteilungen: 1072
Aus: Freiburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
Orthonom
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.09.2010
Mitteilungen: 270
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-02-16


Wie wärs mit 4*200, 1*100 und 5*20?



  Profil  Quote  Link auf diesen Beitrag Link
Orthonom
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.09.2010
Mitteilungen: 270
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
mint
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2011
Mitteilungen: 551
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 952
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2018-02-16


2018-02-16 17:22 - KiliZahl im Themenstart schreibt:
Da gibt es doch sicher einen Trick.

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  Quote  Link auf diesen Beitrag Link
Orthonom
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 02.09.2010
Mitteilungen: 270
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
KiliZahl
Neu Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 16.02.2018
Mitteilungen: 2
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
GrafZahl
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 22.04.2003
Mitteilungen: 1446
Aus: Leverkusen, D
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-02-16


2018-02-16 18:05 - Orthonom in Beitrag No. 8 schreibt:
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.]

Streng genommen, die einzige Lösung, in der jeder Schein mindestens einmal vorkommt( bei einer Gesamtanzahl von 10)

MfG
Graf Zahl



  Profil  Quote  Link auf diesen Beitrag Link
mint
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 20.05.2011
Mitteilungen: 551
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2018-02-16


Es gibt übrigens insgesamt 25 Zerlegungen die den Kriterien entsprechen  smile



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4042
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-02-16

\(\begingroup\)
2018-02-16 19:09 - mint in Beitrag No. 11 schreibt:
Es gibt übrigens insgesamt 25 Zerlegungen die den Kriterien entsprechen  smile

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.

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:
 
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4042
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.  biggrin



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2784
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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




-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
nullptr
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.12.2016
Mitteilungen: 46
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2018-02-17

\(\begingroup\)
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.
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

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.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4042
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2018-02-17

\(\begingroup\)
@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.
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: 

@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!
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2784
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2018-02-18

\(\begingroup\)
2018-02-17 21:37 - weird in Beitrag No. 16 schreibt:
Der von dir beschriebene Algorithmus macht meiner Meinung nach von einer doppelten Rekursion nach der Anzahl $n$ der Scheine und dem Geldbetrag $b$ Gebrauch.

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






-----------------
to fight! (Don Quijote de la Mancha)
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4042
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2018-02-18

\(\begingroup\)
2018-02-18 09:58 - gonz in Beitrag No. 17 schreibt:
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.

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.  wink

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.   biggrin  

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

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.
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2784
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2018-02-18


Ja, ich denke auch dass wir genau das gleiche machen. Trotzdem der Vollständigkeit halber...
C
#include <stdio.h>
#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);
}
 

Ausgabe ( Zeit habe ich nicht gemessen, die Ergebnisse werden quasi instantan ausgeworfen )
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,



-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4042
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2784
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2784
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2784
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 4042
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  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.  wink



  Profil  Quote  Link auf diesen Beitrag Link
digerdiga
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 15.11.2006
Mitteilungen: 1222
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2018-02-18

\(\begingroup\)
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.]
\(\endgroup\)


  Profil  Quote  Link auf diesen Beitrag Link
KiliZahl wird per Mail über neue Antworten informiert.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]