Cash - CS50x 2026

US coins

解くべき問題

あなたが店で働いていて、顧客が50セントのキャンディに対して1.00ドル（100セント）を支払ったとします。あなたはその顧客に、キャンディの代金を支払った後の残りである「お釣り」を渡す必要があります。お釣りを渡す際、各顧客に渡す硬貨の枚数を最小限に抑えたいと考えるでしょう。そうしないと、硬貨が足りなくなったり（あるいは顧客をイライラさせたり！）するかもしれません。cashという名前のフォルダにあるcash.cという名前のファイルに、与えられたお釣りの額（セント単位）に対して必要な最小の硬貨の枚数を出力するC言語のプログラムを実装してください。以下のようになります。

Change owed: 25
1

ただし、プログラムがどんなお釣りの額にも対応できるように、ユーザーに0より大きいint（整数）を入力するように促してください。

Change owed: 70
4

ユーザーの入力が0以上でない場合（または入力がそもそもintでない場合）、繰り返し入力を促してください。

デモ

貪欲法 (Greedy Algorithms)

幸いなことに、コンピュータサイエンスは世界中のレジ係に硬貨の枚数を最小限にする方法を提供してくれました。それが貪欲法（Greedy Algorithms）です。

米国国立標準技術研究所 (NIST) によれば、貪欲法とは「答えを見つける際に、常にその場で最善の、つまり局所的な解を選択する」アルゴリズムです。「貪欲法は、一部の最適化問題に対しては全体的な、つまり大域的な最適解を見つけますが、他の問題の例では最適とは言えない解を見つけることもあります。」

これはどういう意味でしょうか？例えば、レジ係が顧客にお釣りを渡す必要があり、レジの引き出しには25セント硬貨（クォーター）、10セント硬貨（ダイム）、5セント硬貨（ニッケル）、1セント硬貨（ペニー）が入っているとします。解くべき問題は、どの硬貨を何枚顧客に渡すかを決めることです。「貪欲な」レジ係を、引き出しから硬貨を取り出すたびに、この問題からできるだけ大きな一口をかじり取ろうとする人だと考えてみてください。例えば、ある顧客へのお釣りが41セントである場合、最初にかじり取ることができる最大の一口（つまり、その場での最善の選択）は25セントです。（この一口が「最善」なのは、他のどの硬貨よりも早く0セントに近づけるからです。）このサイズの一口をかじると、41セントの問題は16セントの問題へと削られます（41 - 25 = 16）。つまり、残りは似ているけれどより小さな問題になります。言うまでもなく、もう一度25セントをかじると大きすぎます（レジ係が損をしたくないと仮定すれば）。そこで、貪欲なレジ係は10セントの一口に移り、6セントの問題が残ります。その時点で、貪欲さは1枚の5セントの一口、続いて1枚の1セントの一口を求め、そこで問題は解決します。顧客は25セント硬貨1枚、10セント硬貨1枚、5セント硬貨1枚、1セント硬貨1枚の、計4枚の硬貨を受け取ります。

この貪欲なアプローチ（つまりアルゴリズム）は、米国の通貨（および欧州連合の通貨）にとって、局所的に最適であるだけでなく、大域的にも最適であることがわかっています。つまり、レジ係が各硬貨を十分に持っている限り、この「大きいものから小さいものへ」というアプローチは、可能な限り最小の硬貨枚数をもたらします。では、具体的に何枚になるでしょうか？それをあなたが教えてください！

アドバイス

まず、コンパイルできることがわ気っているコードを書く

このプログラムはまだ何もしませんが、少なくともmakeでコンパイルできるはずです！

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

int main(void)
{

}

これで、この問題を解決するのに役立つ関数へのアクセスを提供する2つの「ヘッダーファイル」、cs50.hとstdio.hをインクルードしたことになります。

コードをさらに書く前に、擬似コード（シュードコード）を書く

問題自体の解決方法がわからない場合は、まず解決できそうな小さな問題に分解してください。例えば、この問題は実際にはほんのいくつかの問題の集まりです。

ユーザーにお釣りの額（セント単位）を尋ねる。
顧客に渡すべき25セント硬貨の枚数を計算する。セントの額からそれらの25セント硬貨の価値を引く。
顧客に渡すべき10セント硬貨の枚数を計算する。残りのセントの額からそれらの10セント硬貨の価値を引く。
顧客に渡すべき5セント硬貨の枚数を計算する。残りのセントの額からそれらの5セント硬貨の価値を引く。
顧客に渡すべき1セント硬貨の枚数を計算する。残りのセントの額からそれらの1セント硬貨の価値を引く。
使用した25セント、10セント、5セント、1セント硬貨の合計枚数を出す。
その合計を表示する。

これがこの問題を解決するために使用できる貪欲法です。ですから、それを忘れないようにコメントとして擬似コードを書いてみましょう。

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

