python - 求最大公约数

Question

def gei(a, b):
     '''
     a, b: only positive integers! If you don't, we will make you. Max 1337
     For extracting the juice of the numbers in the form of a common divider
     '''
     #Not Ruby, no to_i, but int()
     smallest = int(abs(min(a, b)))
     biggest = int(abs(max(a, b)))
     print "You inputed: ", smallest, " and ", biggest, " their order doesn't matter."
     print "Do you want to see guess numbers? Type 'yes', if you do! "
     selection = raw_input()
     print
     print
     #To evade infinite loops and too big numbers, we use count.
     count = 0
     ans = smallest
     truth = str(selection) == str('yes')
     def condition(ans, base):
         ans1 = base % ans == 0
         return ans1
     while condition(ans, biggest) == False or condition(ans, smallest) == False:
         ans -= 1
         count += 1
     if count >= 1337:
         break
     elif truth == True:
         print  ans
     if truth == True:
         print
         print
     print  "After weeks of calculation, here is your greater common divider: "
     return ans

所以，是的，八年级的信息学作业来提取常见的更大的分隔符。我想知道，也许你们知道我怎样才能让它不那么麻烦？如何避免在内部使用定义并命名这么多变量？

score 8 · Accepted Answer

import fractions
print fractions.gcd(4,8)
>>> 4

不过你也可以看看源码：

def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a

参考：http ://en.wikipedia.org/wiki/Euclidean_algorithm

score 1 · Accepted Answer

使用欧几里得算法

int GCD(int a,int b){
 if(b==0){
          return a;
 }
 return GCD(b,a%b);        
}

score 0 · Accepted Answer

在您的代码中可以改进一些事情。

首先，truth这是一个真正糟糕的变量名，因为它并没有真正告诉你它的内容是什么意思。我会使用类似的东西show_work。

接下来，您有一个内部函数，它告诉您一个变量除以另一个变量（返回一个布尔值）。我建议直接使用模值，而不是用将其转换为布尔值== 0，而且您也不需要它在函数中。此外，从来没有必要将值与Trueor进行比较False。只需使用值本身（或用于not反转它）。将这些放在一起将使您的while循环条件not biggest % ans and not smallest % ans。

最后，您可以使用比逐个尝试每个值更好的算法。Euclid 算法是一种快速计算最大公约数的好方法，并且在 Python 中很容易实现（但我会留给你）。

score -1 · Accepted Answer

这是一个很好的consise，并且没有命名变量：

def gcd(a,b):
    return max(d for d in xrange(1, min(a, b)+1) if a % d == b % d == 0)

print gcd(15, 25)

>>> 5

但请不要声称它是你自己的:)

python - 求最大公约数

4 回答 4

Related

Reference