金額と枚数を指定した両替

本当に分からないので教えてください４ -OKWave からですが、最初に断っておくと、正しい解き方 (計算量が少ないとか、十分高速に解けるとか) が分かっていません。

金額と枚数を指定した両替 - みずぴー日記でも mzp さんが解いていますが、こちらの場合も計算時間がかかるようです。

さて、問題は以下のようなものです。

金額と枚数を入力する．
硬貨，紙幣の合計が入力金額，合計枚数が入力枚数になる
場合を1つ見つけるプログラムを作成せよ．
使える硬貨，紙幣は
一万円，五千円，千円，五百円，百円，五十円，十円，五円，一円
とする．
また，各硬貨，紙幣の枚数が求められたら，合計枚数と合計金額が
間違いないか確かめを行うプログラムを追加し，結果を表示せよ．
＜実行結果＞
金額:1234
枚数:999
10000 : 0
5000 : 0
1000 : 0
500 : 0
100 : 0
50 : 0
10 : 0
5 : 55
1 : 944

金額 : 1219
枚数 : 999

良く分からないのですが、愚直にループを並べてみます。 絶対に真似をしないでください。

#! /usr/local/bin/gawk -f
# money.awk
# お金の合計金額と枚数から該当するとおりを見つけ出す
# usage: gawk -f money.awk total num

BEGIN {
    total = ARGV[1];
    num   = ARGV[2];

    for (a = 0; a <= num; a++) {
    for (b = 0; b <= num - a; b++) {
    for (c = 0; c <= num - a - b; c++) {
    for (d = 0; d <= num - a - b - c; d++) {
    for (e = 0; e <= num - a - b - c - d; e++) {
    for (f = 0; f <= num - a - b - c - d - e; f++) {
    for (g = 0; g <= num - a - b - c - d - e - f; g++) {
    for (h = 0; h <= num - a - b - c - d - e - f - g; h++) {
    for (i = 0; i <= num - a - b - c - d - e - f - g - h; i++) {
        if (10000 * a + 5000 * b + 1000 * c + 500 * d + 100 * e + 50 * f + \
               10 * g + 5 * h + i == total && \
            a + b + c + d + e + f + g + h + i == num) {
            print "10000 : "    a;
            print "5000 : "     b;
            print "1000 : "     c;
            print "500 : "      d;
            print "100 : "      e;
            print "50 : "       f;
            print "10 : "       g;
            print "5 : "        h;
            print "1 : "        i;
            exit;
        }
    } } } } } } } } }
}

なんというループ・・・ですが、解くことはできます。

$ gawk -f money.awk 1219 55
10000 : 0
5000 : 0
1000 : 0
500 : 0
100 : 0
50 : 18
10 : 30
5 : 3
1 : 4

ただし、999 枚を計算しようとすると終わりません。

真面目に探索した方が良いのか、最近 gawk で採用された Indirect Function を使うと簡単に記載できるのではないかと思案中のまま放置されていました。