找到一个数学算法的方程式 [英] Find a math algorithm for an equation

问题描述

我只是张贴在math.stackexchange一个数学问题，但我会问这里的人一个编程递归算法。

I just post a mathematic question at math.stackexchange, but I'll ask people here for a programmatically recursive algorithm.

的问题：从1到9（一次且仅一次各空白）填空号码完成方程。

The problem: fill in the blank number from 1 to 9 (once and only once each blank) to finish the equation.

附加条件：

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的答案。我想有一个递归算法来找出所有的解决方案。

There should be more than 1 answer. I'd like to have a recursive algorithm to find out all the solutions.

<一个href="http://math.stackexchange.com/questions/1288170/just-a-3rd-grade-math-problem-in-my-country-please-help">Original问题

PS：我想了解递归算法，性能improval。我试图解决使用蛮力的问题。我的电脑冻结了好一阵子。

PS: I'd like to learn about the recursive algorithm, performance improval. I was trying to solve the problem using brute force. My PC freeze for quite a while.

推荐答案

您已经找到合适的permuations

You have to find the right permuations

9！ = 362880

9! = 362880

这是不是一个很大的数字，你可以做你的计算方式如下：

This is not a big number and you can do your calculations the following way:

isValid(elements)
    //return true if and only if the permutation of elements yields the expected result
end isValid

的isValid 的验证，检查一个给定的排列是否正确。

isValid is the validator, which checks whether a given permutation is correct.

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

呼叫计算如下：

calculate(emptySet, 1)

这篇关于找到一个数学算法的方程式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！