Berekening van verandering in eindige denominaties

Ik schrijf een functie om de gegeven wijziging te berekenen - $ 1, $ 5, $ 10, $ 20, $ 50 en $ 100 zijn de soorten rekeningen die ik tot mijn beschikking heb. Elke denominatie wordt ook afgetrokken van een eindig aantal facturen dat zich momenteel in de la bevindt.

Er zijn ook geen centen, stuivers, dubbeltjes of kwartalen om hier mee om te gaan, gewoon hele dollarbedragen.

Dit is wat ik bedacht:

UPDATE

De functie heeft nu een correctie voor foutafhandeling wanneer er geen biljetten meer in de lade zijn voor een coupure, de gebruiker krijgt een bericht om meer geld voor de lade te krijgen.

// Set elsewhere in the program
int numberOnesLeft;
int numberFivesLeft;
int numberTensLeft;
int numberTwentiesLeft;
int numberFiftiesLeft;
int numberHundredsLeft;

int numberOfOnes = 0;
int numberOfFives = 0;
int numberOfTens = 0;
int numberOfTwenties = 0;
int numberOfFifties = 0;
int numberOfHundreds = 0;

void CalculateChange(float amount)
{
    char tempStr[128];

    while(amount >= 100.0)
    {
        if(numberOfHundreds >= numberHundredsLeft)
            break;
        else
            amount = amount - 100.0;
        numberOfHundreds++;
    }
    while(amount >= 50.0)
    {
        if(numberOfFifties >= numberFiftiesLeft)
            break;
        else
            amount = amount - 50.0;
        numberOfFifties++;
    }
    while(amount >= 20.0)
    {
        if(numberOfTwenties >= numberTwentiesLeft)
            break;
        else
            amount = amount - 20.0;
        numberOfTwenties++;
    }
    while(amount >= 10.0)
    {
        if(numberOfTens >= numberTensLeft)
            break;
        else
            amount = amount - 10.0;
        numberOfTens++;
    }
    while(amount >= 5.0)
    {
        if(numberOfFives >= numberFivesLeft)
            break;
        else
            amount = amount - 5.0;
        numberOfFives++;
    }
    while(amount >= 1.0)
    {
        if(numberOfOnes >= numberOnesLeft)
            break;
        else
            amount = amount - 1.0;
        numberOfOnes++;
    }
    if(amount > 0)
    {
      printf("You are still owed: $");
      sprintf(tempStr, "%.2f", amount);
      printf(tempStr);
      printf("\n\n");
      printf("Please obtain more money for the drawer\n");
    }
}

Van de gewaardeerde correctie van arasmussen is de Big O hiervan O (x * n) = x * O (n) = O (n), waarbij x het aantal denominaties is dat er zijn.

Is er een algoritmisch snellere manier om elke denominatie te berekenen?

0
De Big O hiervan zou feitelijk 6 * O (n) = O (6 * n) = O (n) zijn. Er is echter een O (1) -oplossing.
toegevoegd de auteur Andrew Rasmussen, de bron
Is dit huiswerk? Als dit het geval is, label het dan met de huiswerktag.
toegevoegd de auteur Richard J. Ross III, de bron
Het is geen huiswerk.
toegevoegd de auteur NexAddo, de bron
Uw beperkingen zijn zodanig dat er mogelijk geen antwoord is voor een bepaald probleem. Uw code moet een pad hebben voor het afdrukken van een fout, het retourneren van een fout, het gooien van een uitzondering of het aangeven van een fout op een andere manier.
toegevoegd de auteur Robᵩ, de bron
toegevoegd de auteur Pubby, de bron

3 antwoord

Minder loops?

Met oneindige rekeningen, moet eenvoudig genoeg zijn.

int num_100 = amount/100; amount %= 100;
int num_50  = amount/50;  amount %= 50;
int num_20  = amount/20;  amount %= 20;
int num_10  = amount/10;  amount %= 10;
int num_5   = amount/5;   amount %= 5;
int num_1   = amount;

Met eindige aantallen rekeningen ...

void get_change(int &amount, int &left, int denom) {
  int num = amount/denom;
  if (left < num)
    num = left;
  left -= num;
  amount -= num * denom;
}

int amount = ...;
get_change(amount, num_100 , 100);
get_change(amount, num_50  , 50);
get_change(amount, num_20  , 20);
get_change(amount, num_10  , 10);
get_change(amount, num_5   , 5);
num_1 = amount;
2
toegevoegd

U moet de complexiteit aanzienlijk kunnen verminderen door de modulo-operator te gebruiken.

1
toegevoegd

Als ik je vraag goed heb begrepen ... Er is een gesloten formulierformule die een aantal manieren geeft waarop je sum N kunt ontvangen, gegeven een reeks beschikbare munten. Het maakt gebruik van genererende series - dingen van wiskunde op een lager niveau. Als u hier interesse in heeft, volgt hier link , zie het gedeelte In hoeveel manieren waarop u één dollar kunt veranderen? .

Existence of such formula means that you may calculate number of ways much faster than O(n^6)

Er is uitstekend boek voor dit soort zware wiskunde - Concrete Mathematics van Graham, Knuth en Patashnik.

0
toegevoegd