Wechselgeld berechnen

lano

Well-Known Member
c-b Experte
#1
Moin. Ich hab folgendes:
C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


// Die Stueckelung
struct coins {
    unsigned int cent1;
    unsigned int cent2;
    unsigned int cent5;
    unsigned int cent10;
    unsigned int cent20;
    unsigned int cent50;

    unsigned int euro1;
    unsigned int euro2;
    unsigned int euro5;
    unsigned int euro10;
    unsigned int euro20;
    unsigned int euro50;
    unsigned int euro100;
    unsigned int euro200;
    unsigned int euro500;
} coin;

int main() {

   struct coins portemonnaie;        
   struct coins hand;        

    srand(time(NULL));

    portemonnaie.cent1 = rand() % 10;
    portemonnaie.cent2 = rand() % 10;
    portemonnaie.cent5 = rand() % 10;
    portemonnaie.cent10 = rand() % 10;
    portemonnaie.cent20 = rand() % 10;
    portemonnaie.cent50 = rand() % 10;
    portemonnaie.euro1 = rand() % 10;
    portemonnaie.euro2 = rand() % 10;
    portemonnaie.euro5 = rand() % 10;
    portemonnaie.euro10 = rand() % 10;
    portemonnaie.euro20 = rand() % 10;
    portemonnaie.euro50 = rand() % 10;
    portemonnaie.euro100 = rand() % 10;
    portemonnaie.euro200 = rand() % 10;
    portemonnaie.euro500 = rand() % 10;

    hand.cent1 = 0;
    hand.cent2 = 0;
    hand.cent5 = 0;
    hand.cent10 = 0;
    hand.cent20 = 0;
    hand.cent50 = 0;
    hand.euro1 = 0;
    hand.euro2 = 0;
    hand.euro5 = 0;
    hand.euro10 = 0;
    hand.euro20 = 0;
    hand.euro50 = 0;
    hand.euro100 = 0;
    hand.euro200 = 0;
    hand.euro500 = 0;


    printf( "Im Portemonnaie sind: \n");
    printf( "1 Cent : %d\n", portemonnaie.cent1);
    printf( "2 Cent : %d\n", portemonnaie.cent2);
    printf( "5 Cent : %d\n", portemonnaie.cent5);
    printf( "10 Cent : %d\n", portemonnaie.cent10);
    printf( "20 Cent : %d\n", portemonnaie.cent20);
    printf( "50 Cent : %d\n", portemonnaie.cent50);

    printf( "1 Euro : %d\n", portemonnaie.euro1);
    printf( "2 Euro : %d\n", portemonnaie.euro2);
    printf( "5 Euro : %d\n", portemonnaie.euro5);
    printf( "10 Euro : %d\n", portemonnaie.euro10);
    printf( "20 Euro : %d\n", portemonnaie.euro20);
    printf( "50 Euro : %d\n", portemonnaie.euro50);
    printf( "100 Euro : %d\n", portemonnaie.euro100);
    printf( "200 Euro : %d\n", portemonnaie.euro200);
    printf( "500 Euro : %d\n", portemonnaie.euro500);

    // Inhalt des portemonnaies zusammen zaehlen
    double gesamt = (0.01 * portemonnaie.cent1) + (0.02 * portemonnaie.cent2) + \
    (0.05 * portemonnaie.cent5) + (0.1 * portemonnaie.cent10) + (0.2 * portemonnaie.cent20) + \
    (0.5 * portemonnaie.cent50) + (1 * portemonnaie.euro1) + (2 * portemonnaie.euro2) + \
    (5 * portemonnaie.euro5) + (10 * portemonnaie.euro10) + (20 * portemonnaie.euro20) + \
    (50 * portemonnaie.euro50) + (100 * portemonnaie.euro100) + (200 * portemonnaie.euro200) + (500 * portemonnaie.euro500);

    // Zu zahlenden Betrag erzeugen
    double schuld = (rand() % (int)gesamt);
    schuld = schuld / 100;


   printf( "Gesamt %.2lf Euro \n", gesamt);
   printf( "Zu bezahlen %.2lf Euro \n", schuld);


// struct hand mit der benoetigten Anzahl Muenzen fuellen.
// funktion um eine Muenze ins naechst kleinbere zu wechseln.



    printf( "zu uebergebende Muenzen: \n");
    if(hand.cent1 != 0)  printf( "1 Cent : %d\n", hand.cent1);
    if(hand.cent2 != 0) printf( "2 Cent : %d\n", hand.cent2);
    if(hand.cent5 != 0) printf( "5 Cent : %d\n", hand.cent5);
    if(hand.cent10 != 0) printf( "10 Cent : %d\n", hand.cent10);
    if(hand.cent20 != 0) printf( "20 Cent : %d\n", hand.cent20);
    if(hand.cent50 != 0) printf( "50 Cent : %d\n", hand.cent50);

    if(hand.euro1 != 0) printf( "1 Euro : %d\n", hand.euro1);
    if(hand.euro2 != 0) printf( "2 Euro : %d\n", hand.euro2);
    if(hand.euro5 != 0) printf( "5 Euro : %d\n", hand.euro5);
    if(hand.euro10 != 0) printf( "10 Euro : %d\n", hand.euro10);
    if(hand.euro20 != 0) printf( "20 Euro : %d\n", hand.euro20);
    if(hand.euro50 != 0) printf( "50 Euro : %d\n", hand.euro50);
    if(hand.euro100 != 0) printf( "100 Euro : %d\n", hand.euro100);
    if(hand.euro200 != 0) printf( "200 Euro : %d\n", hand.euro200);
    if(hand.euro500 != 0) printf( "500 Euro : %d\n", hand.euro500);


return 0;
}
jetzt suche ich eine funktion um das struct hand mit den benoetigten muenzen zu fuellen.
Wenn ich keine passenden muenzen habe dann soll eine Muenze gewechselt werden.

