Möglichkeiten, 50 Cent zu zahlen / "comparison between pointer and integer"

[noobLolo]

zwischen z.17 und 18 könnte man auch noch ein break; setzen dann würds etwas schneller laufen, behebt aber immer noch nicht mein dubletten problem

lg lolo

[noobLolo]

here we go

void recurse(int val,int l,char *cc){
	char coins[6] = {50, 20, 10, 5, 2, 1};
	int buffer;
	while(l--){
		buffer = val - coins[l];
		if(buffer > 0){
			cc[l]++;
			recurse(buffer,l+1,cc);
			cc[l]--;
			continue;
		}else if(buffer == 0){
			cc[l]++;
			printf("%d:%d:%d:%d:%d:%d\n",cc[0],cc[1],cc[2],cc[3],cc[4],cc[5]);
			cc[l]--;
		}
		break;
	}
}

int main(void) {
	char coinCount[6]={0,0,0,0,0,0};
	recurse(10,6,coinCount);
	return EXIT_SUCCESS;
}

lg lolo

[mngbd]

noobLolo schrieb:

nach dem heut der tag der recursion ist

stellen wir folgendes fest: die Anzahl der Möglichkeiten, einen Geldwert von 50 Cent mit allen 6 Münzarten zu wechseln, ist gleich der Anzahl der Möglichkeiten, 50 Cent mit allen Arten bis auf die 1-Cent-Münze zu wechseln, plus die Anzahl der Möglickeiten, 49 Cent mit allen 6 Münzarten zu wechseln.

Wenn wir 50 Cent mit einer 50-Cent-Münze darstellen, ergibt das eine Möglichkeit, und uns bleiben Null Cent Rest; deshalb müssen wir 1 Möglichkeit rechnen, wenn der Geldwert Null wird. Wenn der Geldwert kleiner Null wird, oder uns die Münzarten ausgehen, müssen wir klarerweise Null Möglichkeiten rechnen.

Also:

#include <stdio.h>

int kleinste_muenze(int anzahl)
{
    switch (anzahl)
    {
        case 6: return 1;
        case 5: return 2;
        case 4: return 5;
        case 3: return 10;
        case 2: return 20;
        case 1: return 50;
    }
}

int moeglichkeiten(int geldwert, int anzahl)
{
    if (geldwert == 0)
        return 1;
    else if (geldwert < 0 || anzahl == 0)
        return 0;
    else
        return moeglichkeiten(geldwert, anzahl - 1) +
               moeglichkeiten(geldwert - kleinste_muenze(anzahl), anzahl);
}

int main(void)
{
    printf("%d\n", moeglichkeiten(50, 6));
}

To iterate is human.

[atomix123]

lolo, dein Code sieht natürlich wesentlich eleganter aus
Danke schonmal dafür. Mit rekursiven Funktionsaufrufen habe ich noch nicht gearbeitet. Ehrlich gesagt steige ich auch durch dein Programm nicht ganz durch...

mngbd, danke auch für deine Idee. Es wird zwar nur die Anzahl der Möglichkeiten angezeigt, aber gut.

Wenn ihr mir noch erklären könntet, wo mein Fehler bei if(ist50cent==1) ist (warum ist die funktion ein pointer??), bin ich zufrieden.

[noobLolo]

atomix123 schrieb:

Ehrlich gesagt steige ich auch durch dein Programm nicht ganz durch...

sehr gut, ich auch nicht :p

atomix123 schrieb:

Wenn ihr mir noch erklären könntet, wo mein Fehler bei if(ist50cent==1) ist (warum ist die funktion ein pointer??), bin ich zufrieden.

denke du solltest z.40-42 so zusammenfassen

if(ist50cent(z, i, j, k, l, m, n)==1)

z.24 sollte auch so gehen "z = muenzen;"

lg lolo

[mngbd]

atomix123 schrieb:

mngbd, danke auch für deine Idee. Es wird zwar nur die Anzahl der Möglichkeiten angezeigt, aber gut.

Liegt daran, dass ich ihn abgeschrieben hab und zu faul war, um nachzudenken, wie man ihn um die Ausgabe erweitern kann. Geht das?

atomix123 schrieb:

Wenn ihr mir noch erklären könntet, wo mein Fehler bei if(ist50cent==1) ist (warum ist die funktion ein pointer??), bin ich zufrieden.

Der Name einer Funktion wird immer als Funktionszeiger verstanden. Weil es sicher kein Aufruf ist, und man mit einer Funktion nicht mehr machen kann als sie aufrufen und ihre Adresse bestimmen.

Wahrscheinlich hast du gemeint:

if(ist50cent(z, i, j, k, l, m, n) == 1)
{
    printf("\t%5d%5d%5d%5d%5d%5d\n", i, j, k, l, m, n);    //tabellarische Ausgabe der passenden Anzahl der Muenzen
    anz++;
}

[noobLolo]

habs jetzt mal ganz ohne schleife versucht auch wenns mir anders etwas besser gefiel, evtl. ist die misch variante auch nicht so stack lastig

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

void recurse(int val,int l,char *cc){
	char coins[6] = {50, 20, 10, 5, 2, 1};
	if(--l)
		recurse(val,l,cc);
	val -= coins[l];
	cc[l]++;
	if(val > 0)
		recurse(val,l+1,cc);
	else if(val == 0)
		printf("%d:%d:%d:%d:%d:%d\n",cc[0],cc[1],cc[2],cc[3],cc[4],cc[5]);
	cc[l]--;
}

int main(void) {
	char coinCount[6]={0,0,0,0,0,0};
	recurse(50,6,coinCount);
	return EXIT_SUCCESS;
}

lg lolo

[noobLolo]

so sollts etwas besser sein als im letzten post

