Wechselgeld 5 besten Kombinationen



  • @wob sagte in Wechselgeld 5 besten Kombinationen:

    @codinglea Hast du schon mal was von "Array" gehört? Das kann doch niemand ernsthaft lesen und überprüfen. Und was, wenn du jetzt keinen 20-Schein mehr hast? Oder wenn ein neuer 30er-Schein eingeführt wird?

    Das hat wade ihm eingeredet. Ist eine Kopie der schrecklichen "Lösung", die er ihm verlinkt hat.



  • @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    @wob sagte in Wechselgeld 5 besten Kombinationen:

    @codinglea Hast du schon mal was von "Array" gehört? Das kann doch niemand ernsthaft lesen und überprüfen. Und was, wenn du jetzt keinen 20-Schein mehr hast? Oder wenn ein neuer 30er-Schein eingeführt wird?

    Das hat wade ihm eingeredet. Ist eine Kopie der schrecklichen "Lösung", die er ihm verlinkt hat.

    tja die art und weise, in der jemand nach 2 monaten programmieren kann, unterscheidet sich eben etwas von der, in der jemand nach 5 jahren programmieren kann, aber das raffen manche ja nicht.

    ps: ihr 😃



  • @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    tja die art und weise, in der jemand nach 2 monaten programmieren kann, unterscheidet sich eben etwas von der, in der jemand nach 5 jahren programmieren kann, aber das raffen manche ja nicht.

    Verarscht du dich grad selbst oder wie wird da ein Schuh draus?



  • @hustbaer sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    tja die art und weise, in der jemand nach 2 monaten programmieren kann, unterscheidet sich eben etwas von der, in der jemand nach 5 jahren programmieren kann, aber das raffen manche ja nicht.

    Verarscht du dich grad selbst oder wie wird da ein Schuh draus?

    naja

    • rekursion ist ein thema für fortgeschrittene
    • die erfahrung, dass da 15 schleifen verschachtelt werden, dürfte nicht unwichtig sein
    • erst "schlecht" programmieren und sich dann "verbessern" ist deutlich motivierender, als alles von vornherein "perfekt" machen zu müssen
    • aus den 15 verschachtelten schleifen lässt sich die rekursionsvorschrift ganz toll ablesen

  • Gesperrt

    "Haushaltsangemessene" Stückelungen nennt man das auch. Für mich wären zum Beispiel die 10 besten Aufteilungen, um 499 € auszuzahlen, folgende:

    #include <iostream>
    #include <vector>
    
    int werte[8] = {500, 100, 50, 20, 10, 5, 2, 1};
    
    int getNext(std::vector<int> &wvec, int idx, long sum)
    {
        if (sum == 0)
            return 1;
        for (size_t i = idx; i < 8; i++)
        {
            sum -= werte[i];
            if (sum >= 0)
            {
                wvec.push_back(i);
                if (getNext(wvec, i, sum))
                {
                    return 1;
                }
                wvec.pop_back();
            }
            sum += werte[i];
        }
        return 0;
    }
    
    int main()
    {
        std::vector<int> wvec;
        wvec.push_back(0);
        for (size_t j = 0; j < 10; j++)
        {
            size_t i = 1;
            for (; i < wvec.size(); i++)
            {
                if (wvec[i - 1] != wvec[i])
                {
                    wvec[i - 1]++;
                    wvec.resize(i);
                }
            }
            std::cout << getNext(wvec, wvec[i - 1], 499) << std::endl;
            for (size_t i = 0; i < wvec.size(); i++)
            {
                std::cout << werte[wvec[i]] << " ";
            }
            std::cout << std::endl;
        }
        return 0;
    }
    
    1
    500 100 100 100 100 50 20 20 5 2 2
    1
    100 100 100 100 100 50 20 20 5 2 2
    1
    100 100 100 100 50 50 50 50 50 50 50 50 50 50 20 20 5 2 2
    1
    100 100 100 50 50 50 50 50 50 50 50 50 50 20 20 5 2 2
    1
    100 100 50 50 50 50 50 50 50 50 50 50 20 20 5 2 2
    1
    100 50 50 50 50 50 50 50 50 50 50 20 20 5 2 2
    1
    50 50 50 50 50 50 50 50 50 50 20 20 5 2 2
    1
    50 50 50 50 50 50 50 50 50 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 10 5 2 2
    1
    50 50 50 50 50 50 50 50 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 10 5 2 2
    1
    50 50 50 50 50 50 50 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 10 5 2 2
    

    Stimmt das mit euren Vermutungen überein? (Ach so, und bei mir gibt es keine 200-€-Scheine. 😞 )



  • @EinNutzer0
    Ich nehm die Auszahlung mit dem 500 Euro Schein, wenn ich nächstes Mal 499 Euro abheben. 😉


  • Gesperrt

    @TGGC sagte in Wechselgeld 5 besten Kombinationen:

    Ich nehm die Auszahlung mit dem 500 Euro Schein, wenn ich nächstes Mal 499 Euro abheben.

    Sorry, ist mir auch gerade aufgefallen. 😉 Man muss natürlich den übrigen Betrag nehmen:

    #include <iostream>
    #include <vector>
    
    int werte[8] = {500, 100, 50, 20, 10, 5, 2, 1};
    
    int getNext(std::vector<int> &wvec, int idx, long sum)
    {
        if (sum == 0)
            return 1;
        for (size_t i = idx; i < 8; i++)
        {
            sum -= werte[i];
            if (sum >= 0)
            {
                wvec.push_back(i);
                if (getNext(wvec, i, sum))
                {
                    return 1;
                }
                wvec.pop_back();
            }
            sum += werte[i];
        }
        return 0;
    }
    
    int main()
    {
        std::vector<int> wvec;
        for (size_t j = 0; j < 10; j++)
        {
            size_t i = 1;
            for (; i < wvec.size(); i++)
            {
                if (wvec[i - 1] != wvec[i])
                {
                    wvec[i - 1]++;
                    wvec.resize(i);
                }
            }
            if (j == 0)
                std::cout << getNext(wvec, 0, 499) << std::endl;
            else
            {
                long sum = 0;
                for (size_t i = 0; i < wvec.size(); i++)
                {
                    sum += werte[wvec[i]];
                }
                std::cout << getNext(wvec, wvec[i - 1], 499 - sum) << std::endl;
            }
            for (size_t i = 0; i < wvec.size(); i++)
            {
                std::cout << werte[wvec[i]] << " ";
            }
            std::cout << std::endl;
        }
        return 0;
    }
    

    Jetzt ist die main Funktion nur sehr unübersichtlich.



  • @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    #include <iostream>
    #include <vector>
    std::vector<int>
    std::cout

    dies ist das c-unterforum. da läuft das alles ein bisschen anders. die zeiten, in denen c++ sowas wie "c mit erweiterungen" war, sind seit bestimmt 20 jahren vorbei.


  • Gesperrt

    @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    #include <iostream>
    #include <vector>
    std::vector<int>
    std::cout

    dies ist das c-unterforum. da läuft das alles ein bisschen anders.

    Mea culpa 😞 (Wollte es eben gleich richtig zeigen.)

    Edit: Aber nehmen wir mal 49 € Auszahlung her, dann wären das:

    1
    20 20 5 2 2
    1
    20 10 5 5 5 2 2
    1
    10 10 10 10 5 2 2
    1
    10 10 10 5 5 5 2 2
    1
    10 10 5 5 5 5 5 2 2
    1
    10 5 5 5 5 5 5 5 2 2
    1
    5 5 5 5 5 5 5 5 5 2 2
    1
    5 5 5 5 5 5 5 5 2 2 2 2 1
    1
    5 5 5 5 5 5 5 2 2 2 2 2 2 2
    1
    5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 1
    

    mMn. "veritable" Aufteilungen.



  • @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    rekursion ist ein thema für fortgeschrittene

    Das haben wir damals sogar in der Schule im Informatikunterricht gelernt, und zwar ungefähr ganz am Anfang, gleich nachdem wir Funktionen hatten. Klasse 11, erstes Halbjahr. Definitiv auch für Anfänger geeignet.

    die erfahrung, dass da 15 schleifen verschachtelt werden, dürfte nicht unwichtig sein

    Die braucht man nicht zu machen. Schon bei 4 Schleifen wäre das für mich zu viel Arbeit.

    erst "schlecht" programmieren und sich dann "verbessern" ist deutlich motivierender, als alles von vornherein "perfekt" machen zu müssen

    Dem stimme ich zu. Aber man braucht es mit so vielen Verschachtelungen nicht zu übertreiben, um zu sehen, dass das nicht flexibel und viel Arbeit ist.

    aus den 15 verschachtelten schleifen lässt sich die rekursionsvorschrift ganz toll ablesen

    Das ist so unübersichtlich, dass ich da gar nichts mehr ablesen kann.



  • @EinNutzer0 sagte in Wechselgeld 5 besten Kombinationen:

    (Wollte es eben gleich richtig zeigen.)

    also wenn ich mir so überlege, dass die wirklich interessanten dinge, wie posix, winapi, xcb, µc, opengl (plus die ganzen anderen open-bibliotheken) eigentlich mit C programmiert werden, halte ich diese aussage für sehr gewagt. also ich sage ja nicht, dass c++ komplett unsinn ist, aber es gibt durchaus dinge, für die du c lernen solltest und eben nicht c++.



  • @wob sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    rekursion ist ein thema für fortgeschrittene

    Das haben wir damals sogar in der Schule im Informatikunterricht gelernt, und zwar ungefähr ganz am Anfang, gleich nachdem wir Funktionen hatten. Klasse 11, erstes Halbjahr. Definitiv auch für Anfänger geeignet.

    naja allem anschein nach hat sie es nicht geschafft, eine rekursive lösung zu entwickeln, dafür aber eine zumindest teilweise funktionierende iterative lösung.

    die erfahrung, dass da 15 schleifen verschachtelt werden, dürfte nicht unwichtig sein

    Die braucht man nicht zu machen. Schon bei 4 Schleifen wäre das für mich zu viel Arbeit.

    vor den erfolg haben die götter eben den schweiß gesetzt. außerdem ist das doch nur copy/paste und ersetzen der variablennamen.

    erst "schlecht" programmieren und sich dann "verbessern" ist deutlich motivierender, als alles von vornherein "perfekt" machen zu müssen

    Dem stimme ich zu. Aber man braucht es mit so vielen Verschachtelungen nicht zu übertreiben, um zu sehen, dass das nicht flexibel und viel Arbeit ist.

    naja es liefert zumindest ein ergebnis und dass rekursion ziemlich langsam ist, ist ja auch kein geheimnis. guck dir zur not halt den verlinkten code mit der programmausgabe an. vermutlich braucht es iterativ bei 3000 etwa 144s bzw. 2,5 min und rekursiv 2256s bzw. 37,6 min. ich glaube, dass die mehrarbeit mit den verschachtelten schleifen bei der praktischen berechnung durchaus gerechtfertigt ist.

    aus den 15 verschachtelten schleifen lässt sich die rekursionsvorschrift ganz toll ablesen

    Das ist so unübersichtlich, dass ich da gar nichts mehr ablesen kann.

    wenn du es selbst eingetippt hast und den vorgang kennst, weißt du ja auch, wie das programm läuft und musst dir eigentlich nur die ersten 3 schleifen ansehen bzw. du kannst das problem auf 3 geldeinheiten reduzieren und die vorschrift trotzdem ableiten. überleg halt mal, wie das war, als du mit dem programmieren angefangen hast und was sich seitdem verändert hat.


  • Gesperrt

    Falls es hilft:

    #include <iostream>
    #include <vector>
    //#include <string>
    #include <cmath>
    
    int main(int argc, char* argv)
    {
    	std::vector<std::string> signs;
    	signs.push_back("a");
    	signs.push_back("b");
    
    	size_t digits = 3;
    	size_t num_variations = pow(signs.size(), digits);
    
    	std::vector<std::string> variations;
    	variations.resize(num_variations * digits);
    
    	size_t sign_index = 0;
    	
    	for (size_t column = 0; column < digits; ++column)
    	{
    		size_t row = 0;
    		
    		for (size_t subindex1 = 0; subindex1 < pow(signs.size(), column + 1); ++subindex1)
    		{
    			for (size_t subindex2 = 0; subindex2 < pow(signs.size(), digits - (column + 1)); ++subindex2)
    			{
    				variations[digits * row + column] = signs[sign_index % signs.size()];
    
    				++row;
    			}
    
    			++sign_index;	
    		}
    	}
    
    	size_t index = 0;
    	for (size_t index_a = 0; index_a < num_variations; ++index_a)
    	{
    		for (size_t index_b = 0; index_b < digits; ++index_b)
    		{
    			std::cout << variations[index] << " ";
    			++index;
    		}
    		std::cout << '\n';
    	}
    }
    

    Auf Ideone https://ideone.com/QtcKFH 😁



  • @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    naja

    • rekursion ist ein thema für fortgeschrittene

    Sehe ich nicht so. Man braucht es zwar je nachdem in welchem Bereich man arbeitet im Alltag viel seltener als manche meinen... Aber ich finde man sollte es von Anfang an können.

    • die erfahrung, dass da 15 schleifen verschachtelt werden, dürfte nicht unwichtig sein
    • erst "schlecht" programmieren und sich dann "verbessern" ist deutlich motivierender, als alles von vornherein "perfekt" machen zu müssen

    Ich verstehe was du meinst. Würde Sinn machen wenn du ne umständliche aber sauber implementierte/kommentierte Lösung gezeigt hättest. Hast du aber nicht. Und wenn du nem Noob Code mit 5-fach verschachtelten Schleifen, 1-Buchstaben Variablennamen und ganz ohne Kommentare zeigst, dann erreichst du damit bloss dass er glaubt dass die Profis so programmieren. Und meint wenn er als cooler Checker durchgehen will, dann müsse er selbst auch solchen Code schreiben.



  • @hustbaer sagte in Wechselgeld 5 besten Kombinationen:

    @Wade1234 sagte in Wechselgeld 5 besten Kombinationen:

    naja

    • rekursion ist ein thema für fortgeschrittene

    Sehe ich nicht so. Man braucht es zwar je nachdem in welchem Bereich man arbeitet im Alltag viel seltener als manche meinen... Aber ich finde man sollte es von Anfang an können.

    der unterschied zwischen "theoretischer informatik" und "programmieren" ist nicht unerheblich.

    • die erfahrung, dass da 15 schleifen verschachtelt werden, dürfte nicht unwichtig sein
    • erst "schlecht" programmieren und sich dann "verbessern" ist deutlich motivierender, als alles von vornherein "perfekt" machen zu müssen

    Ich verstehe was du meinst. Würde Sinn machen wenn du ne umständliche aber sauber implementierte/kommentierte Lösung gezeigt hättest. Hast du aber nicht. Und wenn du nem Noob Code mit 5-fach verschachtelten Schleifen, 1-Buchstaben Variablennamen und ganz ohne Kommentare zeigst, dann erreichst du damit bloss dass er glaubt dass die Profis so programmieren. Und meint wenn er als cooler Checker durchgehen will, dann müsse er selbst auch solchen Code schreiben.

    sorry aber @codinglea war das für dich unverständlich? meinst du "als cooler checker" durchgehen zu müssen, dass die "profis" so programmieren, oder dass du auch so programmieren musst? ehrliche antwort bitte!


  • Gesperrt

    Ich hab mich noch mal ran gemacht, vielleicht auch so, wenn man die "10 besten Kombinationen" ermitteln möchte (und ja, es ist C++, allerdings sollte man dadurch die Funktion verstehen können und es nach C adaptieren können):

    #include <iostream>
    #include <vector>
    
    const int n = 9;
    const int werte[n] = {500, 200, 100, 50, 20, 10, 5, 2, 1};
    
    int getNext(std::vector<std::vector<int>> &v1, std::vector<int> &v2, int idx, long sum)
    {
        if (sum == 0)
        {
            // +++ uncomment this if you want alternative combinations +++
            //if (v1.empty()
            // || v1.back()[0] != v2[0])
            //{
                v1.push_back(std::vector<int>(v2));
            //}
            return 1;
        }
        for (size_t i = idx; i < n; i++)
        {
            sum -= werte[i];
            if (sum >= 0)
            {
                v2.push_back(i);
                getNext(v1, v2, i, sum);
                if (v1.size() >= 10)
                {
                    return 1;
                }
                v2.pop_back();
            }
            sum += werte[i];
        }
        return 0;
    }
    
    int main()
    {
        const int sum = 501;
        std::vector<std::vector<int>> v1;
        std::vector<int> v2;
        std::cout << getNext(v1, v2, 0, sum) << std::endl;
        for (size_t i = 0; i < v1.size(); i++)
        {
            std::cout << i + 1 << ": ";
            for (size_t j = 0; j < v1[i].size(); j++)
            {
                std::cout << werte[v1[i][j]] << " ";
            }
            std::cout << std::endl;
        }
        return 0;
    }
    
    1
    1: 500 1
    2: 200 200 100 1
    3: 200 200 50 50 1
    4: 200 200 50 20 20 10 1
    5: 200 200 50 20 20 5 5 1
    6: 200 200 50 20 20 5 2 2 2
    7: 200 200 50 20 20 5 2 2 1 1
    8: 200 200 50 20 20 5 2 1 1 1 1
    9: 200 200 50 20 20 5 1 1 1 1 1 1
    10: 200 200 50 20 20 2 2 2 2 2 1
    

    ... nur ist das ggf für alle Beträge sehr langsam. Eure Meinungen dazu?



  • Ohh Jungs... mit dem Thema hab ich ja schon wieder für Trubel gesorgt! 😃

    1. @Wade1234 egal, was ich programmiere.... ich will nicht oder brauche nicht der "coole Checker" sein, bzw. @hustbaer & @TGGC ich bin eine Frau! 😅 also eher "coole Checkerin"
    2. mein Ausbilder gibt mir die Aufgaben und ich soll mir das alles selbst beibringen. Er möchte, dass ich Rekursion, genauso wie Brute Force kann.
      Daher ist es in diesem Fall egal, ob ich die Aufgabe rekursiv oder iterativ löse, wie auch immer.

    Ich freue mich, dass so viele mir versuchen zu helfen! 🙂



  • @codinglea sagte in Wechselgeld 5 besten Kombinationen:

    1. mein Ausbilder gibt mir die Aufgaben und ich soll mir das alles selbst beibringen.

    Was ist das für eine Ausbildung?
    Wofür braucht man eigentlich einen Ausbilder, wenn man sich alles selbst beibringen soll?



  • @Belli

    Ich mache eine Ausbildung um später Fachinformatikerin zu sein für die Anwendungsentwicklung.
    Tja, der hat zu viel zu tun und schafft es nicht, mir die Sachen beizubringen.



  • Also wenn du dir alles selbst beibringen sollst, aber noch nicht mal klar ist, das du jetzt auf jeden Fall z.B. Arrays oder Rekursion benutzen müsstest, sondern auch noch bei allem sagst, das du es erstmal weglassen willst, dann ist diese ganze Ausbildung Schwachsinn. Kannst auch einfach die 5 besten Lösungen im Kopf ausrechnen und dann printen.

    Ich hab dir Lösungsansätze skizziert, wie normale Leute an so ein Problem rangehen. Das Sortieren lässt sich auf beliebige Kriterien umbauen. Und für genau so Denkansätze sind wir hier IMHO da. Diese halbfertig programmierten Lösungen in teils schlechtestem Stil helfen nicht wirklich weiter, weder beim Lösen noch beim Lernen. (@EinNutzer0 : 200,100,100,100,1 ist unter den Top 5).