12小球称重

有的公司面试喜欢问这个问题，问题是这样的，12个小球有1个重量不一样，给一个天平，最多称3次，把这个重量不一样的小球找出来
解决这个问题比较难想到的是天平两边放4个球，重量一样的情况，需要怎么调整球的位置。

我把解决方法整理为python代码，如下：

# 左边重
LEFT = '<'
# 右边重
RIGHT = '>'
# 左右相等
EQUAL = '='


def weight(left_balls, right_balls):
    """
    天平对两边的球称重
    :param left_balls: 天平左边的球
    :param right_balls: 天平右边的球
    :return:
    """
    if not isinstance(left_balls, list):
        left_balls = [left_balls]
    if not isinstance(right_balls, list):
        right_balls = [right_balls]
    if sum(left_balls) < sum(right_balls):
        return LEFT
    elif sum(left_balls) == sum(right_balls):
        return EQUAL
    else:
        return RIGHT


def find_different_in_12(balls):
    result = weight(balls[:4], balls[4: 8])
    if result == EQUAL:
        result = weight(balls[:3], balls[8: 11])
        if result == EQUAL:
            return 12, weight(balls[-1], balls[0])
        elif result == LEFT:
            result = weight(balls[8], balls[9])
            if result == EQUAL:
                return 11, '-'
            elif result == LEFT:
                return 10, '>'
            else:
                return 9, '>'
    elif result == LEFT:
        # 关键的地方
        result = weight([balls[4], balls[1], balls[8], balls[9]], [balls[0], balls[5], balls[6], balls[10]])
        if result == EQUAL:
            result = weight([balls[2], balls[7]], [balls[8], balls[9]])
            if result == EQUAL:
                return 3, '<'
            elif result == RIGHT:
                return 7, '>'
            elif result == LEFT:
                return 2, '<'
        elif result == LEFT:
            result = weight([balls[1], balls[5]], [balls[8], balls[9]])
            if result == EQUAL:
                return 6, '>'
            elif result == LEFT:
                return 1, '<'
            elif result == RIGHT:
                return 5, '>'
        elif result == RIGHT:
            result = weight(balls[0], balls[8])
            if result == EQUAL:
                return 4, '>'
            elif result == LEFT:
                return 0, '<'
    elif result == RIGHT:
        # 省略，跟result == LEFT类似
        pass

    return 'no result'


def get_balls(i, w):
    """
    把第i个球换成重量为w的不一样的球
    :param i:
    :param w:
    :return:
    """
    balls = [1] * 12
    balls[i] = w
    print(balls)
    return balls


if __name__ == "__main__":

    balls = get_balls(8, 2)
    print(find_different_in_12(balls))

    balls = get_balls(6, 2)
    print(find_different_in_12(balls))

执行后可以看到结果：

[1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1]
(9, '>')
[1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1]
(6, '>')