我刚刚在 math.stackexchange 上发布了一个数学问题,但我会向这里的人们询问一个以编程方式递归的算法。
问题:填入从 1 到 9 的空白数字(每个空白一次且仅一次)以完成方程。
附加条件:
1. Mathematic priority DOES matter.
2. All numbers (include evaluation result) should be integers.
Which mean the divide should be divisible (E.g. 9 mod 3 = 0 is OK, 8 mod 3 != 0 is not OK).
3. For those who don't know (as one in the original question), the operations in the diagram are:
+ = plus; : = divide; X = multiple; - = minus.
应该有超过 1 个答案。我想要一个递归算法来找出所有的解决方案。
原问题 https://math.stackexchange.com/questions/1288170/just-a-3rd-grade-math-problem-in-my-country-please-help
PS:我想了解一下递归算法,性能改进。我试图用暴力来解决这个问题。我的电脑冻结了很长一段时间。
你必须找到正确的排列
9! = 362880
这不是一个很大的数字,您可以按以下方式进行计算:
isValid(elements)
//return true if and only if the permutation of elements yields the expected result
end isValid
isValid
是验证器,它检查给定的排列是否正确。
calculate(elements, depth)
//End sign
if (depth >= 9) then
//if valid, then store
if (isValid(elements)) then
store(elements)
end if
return
end if
//iterate elements
for element = 1 to 9
//exclude elements already in the set
if (not contains(elements, element)) then
calculate(union(elements, element), depth + 1)
end if
end for
end calculate
Call calculate
如下:
calculate(emptySet, 1)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)