◎知识点
谁在说谎
猴子吃桃
汉诺塔
◎脚本练习
#!/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')