Soweit meine Ueberlegung.
Wie bekomm ich das denn clever hin ?
 

lord_haffi

Well-Known Member
c-b Experte
#2
Mit oder ohne folgendes Rückgeld? Für ohne Rückgeld:
100€ zu zahlen:
In einer Schleife folgendes ausführen:
  • Nächstgrößte Bezahlmöglichkeit nutzen, hier 100€-"coins" und so viel wie nötig / möglich in die Hand packen.
  • Wenn der Betrag stimmt, abbrechen, ansonsten mit der nächstgrößten Bezahlmöglichkeit fortfahren.
Wenn nach der Schleife der Betrag noch nicht stimmt, hast du nicht genug Kleingeld.
Ich würde übrigens in deinem Fall lieber mit Arrays arbeiten, statt mit 20 Variablen... Sowas wie
C:
struct coins {
    unsigned int centstuecke[15][2];
    // Der 1. Index für die verschiedenen coins/Bezahlmöglichkeiten, der 2. für das Wertepaar (Wert der coin, Anzahl der coins)
} coin;
Das macht den Rest dann etwas übersichtlicher, findest du nicht? ;)
 

German

Well-Known Member
c-b Experte
#3
Gibt's bestimmt wieder ein Standard Problem für ;)
Was ist denn das Ziel? So wenig wie möglich Scheine/Münzen in der Hand zu haben? Oder Kleingeld schnellstmöglich los zu werden? Oder was gerade aufgeht, unabhängig von irgendwelchen Präferenzen?
 

lord_haffi

Well-Known Member
c-b Experte
#7
Aber vllt noch nen 500er den ich wechseln koennte?
'Nen 500er aus der Brieftasche mal eben wechseln? Erscheint mir jetzt net so sinnvoll, aber wenn du das unbedingt mit reinbringen willst... Wie German schon gesagt hat, entspricht das dem Rucksackproblem. In deinem Fall aber ein einfacher Rucksack, weil deine Gewichtungen alle gleich sind (du willst ja die Anzahl an Münzen minimieren, da hat jede Münze das Gewicht 1). So wie ich das sehe, kommst du aber nicht um Brute Force herum..
Ich würde es in etwa so machen:
  • Generell optimale Packung berechnen
  • An den Stellen, wo es an Kleingeld hapert, schauen, ob das nötige Kleingeld durch das Wechseln größerer Coins gewonnen werden kann
  • Wenn nicht, dasselbe Spielchen mit der nächstbesten theoretischen Packung
 

German

Well-Known Member
c-b Experte
#8
Sooo, wieder daheim. Hab gestern noch ein bisschen gebastelt. Ganz zufrieden bin ich noch nicht. Normalerweise müsste ich wohl bis zum Schluss cent-weise hochkrabbeln wenn keine Lösung gefunden wurde, aber in der Zeit die das dauert wird 'ne alte Frau wieder jung. Zu viel Mist in der Rekursion.
C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define PURSE_SIZE 16

enum denominations {e500, e200, e100, e50, e20, e10, e5, e2, e1, c50, c20, c10, c5, c2, c1, total};

struct money
{
  int number;
  int value;
};


void InitPurse(struct money *const purse)
{
  memset(purse, 0, PURSE_SIZE * sizeof(struct money));
  purse[e500].value = 50000;
  purse[e200].value = 20000;
  purse[e100].value = 10000;
  purse[e50].value  =  5000;
  purse[e20].value  =  2000;
  purse[e10].value  =  1000;
  purse[e5].value   =   500;
  purse[e2].value   =   200;
  purse[e1].value   =   100;
  purse[c50].value  =    50;
  purse[c20].value  =    20;
  purse[c10].value  =    10;
  purse[c5].value   =     5;
  purse[c2].value   =     2;
  purse[c1].value   =     1;
}


