#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
 @FileName:    python_practice3.py
 @Function:    python practice
 @Author:      Zhihe An
 @Site:        https://chegva.com
 @Time:        2021/7/6
"""


"""一、谁在说谎"""

"""
【问题描述】
    张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎
    这三人中到底谁说的是真话，谁说的是假话？

【设计思路】
    张三说李四在说谎，说明：要么张三说的是真话李四说的是假话，要么张三说的是假话李四说的是真话
    李四说王五在说谎，说明：要么李四说的是真话王五说的是假话，要么李四说的是假话王五说的是真话
    王五说张三和李四都在说谎，说明：要么王五说的是真话张三和李四说的都是假话，
    要么王五说的是假话张三和李四至少有一个说的是真话
    
    设True表示某人说的是真话，设False表示某人说的是假话
    设isZhang、isLi和isWang分别表示张三、李四和王五是否在说谎，则其取值范围都为[True, False]
    通过三重循环穷举isZhang、isLi和isWang，在穷举的过程中，只要满足已知条件：
    isZhang == (not isLi) and isLi == (not isWang) and isWang == ((not isZhang) and (not isLi))
    即找到谁在说谎
"""

# 设True表示某人说的是真话，设False表示某人说的是假话
t = [True, False]

# 设isZhang、isLi和isWang分别表示张三、李四和王五是否在说谎，则其取值范围都为[True, False]
for isZhang in t:
    for isLi in t:
        for isWang in t:
            # 在穷举的过程中，只要满足已知条件
            if isZhang == (not isLi) \
                and isLi == (not isWang) \
                and isWang == ((not isZhang) and (not isLi)):
                # 即找到谁在说谎
                print('张三：{zhang}，李四：{li}，王五：{wang}'
                      .format(zhang = '真话' if isZhang == True else '假话',
                              li = '真话' if isLi == True else '假话',
                              wang = '真话' if isWang == True else '假话'))


"""二、猴子吃桃"""

"""
【问题描述】
    猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个
    第二天早上又将第一天剩下的桃子吃掉一半，又多吃了一个
    以后每天早上都吃了前一天剩下的一半后又多吃一个
    到第10天早上想再吃时，发现只剩下一个桃子了
    求猴子第一天共摘了多少个桃子
    
【设计思路】
    设计思路一：递推
    第1天的桃子数是第2天的桃子数加1后的2倍，第2天的桃子数是第3天的桃子数加1后的2倍，
    ...，一般地，第n天的桃子数是第n+1天的桃子数加1后的2倍
    设第n天的桃子数是L(n)，则有递推关系L(n)=(L(n+1)+1)*2，且初始条件为：L(10)=1
    根据递推关系和初始条件，L(10) -→ L(9) -→ L(8)... -→ L(1)
"""

def monkey_peach1():
    """求猴子第一天共摘了多少个桃子"""
    L = [None] * 11
    # 初始条件为：L(10) = 1
    L[10] = 1

    # 设第n天的桃子数是L(n)，则有递推关系L(n)=(L(n+1)+1)*2，且初始条件为：L(10)=1
    # 根据递推关系和初始条件，L(10) -→ L(9) -→ L(8)... -→ L(1)
    for n in range(9, 0, -1):
        L[n] = (L[n + 1] + 1) * 2

    return L[1]

print('猴子第一天共摘了%d个桃子' % monkey_peach1())    # 猴子第一天共摘了1534个桃子

"""
    设计思路二：递归
    设计思路一的递推关系可看做在一个函数体的内部又调用了该函数
    设计思路一的初始条件可看做递归结束条件(递归出口)
