2023.12.28

貪欲アルゴリズムを使ったお釣りの計算の実装

marugotoyoten

cs50のYoutube動画「貪欲アルゴリズムを使ったお釣りの計算の実装」について要点と要約をまとめました

３つの要点

要点１
貪欲アルゴリズムは、常に利用可能な最大のコインを使用して、与えられた金額のお釣りを可能な限り少ないコインで作ることを目指しています。
要点２
貪欲アルゴリズムは、ループまたはモジュロと除算の組み合わせを使用して実装することができます。
要点３
アルゴリズムを実装した後、プレースホルダーを使用して最終的な使用されたコインの数を表示することができます。

要約

貪欲アルゴリズムについて
このスピーチでは、お釣りの計算における貪欲アルゴリズムの概念について説明します。目標は、与えられた金額のお釣りを可能な限り少ないコインで作ることです。戦略は、常に利用可能な最大のコイン、つまりクォーターコインから始めて、ダイム、ニッケル、最後にペニーを使用することです。

貪欲アルゴリズムの実装
貪欲アルゴリズムを実装するために、まずユーザーにお釣りの金額を入力してもらいます。入力を検証し、ドルからセントに変換します。次に、最大のコインを使用し、使用したコインの数と残りのお釣りの金額を追跡するループに入ります。クォーターコイン、ダイム、ニッケル、ペニーの順にこのプロセスを繰り返し、お釣りの金額がゼロになるまで続けます。

貪欲アルゴリズムのモジュロアプローチ
貪欲アルゴリズムを実装する別のアプローチは、モジュロ演算子を使用する方法です。モジュロと除算を使用して、特定のコインの額を使用できるかどうかをチェックすることができます。例えば、お釣りの金額をクォーターコインで割った余りがゼロより大きい場合、クォーターコインを使用することができます。ダイム、ニッケル、ペニーについても同様のプロセスを続け、お釣りの金額がゼロになるまで繰り返します。

最終的なコインの数の表示
貪欲アルゴリズムを実装した後、最終的な使用されたコインの数を表示する必要があります。プリント文の中で変数に格納された値を表示するためにプレースホルダーを使用することができます。プレースホルダーを使用することで、使用されたコインの数や他の関連情報を簡単に表示することができます。

▼今回の動画