読者です 読者をやめる 読者になる 読者になる

Redundanz

僕の言葉は、人と話をするためにあるんじゃない。

四則ソルバ書いてみました

ruby

再帰的に四則を解くアルゴリズム。遅い。計算量とかよく知らない。

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)))

累乗対応は桁が大きくなりすぎて失敗。対数丸め誤差がこわい。
メモ化なる概念を知ったので今度試してみようと思う。

どうでもいいけど四則ソルバで検索して出てくる記事書いてるのだいたい灘校生で面白い。