例如。循环遍历1-99和1-99的所有组合,使它们的乘法总数按降序进行。

99 * 99 = 9801
99 * 98 = 9702
98 * 98 = 9604
99 * 97 = 9603
98 * 97 = 9506
99 * 96 = 9504
...
 5 *  1 = 5
 2 *  2 = 4
 4 *  1 = 4
 3 *  1 = 3
 2 *  1 = 2
 1 *  1 = 1

我试了几天才想出一个模式。在这一点上,我认为不先进行乘法运算是不可能的有人这样做过吗?

最佳答案

这里有一个合并排序风格的分治方法,它使用o(log n)内存和o(nlogn)时间。它将产品中第一个数字的范围减半,然后懒洋洋地合并生成产品的结果我使用了一个技巧,在生成器中使产品为负,这样结果就以降序而不是升序的形式出现。

import heapq

def inorder(a0, a1):
    if a1 - a0 == 1:
        return ((-a0*b, a0, b) for b in xrange(a0, 0, -1))
    am = (a0 + a1) // 2
    return heapq.merge(inorder(a0, am), inorder(am, a1))

for r, a, b in inorder(1, 100):
    print a, '*', b, '=', -r

关于algorithm - 遍历两组数字的所有组合,以使它们相乘的总数按降序排列,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/25922549/

10-09 01:33