bool AddMoney(struct money *const purse, const int denom, const int number)
{
  if (purse[denom].number + number < 0)
    return false;

  purse[denom].number += number;
  purse[total].number += number;
  purse[total].value += purse[denom].value * number;
  return true;
}


bool Transfer(struct money *const wallet, struct money *const hand, const int denom, const int number)
{
  if (AddMoney(wallet, denom, 0 - number) == false)
    return false;

  if (AddMoney(hand, denom, 0 + number) == false)
  {
    AddMoney(wallet, denom, 0 + number);
    return false;
  }

  return true;
}


bool Recur(struct money *const wallet, struct money *const hand, const int value, const int denom)
{
  if (denom == total)
    return false;

  if (wallet[denom].value > value - hand[total].value || wallet[denom].number == 0)
    return Recur(wallet, hand, value, denom + 1);

  int max_of_denomination = (value - hand[total].value) / wallet[denom].value;
  if (max_of_denomination > wallet[denom].number)
    max_of_denomination = wallet[denom].number;

  struct money **array = malloc(max_of_denomination * sizeof(struct money *));
  if (array == NULL)
    return false;

  struct money *mem = malloc(max_of_denomination * PURSE_SIZE * sizeof(struct money));
  if (mem == NULL)
  {
    free(array);
    return false;
  }

  unsigned lowest = -1;
  for (int i = max_of_denomination; i-- > 0; )
  {
    array[i] = &mem[i];
    memcpy(array[i], hand, PURSE_SIZE * sizeof(struct money));
    if (Transfer(wallet, array[i], denom, i + 1) == true)
    {
      if (array[i][total].value == value)
      {
        AddMoney(wallet, denom, i + 1);
        memcpy(hand, array[i], PURSE_SIZE * sizeof(struct money));
        free(mem);
        free(array);
        return true;
      }
      else if (Recur(wallet, array[i], value, denom + 1) == true && lowest > (unsigned)array[i][total].number)
      {
        lowest = (unsigned)array[i][total].number;
        memcpy(hand, array[i], PURSE_SIZE * sizeof(struct money));
      }

      AddMoney(wallet, denom, i + 1);
    }
  }

  free(mem);
  free(array);
  return (lowest != (unsigned)-1);
}


int CollectHand(struct money *const wallet, struct money *const hand, const int value)
{
  if (value < 1)
  {
    puts("Makes no sense.");
    return -1;
  }

  if (value > wallet[total].value)
  {
    puts("You need a loan!");
    return -1;
  }

  if (value == wallet[total].value)
  {
    memcpy(hand, wallet, PURSE_SIZE * sizeof(struct money));
    return 0;
  }

  int least_possible = 0, least_denom = 0;
  for (int i = total; i-- > 0; )
  {
    if (wallet[i].value <= value)
    {
      least_denom = i;
      least_possible += wallet[i].value * wallet[i].number;
    }
  }

  for (int i = 0; i < least_possible - value; ++i)
  {
    if (Recur(wallet, hand, value + i, e500))
    {
      for (int j = 0; j < total; ++j)
        AddMoney(wallet, j, 0 - hand[j].number);

      return i;
    }
  }

  for (int i = least_denom; i-- > 0; )
  {
    for (int j = 0; j < wallet[i].number; ++j)
    {
      if (Recur(wallet, hand, wallet[i].value * (j + 1), i))
      {
        for (int k = 0; k < total; ++k)
          AddMoney(wallet, k, 0 - hand[k].number);

        return hand[total].value - value;
      }
    }
  }

  return -1;
}


void PrintPurse(const struct money *const purse)
{
  for (int i = 0; i < total; ++i)
    if (purse[i].number != 0)
      printf("%3d.%02d EUR  %5dx\n", purse[i].value / 100, purse[i].value % 100, purse[i].number);

  printf("\nHaving %d pcs. for %d.%02d EUR\n", purse[total].number, purse[total].value / 100, purse[total].value % 100);
}


