-4

我想将一个大小为 n 的整数数组消除为两个数字，只需将两个以上的数字相乘即可。这两个数（M1 和 M2）的条件是 M1-M2 相减的结果是其他可能情况中的较小值。以下示例更详细地说明了该问题：

假设数组的大小为 4，元素为 [n1,n2,n3,n4]

可能的消除是：

M1 = n1 和 M2 = n2xn3xn4

M1 = n2 和M2 = n1xn3xn4

M1 = n3 和M2 = n1xn2xn4

M1 = n4 和M2 = n1xn2xn3

M1 = n1xn2 和M2 = n3xn4

M1 = n1xn3 和M2 = n2xn4

M1 = n1xn4 和M2 = n2xn3

M1 = n2xn3 和M2 = n1xn4

M1 = n2xn4 和M2 = n1xn3

M1 = n3xn4 和M2 = n1xn2

在这个例子中， M1和M2有十个可能的值，我在我的问题中想要的正确值是 ABS( M1 - M2 ) 在其他九个值中的最小值。它们有可能不止一个正确答案（类似），但这可以忽略，我想要的输出是M1的一个值和M2的一个值

注意：如果它是在 C++ 中，我将不胜感激 :)

提前致谢...

4

1 回答 1

1

我建议使用std::next_permutation生成输入数组的所有排列，并且对于每个排列，您std::accumulate多次使用来创建不同的产品（即一个产品M1只是排列的第一个元素，M2其余的产品，一个产品M1是第一个两个元素的排列和M2是其余的，依此类推，直到你打到中间）。

虽然这不是最优的，因为它会生成一些重复的产品，即它将使用 and 处理排列[n1, n2, n3, n4]，M1 = n1 * n2然后M2 = n3 * n4它将[n2, n1, n4, 3]使用M1 = n2 * n1and处理排列M2 = n4 * n3。该解决方案非常简单且易于编写，但它未能利用乘法可交换的事实。

于 2013-07-30T09:55:31.807 回答