CS50グリーディアルゴリズム

Question

私はちょうどcs50でCプログラミングを始めました。

私は貪欲なアルゴリズムに関して問題を設定しようとしましたが、バグを見つけられないようです。私のコードは以下の通りです。

#include <cs50.h> 
#include <stdio.h> 
#include <math.h> 


int main (void) 
{ 

int count = 0; 

printf("how much is the change?: "); 

float change = get_float(); 

while(change < 0) 
{ 
    printf("change is to be more than 0"); 
    change = get_float(); 
} 

int amount = lroundf(change*100); 

while(amount > 0) 
{ 
    if ((amount-25) >= 25) 
    { 
     amount = amount - 25; 
     count++; 
    } 

    else if ((amount-10) >= 10) 
    { 
     amount = amount - 10; 
     count++; 
    } 

    else if ((amount-5) >= 5) 
    { 
     amount = amount -5; 
     count++; 
    } 

    else if((amount-1) >= 1) 
    { 
     amount = amount -1; 
     count ++; 
     break; 
    } 

    else 
    { 
    printf("you have no change \n"); 
    } 
    } 
    printf("your number of coins is %i\n", count); 

    } 

変更を1と入力すると、8個のコインが返されます。バグがどこにあるのかわからない。誰でも助けてくれますか？

Answer 1

最初にchangeの値を使用して、たとえば1つのコインのような簡単な答えを返すプログラムを試してみてください。例えば、change = 0.25です。その場合は、1.00のように1つのタイプを繰り返したり、0.06のようないくつかのタイプに参加して、いくつかのコインで試してみるべきです。その後、浮動小数点精度の高い数値や数値を試してみましょう（4.10など）。これに続いてあなたの答えにつながるはずです。

それでも問題が見つからない場合は、ここに答えがあります：問題はif/else ifという表現です。たとえば、四半期を数えようとしているときには、(amount-25) >= 25は正しく動作しません。 amountは25より大きいか等しいですが、あなたのコードはそれが50未満になるまでそれを行います。(amount-25) >= 25 - >(amount-25) + 25 >= 25 + 25 - >amount >= 50のように、式を作成すると役立ちます。

もう1つの問題は、そのbreakステートメントです。予想よりも早くループから抜ける可能性があります。 0.04と0.03のような数字を試してみると、カウントは1に止まっています。最初のペニーを削除した後、コードはループから外れて、amountはまだ0より大きくなります。breakは、コードがループから脱出するのを見にくくします。そのため、可能な限り避けることを推奨します。