int main(void)
{
  struct money wallet[PURSE_SIZE] = {0};
  InitPurse(wallet);

  AddMoney(wallet, e500, 1);
  AddMoney(wallet, e200, 2);
  AddMoney(wallet, e100, 0);
  AddMoney(wallet, e50,  0);
  AddMoney(wallet, e20,  2);
  AddMoney(wallet, e10,  8);
  AddMoney(wallet, e5,   6);
  AddMoney(wallet, e2,   7);
  AddMoney(wallet, e1,   9);
  AddMoney(wallet, c50,  5);
  AddMoney(wallet, c20,  2);
  AddMoney(wallet, c10,  1);
  AddMoney(wallet, c5,   0);
  AddMoney(wallet, c2,   4);
  AddMoney(wallet, c1,   8);

  puts("\n~~~~~~~~~~~~~~~~ Wallet ~~~~~~~~~~~~~~~~~~~");
  PrintPurse(wallet);


  struct money hand[PURSE_SIZE] = {0};
  InitPurse(hand);

  const int to_pay = 29990; // Cent

  int change = CollectHand(wallet, hand, to_pay);
  if (change != -1)
  {
    puts("\n~~~~~~~~~~~~~~~~~ Hand ~~~~~~~~~~~~~~~~~~~~");
    PrintPurse(hand);
    if (change > 0)
      printf("\nChange: %d.%02d EUR\n", change / 100, change % 100);

    puts("\n~~~~~~~~~~~~~~~~ Wallet ~~~~~~~~~~~~~~~~~~~");
    PrintPurse(wallet);

    return 0;
  }

  return 1;
}
Dein struct hab ich ziemlich schnell verworfen. Da lässt sich nicht vernünftig mit Schleifen drüber iterieren. Ist jetzt ein Array. Ein enum gibt dir ein paar menschenlesbare Indizes. Logischerweise arbeitet der ganze Kram mit Cent. Fließkommazahlen rechnen und vergleichen ist fehlerbehafteter Müll. Die kannst du für die Ausgabe immer noch zusammenbasteln, damit es lesbarer wird. Hab die Zufallswerte rausgeworfen. Wollte schließlich immer nachvollziehen können was sich tut. Um aus allen möglichen Wegen, den mit den wenigsten Geldscheinen/-stücken herauszufischen, ist mir nichts dümmeres als Backtracking eingefallen. Vielleicht gibt's was Schlaueres. Unsere Studenten und Studierten werden's wissen...
 

lord_haffi

Well-Known Member
c-b Experte
#9
Vielleicht gibt's was Schlaueres.
Glaube nicht. Jedenfalls nichts Signifikantes. Das Rucksackproblem ist im allgemeinen ja NP-vollständig und mir ist für diesen Fall hier auch kein Trick eingefallen, mit dem du das vereinfachen könntest..
Aber Hut ab, deine Rekursion sieht auf den ersten Blick echt überladen aus ^^ Naja, sähe bei mir bestimmt noch schlimmer aus...
 

German

Well-Known Member
c-b Experte
#10
deine Rekursion sieht auf den ersten Blick echt überladen aus
Hehe, finde ich auch. Da lässt sich sicher optimieren. Die Rekursion ist bei so was immer der Game Stopper. Da darf wirklich nur das Nötigste drin sein. Wenn ich da anfange Speicherallokationen zu machen, wird's schon interessant. Allerdings komme ich aus dem Dilemma nicht ganz raus. So lange beim ersten Backtracking eine Punktlandung rauskommt, ist das ja auch noch akzeptabel. Jetzt fehlt mir aber ein vernünftiger Algorithmus, mit welchen nächstgrößeren Werten ich weitersuche (dann halt mit Rückgeld vom Verkäufer). Cent-weise inkrementieren dauert Äonen. Ich nehme dann ab einem gewissen Punkt die nächstgrößeren Geldwerte eines Scheins. Das geht auch gut, solange es nicht knapp an den Inhalt der Brieftasche ran kommt. Dann könnte dieser Sprung aber schon zu groß sein und ich bekomme keine Lösung mehr, obwohl ich mehr als den Kaufpreis in der Brieftasche habe. Dazu fällt mir irgendwie nichts Schlaues ein.
 

lano

Well-Known Member
c-b Experte
#11
Ganz zufrieden bin ich noch nicht.
Gar nicht schlecht, noch nen paar Kleinigkeiten.

Ich probier das mal zurecht zu basteln.
Da soll sone art Wirtschaftssimulation draus werden.
Der Kreislauf des Geldes mit schwerpunkt auf die ominoese Geldvermehrung der Banken.
Aber wie es so ist hab ich schon die halbe Welt im Kopf mit allen Details, da ist dann immer scheisse nen Anfang zu finden.
Ka. wie ich mir das abgewoehnen koennte. Zu meinem Leid probiere ich jetzt auch KDevelop aus.
Bisher hatte mir der mcedit gereicht, aber so langsam werden die Sachen immer groesser und unuebersichtlicher.
 

lord_haffi

