1. 计算阶乘
def fact(n):
if n == 1:
return 1
else:
return n * fact(n - 1)
if __name__ == '__main__':
print(fact(6)) # 720
2. 猴子吃桃
猴子第1天摘了一堆桃子吃了一半又多一个,第2天吃了剩下的一半又多一个,…,第10天早上时发现只有1个桃子了。问第1天摘了多少?
def g(n):
if n==10:
return 1
else:
return 2*(g(n+1)+1)
print(g(1))
3.汉诺塔
汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
柱子编号为a, b, c,将所有圆盘从a移到c可以描述为: 如果a只有一个圆盘,可以直接移动到c; 如果a有N个圆盘,可以看成a有1个圆盘(底盘) + (N-1)个圆盘,首先需要把 (N-1) 个圆盘移动到 b,然后,将 a的最后一个圆盘移动到c,再将b的(N-1)个圆盘移动到c。 请编写一个函数move(n, a, b, c) ,给定输入 n, a, b, c,打印出移动的步骤: 例如,输入 move(2, ‘A’, ‘B’, ‘C’),打印出: A –> B A –> C B –> C
def hanoi_move(n, a, b, c):
"""接收一个表示圆盘数量的整数n和三个表示柱子的字符,打印输出把n个圆盘从第一个柱子移动到第三个柱子的过程。"""
if n == 1: # 终止条件,当只有一个圆盘时,从A移动到C后结束程序
print(a, '-->', c)
return None
else: # 递归调用,每调用一次圆盘次减少一个
hanoi_move(n - 1, a, c, b) # 首先需要把 (N-1) 个圆盘移动到 b
hanoi_move(1, a, b, c) # 将a的最后一个圆盘移动到c
hanoi_move(n - 1, b, a, c) # 再将b的(N-1)个圆盘移动到c
if __name__ == '__main__': # 使前面定义的函数可以被其他模块调用
num = int(input()) # 输入最初圆盘数量
s1, s2, s3 = input().split() # 输入表示柱子的字符,例如输入A B C
hanoi_move(num, s1, s2, s3) # 调用递归函数移动圆盘
汉诺塔演示
import turtle
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[len(self.items) - 1]
def size(self):
return len(self.items)
def drawpole(n): # 画柱子,距离500
t = turtle.Turtle()
t.hideturtle()
def pole(k,n):
t.up()
t.pensize(10)
t.speed(100)
t.pencolor('green')
t.goto(30*n * (k - 1), n*15) #柱子高度可根据盘子数量变化
t.down()
t.goto(30*n * (k - 1), -150)
t.goto(30*n * (k - 1) - 40, -150)
t.goto(30*n * (k - 1) + 40, -150)
pole(0,n) # 画柱子1
pole(1,n) # 画柱子2
pole(2,n) # 画柱子3
def creatPlates(n): # 创建盘子,传入数量
plates = [turtle.Turtle() for i in range(n)]
for i in range(n):
plates[i].up()
plates[i].hideturtle()
plates[i].fillcolor(cl[i%8]) #填充颜色,超过8个盘子时,颜色循环利用
plates[i].shape("square") #利用内置形状
plates[i].shapesize(1, n - i)
plates[i].goto(-30*n, -140 + 20 * i)
plates[i].showturtle()
return plates
def p_stack(): # 制造栈
poles = [Stack() for i in range(3)]
return poles
def moveDisk(plates, poles, fromPole, toPole): # 把poles[fromPole]顶端的盘子plates[mov]从poles[fromPole]移到poles[toPole]
mov = poles[fromPole].peek()
plates[mov].goto((fromPole - 1) * 30*n, 150)
plates[mov].goto((toPole - 1) * 30*n, 150)
l = poles[toPole].size() # 确定移动到底部的高度
plates[mov].goto((toPole - 1) * 30*n, -140 + 20 * l)
def moveTower(plates, poles, height, fromPole, toPole, withPole): # 递归移动盘子
if height >= 1:
moveTower(plates, poles, height - 1, fromPole, withPole, toPole)
moveDisk(plates, poles, fromPole, toPole)
poles[toPole].push(poles[fromPole].pop())
moveTower(plates, poles, height - 1, withPole, toPole, fromPole)
turtle.setup(1300,600,0,0)
myscreen = turtle.Screen()
#turtle.tracer(5) #修改参数可调整移动速度
turtle.update()
n = int(input("输入汉诺塔的层数:\n"))
#n = 5
drawpole(n)
cl = ['red','blue','yellow','green','darkorange','deeppink','dodgerblue','pink']
plates = creatPlates(n)
poles = p_stack()
for i in range(n):
poles[0].push(i)
moveTower(plates, poles, n, 0, 2, 1)
turtle.update()
myscreen.exitonclick()