Python基础(34)–经典练习题:谁在说谎、猴子吃桃、汉诺塔

◎知识点

  1. 谁在说谎

  2. 猴子吃桃

  3. 汉诺塔


◎脚本练习

#!/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')

◎脚本地址:https://github.com/anzhihe/learning/blob/master/python/practise/learn-python/python_basic/python_practice3.py

anzhihe安志合个人博客,版权所有丨 如未注明,均为原创 丨转载请注明转自:https://chegva.com/4931.html | ☆★★每天进步一点点,加油!★★☆

您可能还感兴趣的文章!

发表评论

电子邮件地址不会被公开。 必填项已用*标注