解决把两个数字的和、积分别告诉两个人猜两个数字组合的问题

以下代码由PHP站长网 52php.cn收集自互联网

现在PHP站长网小编把它分享给大家，仅供参考

# -*- 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,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,[k for k in b1.values()]) 
    # print u'----------乙第一次不知道后可以排除的组合b1-------------------n',list(b1)

    # 排除a1、b1后剩下的数字组合
    c = set()
    for i in range(begin,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 c2

for i in range(3,20):
    for j in range(2,i):
        print '%d-%d'%(j,i),find_ijs(j,i)

以上内容由PHP站长网【52php.cn】收集整理供大家参考研究

如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!