有限単位の計算の変更

Question

私が利用できる請求書のタイプは、$ 1、$ 5、$ 10、$ 20、$ 50、$ 100の変更を計算する関数を作成しています。各金種はまた、現時点で引き出し内にある有価証券番号から差し引かれます。

ここで扱うペニー、ニッケル、ダイムまたは四半期はありません。ドル金額のみです。

これは私が思い付いたものです。これ以上の法案はすべての宗派のための引き出しの中に存在しない場合

機能は現在、エラー処理のための補正は、ユーザーが付属されてい

UPDATE引き出しのためのより多くのお金を得るためのメッセージ。 arasmussenの値の補正から

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

、このビッグOは、O（X * nは）×*のO（N）= xがある金種の数であり、O（N）=です。

各金種を計算するためのアルゴリズム的に高速な方法はありますか？

Answer 1

ループが少ないですか？

無制限の請求書では、十分に単純である必要があります。法案の有限数字で

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; 

Answer 2

modulo operatorを使用すると、複雑さを大幅に軽減することができます。

Answer 3

私は理解している場合、あなたの質問に正しく...あなたは合計Nを受け取ることができるいくつかの方法を与える閉じた形の式、利用できるの与えられたセットがありますコイン。それはシリーズを生成するを採用しています - 学部レベルの数学のもの。興味があればlinkを参照してください。1ドルをどのように変更できますか？。

、このような式の存在はあなたがはるかに高速Oよりも、いくつかの方法を計算することができることを意味し（N^6）

重い数学のもののこの種のための素晴らしい本あります - コンクリート数学は、グラハムによってクヌスとパタシニック。