使用Counter-Python查找GCD

我正在嘗試使用Counter類來計算兩個數字的GCD。我已經實施了我的因子分解，並使用了一個交點來獲得最小因子，但我不確定我從這裏可以取得什麼進展。更具體 -使用Counter-Python查找GCD

GCD（120，500）具有我在含有2計數器的點：2,5：1

如何可以在表示2^2×的方式使用這些數字5^1？

x = Counter(factors(a)) 
y = Counter(factors(b)) 

min = x & y 

return min

我的電流輸入/輸出：

在[29]：GCD（120，500）

缺貨[29]：計數器（{2：2,5：1}）

我對Python相當陌生，因此對於如何進步的任何解釋和建議將不勝感激！謝謝:)

來源

2015-09-15 Forever_Lona

計數器是一種字典。只需遍歷字典並計算產品。 –

你爲什麼使用計數器？ –

其所需的 - 是的，這是一個教程的一部分，但我很卡住，無法與我的導師:) 我馬上去字典類型有點接近取得聯繫，謝謝 –

我發現在最後一個相當簡單的答案 -

x = Counter(factors(a)) 
y = Counter(factors(b)) 

min = x & y 

gcd = 1 

for key, value in min.items(): 
    gcd = gcd * key ** value 

return gcd

謝謝大家的幫助，我覺得我肯定知道如何同時處理好遠，現在對抗的字典類。

來源

2015-09-16 00:40:07

...這就是在那裏我希望我的回答會導致你。請「接受」的答案之一 - 比如你自己 - 所以，這個問題正確關閉。 – Prune

我不能接受我自己的，但我會這樣做:) –

循環「min」項目。開始正在運行的產品，prod = 1 對於每個項目：關鍵是乘數;該值是電源通過「鑰匙」，「電源」次數的多個「prod」。

當你在「min」中經歷了所有因素後，prod就是你的GCD。

來源

2015-09-15 23:40:47 Prune

你可以從計數器對象items：

>>> counter = Counter({2: 2, 5: 1}) 
>>> import operator 
>>> reduce(operator.mul, (factor ** count for factor, count in counter.items()) 
20

reduce保持在序列和以前的結果應用函數值，直到它使用了序列中的一切。

所以我們採用乘法運算mul一切由發電機(factor ** count for factor, count in counter.items())

來源

2015-09-15 23:43:10

我已經成功通過一些試驗和錯誤來得到答案9，然而我相信的答案應該是20（2^2 = 4，5^1 = 5，5 * 4 = 20）。這是我掙扎的地方。我會堅持下去！ –

@Forever_Lona'5 * 4'從哪裏來？ –

也許我在某個地方被誤解了，但我的講義建議找到GCD，2^2和5^1的結果必須相乘。 –

得到解決你的問題，並在同一時間學習Python的最好方法是交互式探索類。在你的情況，你可以嘗試以下

>>> import collections 
>>> counter = collections.Counter() 
>>> counter[2] = 2 
>>> counter[5] = 1 
>>> print counter 
Counter({2: 2, 5: 1}) 
>>> dir(counter) 
['__add__', '__and__', '__class__', '__cmp__', '__contains__', '__delattr__', 
'__delitem__', '__dict__', '__doc__', q__', '__format__', '__ge__', '__getattribute__', 
'__getitem__', '__gt__', '__hash__', '__init__', '__iter__', '__len__', '__lt__', 
'__missing__', '__module__', '__ne__', '__new__', '__or__', '__reduce__', '__reduce_ex__', 
'___', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__sub__', '__subclasshook__', 
'__weakref__', 'clear', ', 'elements', 'fromkeys', 'get', 'has_key', 'items', 'iteritems', 
'iterkeys', 'itervalues', 'keys', 'most_common', ', 'popitem', 'setdefault', 'subtract', 
'update', 'values', 'viewitems', 'viewkeys', 'viewvalues']

在這個階段，你應該探究一下每個方法的

>>> counter.keys() 
[2, 5] 
>>> counter.values() 
[2, 1] 
>>> counter.items() 
[(2, 2), (5, 1)]

讓我們確認items()纔是正道

>>> help(counter.items) 
Help on built-in function items: 

items(...) 
    D.items() -> list of D's (key, value) pairs, as 2-tuples

然後解決方案很簡單 - 我們要添加每對的指數

>>> [ factor ** count for factor, count in counter.items()] 
[4, 5] 
>>> sum([ factor ** count for factor, count in counter.items()]) 
9

來源

2015-09-15 23:51:05

你並不需要建立名單只是爲了總結 –

使用Counter-Python查找GCD

回答

相關問題