3

假设我有一些 6 个随机数，我想从这些数字中计算出一些唯一值。

编辑： 允许的操作是 +、-、* 和 /。每个号码只能使用一次。您不必使用所有数字。

例子： 

Given numbers: 3, 6, 100, 50, 25, 75
Requested result: 953

3 + 6 = 9
9 * 100 = 900
900 + 50 = 950
75 / 25 = 3
3 + 950 = 953

编写解决此问题的程序的最简单算法方法是什么？

4

5 回答 5

4

最简单的方法是全部尝试：您有六个数字，这意味着您可以在最多五个位置放置运算符，并且最多可以6!排列。鉴于只有四个运算符，您需要通过6!*4^5, 或 737280 种可能性。这可以通过递归函数轻松完成，甚至可以使用嵌套循环。根据语言，您可以使用库函数来处理排列。

与语言无关的递归方法将让您定义三个函数：

int calc(int nums[6], int ops[5], int countNums) {
    // Calculate the results for a given sequence of numbers
    // with the specified operators.
    // nums are your numbers; only countNums need to be used
    // ops are your operators; only countNums-1 need to be used
    // countNums is the number of items to use; it must be from 1 to 6
}

void permutations(int nums[6], int perm[6], int pos) {
    // Produces all permutations of the original numbers
    // nums are the original numbers
    // perm, 0 through pos, is the indexes of nums used in the permutation so far
    // pos, is the number of perm items filled so far
}

void solveRecursive(int numPerm[6], int permLen, int ops[5], int pos) {
    // Tries all combinations of operations on the given permutation.
    // numPermis the permutation of the original numbers
    // permLen is the number of items used in the permutation
    // ops 0 through pos are operators to be placed between elements
    // of the permutation
    // pos is the number of operators provided so far.
}
于 2012-12-31T15:12:11.317 回答
4

我认为最简单的算法方法是回溯。它相当容易实现，如果存在，总会找到解决方案。基本思想是递归的：在构建解决方案的每个步骤中做出任意选择，然后从那里开始。如果不成功，请尝试不同的选择。当您用完选项时，将失败报告到上一个选择点（如果没有上一个选择点，则报告找不到解决方案）。

您的选择是：将涉及多少个数字，每个数字是什么（每个数字位置的选择）以及操作员如何连接它们（每个操作员位置的选择）。

于 2012-12-31T15:16:29.093 回答
1

当您提到“唯一数字”时，假设您的意思是使用手头的所有数字生成的可能结果域中的结果。

如果是这样，为什么不首先尝试排列所有运算符和可用数字呢？

于 2012-12-31T15:14:07.863 回答
1

如果你想保证你从这些数字中生成一个唯一的数字，而没有机会从不同的数字集中得到相同的数字，那么你应该使用基数算术，类似于十进制、十六进制等。

但是您需要知道数字的最大值。

基本上，它会是A + B * MAX_A + C * MAX_A * MAX_B + D * MAX_A * MAX_B * MAX_C + E * MAX_A * MAX_B * MAX_C * MAX_D + F * MAX_A * ... * MAX_E

于 2012-12-31T15:36:57.080 回答
0

使用递归来排列数字和运算符。它是 O(6!*4^5)

于 2012-12-31T15:22:15.110 回答