使用计数器查找 GCD - Python

Question

我正在尝试使用计数器 class 计算两个数字的 GCD。我已经实施了我的因式分解并使用交集来获得最小因式分解，但是我不确定我究竟如何从这里取得进展。更具体地说-

gcd(120, 500) 让我在包含 2:2、5:1

的计数器处

如何以表示 2^2 x 5^1 的方式使用这些数字？

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

min = x & y

return min

我现在的input/output：

在[29]中：gcd(120, 500)

输出[29]: 计数器({2:2, 5:1})

我是 Python 的新手，所以任何关于如何进步的解释和建议都将不胜感激！谢谢:)

Answer 1

遍历 "min" 的项目。启动运行产品，prod = 1 对于每个项目：关键是乘数；价值就是力量 "prod" "key"、"power" 倍。

当您完成 "min" 中的所有因素后，prod 就是您的 GCD。

Answer 2

您可以从计数器对象中获取 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())

产生的所有内容

Answer 3

解决您的问题并同时学习 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

Answer 4

我最终找到了一个相当简单的答案 -

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

谢谢大家的帮助，我觉得我现在当然明白如何处理 counter an dict 类好多了。

使用计数器查找 GCD - Python

Finding the GCD using Counter - Python

python

counter