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

Luckyingmar

@Schlangenmensch
Stimmt, die Kommentare sind nicht ganz richtig.
Zeile 21, war ein alter versuch.
Wir kommen noch zu keinem Algorithmus und hatten es daher mit modulo versucht. Mit modulo kann man nur zwei möglichkeiten bestimmen.

Th69

Überlege zuerst einmal welche Gleichung erfüllt sein muß und dann kannst du darum einen Algorithmus schreiben, der alle Möglichkeiten durchgeht (und die Anzahl der Lösungen aufaddiert).

Luckyingmar

@Th69
Ich bin gerade leicht über fordert meinst du zum Beispiel so etwas?:

Wie oft passt dort die 10 in die 13 hinein dann die nächst kleinere Zahl im Array wie oft passt die 5 hinein, dann die 2 und die eins.

   Array[]= {10, 5, 2, 1}
        13:
Array  0    10 + 2 + 1
Array  0    10 + 1 + 1 + 1
Array  1    5 + 5 + 2 + 1
Array  1    5 + 5 + 1 +1 +1
Array  1    5 + 2 + 2 + 2 + 2
Array  1    5 + 2 + 2 + 2 + 1 + 1
Array  1    5 + 2 + 2 + 1 + 1 + 1 + 1
Array  1    5 + 2 + 1 + 1 + 1 + 1 + 1 + 1
Array  1    5 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Array  2    2 + 2 + 2 + 2 + 2 + 2 + 1
Array  2    2 + 2 + 2 + 2 + 2 + 1 + 1 + 1
Array  2    2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1
Array  2    2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Array  2    2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Array  2    2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Array  3    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Schlangenmensch

@Luckyingmar
Ich denke @Th69 meint sowas:

a*1+b*2+c*5+d*10 = 100

Du suchst alle möglichen Lösungen für die Gleichungen.

Dein Ansatz ist Rekursiv, dass geht auch und wäre wahrscheinlich auch mein erster Ansatz gewesen.

TGGC

Man kann da ganz simpel eine Formel herleiten und rekursiv berechnen. Angenommen wir haben die Münzen aufsteigend geordnet als m1,m2... und wir haben die Summe s, die man bilden soll und suchen nun Anzahl(s,m1,m2,...,mn) dann gilt folgendes:
Anzahl(s,m1,m2,...,mn) = Anzahl(s - mn,m1,m2,...,mn) + Anzahl(s,m1,m2,...,mn-1)

Was genau bedeudet das? Nehmen wir ein konkretes Beispiel! Ich soll 13 cent bauen aus 1,2,5. Wenn ich die 13 cent baue, habe ich 2 Möglichkeiten, ich habe mindestens eine 5 dabei, oder ich habe keine 5 dabei. Die Anzahl ohne 5 ist Anzahl(s,m1,m2,...,mn-1), die Anzahl mit einer 5 ist Anzahl(s - mn,m1,m2,...,mn). Konkret ist das erste Anzahl(13,1,2) und das zweite Anzahl(8,1,2,5). Diese beiden Möglichkeiten muss ich nun nur noch addieren um auf meine Gesamtmöglichkeiten zu kommen.

Logischerweise ist Anzahl(n,1) =1 und Anzahl(s,m1,m2,...,mn) == Anzahl(s,m1,m2,...,mn-1) wenn mn > s und das war quasi schon.

Th69

@Schlangenmensch: Ja, genau.

Der rekursive Ansatz ist eleganter, aber ob @Luckyingmar den hinkriegt?

SeppJ

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

@Schlangenmensch: Ja, genau.

Der rekursive Ansatz ist eleganter, aber ob @Luckyingmar den hinkriegt?

Ich würde sogar darauf wetten, dass es bei der Übungsaufgabe genau darum geht, Rekursion zu üben. Um was sollte es sonst gehen? Das Aufstellen einer kombinatorischen Formel wäre interessante Mathematik, aber man würde nichts über Programmierung lernen. Dann bliebe als Alternative noch das manuelle Abwickeln der Rekursion. Aber das wäre doch sehr anstrengend im Vergleich zur Rekursion, und damit wahrscheinlich nicht das Ziel.

also iterativ könnte man 4 (bzw. der anzahl der verschiedenen geldstücke entsprechend viele) for-schleifen über 0 bis zum maximalwert laufen lassen und den zähler immer dann erhöhen, wenn die gleichung erfüllt ist.

TGGC

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

also iterativ könnte man 4 (bzw. der anzahl der verschiedenen geldstücke entsprechend viele) for-schleifen über 0 bis zum maximalwert laufen lassen und den zähler immer dann erhöhen, wenn die gleichung erfüllt ist.

Das ist aber nicht nur kompliziert zu programmieren und warten sondern auch noch eine sehr aufwendige Art, wenn man nur die Anzahl braucht.

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

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

int main()
{
        int i;
        int j;
        int k;
        int l;

        struct timespec t1;
        struct timespec t2;

        int betrag;
        int moeglichkeiten;

        int maxi;
        int maxj;
        int maxk;
        int maxl;

        int anzahl = 0;

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

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

        clock_gettime(CLOCK_REALTIME, &t1);

        for(i = 0; i <= maxi; i++)
        {
                for(j = 0; j <= maxj; j++)
                {
                        for(k = 0; k <= maxk; k++)
                        {
                                for(l = 0; l <= maxl; l++)
                                {
                                        if(i * ival + j * jval + k * kval + l * lval == betrag)
                                        {
                                                anzahl++;
                                        }
                                }
                        }
                }
        }

        clock_gettime(CLOCK_REALTIME, &t2);

        printf("Anzahl Kombinationen: %d\n", anzahl);
        printf("Benoetigte 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 && ./kombtest
Betrag (ct): 1000
Anzahl Kombinationen: 1712051
Benoetigte Zeit: 10 s 55022303 ns
root@FreeBSD:/home/ralf # cc -O2 -o kombtest kombtest.c && ./kombtest
Betrag (ct): 100
Anzahl Kombinationen: 2156
Benoetigte Zeit: 0 s 2140391 ns

sie funktioniert aber. also die zeiten sind von meinem experimentier-board mit 1 GHz taktrate oder so. wenn man das ganze mit 4 GHz und parallelisiert betreiben würde, sähen die zeiten sicherlich anders aus. rekursion ist nach meinem wissen auch immer deutlich langsamer.

edit: ich hab die programmfehler mal korrigiert. natürlich <= maxi, maxj usw. und nicht < maxi, maxj, ...

Swordfish

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

sie funktioniert aber.

Es hat doch niemand gesagt, daß es nicht funktioniert. Es ist halt die naive Brute-Force-Lösung.

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

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

sie funktioniert aber.

Es hat doch niemand gesagt, daß es nicht funktioniert. Es ist halt die naive Brute-Force-Lösung.

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.

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.