横着なそろばん(Ruby)
アルゴリズム・パズルです。
問題:
そろばんで例えば「8 + 9」をこの順に計算すると、「8 を入れる」のに玉を 4つ動かし、「9 を足す」のに玉を 2つ動かすので、全部で 6回玉を動かすことになります。また、逆に「9 + 8」の順に計算すると、全部で玉を 8回動かすことになります。このように、同じ答えになる場合でも、玉を動かす回数が異なることがあります。
さて、1 から 10 までの総和をこのようにそろばんで求めるとき、玉を動かす数の最小値はいくらになるでしょうか。
Ruby で解いてみました。
q55.rb
@table = [[0, 1, 2, 3, 4, 1, 2, 3, 4, 5], [0, 1, 2, 3, 2, 1, 2, 3, 4, 1], [0, 1, 2, 3, 2, 1, 2, 3, 2, 1], [0, 1, 4, 3, 2, 1, 2, 3, 2, 1], [0, 5, 4, 3, 2, 1, 4, 3, 2, 1], [0, 1, 2, 3, 4, 1, 2, 3, 4, 5], [0, 1, 2, 3, 2, 1, 2, 3, 4, 1], [0, 1, 2, 3, 2, 1, 2, 3, 2, 1], [0, 1, 4, 3, 2, 1, 2, 3, 2, 1], [0, 5, 4, 3, 2, 1, 4, 3, 2, 1]] def cal(a, b) n1, n2 = a / 10, a % 10 if b == 10 @table[n1][1] else @table[n2][b] + ((n2 + b >= 10) ? @table[n1][1] : 0) end end def solve(before, after, sum, co) if before.empty? if @min > co @min = co p [@min, after] #=>[26, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]] end return end before.size.times do |i| a = before[i] b = co + cal(sum, a) next if b >= @min after1 = after + [a] before1 = before[0, i] + before[i + 1..-1] solve(before1, after1, sum + a, b) end end @min = Float::INFINITY solve([*1..10], [], 0, 0)
答えは 26回ですね。ふつうに 1 から 10 まで順に足すのが最小値を与えるようです(この順だけが最小値を与えるわけではありません。最小値を与える足し方は 614880 通りもあります)。かかった時間は自分の環境でほぼ 4.2秒、solve() 呼び出しの回数は 4090969回です。模範解答とはちがって Array#permutation を使ってはいません。
なお、コード中の after の項はここでは本質的に必要ないので、これをカットすると多少高速化し、実行時間は 3.3秒ほどになります。
ちなみに、最大値は 42 で、例えば [3, 2, 4, 1, 5, 8, 7, 9, 6, 10] の順に足すとこれが得られます。なるほど、5 を作っていくと大きくなるようです。26 と 42 とは結構差があるものですね。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (9件) を見る