最小交換硬貨枚数（２）

最小交換硬貨枚数（１）からの続き

前回の結果からいくつかの疑問がでてきた。最小交換硬貨枚数の平均値が最小となる中間硬貨は5円でよいのだろうか。5の倍数以外だと，ドルでは25セント，ユーロでは，0.02ユーロ，0.2ユーロ，2ユーロなどの硬貨がある。中国（元，角）や韓国（ウォン）は日本と同じで5の倍数だけだ。

そこで，2円〜9円までの中間硬貨を設定したときの最小交換硬貨枚数の平均値を求めてみることにする。ついでに，硬貨種類別の交換枚数の合計や情報エントロピーも合わせて計算する。なお，1円から1000円までの一円刻みの商品の支払いを硬貨のみで行い，手持ち硬貨数やおつりの硬貨数は冗長性をはぶいた最小の値の範囲で考える。

function foop(m,y)

    nmin = 100

    mm = div(9,m)

    c=[1,m,10,10*m,100,100*m]

    k=[0,0,0,0,0,0]

    t=[0,0,0,0,0,0]

    for k[1] in -(m-1):(m-1)

    for k[2] in -mm:mm

        for k[3] in -(m-1):(m-1)

        for k[4] in -mm:mm

            for k[5] in -(m-1):(m-1)

            for k[6] in 0:mm+1

                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)

                    if n < nmin

                        nmin = n

                        for l in 1:6

                            t[l] = abs(k[l])

                        end

                    end

                end

            end

            end

        end

        end

    end

    end

    return nmin,t

end

function main(m)

  p=[0.,0.,0.,0.,0.,0.]

  s=[0,0,0,0,0,0]

  t=[0,0,0,0,0,0]

  a=zeros(Int,1000)

  sum=0

  for i in 1:1000

    (n,t) = foop(m,i)

    a[i]=n

    sum = sum + n

    for j in 1:6

        s[j] = s[j] + t[j]

    end

#    println(i," ",n)

  end

  inf = 0.0

  for j in 1:6

     p[j] = s[j]/sum

     inf = inf -p[j]*log2(p[j])

  end

  @printf("%.3f : %04d %04d %04d %04d %04d %04d -> %.3f\n",

          inf,s[1],s[2],s[3],s[4],s[5],s[6],sum/1000)

#    println(a)

  plot(a)

end

for i in 2:9

    print(i," ")

    main(i)

end

2 2.301 : 0500 1025 0445 1000 0455 2275 -> 5.700

3 2.473 : 0753 0747 0601 0758 0547 1611 -> 5.017

4 2.552 : 0700 0738 0564 0728 0826 1118 -> 4.674

5 2.487 : 1254 0446 1020 0450 1000 0956 -> 5.126

6 2.466 : 0984 0500 0814 0500 1530 0690 -> 5.018

7 2.491 : 0900 0600 0793 0600 1518 0636 -> 5.047

8 2.458 : 1358 0614 1065 0640 1640 0545 -> 5.862

9 2.314 : 2054 0446 1644 0442 1650 0510 -> 6.746

等比数列の中間値である√10や根拠はないけれどネピア数e 近辺あたりの3円がよいのかと思いきや，4円にすると平均交換硬貨枚数が 4.67枚となって，5円の5.13枚よりも小さくなるのだった。ただし，情報エントロピーの最小値は2円の 2.30なのである。どういう意味かまではわかっていない。

図：1円から1000円までの交換硬貨枚数（中間硬貨は5円）