algorithm - 最大の合計と最小の正の差を見つける方法は?

Question

数字の 9、8、7、6、5、4 をそれぞれ 1 回使用して、次を見つけます。

a) 可能な最大額

可能な最大の合計を与えるソリューション以上のものはありますか? それが可能な最大の合計であることをどのように知っていますか?

b) 可能な限り小さい (正の) 差

複数の解決策がありますか? それが可能な限り最小の違いであることをどのように知っていますか?

数字は 3 桁でなければなりません。たとえば、965 + 784 または 879 - 654

Answer 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)]

したがって、違いには独自の解決策があります。

他の人が示しているように、論理的な推論によってこの問題を解決する方がエレガントだと思います。これは、彼らが正しかったことを証明しています。