void recurse(int val,int l,char *cc){
    char coins[6] = {50, 20, 10, 5, 2, 1};
    int buffer = val;
    val -= coins[--l];
    if(val>=0){
    	cc[l]++;
	    if(val > 0){
			recurse(val,l+1,cc);
			cc[l]--;
			if(l)
				recurse(buffer,l,cc);
		}else{
			printf("%d:%d:%d:%d:%d:%d\n",cc[0],cc[1],cc[2],cc[3],cc[4],cc[5]);
			cc[l]--;
		}
    }
}

lg lolo

[atomix123]

Ausgezeichnet, jetzt funktioniert mein Programm auch so, wie es soll
Vielen Dank für eure Vorschläge! Wieder was gelernt.

[mngbd]

atomix123 schrieb:

Ausgezeichnet, jetzt funktioniert mein Programm auch so, wie es soll

Aber es ist sehr ineffizient, weil es auch alle Möglichkeiten durchprobiert, die nicht 50 ergeben (die meisten ergeben mehr als 50).

Der rekursive Ansatz ist viel einfacher, und mit ein wenig Mühe kann man die gezählten Münzen in einem weiteren Parameter unterbringen:

#include <stdio.h>
#include <assert.h>

// alle Muenzen, von 1 bis 6, Index 0 wird nicht verwendet
int muenzen[] = {42, 1, 2, 5, 10, 20, 50};

// 6 Bits sind sicher genug, um jede Muenz-Anzahl zu speichern
// wir haben 6 Muenz-Arten, also koennen wir 6 Zaehler in einem
// unsigned long long unterbringen
// das Bit-Schema sieht so aus:
// 000000 000000 000000 000000 000000 000000
// 50c    20c    10c    5c     2c     1c
typedef unsigned long long zaehler_t;

// den Zaehler fuer die n-te Art (1 bis 6)
int art(zaehler_t z, int muenze)
{
    int pos = (muenze - 1) * 6;
    return (z & (077 << pos)) >> pos;
}

// den Zaehler erhoehen
zaehler_t erhoehen(zaehler_t z, int muenze)
{
    int pos = (muenze - 1) * 6;
    zaehler_t mask = 077 << pos;
    return (z & ~mask) | ((((z & mask) >> pos) + 1) << pos);
}

// alle zaehler ausgeben
void ausgabe(zaehler_t flags)
{
    int i;
    for (i = 6; i > 0; i--)
        printf("%d%c", art(flags, i), i != 1 ? '\t' : '\n');
}

int moeglichkeiten(int geldwert, int anzahl, zaehler_t z)
{
    if (geldwert == 0)
    {
        ausgabe(z);
        return 1;
    }
    else if (geldwert < 0 || anzahl == 0)
        return 0;
    else
        return moeglichkeiten(geldwert, anzahl - 1, z) +
               moeglichkeiten(geldwert - muenzen[anzahl],
                              anzahl,
                              erhoehen(z, anzahl));
}

int main(void)
{
    // sicherstellen, dass zaehler_t gross genug ist
    assert(sizeof(zaehler_t) * 8 > 36);

    printf("50c\t20c\t10c\t5c\t2c\t1c\n");
    printf("Gesamt: %d\n", moeglichkeiten(50, 6, 0));

    return 0;
}

Sollte viel schneller sein.

Edit: ist jetzt auch C89

[noobLolo]

mngbd schrieb:

Aber es ist sehr ineffizient, weil es auch alle Möglichkeiten durchprobiert, die nicht 50 ergeben (die meisten ergeben mehr als 50).

und ich dachte ich hätt schon fast das optimum getroffen, naja werds mal auf nen kleinen benchmark ankommen lassen

lg lolo

[noobLol]

mngbd schrieb:

Aber es ist sehr ineffizient, weil es auch alle Möglichkeiten durchprobiert, die nicht 50 ergeben (die meisten ergeben mehr als 50).

ach das bezog sich auf den ersten post, wie peinlich

[mngbd]

noobLol schrieb:

ach das bezog sich auf den ersten post, wie peinlich

Ach, egal, was kommt denn beim Benchmark raus? Ich erwarte eigentlich, dass meine Variante alle anderen schlägt. Dafür hat sie dieses Bitgefrickel, das die Lesbarkeit nicht unbedingt fördert. (Das bräuchte sie prinzipiell natürlich gar nicht, aber dann müsste man uU einen Typ einführen, der zu gross für den Stack und damit auch für die automatische C-Speicherverwaltung ist)

[noobLolo]

mngbd schrieb:

noobLol schrieb:

ach das bezog sich auf den ersten post, wie peinlich

Ach, egal, was kommt denn beim Benchmark raus? Ich erwarte eigentlich, dass meine Variante alle anderen schlägt. Dafür hat sie dieses Bitgefrickel, das die Lesbarkeit nicht unbedingt fördert.

ich werd da jetzt nicht rumbenchmarken, hab nur gestern die aufrufe der function gezählt und hatte da ca. das ergebnis der rückgabe deines ersten posts also dachte ich, das es schon fast nicht mehr schneller geht. daher war ich ein bischen verwundert als ich "Sollte viel schneller sein." las und das auf meinen letzten post bezog.

lg lolo

[mngbd]

noobLolo schrieb:

ich werd da jetzt nicht rumbenchmarken, hab nur gestern die aufrufe der function gezählt und hatte da ca. das ergebnis der rückgabe deines ersten posts also dachte ich, das es schon fast nicht mehr schneller geht.

Könnte ja auch sein, dass du schneller bist. Wäre aber mühsam, das zu testen, weil am meisten Zeit fast immer die Ausgabe braucht.

Den Ansatz hab ich übrigens von hier gestohlen:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_Temp_52

Deshalb sind in meiner Variante auch alle Variablen konstant.