"""

def monkey_peach2(day):
    """求猴子第一天共摘了多少个桃子"""
    # 递归结束条件(递归出口): L(10) = 1
    if day == 10:
        return 1
    else:
        # 递推关系L(n)=(L(n+1)+1)*2可看做在一个函数体的内部又调用了该函数
        return (monkey_peach2(day + 1) + 1) * 2

print('猴子第一天共摘了%d个桃子' % monkey_peach2(1))    # 猴子第一天共摘了1534个桃子


"""三、汉诺塔"""

"""
【问题描述】
    有一个梵塔叫汉诺塔，汉诺塔上有三根柱子A、B和C，
    柱子A上有若干圆盘，所有圆盘大小不等，且小的在上大的在下。
    将柱子A上的所有圆盘借助柱子B移动到柱子C上，移动的过程中每次只能移动一个圆盘，
    移动后仍然是小的在上大的在下，如下图所示：
    -----------------------------------
       X      |      |   
      XXX     |      |   
     XXXXX    |      |   
    ---A------B------C-----------------
    -----------------------------------
       |      |      X   
       |      |     XXX  
       |      |    XXXXX 
    ---A------B------C-----------------
    求汉诺塔的三根柱子上所有圆盘的的移动过程
    
【设计思路】
   当柱子A有1个圆盘时，只需要将圆盘从柱子A移动到柱子C
   
   当柱子A有2个圆盘时，先将柱子A上面的圆盘从柱子A移动到柱子B，
   再将柱子A下面的圆盘从柱子A移动到柱子C，最后将柱子B的圆盘从柱子B移动到柱子C
   
   当柱子A有3个圆盘时，先将柱子A上面的两个圆盘从柱子A借助柱子C移动到柱子B，
   然后将柱子A最下面的圆盘从柱子A移动到柱子C，最后将柱子B的两个圆盘从柱子B借助柱子A移动到柱子C
   
   一般地，当柱子A有n个圆盘时，从上到下依次编号为1，2，3，...，n，
   先将柱子A上面编号为1至n-1的圆盘从柱子A借助柱子C移动到柱子B，
   然后将柱子A最下面编号为n的圆盘从柱子A移动到柱子C，
   最后将柱子B的n-1个圆盘从柱子B借助柱子A移动到柱子C
   
   所求的问题是：将柱子A的n个圆盘借助柱子B移动到柱子C
   结合上面的一般性步骤，很容易想到使用递归。
   假设递归函数hanoi(n, A, B, C)用于将n个圆盘从柱子A借助柱子B移动到柱子C，
   函数move(m, A, C)用于将编号为m的圆盘从柱子A移动到柱子C，
   则上面的一般步骤可以表示为：
   (1) 当n = 1时，调用move(1, A, C)，将圆盘从柱子A移动到柱子C
   (2) 当n > 1时，
        1) 调用hanoi(n - 1, A, C, B),
        将柱子A上面编号为1至n - 1的圆盘从柱子A借助柱子C移动到柱子B
        2) 调用move(n, A, C)，将柱子A最下面编号为n的圆盘从柱子A移动到柱子C
        3) 调用hanoi(n - 1, B, A, C),将柱子B的n - 1个圆盘从柱子B借助柱子A移动到柱子C 
    
    参考：如何理解汉诺塔的递归？(https://www.zhihu.com/question/24385418)
"""

def move(m, A, C):
    """将编号为m的圆盘从柱子A移动到柱子C"""
    print('移动%d号圆盘，%s --→ %s' % (m, A, C))

def hanoi(n, A, B, C):
    """将n个圆盘从柱子A借助柱子B移动到柱子C"""
    if n == 1:
        # 将圆盘从柱子A移动到柱子C
        move(1, A, C)
    else:
        # 将柱子A上面编号为1至n - 1的圆盘从柱子A借助柱子C移动到柱子B
        hanoi(n - 1, A, C, B)
        # 将柱子A最下面编号为n的圆盘从柱子A移动到柱子C
        move(n, A, C)
        # 将柱子B的n - 1个圆盘从柱子B借助柱子A移动到柱子C
        hanoi(n - 1, B, A, C)

hanoi(5, 'A', 'B', 'C')