循環兩組數字的所有組合，使得它們的乘積的總和按降序排列

例如，循環遍歷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

我試了幾天想出一個模式。在這一點上，我認爲如果不先進行乘法運算是不可能的。有沒有人做過這個？

來源

2014-09-18 Inaccurate-

http://pastebin.com/x5HSPjPG是一個開始。數字組合在那裏，只是不按順序。 – 2014-09-18 22:52:13

下面是使用O（log n）內存和O（n log n）時間的合併排序樣式分而治之方法。它將產品中第一個數字的範圍縮小一半，然後懶散地合併懶惰地生成產品的結果。我已經使用了在發生器中使產品成爲負數的技巧，以便結果以降序而不是升序排列。

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

來源

2014-09-18 23:52:39

這是完美而神奇的。謝謝！ – 2014-09-19 14:43:12

這個問題本質上是Order (a,b) pairs by result of a*b

我已經通過對問題的所有答案顯得重複，仍然相信我的是最好的，但它不是被接受的一個。 :)

關鍵的一點是：

假設a * b = c，以使得C是目前唯一可以得到
最大的產品則是下一個最大的產品(a - 1) * b或a * (b - 1)？
我們不知道，除非我們對它們進行比較，因此，我們需要在每個迭代中保持優先級隊列
所以，我們從優先級隊列的最大的產品，然後添加到優先級隊列(a - 1) * b和a * (b - 1)

但是，如果您需要循環所有組合，到目前爲止，最簡單的解決方案是生成所有產品然後進行排序。它只有10000個項目，所以通過使用上述方法獲得的效率增益最小。

來源

2014-09-19 00:27:45 wookie919

感謝您的鏈接;這是完美的。我不確定你的算法是否完全正確。例如，對於a * b = c，使得c是當前最大的乘積，a是98，b是98.c將是9604。第二大實際上是（a + 1）*（b-1）'。不是「（a-1）* b」或「a *（b-1）」。儘管我沒有真正考慮過，但優先隊列是一個好主意。 – 2014-09-19 14:37:12

這是正確的，因爲'（a + 1）*（b-1）'已經在優先級隊列中或者已經從優先級隊列中移除。（而且我之前實際上已經實現了這一點。） – wookie919 2014-09-21 21:15:08

循環兩組數字的所有組合，使得它們的乘積的總和按降序排列

回答

相關問題