「数値と演算の組み合わせの問題」とはどういうことかと言いますと、先日Twitterに流れてきた投稿をみたらこんなんがありました。（元ネタがアレなので、問題の設定は変えてあります）
勇者は５種類の薬を持っている。
A. MPを半分にする薬
B. MPを900減らす薬
C. MPを2000増やす薬
D. MPを5倍にする薬
E. MPを500増やす薬今のMPは0である。MPを3000にしたい場合、どの順序で薬を飲めばよいか？
普通に計算してもよいのですが、今回は計算機の力を使い総当たりでやってみしょう。
愚直にfor loopを薬の数だけ書くやり方もありますが、面倒くさいので深さ優先探索を使います。
# n: 計算途中のMP
# lst: 残っている薬
# hist: これまで使った薬
def calc(n, lst, hist):
# 全て薬を使ったら、3000になっているかチェック
if len(lst) == 0:
if n == 3000:
print(hist)
return
# 残っている薬でイテレーション
for i in range(len(lst)):
# 元のリストが変わると困るのでコピー
l = lst[:]
h = hist[:]
oper, num = l[i]
# これまで使った薬リストに選んだ薬を入れる
h.append(l[i])
# 使った薬をリストから消す
l.pop(i)
# 足し算か掛け算かで分ける
if oper == '+':
calc(n + num, l, h)
else:
calc(n * num, l, h)
# 計算する
calc(0, [('*', 0.5), ('*', 5), ('+', -900), ('+', 500), ('+', 2000)], [])
再帰を使って総当りを表現した、何の変哲もない深さ優先探索です。
結果は以下。
[('+', -900), ('+', 2000), ('*', 5), ('+', 500), ('*', 0.5)]
[('+', 2000), ('*', 0.5), ('+', -900), ('+', 500), ('*', 5)]
[('+', 2000), ('*', 0.5), ('+', 500), ('+', -900), ('*', 5)]
[('+', 2000), ('+', -900), ('*', 5), ('+', 500), ('*', 0.5)]
たかだか$5!$=120通りの演算なので楽勝ですね。以上。