例如。循环遍历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/