Python递归练习

1. 出售金鱼问题

题目描述：

第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼。问这鱼缸里原有多少条金鱼？

题目分析：

得知最后还剩11条金鱼，用递归法以此类推出第四次、第三次、第二次、第一次出售前金鱼的数量。

得到递归函数：result=(Fish(i+1)+(Fish(i+1)+1)/i)。

代码实现：

def fish(n): #第几次卖鱼时共有多少条鱼
    if n == 5:
        return 11
    else:
        return ((n+1)/n)*(fish(n+1)+1/(n+1))
        # return (fish(n+1)*(n+1)+1)/n #化简后的表达式


n = eval(input())
print(fish(n))

运行结果

---

2. 公交车问题

题目描述：

某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？

题目分析

递归出口：终点站有六名乘客

递归体：num(i)=(num(i+1)-8+i)*2  //计算到第i站车上的人数

那么到达第2站时车上的人数就是发车时车上的乘客数

代码

def num(i):
    if i == 8:  # 终点站
        return 6
    else:
        return (num(i+1)-8+i)*2


i = eval(input())
print(num(i))

运行结果

---

 3. 猴子吃桃问题

问题描述：

有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？

代码

def peach(n):
    if n > 9:
        return 0
    elif n == 9:
        return 2  # 第九天还有两个桃子，都被吃了
    else:
        return (peach(n+1)+1)*2


print("猴子们摘来了:{}个桃子".format(peach(1)))
s = peach(1)
for i in range(1, 10):
    print("第{}天吃了{}个桃子，剩余桃子数为{}". format(i, s-peach(i+1), peach(i+1)))
    s = peach(i+1)

运行结果

---

4. 小华读书

问题描述：

小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？

代码实现：

def num(n):
    if n > 6:
        return 0
    elif n == 6:
        return 3
    else:
        return (num(n+1)+2)*2


print("全书共:{}页".format(num(1)))
sum = num(1)
for i in range(1, 7):
    print("第{}天读了{}页，剩余{}页". format(i, sum-num(i+1), num(i+1)))
    sum = num(i+1)

运行结果：

5. 台阶问题

题目描述：

30个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？

题目分析

由题意可知，一次可以上一阶或两阶阶梯，由此可以列出当有一阶，两阶，三阶，四阶，五阶…它们的走法，可以推导出递推公式。

因为只能是一阶一阶上或者两阶两阶上，所以到达顶点的最后一步不是一阶就是两阶,倒数第二步也是这样

 边界条件：当阶梯数为1和0时，都只有一种走法

递推公式：step(n)=step(n-1)+step(n-2)

代码实现：

def step(n):
    if n <= 1:
        return 1
    else:
        return step(n-1)+step(n-2)


n = eval(input())
print(step(n))

运行结果：

6. 汉诺塔问题

汉诺塔问题是一个经典的问题。汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？

用python程序计算次数：

1 2 3 4 5 6 7

def f(n):     if n==0:         return 0     else:         return 2*f(n-1)+1 x=int(input("请输入片的个数：")) print("需要移动",f(x),"次")

请输入片的个数：64

需要移动 18446744073709551615 次

 代码实现：

def hanoi(n, x, y, z):
    if n == 1:
        print(x, '-->', z)  # 如果只有一层，直接从X移动到Z
    else:
        hanoi(n-1, x, z, y)  # 将前n-1个盘子从X移动到Y
        print(x, '-->', z)  # 将最底下的第64个盘子从X移动到Z上
        hanoi(n-1, y, x, z)  # 将Y上的63个盘子移动到Z上


n = eval(input('请输入汉诺塔的层数:'))
hanoi(n, 'X', 'Y', 'Z')

运行结果：

7. 传染病问题

题目描述：

某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。

题目分析：

患者数=潜伏期人数+发作期人数

图片来源：

代码

def num(n):
    if n == 0:
        return 0
    if n <= 5:
        return 1
    elif 5 < n <= 10:
        return num(n-5)*3+num(n-1)
    elif n == 11:
        return (num(n-5)-num(n-10))*3+num(n-1)-num(n-10)
    elif n > 11:
        return (num(n-5)-num(n-10))*3+num(n-1)


N = eval(input())
print(num(N))

运行结果

卡了一天，今天修改了一下条件就运行成功了。

 8. 佩尔数列

题目分析

佩尔数列是一个整数数列。它的第一项为0，第二项为1，第3项是第2项的2倍再加上第1项，第4项是第3项的2倍再加上第2项，……。最初几个佩尔数是：0,1,2,5,12,29,70,169,408,985,2378……。
请编写程序从键盘输入整数n，求出佩尔数列第n项。

代码实现

def get_pell(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n > 2:
        return get_pell(n - 1) * 2 + get_pell(n - 2)


n = eval(input("输入整数n；"))
num = get_pell(n)
print("佩尔数列的第{}项为{}".format(n, num))

运行结果 

9. 年龄问题

题目描述：

有5个人坐在一起。问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第3个人大2岁。问第三个人，又说比第2人大两岁。问第2个人，说比第一个人大两岁。最后问第一个人，他说是10岁。请问第五个人多大？ 

题目分析：递归出口：第一个人10岁；递归链 age(n) = age(n-1)+2

代码实现：

def age(n):
    if n == 1:
        return 10
    else:
        return age(n - 1) + 2


print("第五个人{}岁。".format(age(5)))

 输出结果为：第五个人18岁。

---

大家有什么好的题目和想法可以留言~~~