5

使用数字 9、8、7、6、5 和 4 各一次，找到以下内容：

a) 最大可能的总和

除了提供最大可能总和的解决方案之外，还有更多的解决方案吗？你怎么知道这是可能的最大金额？

b) 尽可能小的（正）差异

有不止一种解决方案吗？你怎么知道这是最小的差异？

数字必须是 3 位数字。例如，965 + 784 或 879 - 654

4

3 回答 3

3

嗯很有趣

区别：

(a_1,b_1),(a_2,b_2),(a_3,b_3)如果你总是为tupels 取值a_1a_2a_3-b_1b_2b_3，那么区别是：

100*(a_1-b_1)+10*(a_2-b_2)+(a_1-b_1)

因此，对于最小的差异，我想这应该是完整的-(a_2-b_2) > -(a_3-b_3) > (a_1-b_1)：：

(a_2-b_2) = 4-9 = -5 = d_2
(a_3-b_3) = 5-8 = -3 = d_3
(a_1-b_1) = 7-6 =  1 = d_1

给你745-698 = 47哪个是唯一最小的，因为在所有其他变体d_2中会更大或d_3更大甚至d_1。它也是独一无二的（所以只有一个解决方案），因为它是在正差异之后询问的，所以你不能切换数字。

和：

所以对于我们得到的总和：

100*(a_1+b_1) + 10*(a_2+b_2) + (a_2+b_2)

所以现在(a_1+b_1)>(a_2+b_2)>(a_3+b_3)：

a_1+b_1 = 8+9 = 17
a_2+b_2 = 7+6 = 13
a_3+b_3 = 4+5 = 9

所以它964+875 = 975+864 = 1839不是唯一的，但仍然是最大的。因为你可以改变b_i并且a_i你有2^3可能建立这个总和。

于 2013-10-07T22:15:01.930 回答
1

确保尝试所有组合并记住最佳解决方案。但是当你聪明时，你可以通过以下方式避免它：

  1. 最大总和为 975 + 864 = 1839

    • 或任何将较大数字均匀分配到较高数字位置的组合
    • 就像 Shashank Gupta 在评论中所写

  2. 最小正差相似 745 - 698 = 47

    • 第二个数字（没有第一个数字）必须尽可能大
    • 第一个数字（没有第一位）必须尽可能小
    • 第一位数字只能相差 1
    • 经过一番思考，您应该得出相同的结果
于 2013-10-07T22:17:12.850 回答
1

由于您要求算法，因此这是python中的蛮力解决方案：

In [1]: from itertools import permutations
In [2]: def gen_pairs():
   ...:     for p in permutations('987654'):
   ...:         yield int(''.join(p[:3])), int(''.join(p[3:]))
In [3]: '%i = %i + %i' % max((a+b, a, b) for a,b in gen_pairs())
Out[3]: '1839 = 975 + 864'
In [4]: '%i = %i - %i' % min((a-b, a, b) for a,b in gen_pairs() if a>b)
Out[4]: '47 = 745 - 698'

这只是为您提供最小值和最大值。要检查唯一性：

In [4]: [(a,b) for (a,b) in gen_pairs() if a+b == 1839]
Out[4]: 
[(975, 864),
 (974, 865),
 (965, 874),
 (964, 875),
 (875, 964),
 (874, 965),
 (865, 974),
 (864, 975)]

请注意，如果您不计算交换的答案，这些只是 4 个解决方案。

In [5]: [(a,b) for (a,b) in gen_pairs() if a-b == 47]
Out[6]: [(745, 698)]

所以差异有一个独特的解决方案。

我认为通过逻辑推理来解决这个问题更优雅，正如其他人所展示的那样。这只是证明他们是对的。

于 2013-10-07T22:22:00.057 回答