Well-Known Member
c-b Experte
#12
Da soll sone art Wirtschaftssimulation
Ach du... Da hast du dir ja was vorgenommen :D Wenn das so einfach wäre, würden nicht so viele Menschen an der Börse scheitern... Du kleiner Spekulant du ;)
Cent-weise inkrementieren dauert Äonen.
Jo. Aber wenn du jeden Fall abdecken möchtest, musst du leider genau das machen... Man könnte 'nen Kompromiss machen, dass man (wie du es schon angedeutet hast) nicht immer die beste Lösung findet, dafür aber die Laufzeit in einem "vernünftigen" Rahmen hält.

Allerdings hab ich wohl noch nicht ganz verstanden, was genau lano hier will bzw. warum. Du hast eine gewisse Menge Kleingeld in der Brieftasche und musst jetzt mit deinem Bargeld einen Betrag x zahlen. Soweit so gut. Aber warum größere Scheine wechseln? Dann kann man doch auch direkt einen größeren Betrag zahlen und der Verkäufer gibt entsprechend Rückgeld? Oder willst du auch noch berücksichtigen wie viel Kleingeld der Verkäufer hat?
 

German

Well-Known Member
c-b Experte
#13
Jo. Aber wenn du jeden Fall abdecken möchtest, musst du leider genau das machen...
Die Befürchtung hab ich auch.
Dann kann man doch auch direkt einen größeren Betrag zahlen und der Verkäufer gibt entsprechend Rückgeld?
Hehe, wenn die Scheine alle sind, hast du die Tasche voll Kleingeld. Und dann? Nee, erst mal versuchen passend zu zahlen ist schon sinnvoll. Der Rest ergibt sich. Das Rückgeld muss ja auch wieder passend einsortiert werden. Hab ich hier nicht betrachtet, weil ich gar nicht wissen kann, ob ich nun 10€ als Schein oder im Worst Case 1000 Centstücke bekomme. Also ist erst mal der gesamte gezahlte Betrag abgezogen und das Wechselgeld ist gesondert nur als Betrag ausgewiesen.
 

lord_haffi

Well-Known Member
c-b Experte
#14
Nee, erst mal versuchen passend zu zahlen ist schon sinnvoll.
Aber das geht ja einfach (wie ich in meinem 1. Post geschrieben hab). Und wenn man nicht passend zahlen kann, kann man doch direkt mit 'nem größeren Schein zahlen und auf's Rückgeld warten, statt ihn zuerst in Kleingeld wechseln zu lassen und dann selbst passend zu zahlen, das find' ich irgendwie unsinnig...
 

German

Well-Known Member
c-b Experte
#15
Erst mal - Allokationen rausgeworfen und Fehler beseitigt.
C:
bool Recur(struct money *const wallet, struct money *const hand, const int value, const int denom)
{
  if (denom == total)
    return false;

  if (wallet[denom].value > value - hand[total].value || wallet[denom].number == 0)
    return Recur(wallet, hand, value, denom + 1);

  int max_of_denomination = (value - hand[total].value) / wallet[denom].value;
  if (max_of_denomination > wallet[denom].number)
    max_of_denomination = wallet[denom].number;

  struct money hand_copy[PURSE_SIZE] = {0}, worker[PURSE_SIZE] = {0};
  memcpy(hand_copy, hand, PURSE_SIZE * sizeof(struct money));

  unsigned lowest = -1;
  for (int i = max_of_denomination; i-- > 0; )
  {
    memcpy(worker, hand_copy, PURSE_SIZE * sizeof(struct money));
    if (Transfer(wallet, worker, denom, i + 1) == true)
    {
      if (worker[total].value == value)
      {
        AddMoney(wallet, denom, i + 1);
        memcpy(hand, worker, PURSE_SIZE * sizeof(struct money));
        return true;
      }
      else if (Recur(wallet, worker, value, denom + 1) == true && lowest > (unsigned)worker[total].number)
      {
        lowest = (unsigned)worker[total].number;
        memcpy(hand, worker, PURSE_SIZE * sizeof(struct money));
      }

      AddMoney(wallet, denom, i + 1);
    }
  }

  return (lowest != (unsigned)-1);
}
Vorher:
struct money **array = malloc(max_of_denomination * sizeof(struct money *));
Mindestens das war unnötig.

array[i] = &mem[i];
Fatal Error. Wenn schon dann array[i] = &mem[i * PURSE_SIZE];

UUNNDD Am Anfang der Schleife habe ich immer hand in das entsprechende Arrayelement kopiert. In der Schleife wurde die erste Lösung in hand zurück kopiert. Am Ende hab ich also nie die Lösung mit den wenigsten Geldstücken zurückgegeben, sondern die erste gefundene. Autsch! :oops:


