Python递归实现猴子吃桃问题及解析

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

Python递归实现猴子吃桃

猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了，求第一天共摘了多少桃子？

对于此性质的问题适合用递归的思想去解决，即当前问题可以转化为性质相同的子问题去解决：

要想知道第一天的桃子数量，需要知道第二天的桃子数量，然后将第二天的桃子数量加1乘以2就可以得到第一天的桃子数量。按照此法进行倒推，我已知道第十天的桃子数量为1个，则第九天的桃子数量为第10天的桃子数量加1乘以2,第八天的桃子数量等于第九天的数量加1再乘以2,...

则可以定义函数去实现：n代表天数，如果输入的n不合理，则直接退出函数，如果n等于10，则返回1，否则返回其后面天数桃子数量加1再乘以2

代码如下：

def monkey_tao(n):
    if n>10 or n<1:
        return
    elif n==10:
        return 1
    else:
        return (monkey_tao(n+1)+1)*2
print (monkey_tao(1))

Python函数（闰年&猴子偷桃)问题

函数

1. 函数简介

函数也是一个对象
函数用来保存一些可执行的代码，并且可以在需要时，对这些语句进行多次调用
语法：

def 函数名([形参1,形参2,形参3....]):
    代码块

注意：

函数名必须符合标识符的规范(可以包含字母、数字、下划线但是不能以数字开头)

print是函数对象 print()是调用函数

函数的参数

形参和实参

形参(形式参数) 定义形参就相当于在函数内部声明了变量，但是并不是赋值
实参(实际参数)指定了形参，那么在调用函数时必须传递实参，实参将会赋值给对应的形参，简单来说有几个形参就要有几个实参

函数的传递方式

定义形参时,可以为形参指定默认值。指定了默认值以后，如果用户传递了参数则默认值不会生效。如果用户没有传递，则默认值就会生效
位置参数：位置参数就是将对应位置的实参赋值给对应位置的形参
关键字参数 : 关键字参数可以不按照形参定义的顺序去传递，而根据参数名进行传递
混合使用位置参数和关键字参数的时候必须将位置参数写到关键字参数前面去

不定长参数

定义函数时，可以在形参前面加一个*,这样这个形参可以获取到所有的实参，它会将所有的实参保存到一个元组中
带*号的形参只能有一个，可以和其他参数配合使用
*形参只能接受位置参数，不能接受关键字参数
**形参可以接收其他的关键字参数,它会将这些参数统一保存到字典当中。字典的key就是参数的名字,字典的value就是参数的值
**形参只有一个，并且必须写在所有参数的后面

参数的解包

传递实参时，也可以在序列类型的参数前添加星号，这样它会自动的将序列中元素依次作为参数传递
要求序列中的元素的个数必须和形参的个数一致函数中

1.函数的返回值

返回值就是函数执行以后返回的结果
通过return来指定函数的返回值
return后面可以跟任意对象，返回值甚至可以是一个函数

2.文档字符串

help()是Python中内置函数，通过help()函数可以查询Python中函数的用法
在定义函数时，可以在函数内部编写文档字符串，文档字符串就是对函数的说明

函数的作用域

作用域(scope)
作用域指的是变量生效的区域
在Python中一共有两种作用域
全局作用域

全局作用域在程序执行时创建，在程序执行结束时销毁

所有函数以外的区域都是全局作用域

在全局作用域中定义的变量，都是全局变量，全局变量可以在程序的任意位置进行访问

函数作用域

函数作用域在函数调用时创建，在调用结束时销毁
函数每调用一次就会产生一个新的函数作用域
在函数作用域中定义的变量，都是局部变量，它只能在函数内部被访问

命名空间

命名空间实际上就是一个字典，是一个专门用来存储变量的字典
locals()用来获取当前作用域的命名空间
如果在全局作用域中调用locals()则获取全局命名空间，如果在函数作用域中调用locals()则获取函数命名空间
返回值是一个字典

递归函数

递归是解决问题的一种方式，它的整体思想，是将一个大问题分解为一个个的小问题，直到问题无法分解时，在去解决问题
递归式函数有2个条件

基线条件问题可以被分解为最小问题，当满足基线条件时，递归就不执行了

递归条件可以将问题继续分解的条件

作业

闰年

用函数实现一个判断用户输入的年份是否是闰年的程序

能被400整除的年份
能被4整除，但是不能被100整除的年份

以上2种方法满足一种即为闰年

def leap_year():
    i = int(input('请输入一个年份：'))
    if i%400 == 0 or (i%4 == 0 and i%100 != 0):
        print('此年分是闰年')
    else:
        print('次年分不是闰年')
leap_year()

运行结果：

猴子吃桃问题（递归）

猴子第一天摘下若干个桃子，当即吃了一半，还不瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃了前一天剩的一半零一个。到第10天早上想再吃时，见只剩下一个桃子了，求第一天共摘了多少桃子？

def hou_tao(i, x):       # i为天数  x为剩余桃子数
    if i == 1:
        return x
    else:
        return (hou_tao(i-1, x) + 1)*2
print(f'第一天共摘{hou_tao(10, 1)}个桃子')

运行结果：