Cash

貪欲アルゴリズム

両替を行う際には、各お客に分配するコインの数を最小限にして、自分の手持ちのコインが不足しないようにする必要があります (さもないとお客が困ります)。幸いなことに、コンピューターサイエンスはあらゆる場所のレジ係に、必要なコインの数を最小限に抑える方法を提供してきました。それが貪欲 (greedy) アルゴリズムです。

米国立標準技術研究所 (NIST) によると、貪欲アルゴリズムは「答えを見つけるには、常に最良の即効性のある局所的な解決策が必要である。貪欲アルゴリズムは、一部の最適化問題の全体的な最適解を見つけるが、他の問題の一部のケースでは、最適解よりは効率が劣る解を見つけることがある」ということです。

これはどういう意味でしょうか？レジ係がお客にいくらかの小銭を借りていて、そのレジ係の引き出しには、25セント (クオーター)、10セント (ダイム) 、5セント (ニッケル) 、および1セント (ペニー) が入っているとします。問題は、どのコインを何枚お客に渡すかを決めることです。「欲張りな」 レジ係は、引き出しから取り出した硬貨1枚1枚で、その硬貨がある限り、最大の硬貨で支払いたいと考えている人だとしましょう。例えば、41セントをお客に支払わなければならない場合、最初の最大の1手 (最良の即時解または局所解) は25セントです (他のどのコインよりも速く0セントに近づけるという意味で、これは 「ベスト」 です) 。このようにすることで、41セントの問題が16セントの問題になります (41 – 25 = 16)。つまり、残りの問題は似ていますが小さい問題となります。言うまでもないことですが、次は、25セントは大きすぎるので (レジ係は損をしないことを望んでいると仮定して) 、欲張りなレジ係は10セントを支払い、残りは6セントとなります。その時点で、貪欲アルゴリズムは5セントを要求し、その後1セントを要求し、その時点で問題は解決します。お客は25セント硬貨1枚、10セント硬貨1枚、5セント硬貨1枚、1セント硬貨1枚の合計4枚を受け取ることになります。

この貪欲なアプローチ (アルゴリズム) は、局所的に最適であるだけでなく、世界的にもアメリカの通貨にとって (そしてヨーロッパでも) 最適であることがわかりました。つまり、レジ係がそれぞれの硬貨を十分に持っている限り、この大域から局所へのアプローチでは、可能な限り少ない硬貨を使うという結果が得られます。それは何枚でしょうか。考えてみましょう！

実装の詳細

~/pset1/cashディレクトリにあるcash.cというファイルにプログラムを実装します。このプログラムは、まずユーザにいくらの両替が必要かを尋ね、次にその両替が可能な最小のコイン数を出力します。

  • get_floatを使用してユーザの入力を取得し、printfを使用して回答を出力します。使用可能な硬貨は、25セント (クオーター) 、10セント (ダイム) 、5セント (ニッケル) 、および1セント (ペニー) のみであるとします。
    • ドル記号がなくてもドルとセントを扱えるように、get_floatを使用してください。つまり、あるお客が9.75ドルのお釣りを抱えている場合 (25セントの新聞にお客が10ドル札で支払っている場合など) 、プログラムからの入力は$9.75や975ではなく9.75であると仮定します。また、あるお客がちょうど9ドルのお釣りを抱えている場合、プログラムからの入力は9.00や9であると仮定し、$9や900ではないとします。もちろん、浮動小数点値の性質上、プログラムは9.0や9.000などの入力でも機能するでしょう。ユーザの入力がお金のように 「フォーマット」 されているかどうかを確認する必要はありません。
  • ユーザの入力が大きすぎてfloatに収まらないかどうかを確認する必要はありません。get_floatだけの使用であれば、ユーザの入力が実際に浮動小数点 (または整数) 値であることが保証され、そしてそれは負ではありません。
  • ユーザが負でない値を指定しなかった場合、プログラムはユーザがそうするまで、有効な値の入力を何度もユーザに求める必要があります。
  • コードのテストを自動化できるように、プログラムの出力の最後の行が、コインの最小数 (整数の後に\nが続く) であることを確認します。
  • 浮動小数点値の本質的な非精度に注意してください。floats.cをクラスから呼び出し、xが2でyが10の場合、x / yは正確には2/10とはなりません。したがって、両替を行う前に、ユーザが入力したドルをセントに (つまり、floatからintへ) に変換して、計算される可能性のある小さなエラーを回避する必要があります。
  • math.hで宣言されているroundのように、セントを最も近い1セントに丸めるように注意してください。たとえば、dollarsがユーザ入力のfloat (例:0.20) である場合、次のようにコード化します。
int cents = round(dollars * 100);

これで、0.20 (実は0.200000002980232238769531250) は正しく20に変換されます。

プログラムは、次の例に従って動作する必要があります。

$ ./cash
Change owed: 0.41
4
$ ./cash
Change owed: -0.41
Change owed: foo
Change owed: 0.41
4

ウォークスルー

コードのテスト方法

コードは以下の入力時に指定されたとおりに動作しますか。

  • -1.00 (または他の負の数)
  • 0.00
  • 0.01 (または他の正の数)
  • 文字列や単語
  • 何も入力せず、Enterキーだけを押したとき

check50を使用して以下を実行し、コードの正確さを評価することもできます。ただし、必ず自分でコンパイルしてテストしてください。

check50 cs50/problems/2021/x/cash

以下を実行し、style50を使用してコードのスタイルを評価します。

style50 cash.c

提出方法

次のコマンドを実行し、GitHubのユーザ名とパスワードを入力してログインします。セキュリティのため、パスワードには実際の文字ではなくアスタリスク (*) が表示されます。

submit50 cs50/problems/2021/x/cash