Algorithm|ZOJ--003Crashing Balloon python|算法|exercise

题目描述 Crashing Balloon：问题可以简化为判断两个数是否一定有相同公因子。且每个数的因子集合中不能有相同因子，且每个因子都属于集合{1,2,…,100}.
题目详细描述请参考ZOJ
解题思路：如果数字冲突，小胜；反之，大胜。
代码如下：

import sysfactors = []def factoring(buf, num): ''' :param buffer: 缓冲备份列表 :param num: 待分解整数 :return:用factors列表返回分解结果,要求因子各不相同 ''' global factors i = 2 while i <= num: if i > 100: break if num % i == 0 and i not in buf: buf.append(i) factor = buf[:] temp = int(num / i) if temp not in factor and temp < 101: if temp != 1: factor.append(temp) factor.sort() if factor not in factors: factors.append(factor) factoring(buf, temp) buf.pop() i += 1 return factorsdef winner(num1, num2): ''' :param num1: :param num2: :return: 获胜者 ''' global factors if num1 == num2: return num1 if num1 < num2: num1, num2 = num2, num1 factors = [] factors1 = factoring([], num1) factors = [] # 非常关键 if num2 == 1: factors2 = [[1]] else: factors2 = factoring([], num2) # print('num1:', factors1) # print('num2:', factors2) if len(factors2) == 0: # num2假num1获胜 return num1 elif len(factors1) == 0: # num1假 num2真num2获胜 return num2 else: # num1、num2皆真 for factor1 in factors1: for factor2 in factors2: if len(set(factor1).intersection(set(factor2))) == 0: # 存在不冲突num1获胜 return num1 # 完全冲突num2获胜 return num2if __name__ == '__main__': for line in sys.stdin: s = [] s = line.split() print(winner(int(s[0]), int(s[1])))

【Algorithm|ZOJ--003Crashing Balloon】联系邮箱：antarm@outlook.com