1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus

SeppJ

@Wade1234 sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

die reicht doch für den anfang, oder? also wenn ich irgendetwas berechnen muss und vor allem an dem ergebnis interessiert bin, ist es ja eigentlich egal, ob dieses ergebnis sofort oder nach einigen stunden auftaucht, oder? also optimieren kann man ja immer noch.

Das hier ist offensichtlich eine Programmierübungsaufgabe. Da geht es nicht um das Ergebnis, sondern um die möglichst optimale Umsetzung. Dazu gehört natürlich auch eine Diskussion verschiedener Möglichkeiten.

TGGC

@Wade1234

Also wenn die simple Lösung nur 3 Zeilen hat und auch die Variante mit allen 8 Münzen in Sekundenbruchteilen löst, frag ich mich schon wo der Sinn ist deine Variante überhaupt einzutippen? Optimiert ist das von mir beschriebene noch gar nicht, denn dabei würde man die Zwischenschritte in einer Matrix cashen.

@SeppJ sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Wade1234 sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

die reicht doch für den anfang, oder? also wenn ich irgendetwas berechnen muss und vor allem an dem ergebnis interessiert bin, ist es ja eigentlich egal, ob dieses ergebnis sofort oder nach einigen stunden auftaucht, oder? also optimieren kann man ja immer noch.

Das hier ist offensichtlich eine Programmierübungsaufgabe. Da geht es nicht um das Ergebnis, sondern um die möglichst optimale Umsetzung. Dazu gehört natürlich auch eine Diskussion verschiedener Möglichkeiten.

da hast du natürlich recht. ich habe halt schon einmal die erste funktionierende möglichkeit geliefert. also wenn man irgendwann einmal in die situation gerät, irgendetwas derartiges zu berechnen, dann bekommt man das schon einmal hin.

schöner wäre vielleicht der aufruf entsprechender funktionen, um das ganze noch weiter zu verallgemeinern und sie summierung von zwischenergebnissen und der abbruch der berechnung bei überschreitung der gesamtsumme.

@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Wade1234

Also wenn die simple Lösung nur 3 Zeilen hat und auch die Variante mit allen 8 Münzen in Sekundenbruchteilen löst, frag ich mich schon wo der Sinn ist deine Variante überhaupt einzutippen? Optimiert ist das von mir beschriebene noch gar nicht, denn dabei würde man die Zwischenschritte in einer Matrix cashen.

wie sähe die simple lösung mit 3 zeilen denn aus?

Swordfish

@Wade1234 sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

wie sähe die simple lösung mit 3 zeilen denn aus?

template<typename T>
int count_solutions(int amount, T const &coins, typename T::size_type index = 0)
{
	if (amount == 0) return 1;	
	if (amount < 0 || coins.size() == index) return 0;
	return count_solutions(amount - coins[index], coins, index) + count_solutions(amount, coins, index + 1);
}

Schlangenmensch

Und in C

Swordfish

@Schlangenmensch Keine Ahnung? Analog?

TGGC

@Schlangenmensch
int calc(int s, int l, int* c)
{
if (l < 2) return s % c[l] ? 0 : 1;
if (s < c[l] ) return calc(s,l-1, c);
return calc(s,l-1,c) + calc(s-c[l],l,c);
}

Luckyingmar

Vielen Dank für die fleißigen Antworten!
Bei der Aufgabe ist es egal, ob sie iterativ oder rekursiv gelöst wird...
Da ich bisher viele Aufgaben iterativ gelöst habe, freue ich mich über rekursive Ansätze für meine Aufgabe.

Luckyingmar

Das sind unsere heutigen Ansätze:

#include <stdio.h>
#include <stdlib.h>

int arra[]= {1, 2, 5, 10};
int muenzwert(int betrag)
{
int zahler =0;
int i =0;
    
    if(betrag<=0)
    {
        return 1;
    }
    else
    {

        while(i<4)
        {
            zahler+=muenzwert(betrag-arra[i]);
            i++;
        }
        return zahler;
        printf("%d", zahler);
    }
    return 0;

}

int main()
{
    int eingabe;
    scanf("%i", &eingabe);
    printf("%i", muenzwert(eingabe));


    return 0;
}

oder

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int muenzwert(int c1=1, int c2=2, int c5=5, int c10=10)
    if(betrag<=0)
    {
        return 1;
    }
    else
    {
        c1*1+c2*2+c5*5+c10*10=betrag;
    }
    return 0;

int main(void)
{
    int betrag;
    printf("Geben Sie einen Centbetrag zwischen 1 und 100 ein: ");
    scanf("%i", &betrag);

    printf("\n\nFuer %i Cent gibt es %i Moeglichkeiten der Bezahlung.", betrag, zaehler);

    return 0;
}

funktionieren nur noch nicht richtig.

SeppJ