Aber das geht ja einfach (wie ich in meinem 1. Post geschrieben hab). Und wenn man nicht passend zahlen kann, kann man doch direkt mit 'nem größeren Schein zahlen und auf's Rückgeld warten, statt ihn zuerst in Kleingeld wechseln zu lassen und dann selbst passend zu zahlen, das find' ich irgendwie unsinnig...
Ja, so in etwa funktioniert der Code jetzt. Ich inkrementiere nur solange cent-weise, wie der Nennwert der Geldstücke/-scheine <= dem zu zahlenden Wert ist. Dann fange ich an einfach den nächstgrößeren Nennwert (oder ein Vielfaches davon) als zu zahlenden Betrag anzunehmen. Aber wie gesagt, das geht nicht in jedem Fall gut.
 

lano

Well-Known Member
c-b Experte
#16
Ach du... Da hast du dir ja was vorgenommen :D Wenn das so einfach wäre, würden nicht so viele Menschen an der Börse scheitern... Du kleiner Spekulant du ;)
Ne das hat damit nix zutun.
Das soll das auf ganz einfache Weise zeigen. Aber komplex genug.

Hehe, wenn die Scheine alle sind, hast du die Tasche voll Kleingeld.
Ja das sind auch so die Probleme ueber die ich stosse.

Aber bevor das aus dem Ruder laeuft, nochmal erklaert.

Ich hab zwei Person, eine Bank und eine Firma.
Jetzt gibt es Geld. Das hat einen Wert und eine Seriennummer.
Jedes Geldstueck gibt es nur ein mal.

Die Person hat ein Konto und Bargeld.
Wenn ich jetzt einen Betrag x an Person Z zahlen will.
Dann schaue ich zuerst beim Bargeld.
Reicht das Bargeld aus um zu bezahlen alles gut.
Reicht es nicht, muss ich mir erst geld von der Bank auszahlen lassen.
Oder mit Karte bezahlen :)
Wenn ich jetzt das Bargeld aus meiner Tasche abzaehle und in die Hand nehme.
Und ich hab das nicht passend. Dann kann ich versuchen bei meinem gegenueber zu wechseln.
Hat der nicht genug bargeld, muss ich zur bank und geld am automaten wechseln.
Dann kann ich passend bezahlen.

So meine Vorstellung.

Jetzt kann man das noch nen bisschen flexibler machen, das nicht nur 2 Personen da sind und nicht nur eine Bank und nicht nur eine Stadt und nicht nur ein Land sondern wie man speicher hat.

Mit der Bank soll es aehnlich funktionieren. von wegen ueberweisungen machen, und der zusammenhang mit quasi EZB
Die Personen haben unterschiedliche Jobs mit unterschiedlichen Stundenloehnen und die Firmen stellen unterschiedliche Produkte her.
usw usw
Eigentlich woll ich das nur ganz minimalistisch machen. aber da bin ich echt nicht der typ fuer...

Nee, erst mal versuchen passend zu zahlen ist schon sinnvoll. Der Rest ergibt sich.
Genau. Wie gesagt, es muessen im endefekt wirklich die muenzen getauscht werden.

Das Rückgeld muss ja auch wieder passend einsortiert werden. Hab ich hier nicht betrachtet, weil ich gar nicht wissen kann, ob ich nun 10€ als Schein oder im Worst Case 1000 Centstücke bekomme.
Das ist halt die frage was der andere hat. aber da kommen wir zum naechsten thema.
Was macht man mit nem Sack voll Kleingeld? Richtig, zur Bank bringen und einzahlen.
Legen wir einen Betrag fest den die Person maximal dabei haben sollte.
Und da waere es ja nett wenn man das nen bisschen klever stueckeln koennte.
Das auch mein Problem beim Wechselautomaten. wenn ich 50€ einwerfe, was bekomm ich da raus?

Und wenn man nicht passend zahlen kann, kann man doch direkt mit 'nem größeren Schein zahlen und auf's Rückgeld warten, statt ihn zuerst in Kleingeld wechseln zu lassen und dann selbst passend zu zahlen, das find' ich irgendwie unsinnig...
Genau, so lange ich genug geld habe und der andere im schlimmsten fall passend wechseln kann, dann brauche ich nicht zur bank.
 

lord_haffi

Well-Known Member
c-b Experte
#17
Dann kann ich versuchen bei meinem gegenueber zu wechseln.
Oh... Dann musst du ja noch die Coins vom Verkäufer betrachten... Das wird nicht einfach.....
Meine Idee:
Zuerst schauen, ob du genug Kleingeld hast, um es direkt zu bezahlen.
Wenn nicht, musst du mit dem gesamten Geld von Käufer (positiv gewertet) und Verkäufer (negativ gewertet) irgendwie auf den zu zahlenden Betrag kommen. Und das Problem ist, wenn ich das grade richtig einschätze, np-vollständig, sprich, die Laufzeit sollte exponentiell werden.. Dann musst du alle Möglichkeiten (oder die meisten, man kann bestimmt ein paar gleich verwerfen) durchprobieren. Dann könnte man, wenn mehrere Lösungen existieren z.B. über die Anzahl an zu transferierenden Münzen minimieren, aber das ist erstmal zweitrangig.
 

