計算有限面值的變化

我正在寫一個函數來計算給定的變化 - $ 1，$ 5，$ 10，$ 20，$ 50和$ 100是我可用的賬單類型。每個面額也從當前抽屜中的有限票據數中扣除。計算有限面值的變化

也沒有便士，鎳，硬幣或宿舍來處理在這裏，只是整個美元的金額。

這是我想出了：

UPDATE

功能現在有錯誤處理的修正時在抽屜裏的任何面值沒有更多的鈔票，用戶與供應爲抽屜獲取更多錢的消息。

// 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"); 
    } 
}

從arasmussen的值校正，這樣做的大O是O（X * N）= X *爲O（n）= O（n），其中x是有面額的數目。

是否有算法更快的方式來計算每個面額？

來源

2011-12-06 NexAddo

[這是否有幫助？]（http://en.wikipedia.org/wiki/Change-making_problem） – Pubby

這是功課嗎？如果是這樣，請用作業標籤標記它。 –

這不是作業。 – NexAddo

更少的循環？

無限票據應該足夠簡單。

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;

與票據的有限數...

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;

來源

2011-12-06 19:50:56