[C言語]お釣りの貨幣の枚数を最小にする計算を行うプログラム[コード付]

どうも　シュモクザメです。
今回は情報系の講義の課題でありがちな
「現金購入の際に返ってくるお釣りの各貨幣の枚数を求める」ってことをやっていきたいと思います。

まあ噛み砕いでいうとレジのあの機械の中身の計算をやっちゃおうってことですね。

最小のお釣りって？
貨幣の枚数計算のアルゴリズム
コードの実装
全体のコード
実際に動かしてみた〜まとめ

最小のお釣りって？

まず日本で現在持ちられている貨幣の種類は、

¥10000
¥5000
¥2000
¥1000
¥500
¥100
¥50
¥10
¥5
¥1

の10種類ですよね。
この中でお釣りとして返ってくることを考えると、
一万円札が返ってくることはありませんよね。

一万円が返ってくるってことはそもそも、その一万円札は支払いの時に出さなくてよかった一万円だからね

そして二千円さつが返ってくることもありませんよね。

流通量が少ないしね

てことで残りの8種類の貨幣が返ってくるわけですがその際の枚数は可能な限り少なく返ってきます。
例えば、お釣りが¥6000だとしたら、
千円札が6枚ではなく、五千円札１枚と、千円札1枚で返ってきますよね。
この時の各貨幣の枚数の計算を、今回はお釣りの最小化問題としてプログラミングしてみます！

貨幣の枚数計算のアルゴリズム

まあこれはアルゴリズムっていうほどでもないですね。
お釣りの合計から、できる限り大きな金額の貨幣を出し続けることで最小化できます。
これを四則演算を用いて表記すると以下のようになります。

お釣りの合計を5000で割った商を求める

お釣りの合計から5000と上で求めた商との積を引く

そのお釣りの残金を1000で割った商を求める

お釣りの残金から1000と上で求めた商との積を引く
・
・
・
お釣りの残金から5と上で求めた商との積を引く

ここまで計算して、
画数で割った際の商がその貨幣の枚数であり、
最終的に残った値が1円の枚数となります。

具体的やってみましょう。
¥2153の商品を、1万円札を出して購入した際のお釣りは
10000-2153=7467
であり、これを上のアルゴリズムで計算してみます。

こんな感じで筆算を行なって５で割れないところまで来ました。
この時の貨幣の枚数は
五千円札が１枚
千円札が2枚
百円玉が4枚
五十円玉が1枚
十円玉が1枚
五円玉が1枚
一円玉が２枚
て感じです。良さそうですね。

コードの実装

ここからは実装です。

貨幣の金額を入れた配列

まずは貨幣の情報を打ち込みましょう。

int money[7] = {5000,1000,500,100,50,10,5};

これは関数の外側に定義する配列です。
ここには上で説明した8種類の貨幣のうち1円以外を全て羅列したものです。
ここで配列にすることで後の操作を楽にしています。

最小化の関数

ここから最小化の関数です。

void cal_change(int x){
    int X = x;
    
    for(int i=0; i<7; i++){
        printf("¥%d:%d枚\n",money[i],X/money[i]);
        X -= money[i]*(X/money[i]);
    }
    printf("¥1:%d枚\n",X);
}

仮引数のint xでお釣りの金額を受け取ります。
そしたらすぐにXにその値を代入。
なんでXに代入するかというと、その値からどんどん引いて残金を求めていくからですね。

ここからはfor文です。
一文目はprintf文。

printf("¥%d:%d枚\n",money[i],X/money[i]);

一つ目の引数がmoney[i]です。
これは先ほど定義した貨幣の金額を出力してるってことですね。

二つ目の引数はX/money[i]です。
これが商を求めている、つまり貨幣money[i]の枚数を出力しているってことですね。

この二つを合わせて、
¥AAA : BBB枚
という出力になります。

二文目は残金計算

X -= money[i]*(X/money[i]);

money[i]*(X/money[i])は
money[i]とお釣りの残金をmoney[i]で割った商との積
を表しています。

その値をお釣りの残金から引いて、それを新たなお釣りの残金としています。

そして、最後にXに残る値は5で割り切れなかったお釣りの残金。
つまり1円の枚数そのものなので

printf("¥1:%d枚\n",X);

として1円の枚数を出力してます。

全体のコード

int money[7] = {5000,1000,500,100,50,10,5};

void cal_change(int x){
    int X = x;
    
    for(int i=0; i<7; i++){
        printf("¥%d:%d枚\n",money[i],X/money[i]);
        X -= money[i]*(X/money[i]);
    }
    printf("¥1:%d枚\n",X);
}

int main(int argc, const char * argv[]) {
    int change;
    printf("お釣りの金額を入力:");
    scanf("%d",&change);
    cal_change(change);
    
    return 0;
}