German

Well-Known Member
c-b Experte
#18
Hab noch mal gebastelt.
Der Versuch den ganzen Kram mit Multithreading zu versehen hat wie erwartet zu einem exponentiellen Anstieg der Anzahl der Threads und damit zum Forkbomb-ähnlichen Einfrieren des Rechners geführt. Hab jetzt eine zweite Rekursion reingenommen, die mit ein bisschen Nachbereitung ein ganz gutes Ergebnis liefert. Ist nicht auf ein Ergebnis getrimmt, immer so wenig wie möglich Wechselgeld zurück zu bekommen. Das kriege ich nicht hin. Aber es liefert ein Ergebnis mit einer angemessenen Laufzeit.
C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define PURSE_SIZE 16

enum denominations {e500, e200, e100, e50, e20, e10, e5, e2, e1, c50, c20, c10, c5, c2, c1, total};

struct money
{
  int number;
  int value;
};


void InitPurse(struct money *const purse)
{
  memset(purse, 0, PURSE_SIZE * sizeof(struct money));
  purse[e500].value = 50000;
  purse[e200].value = 20000;
  purse[e100].value = 10000;
  purse[e50].value  =  5000;
  purse[e20].value  =  2000;
  purse[e10].value  =  1000;
  purse[e5].value   =   500;
  purse[e2].value   =   200;
  purse[e1].value   =   100;
  purse[c50].value  =    50;
  purse[c20].value  =    20;
  purse[c10].value  =    10;
  purse[c5].value   =     5;
  purse[c2].value   =     2;
  purse[c1].value   =     1;
}


bool AddMoney(struct money *const purse, const int denom, const int number)
{
  if (purse[denom].number + number < 0)
    return false;

  purse[denom].number += number;
  purse[total].number += number;
  purse[total].value += purse[denom].value * number;
  return true;
}


bool Transfer(struct money *const from, struct money *const to, const int denom, const int number)
{
  if (AddMoney(from, denom, 0 - number) == false)
    return false;

  if (AddMoney(to, denom, 0 + number) == false)
  {
    AddMoney(from, denom, 0 + number);
    return false;
  }

  return true;
}


bool FindExactAmount(struct money *const wallet, struct money *const hand, const int value, const int denom)
{
  if (denom == total)
    return false;

  int remaining = value - hand[total].value;
  if (wallet[denom].value > remaining || wallet[denom].number == 0)
    return FindExactAmount(wallet, hand, value, denom + 1);

  int max_of_denomination = remaining / wallet[denom].value;
  if (max_of_denomination > wallet[denom].number)
    max_of_denomination = wallet[denom].number;

  struct money wallet_template[PURSE_SIZE] = {0}, wallet_worker[PURSE_SIZE] = {0}, hand_template[PURSE_SIZE] = {0}, hand_worker[PURSE_SIZE] = {0};

  memcpy(wallet_template, wallet, PURSE_SIZE * sizeof(struct money));
  memcpy(hand_template, hand, PURSE_SIZE * sizeof(struct money));

  unsigned lowest_num = -1;

  for (int i = max_of_denomination; i-- > 0; )
  {
    memcpy(wallet_worker, wallet_template, PURSE_SIZE * sizeof(struct money));
    memcpy(hand_worker, hand_template, PURSE_SIZE * sizeof(struct money));

    if (Transfer(wallet_worker, hand_worker, denom, i + 1) == true)
    {
      if (hand_worker[total].value == value)
      {
        Transfer(wallet, hand, denom, i + 1);
        return true;
      }

      if (FindExactAmount(wallet_worker, hand_worker, value, denom + 1) == true && lowest_num > (unsigned)hand_worker[total].number)
      {
        lowest_num = (unsigned)hand_worker[total].number;
        memcpy(wallet, wallet_worker, PURSE_SIZE * sizeof(struct money));
        memcpy(hand, hand_worker, PURSE_SIZE * sizeof(struct money));
      }
    }
  }

  return (lowest_num != (unsigned)-1);
}


