最小交換硬貨枚数（１）

大学入学共通テスト（４）からの続き

2025年度の大学入学共通テストに新規参入する「情報Ｉ」の試作問題が，日経の朝刊に掲載されていた。

退職前には，監督に当たるのはこれ以上体力的精神的な限界をはるかにこえてもう絶対無理と思っていた大学入学センター試験だ。これが，大学入学共通テストと看板を替えて，教科「情報」を新しい試験科目として追加採用してしまった。情報教育関係の大学や高校の教員の皆さんはお喜びのようであるが，なんだかなぁの案件である。

60分で全問必答の大問が4問出題されている。掲載されていた第3問がプログラミングの問題だったので，さっそくチャレンジしてみた。その問題のテーマは最小交換硬貨枚数だ。最近は，PayPayで支払うことが増えてきたが，財布の硬貨数の制御は老人の認知症防止のために最適である。おつりが増えすぎないように，少し硬貨を加えて切りのよいおつりにするあれね。

例えば，46円の支払いだと，10円×４ + 5円×１ + 1円×１ でもよいし，50円×１ + 1円×１ - 5円×１ もある。ここで，マイナスはお店から戻ってくる硬貨を表わしている。前者の交換硬貨枚数は6枚であり，後者では3枚となり，後者の方が交換硬貨枚数は少ない。

問題の誘導部分を読む前に，さっそくプログラムを作ってみたが，肝腎の多めに払っておつりが返ってくるところに不備がありまくりだった。

function pay(m,y)

    n = 0

    c=[500,100,50,10,5,1]

    d=[y]

    for i in 1:6

        while y-c[i] >= 0

            y = y - c[i]

            n = n + 1

            push!(d,c[i])

        end

    end

    push!(d,-(m+n))

    println(d)

    return m+n

end

function change(y)

    m = 0

    n = 0

    c=[1,5,10,50,100,500]

    d=[y]

    pay(0,y)

    for i in 1:5

        while mod(y,c[i+1])!=0

            y = y + c[i]

            n = n + 1

            push!(d,c[i])

        end

        m1 = m + n

        if m1!=m

            push!(d,-m1)

            print(d)

            pay(m1,y)

            n=0

            deleteat!(d,length(d))

        end

        m = m1

    end

end

change(46)

[46, 10, 10, 10, 10, 5, 1, -6]
[46, 1, 1, 1, 1, -4][50, 50, -5]
[46, 1, 1, 1, 1, 50, -5][100, 100, -6]
[46, 1, 1, 1, 1, 50, 100, 100, 100, 100, -9][500, 500, -10]

そこで，1000円以下なら数もしれているということで，方針を変えて総当たりで確認するアルゴリズムに変更した。全くスマートではないのである。この中から最小値を探すのは目の子でできる。出力される配列 [ ] の中身は，交換される硬貨枚数が並んでいて，マイナスがついたものは店から客へのバック分を表わしている。最後の出力値が交換硬貨枚数だ。

function foop(y)
    c=[1,5,10,50,100,500]
    k=[0,0,0,0,0,0]
    for k[1] in -4:4
    for k[2] in -1:1
        for k[3] in -4:4
        for k[4] in -1:1
            for k[5] in -4:4
            for k[6] in 0:2
                z = 0
                n = 0
                for j in 1:6
                    n = n + abs(k[j])
                    z = z + c[j]*k[j]
                end
                if z==y
                    println(z," : ",k," : ",n)
                end
            end
            end
        end
        end
    end
    end
end

foop(46)

46 : [-4, 0, 0, -1, -4, 1] : 10
46 : [-4, 0, 0, -1, 1, 0] : 6
46 : [-4, 0, 0, 1, 0, 0] : 5
46 : [1, -1, 0, -1, -4, 1] : 8
46 : [1, -1, 0, -1, 1, 0] : 4
46 : [1, -1, 0, 1, 0, 0] : 3
46 : [1, 1, -1, -1, -4, 1] : 9
46 : [1, 1, -1, -1, 1, 0] : 5
46 : [1, 1, -1, 1, 0, 0] : 4
46 : [1, 1, 4, 0, 0, 0] : 6

ここまでくるのに2時間くらいかかったので，とてもじゃないけれど自分の場合60分で大問4問も解けそうにはない。ループ変数を配列にするなんていうのは初めての経験だった。


写真：日本の通常硬貨（造幣局から引用）