Cash

入門

VS Codeを開きます。

$

wget https://cdn.cs50.net/2021/fall/psets/1/cash.zip

その後にEnterを押すと、mario-more.zipというZIPがあなたのコードスペースにダウンロードされます。wgetと次のURLの間にあるスペースや、その他の文字を見落とさないように注意してください。

次に

unzip cash.zip

を実行して、cashというフォルダを作成します。
ZIPファイルは不要になりましたので、

rm cash.zip

を実行し、プロンプトで “y “に続いてEnterで応答すると、ダウンロードしたZIPファイルが削除されます。

次に

cd cash

の後にEnterを押して、そのディレクトリに移動する（つまり、開く）。これでプロンプトは以下のようになります。

cash/ $

すべて成功した場合は、次のように実行します。

ls

code cash.cを実行すると、このProblem setのコードを入力するファイルが開かれるはずです。そうでない場合は、手順をたどって、どこで間違ったのかを判断してください。

貪欲アルゴリズム

両替を行う際には、各お客に分配するコインの数を最小限にして、自分の手持ちのコインが不足しないようにする必要があります (さもないとお客が困ります)。幸いなことに、コンピューターサイエンスはあらゆる場所のレジ係に、必要なコインの数を最小限に抑える方法を提供してきました。それが貪欲 (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枚を受け取ることになります。

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

実装の詳細

cash.c では、顧客に支払うべきセントの数をユーザに尋ね、そのおつりが出る最小の硬貨の数を表示するプログラムのほとんどを実装しました(全部ではありません!)。確かに、main はすでにあなたのために実装されています。しかし、main がまだ実装されていないいくつかの関数を呼び出していることに注目してください。そのうちの1つ、get_centsは引数を取らず(voidで表示)、intを返します。残りの関数はすべて1つの引数、intを取り、intを返します。現在、これらの関数はすべて0を返すので、コードはコンパイルできます。しかし、あなたはすべてのTODOとreturn 0;をあなた自身のコードで置き換えることを望むでしょう。具体的には、これらの関数の実装を以下のように完成させてください。

• get_cents を実装し、get_int を使ってユーザーにセントの数を入力させ、その数を int で返すようにします。もしユーザが負の値を入力した場合は、再度プロンプトが表示されます。(しかし、ユーザーが例えば文字列を入力しても、get_intが処理してくれるので、心配する必要はありません)。mario.cのようなdo whileループが役に立つかもしれません!
• この関数は、あるセント数の借金がある場合、顧客に何セント渡すべきかを計算する（そしてintで返す）ような方法でcalculate_quarterを実装してください。例えば、もし cents が 25 ならば、calculate_quarter は 1 を返さなければなりません。もし cents が 26 あるいは 49 (あるいはその中間) ならば、calculate_quarter は 1 を返すべきでしょう。もし cents が 50 か 74 (またはその中間) ならば、calculate_quarter は 2 を返します。といった具合です。

• calculate_dimes関数が10セント硬貨について同じように計算するように実装します。
• calculate_nickels関数がニッケルについても同じように計算するように実装します。
• calculate_pennies関数がペニーに対して同じように計算するように実装します。

副作用だけを持つ関数とは異なり、値を返す関数は明示的にreturn！を使用して返す必要があることに注意してください。配布コード自体を変更しないように注意してください。指定されたTODOsとそれに続くreturn値のみを置き換えてください。抽象化の概念を思い出して、各計算関数は、貪欲アルゴリズムが示唆する値だけでなく、任意の値を受け入れる必要があることにも注意してください。たとえば、が85の cents場合、centscalculate_dimesは 8を返す必要があります。

ヒント
Week1のソースコードには、関数がどのように値を返すかを説明するいくつかのサンプルプログラムがあることを思い出してください。discount1.c と discount2.c が参考になると思います。
あなたのプログラムは以下の例のように動作するはずです。

$ ./cash
Change owed: 41
4

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

コードのテスト方法

このプログラムでは、コードを手動でテストしてみてください。これは良い習慣です。

• もし-1を入力したら、プログラムは再度プロンプトを表示しますか？
• 0を入力すると、プログラムは0を出力しますか？
• 1 を入力すると、プログラムは 1 (すなわち 1 ペニー) を出力しますか?
• もし4を入力したら、プログラムは4(すなわち4枚の小銭)を出力しますか?
• もし5を入力したら、プログラムは1（つまり5セント）を出力しますか？
• 24を入力すると、プログラムは6（つまり10セント硬貨2枚とペニー4枚）を出力しますか？
• 25を入力すると、プログラムは1（すなわち1/4）を出力しますか？
• 26と入力すると、プログラムは2（すなわち、1/4と1/1）を出力しますか？
• 99と入力すると、プログラムは9（すなわち、3クォーター、2ダイム、および4ペニー）を出力しますか？

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

check50 cs50/problems/2022/x/cash

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

style50 cash.c

提出方法

お使いの端末で、以下を実行して作品を提出してください。

submit50 cs50/problems/2022/x/cash