アルゴリズム入門(自動販売機でお釣りを計算)

今回は、単純な自動販売機を考えてみます。
自動販売機は、投入した金額と購入したい商品の金額を比較して、投入した金額が商品の金額と同じ、または投入した金額のほうが多ければ商品を購入出来ます。
そして、投入した金額のほうが多かった場合はお釣りを計算して返します。
ここでは、この「お釣りを計算して返す部分」を考えます。
金額を計算するだけでなく、どの紙幣、硬貨をそれぞれ何枚ずつ返せばいいのか求めることがポイントです。
例えば、1万円を投入して、2,362円の商品を購入すると、お釣りは7,638円です。
このとき、お釣りはどのように返せばよいでしょうか？
一般的には、お釣りの枚数が少なくなるように計算して返します。
例えば、5千円札1枚と千円札2枚、500円玉1枚、100円玉1枚、10円玉3枚、5円玉1枚、1円玉3枚を返すでしょう。

#!/usr/bin/awk -f

BEGIN{
    turi[0] = 10000;
    turi[1] = 5000;
    turi[2] = 1000;
    turi[3] = 500;
    turi[4] = 100;
    turi[5] = 50;
    turi[6] = 10;
    turi[7] = 5;
    turi[8] = 1;

    printf "insert:";
    getline insert;

    printf "product:";
    getline product;
    money = insert - product;
    if(money < 0){
        print "金額が不足しています";
        exit;
    }
    for(i = 0; i <= length(turi); i++){
        num = int(money / turi[i]);
        if(num){
            print turi[i] "は" num "つ"
            money %= turi[i];
        }
        if(!money){
            break;
        }
    }
}

awk -f oturi.awk 
insert:10000
product:2362
5000は1つ
1000は2つ
500は1つ
100は1つ
10は3つ
5は1つ
1は3つ

自動販売機の出来上がりです。