int main(void)
{
    // ユーザーにお釣りの額（セント単位）を尋ねる

    // 顧客に渡すべき25セント硬貨の枚数を計算する
    // セントの額からそれらの25セント硬貨の価値を引く

    // 顧客に渡すべき10セント硬貨の枚数を計算する
    // 残りのセントの額からそれらの10セント硬貨の価値を引く

    // 顧客に渡すべき5セント硬貨の枚数を計算する
    // 残りのセントの額からそれらの5セント硬貨の価値を引く

    // 顧客に渡すべき1セント硬貨の枚数を計算する
    // 残りのセントの額からそれらの1セント硬貨の価値を引く

    // 使用した25セント、10セント、5セント、1セント硬貨の合計枚数を出す
    // その合計を表示する
}

擬似コードをコードに変換する

まず、ユーザーに返すべきセントの額を尋ねる方法を考えます。do whileループは、以下のように何かを少なくとも1回、そして必要に応じて何度も繰り返したい場合に便利です。

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

int main(void)
{
    // ユーザーにお釣りの額（セント単位）を尋ねる
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);
}

ここで一度立ち止まって、プログラムをmakeするのが賢明です。プログラムがコンパイルできること、そして0セント未満を入力した場合（または「cat」のような入力を入力した場合）に再度入力を促されることを確認してください。

次に、顧客に渡すべき25セント硬貨の枚数を計算する方法を考えます。貪欲法を使用しているので、この問いは「渡すことができる最大の25セント硬貨の枚数はいくつか？」になります。この問題の解決策をmain関数の中に書くこともできます。しかし、calculate_quartersという新しい関数を書くことで、考えが整理されるかもしれません。そうすれば、25セント硬貨を計算するロジックに集中できます。後で、この関数をより大きな解決策に統合できます。

int calculate_quarters(int cents)
{
    // 顧客に渡すべき25セント硬貨の枚数を計算する
}

この関数の名前が確かにcalculate_quartersであることに注目してください。括弧内のint centsにより、これは入力としてcentsという名前のintを受け取ります。そして、名前の前にあるintにより、これもintを「返す（return）」必要があります。つまり、この関数の出力は整数、すなわちcentsの中に収まる25セント硬貨の枚数です。

では、25セント硬貨に変換できるセントがなくなるまで25セント硬貨の枚数を増やしていく、calculate_quartersの実装方法を考えてみましょう。

int calculate_quarters(int cents)
{
    // 顧客に渡すべき25セント硬貨の枚数を計算する
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}

確かに、このcalculate_quartersの問題を解決するより簡単な方法が少なくとも1つあります。ですが、それはあなた自身で見つけてもらうことにしましょう！

calculate_quartersが意図した通りに機能するようになったら、この関数をプログラムに統合できます。関数の「シグネチャ」（つまり int calculate_quarters(int cents)）をmain関数の上で「宣言」するように注意してください。そうすれば、mainの中でcalculate_quartersを使用でき、後でmainの下で定義することができます。

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

int calculate_quarters(int cents);

int main(void)
{
    // ユーザーにお釣りの額（セント単位）を尋ねる
    int cents;
    do
    {
        cents = get_int("Change owed: ");
    }
    while (cents < 0);

    // 顧客に渡すべき25セント硬貨の枚数を計算する
    int quarters = calculate_quarters(cents);

    // それらの25セント硬貨の価値をセントから引く
    cents = cents - (quarters * 25);
}

int calculate_quarters(int cents)
{
    // 顧客に渡すべき25セント硬貨の枚数を計算する
    int quarters = 0;
    while (cents >= 25)
    {
        quarters++;
        cents = cents - 25;
    }
    return quarters;
}

いくつかの問題が解決し、あと数件残っています！ここで再利用できるパターンに気づきましたか？

テスト方法

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

-1を入力した場合、プログラムは再度入力を促しますか？
0を入力した場合、プログラムは0を出力しますか？
1を入力した場合、プログラムは1（つまり1セント硬貨1枚）を出力しますか？
4を入力した場合、プログラムは4（つまり1セント硬貨4枚）を出力しますか？
5を入力した場合、プログラムは1（つまり5セント硬貨1枚）を出力しますか？
24を入力した場合、プログラムは6（つまり10セント硬貨2枚と1セント硬貨4枚）を出力しますか？
25を入力した場合、プログラムは1（つまり25セント硬貨1枚）を出力しますか？
26を入力した場合、プログラムは2（つまり25セント硬貨1枚と1セント硬貨1枚）を出力しますか？
99を入力した場合、プログラムは9（つまり25セント硬貨3枚、10セント硬貨2枚、1セント硬貨4枚）を出力しますか？

正確性

check50 cs50/problems/2026/x/cash

スタイル

style50 cash.c

ターミナルで以下を実行して、表示されるプロンプトに答えながら提出してください。

submit50 cs50/problems/2026/x/cash