今天在园子里看到博客：超难面试题：甲乙两人互猜数字（数理逻辑）。然后琢磨了半天，写了个Python程序实现算法，我得出来的结果是1,6或1,8或35,42的组合，
不知道是否正确，请高人指点？
下面列出实现算法代码（代码按照题目文字一步步进行的，没有优化）：
# -*- coding: utf-8 -*- #!/usr/local/bin/python def is_prime2(number): ''' 判断数字是否是特殊质数（数学上质数和分解因子相同的数）。分解因子相同的数，如：4，9等。 ''' _is_primenum = True for item in range(2,number,1):#不考虑1乘以number if number % item == 0: if (number/item) == item: #两个因子不能相同 continue _is_primenum = False break return _is_primenum def combination(data, t, vl): ''' 计算一组数的组合 ''' _kk = len(data) _ret_list = [] for _i in range(_kk-t+1): vl.append(data[_i]) new_data = data[_i+1:] if t-1 == 1: for _j in range(len(new_data)): _data_str = ','.join(map(str,vl))+','+str(new_data[_j]) _ret_list.append(_data_str) else: _ret_list.extend(combination(new_data, t-1, vl)) vl.pop() return _ret_list def generate_combine(num_list, pick_num): _v1 = [] # temp variable. return combination(num_list, pick_num, _v1) def filter_1_a(_combination_list): ''' 甲：“我不知道这两个数是什么” 遍历所有组合，过滤掉能判断出结果的组合 ''' _result_dict = {} # 存储key为乘积的字典，value是组合的数组。 _new_combination_list = [] #存储还有效的组合 #由于甲不知道这两个数，可以肯定乘积不是质数，排除这类组合。 for item in _combination_list: a, b = item.split(',',1) _product = int(a) * int(b) #甲得到的数字 if not is_prime2(_product): if _product in _result_dict: _result_dict[_product] +=[item] else: _result_dict[_product] =[item] _new_result_dict = {} #便于理解，使用一个新变量存字典值 #由于甲不知道，表示value肯定要大于1种组合。 #比如[min=1，max=10], 乘积是15的组合：3*5一种，这样的组合应该排除掉。 for key,value in _result_dict.iteritems(): if len(value) > 1: _new_result_dict[key] = value _new_combination_list.extend(value) return _new_combination_list, _new_result_dict def filter_1_b(_combination_list): ''' 乙：“我也不知道” 遍历所有组合，过滤掉能判断出结果的组合 ''' _new_combination_list = [] #存储还有效的组合 _result_dict = {} # 存储key为两值相加的字典，value是组合的数组。 for item in _combination_list: a, b = item.split(',',1) _sum = int(a) + int(b) #乙得到的数字 if _sum in _result_dict: _result_dict[_sum] +=[item] else: _result_dict[_sum] =[item] _new_result_dict = {} #由于乙不知道，表示value肯定要大于1种组合。 for key,value in _result_dict.iteritems(): if len(value) > 1: _new_result_dict[key] = value _new_combination_list.extend(value) return _new_combination_list, _new_result_dict def filter_2_a(_combination_list, product_dict, sum_dict): ''' 甲：“那我知道了” 遍历所有组合，过滤掉能判断出结果的组合 ''' _new_prodcut_dict = {} #在乘积字典中，去除多余的组合 for key,value in product_dict.iteritems(): _new_value = [] for item in value: if item in _combination_list: _new_value.append(item) if _new_value: _new_prodcut_dict[key] = _new_value # 去除已经不在相加字典中的组合， for key,value in _new_prodcut_dict.items(): _new_value = [] for item in value: a, b = item.split(',',1) _sum = int(a) + int(b) #乙得到的数字 if _sum in sum_dict: _new_value.append(item) _new_prodcut_dict[key] = _new_value # 由于甲知道，表示肯定等于1种组合。 _new_combination_list = [] #存储还有效的组合 _result_dict = {} for key,value in _new_prodcut_dict.iteritems(): if len(value) == 1: _result_dict[key] = value _new_combination_list.extend(value) return _new_combination_list, _result_dict def filter_2_b(_combination_list, sum_dict): ''' 乙：“那我也知道了” ''' _new_sum_dict = {} #在相加字典中，去除多余的组合 for key,value in sum_dict.iteritems(): _new_value = [] for item in value: if item in _combination_list: _new_value.append(item) if _new_value: _new_sum_dict[key] = _new_value return _new_sum_dict if __name__ == '__main__': print "start..." _min_num=1 _max_num=50 #产生数组 _num_list = range(_min_num,_max_num+1,1) #[1,2,3...,49,50] #生成Cn2的所有组合列表，如：['1,6', '2,3', '2,6', '3,4'...] _combination_list = generate_combine(_num_list, 2) # 甲：“我不知道这两个数是什么” _combination_list, _result_product_dict = filter_1_a(_combination_list) # 乙：“我也不知道” _combination_list, _result_sum_dict = filter_1_b(_combination_list) # 甲：“那我知道了” _new_combination_list, _result_product_dict = filter_2_a(_combination_list, _result_product_dict, _result_sum_dict) print u"最终的组合：", _new_combination_list print u"最终的乘积字典：", _result_product_dict # 乙：“那我也知道了” _result_sum_dict = filter_2_b(_new_combination_list, _result_sum_dict) print u"最终的相加字典：", _result_sum_dict print "end..."