bool FindHigherAmount(struct money *const wallet, struct money *const hand, const int value, const int denom)
{
  if (denom == total)
    return false;

  if (wallet[denom].number == 0)
    return FindHigherAmount(wallet, hand, value, denom + 1);

  int remaining = value - hand[total].value;
  if (wallet[denom].value > remaining && FindHigherAmount(wallet, hand, value, denom + 1) == true)
    return true;

  int max_of_denomination = remaining / wallet[denom].value + 1;
  if (max_of_denomination > wallet[denom].number)
    max_of_denomination = wallet[denom].number;

  struct money wallet_template[PURSE_SIZE] = {0}, wallet_worker[PURSE_SIZE] = {0}, hand_template[PURSE_SIZE] = {0}, hand_worker[PURSE_SIZE] = {0};

  memcpy(wallet_template, wallet, PURSE_SIZE * sizeof(struct money));
  memcpy(hand_template, hand, PURSE_SIZE * sizeof(struct money));

  unsigned lowest_val = -1;

  for (int i = 0; i < wallet[denom].number; ++i)
  {
    memcpy(wallet_worker, wallet_template, PURSE_SIZE * sizeof(struct money));
    memcpy(hand_worker, hand_template, PURSE_SIZE * sizeof(struct money));

    if (Transfer(wallet_worker, hand_worker, denom, i + 1) == true)
    {
      if (hand_worker[total].value > value)
      {
        Transfer(wallet, hand, denom, i + 1);
        return true;
      }

      if (FindHigherAmount(wallet_worker, hand_worker, value, denom + 1) == true && lowest_val > (unsigned)hand_worker[total].value && hand_worker[total].value > value)
      {
        lowest_val = (unsigned)hand_worker[total].value;
        memcpy(wallet, wallet_worker, PURSE_SIZE * sizeof(struct money));
        memcpy(hand, hand_worker, PURSE_SIZE * sizeof(struct money));
      }
    }
  }

  return (lowest_val != (unsigned)-1);
}


int CollectHand(struct money *const wallet, struct money *const hand, const int value)
{
  if (value < 1)
  {
    puts("Makes no sense.");
    return -1;
  }

  if (value > wallet[total].value)
  {
    puts("You need a loan!");
    return -1;
  }

  if (value == wallet[total].value)
  {
    memcpy(hand, wallet, PURSE_SIZE * sizeof(struct money));
    return 0;
  }

  if (FindExactAmount(wallet, hand, value, e500))
    return 0;

  struct money wallet_worker[PURSE_SIZE] = {0}, hand_worker[PURSE_SIZE] = {0};
  memcpy(wallet_worker, wallet, PURSE_SIZE * sizeof(struct money));
  memcpy(hand_worker, hand, PURSE_SIZE * sizeof(struct money));
  if (FindHigherAmount(wallet_worker, hand_worker, value , e500))
  {
    for (int i = 0; i < total; ++i)
      while (hand_worker[total].value - hand_worker[i].value > value && hand_worker[total].value / hand_worker[i].value > 0 && Transfer(hand_worker, wallet_worker, i, 1));

    FindExactAmount(wallet, hand, hand_worker[total].value, e500);
    return hand[total].value - value;
  }

  return -1;
}


void PrintPurse(const struct money *const purse)
{
  for (int i = 0; i < total; ++i)
    if (purse[i].number != 0)
      printf("%3d.%02d EUR  %5dx\n", purse[i].value / 100, purse[i].value % 100, purse[i].number);

  printf("\nHaving %d pcs. for %d.%02d EUR\n", purse[total].number, purse[total].value / 100, purse[total].value % 100);
}


int main(void)
{
  struct money wallet[PURSE_SIZE] = {0};
  InitPurse(wallet);

  AddMoney(wallet, e500, 1);
  AddMoney(wallet, e200, 2);
  AddMoney(wallet, e100, 0);
  AddMoney(wallet, e50,  0);
  AddMoney(wallet, e20,  2);
  AddMoney(wallet, e10,  8);
  AddMoney(wallet, e5,   6);
  AddMoney(wallet, e2,   7);
  AddMoney(wallet, e1,   9);
  AddMoney(wallet, c50,  5);
  AddMoney(wallet, c20,  2);
  AddMoney(wallet, c10,  1);
  AddMoney(wallet, c5,   0);
  AddMoney(wallet, c2,   8);
  AddMoney(wallet, c1,   0);

  puts("\n~~~~~~~~~~~~~~~~ Wallet ~~~~~~~~~~~~~~~~~~~");
  PrintPurse(wallet);


  struct money hand[PURSE_SIZE] = {0};
  InitPurse(hand);

  const int to_pay = 909; // Cent

  int change = CollectHand(wallet, hand, to_pay);
  if (change != -1)
  {
    puts("\n~~~~~~~~~~~~~~~~~ Hand ~~~~~~~~~~~~~~~~~~~~");
    PrintPurse(hand);
    if (change > 0)
      printf("\nChange: %d.%02d EUR\n", change / 100, change % 100);

    puts("\n~~~~~~~~~~~~~~~~ Wallet ~~~~~~~~~~~~~~~~~~~");
    PrintPurse(wallet);

    return 0;
  }

  return 1;
}
 
Oben