So allgemein, fiel mir schon bei deiner ersten Frage auf, dass du dies lesen solltest: https://www.c-plusplus.net/forum/topic/200753/du-brauchst-hilfe
Besonders den Abschnitt darüber, wie man Probleme nachvollziehbar macht und wie man Fragen richtig stellt.

Du klatscht hier Code hin, der teilweise nicht einmal compilierbar ist, und sagst bloß "geht nicht". Was soll dir da jemand helfen?

Luckyingmar

@SeppJ
Der obere funktioniert er rechnet lange und kommt zu einem nicht richtigen Ergebnis. Im Debugger ist erkennbar das er immer wieder in die erste if hineingeht, dass ist für mich unverständlich warum er das macht.
Den zweiten Code hat meine Studienkollegin geschrieben, mit der ich mich immer austausche.

TGGC

Euch fehlen Grundlagen und ihr werdet daher dieses Problem nicht lösen, wenn ihr die nicht nachholt. Ihr werdet maximal irgendwas zusammenkopieren, was zufällig den richtigen Wert berechnet und nicht verstehen warum.

SeppJ

@Luckyingmar sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@SeppJ
Der obere funktioniert er rechnet lange und kommt zu einem nicht richtigen Ergebnis. Im Debugger ist erkennbar das er immer wieder in die erste if hineingeht, dass ist für mich unverständlich warum er das macht.
Den zweiten Code hat meine Studienkollegin geschrieben, mit der ich mich immer austausche.

Beim ersten Code: Das ist schon korrekt, dass er oft (aber nicht immer!) in den ersten Fall läuft. Die Bedingung <= 0 umfasst schließlich auch all die Fälle, die nicht aufgehen und das sind halt ziemlich viele. Da ist aber auch gleich einer der Fehler: Du zählst all diese Fälle, wo es nicht passt, als 1. Kein Wunder, dass das viel zu viele sind. Du brauchst eine Unterscheidung nach

Es passt nicht und zählt dann als nichts
Es geht genau auf und zählt als 1
Es ist noch nicht fertig und wir müssen weiter machen, bis wir bei 1 oder 2 sind.

Selbst wenn du das korrigierst, werden es aber trotzdem zu viele Möglichkeiten sein. Wenn du bei deinem Programm 4 Cent aufteilen wolltest, würdest du nämlich folgende Möglichkeiten zählen:
1+1+1+1
2+2
2+1+1
1+2+1
1+1+2
Was aber auch zu viele sind, da die Reihenfolge bei der Fragestellung egal sein sollte. Das zu lösen, überlasse ich dir. Oder lies den Rest des Threads aufmerksam, es wurde schon alles gesagt was zur Lösung nötig ist.

Der zweite Code ist indiskutabler Schrott.

@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Schlangenmensch
int calc(int s, int l, int* c)
{
if (l < 2) return s % c[l] ? 0 : 1;
if (s < c[l] ) return calc(s,l-1, c);
return calc(s,l-1,c) + calc(s-c[l],l,c);
}

bist du dir sicher, dass das funktioniert? bzw. was ist denn genau s, was l und was c? also ich bekomme als ergebnis immer 66.

@Luckyingmar mach dir halt erstmal gedanken, wie du die kombinationen alle zusammen bekommst.

TGGC

@Wade1234 sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@TGGC sagte in 1 bis 100 Centbeträge Möglichkeiten/Kombinationen Algorithmus:

@Schlangenmensch
int calc(int s, int l, int* c)
{
if (l < 2) return s % c[l] ? 0 : 1;
if (s < c[l] ) return calc(s,l-1, c);
return calc(s,l-1,c) + calc(s-c[l],l,c);
}

bist du dir sicher, dass das funktioniert? bzw. was ist denn genau s, was l und was c? also ich bekomme als ergebnis immer 66.

Ja funktioniert wenn korrekt aufgerufen, möchte aber 1:1 kopieren verhindern. Wie genau ist oben erklärt.

Th69

@TGGC: Es muß bei deinem Code aber if (l < 1) heißen, sonst kommt z.B. bei 5 nur 1 und nicht 4 heraus!

TGGC

@Th69
Nein, ist auch anders lösbar entsprechend meiner ursprünglichen Definition.

also ich habe heute mal ein bisschen herumprobiert:

der naive bruteforce-ansatz von oben mit einer kleinen zusätzlichen optimierung, sehr schnell aber unflexibel:

#include <stdio.h>
#include <time.h>

#define ival 10
#define jval 5
#define kval 2
#define lval 1

