从给定的数字计算唯一值

Question

从给定的数字计算唯一值

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

什么是最简单的算法方法来编写一个解决这个问题的程序？

- Rckt

@jozefg 看起来它没有重复使用数字。((3+6)*100)+50)+75/25=953。 - ntalbs

哦，我忘了说明。每个数字只能使用一次。允许的操作：+、-、*和/。 - Rckt

你近期会进行倒计时吗？ - diolemo

@diolemo 抱歉，我不明白你的意思。 - Rckt

@Rckt Countdown是一档电视节目。你的问题与节目中的数字部分相同。参赛者必须使用6个数字和定义的运算符获得结果。https://www.youtube.com/watch?v=pfa3MHLLSWI - diolemo

显示剩余4条评论

5个回答

4

我认为最简单的算法方法是回溯算法。它相当容易实现，并且始终会找到解决方案（如果存在）。基本思想是递归的：在构建解决方案的每个步骤中进行任意选择，然后从那里继续。如果不起作用，请尝试其他选择。当您用尽所有选择时，请向前一个选择点报告失败（或者如果没有前一个选择点，则报告无法找到解决方案）。

你的选择是：涉及多少数字、每个数字是什么（每个数字位置的一个选择）以及它们如何通过运算符连接（每个运算符位置的一个选择）。

- Ted Hopp

1

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

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

- gnlogic

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

- Hot Licks

0

使用递归对数字和运算符进行排列。其时间复杂度为O(6!*4^5)。

- songlj

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sergey Kalinichenko · Accepted Answer

最简单的方法是尝试它们所有：您有六个数字，这意味着有最多五个位置可以放置运算符，以及高达 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.
}