再帰的に四則を解くアルゴリズム。遅い。計算量とかよく知らない。
def copy(a,m,n) b = [] for i in 0..(a.length()-1) if i != m && i != n b[i] = a[i] else b[i] = nil end end return b.compact end def shisoku_sub(a,n,siki) num = a.length() if a.length() == 1 then if a[0] == n then puts siki @ans << siki end else for i in 0..(num-1) for j in 0..(num-1) unless i == j if i > j then shisoku_sub(copy(a,i,j).push(a[i]+a[j]),n,copy(siki,i,j).push("("+siki[i]+"+"+siki[j]+")")) shisoku_sub(copy(a,i,j).push(a[i]*a[j]),n,copy(siki,i,j).push("("+siki[i]+"×"+siki[j]+")")) end shisoku_sub(copy(a,i,j).push(a[i]-a[j]),n,copy(siki,i,j).push("("+siki[i]+"-"+siki[j]+")")) if a[j] != 0 then shisoku_sub(copy(a,i,j).push(Rational(a[i],a[j])),n,copy(siki,i,j).push("("+siki[i]+"÷"+siki[j]+")")) end end end end end end def shisoku(a,n) @ans = [] siki = a.map do |i| i.to_s end shisoku_sub(a,n,siki) puts "complete!!" puts @ans.uniq end
shisoku([3,3,8,8],24) #=> (8÷(3-(8÷3)))
累乗対応は桁が大きくなりすぎて失敗。対数は丸め誤差がこわい。
メモ化なる概念を知ったので今度試してみようと思う。
どうでもいいけど四則ソルバで検索して出てくる記事書いてるのだいたい灘校生で面白い。