解决把两个数字的和、积分别告诉两个人猜两个数字组合的问题，数字两个人,# -*- coding
# -*- coding: utf-8 -*-# 原题：一个老师从2到9中取两个数字，给甲说了和，给乙说了积，# 甲说我不知道，乙说我也不知道，甲说你不知道那我就知道了，# 乙说你知道了那我也知道了# 这两个数分别是多少?# ========================================================# 为了方便表示，记两个数字的组合为字符串i&j，如2&3这种格式# 以下是工具函数# ========================================================# 通过数字i和j生成组合（注意i&j和j&i其实是一样的）def genij(i, j): return '%d&%d'%(i, j) if i >=j else '%d&%d'%(j, i)# 获得组合的和def add_ij(ij): v = ij.split('&') return int(v[0]) + int(v[1])# 获得组合的积def mul_ij(ij): v = ij.split('&') return int(v[0]) * int(v[1])# ========================================================# 以下开始计算# ========================================================def find_ijs(begin, end): end = end + 1 # 生成两个begin-end数字所有可能的和、积 a = {} b = {} for i in range(begin, end): for j in range(begin, end): v = genij(i, j) if i+j in a: a[i+j].add(v) else: a[i+j] = set() a[i+j].add(v) if i*j in b: b[i*j].add(v) else: b[i*j] = set() b[i*j].add(v) # print u'----------两个%d-%d数字和的可能组合a-------------------\n'%(begin, end), a # print u'----------两个%d-%d数字积的可能组合b-------------------\n'%(begin ,end), b # 排除和是唯一的组合（如果是唯一，甲第一次就应该知道这两个数字） a1 = {k: v for k, v in a.items() if len(v) == 1} a1 = reduce(lambda x, y: x | y, [k for k in a1.values()]) # print u'----------甲第一次不知道后可以排除的组合a1-------------------\n',list(a1) # 排除积是唯一的组合（如果是唯一，乙第一次就应该知道这两个数字） b1 = {k: v for k, v in b.items() if len(v) == 1} b1 = reduce(lambda x, y: x | y, [k for k in b1.values()]) # print u'----------乙第一次不知道后可以排除的组合b1-------------------\n',list(b1) # 排除a1、b1后剩下的数字组合 c = set() for i in range(begin, end): for j in range(begin, end): v = genij(i, j) if v not in a1 and v not in b1: c.add(v) # print u'----------甲乙第一次不知道后的可能组合c-------------------\n',list(c) # 甲第二次知道了，是因为他能够排除和为m数字中其他非正确答案的组合 # 那就是说和为m的可能的数字组合除正确答案之外都在不可能的数字组合a1和b1里面 c1 = [] for i in c: v = add_ij(i) test = True for j in a[v]: if j != i: if j in c: # 相当于 if j not in a1 and j not in b1: test = False if test: c1.append(i) # print u'----------甲第二次知道后的可能组合c1-------------------\n',c1 # 乙第二次知道了，是因为他能够排除积为n数字中其他非正确答案的组合 # 他的依据是甲既然知道，那么这个数字组合肯定是c1中的一种 # 然后他再根据c1做一下排除, 积为n的可能的数字组合除正确答案之外都在不可能的数字组合c1里面 c2 = [] for i in c1: v = mul_ij(i) test = True for j in b[v]: if j != i: if j in c1: test = False if test: c2.append(i) # print u'----------乙第二次知道后答案c2-------------------\n',c2 return c2for i in range(3, 20): for j in range(2, i): print '%d-%d'%(j, i), find_ijs(j, i)
评论关闭