int main()
{
        int i, j, k, l;
        int maxi, maxj, maxk, maxl;

        int betrag;
        int anzahl;

        struct timespec t1, t2;

        printf("betrag: ");
        scanf("%d", &betrag);

        maxi = betrag / ival;
        maxj = betrag / jval;
        maxk = betrag / kval;
        maxl = betrag / lval;

        clock_gettime(CLOCK_REALTIME, &t1);

        anzahl = 0;

        for(i = 0; i <= maxi; i++)
        {
                for(j = 0; j <= maxj; j++)
                {
                        if(i * ival + j * jval > betrag)
                        {
                                break;
                        }

                        for(k = 0; k <= maxk; k++)
                        {
                                if(i * ival + j * jval + k * kval > betrag)
                                {
                                        break;
                                }

                                for(l = 0; l <= maxl; l++)
                                {
                                        if(i * ival + j * jval + k * kval + l * lval > betrag)
                                        {
                                                break;
                                        }

                                        if(i * ival + j * jval + k * kval + l * lval == betrag)
                                        {
                                                anzahl++;
                                        }
                                }
                        }
                }
        }

        clock_gettime(CLOCK_REALTIME, &t2);

        printf("anzahl: %d\n", anzahl);
        printf("zeit: %ld s %ld ns\n", t2.tv_sec - t1.tv_sec, t2.tv_nsec - t1.tv_nsec);

        return 0;
}

root@FreeBSD:/home/ralf # cc -O2 -o kombtest3 kombtest3.c && ./kombtest3
betrag: 1000
anzahl: 1712051
zeit: 1 s 405792806 ns
root@FreeBSD:/home/ralf # cc -O2 -o kombtest3 kombtest3.c && ./kombtest3
betrag: 2000
anzahl: 13514101
zeit: 21 s 397108443 ns

der rekursive ansatz, sehr übersichtlich aber unglaublich langsam:

#include <stdio.h>
#include <time.h>

int calc_rek(int betrag, int nummer, int werte[])
{
        if(betrag == 0)
        {
                return 1;
        }

        if(betrag < 0 || nummer == 4)
        {
                return 0;
        }

        return calc_rek(betrag - werte[nummer], nummer, werte) + calc_rek(betrag, nummer + 1, werte);
}

int main()
{
        int betrag;
        int anzahl;
        int werte[] = {10, 5, 2, 1};

        struct timespec t1, t2;

        printf("Betrag: ");
        scanf("%d", &betrag);

        clock_gettime(CLOCK_REALTIME, &t1);
        anzahl = calc_rek(betrag, 0, werte);
        clock_gettime(CLOCK_REALTIME, &t2);

        printf("anzahl: %d\n", anzahl);
        printf("zeit: %ld s %ld ns\n", t2.tv_sec - t1.tv_sec, t2.tv_nsec - t1.tv_nsec);

        return 0;
}

root@FreeBSD:/home/ralf # cc -O2 -o kombtest kombtest.c -lpthread && ./kombtest
Betrag: 1000
anzahl: 1712051
zeit: 12 s -175423158 ns
root@FreeBSD:/home/ralf # cc -O2 -o kombtest kombtest.c -lpthread && ./kombtest
Betrag: 2000
anzahl: 13514101
zeit: 188 s 37553069 ns

der "hybrid-ansatz", genauso flexibel wie der rekursive ansatz, aber etwa doppelt so schnell.

#include <stdio.h>
#include <time.h>

int loopfunc(int betrag, int summe, int nummer, int werte[], int numwerte)
{
        int i;
        int maxi;

        int anzahl;
        int summeneu;

        anzahl = 0;

        if(nummer == numwerte)
        {
                return 0;
        }

        maxi = betrag / werte[nummer];

        for(i = 0; i <= maxi; i++)
        {
                summeneu = summe + i * werte[nummer];

                if(summeneu == betrag)
                {
                        anzahl++;
                        continue;
                }

                if(summeneu > betrag)
                {
                        return anzahl;
                }

                anzahl = anzahl + loopfunc(betrag, summeneu, nummer + 1, werte, numwerte);
        }

        return anzahl;
}

int main()
{
        int betrag;
        int anzahl;
        int werte[] = {10, 5, 2, 1};

        struct timespec t1, t2;

        printf("betrag: ");
        scanf("%d", &betrag);

        clock_gettime(CLOCK_REALTIME, &t1);
        anzahl = loopfunc(betrag, 0, 0, werte, 4);
        clock_gettime(CLOCK_REALTIME, &t2);

        printf("anzahl: %d\n", anzahl);
        printf("zeit: %ld s %ld s\n", t2.tv_sec - t1.tv_sec, t2.tv_nsec - t1.tv_nsec);

        return 0;
}

root@FreeBSD:/home/ralf # cc -O2 -o kombtest2 kombtest2.c -lpthread && ./kombtest2
betrag: 1000
anzahl: 1712051
zeit: 6 s -39405363 s
root@FreeBSD:/home/ralf # cc -O2 -o kombtest2 kombtest2.c -lpthread && ./kombtest2
betrag: 2000
anzahl: 13514101
zeit: 93 s -871818673 s

@Luckyingmar lesen, verstehen, selber programmieren!

SeppJ

Du solltest deine Zeitberechnung überdenken. Zeit zwischen 15. Oktober und 6. Dezember ist nach dir 2 Monate und -9 Tage.

jetzt wo dus sagst verstehe ich auch, wo die negativen zahlen herkommen.