最適なお釣りの計算

大学のプログラミング課題ができません。という書き込みを見て、こういう支払いをするのは日本人的な発想なんだろうなと毎回思います。 イギリスに何ヶ月か行っていた時に、スーパーで同じような支払いをすると断られたことがあります。 所持金が 1443 円で 667 円の買物をしたら、1000 円出すのが普通らしく、667 円、668 円、669 円、670 円、680, 690, 700, 800, 900, 1000 と足し算で数えながらお釣りをくれます。(もちろん、イギリスなので円ではなく当時はポンドでしたが)

いろいろな方法があると思いますが、ここでは最初に払えるかどうかを計算して、払える中で計算しています。 この場合、多値が扱えたりオブジェクト指向で組むことができるともっと簡単に組むことができるでしょう。

#! /usr/bin/gawk -f
# change_calc.awk

BEGIN {
    my_money = ARGV[1];
    value    = ARGV[2];

    min_count = 10000;

    for (i = value; i <= my_money; i++) {
        num_unit = split(calc_change_mount(i), each_i);
        num_my_unit = split(calc_change_mount(my_money), each_my);

        # 支払うことができるかどうか?
        enable = 1;
        for (j in each_i) {
            if (each_my[j] < each_i[j]) {
                enable = 0;
            }
        }

        # 支払える場合
        if (enable == 1) {
            count = 0;
            diff = i - value;
            num_diff = split(calc_change_mount(diff), each_diff);
            for (j in each_diff) {
                count += each_diff[j];
            }
            if (min_count > count) {
                min_count = count;
                min_pay = i;
                min_diff = diff;
            }
        }
    }

    print min_pay " 円払うといいよ。"
    ##print min_count;
    ##print calc_change_mount(min_pay);
    ##print calc_change_mount(min_diff);
}

function calc_change_mount(val,     i, unit, num_unit, each_unit, \
                           num_each_unit, ret_val) {
    unit = "1000 500 100 50 10 5 1";
    num_unit = split(unit, each_unit);

    for (i = 1; i <= num_unit; i++) {
        num_each_unit[i] = int(val / each_unit[i]);
        val -= each_unit[i] * num_each_unit[i];
    }

    for (i = 1; i <= num_unit; i++) {
        ret_val = ret_val " " num_each_unit[i];
    }

    return ret_val;
}

実際に計算してみます。

$ gawk -f change_calc.awk 1443 667
1222 円払うといいよ。

決して難しいことをしているわけではなく、if 文と for 文のみです。

正直初心者にここまでやらせるのはどうかと思ってしまうマス。

とありますが、Drald E. Knuth の言葉を借りれば、頭の整理をすれば良いだけなのではないでしょうか。

It has been often said that a person does not really understand
something until he teaches it to someone else. Actually a person does
not really understand something until he can teach it to a computer,
i.e., express it as an algorithm.