知识点
这节课主要讲解用递归的方法，实现汉诺塔的解答
对于游戏的玩法，我们可以简单分解为三个步骤:
1) 将前63个盘子从X移动到Y上。
2) 将最底下的第64个盘子从X移动到Z上。
3) 将Y上的63个盘子移动到Z上。
问题一：将X上的63个盘子借助Z移到Y上；
1) 将前62个盘子从X移动到Z上。
2) 将最底下的第63个盘子移动到Y上。
3) 将Z上的62个盘子移动到Y上。问题二：将Y上的63个盘子借助X移到Z上。
1) 将前62个盘子从Y移动到X上。
2) 将最底下的第63个盘子移动到Z上。
3) 将X上的62个盘子移动到Y上。
用递归方法实现
#汉诺塔
def hanoi(n,x,y,z):
if n == 1:
print(x,'-->移动至',z)
else:
hanoi(n-1,x,z,y)#将前n-1个盘从x移动至y上
print(x,'-->移动至',z)#将最底下一个盘从x移动至z上
hanoi(n-1,y,x,z)#将y上的n-1个盘从y移动至z上
n = int(input('请输入汉诺塔的层数：'))
hanoi(n,'A','B','C')
================= RESTART: C:UsersThinkPadDesktop est.py =================
请输入汉诺塔的层数：5
A -->移动至 C
A -->移动至 B
C -->移动至 B
A -->移动至 C
B -->移动至 A
B -->移动至 C
A -->移动至 C
A -->移动至 B
C -->移动至 B
C -->移动至 A
B -->移动至 A
C -->移动至 B
A -->移动至 C
A -->移动至 B
C -->移动至 B
A -->移动至 C
B -->移动至 A
B -->移动至 C
A -->移动至 C
B -->移动至 A
C -->移动至 B
C -->移动至 A
B -->移动至 A
B -->移动至 C
A -->移动至 C
A -->移动至 B
C -->移动至 B
A -->移动至 C
B -->移动至 A
B -->移动至 C
A -->移动至 C课后习题
动动手
- 使用递归编写一个十进制转换二进制的函数（要求采用“除2取余”的方式，结果与调用bin()一样返回字符串形式）
#迭代形式
def Dec2Bin(dec):
temp = []
result =''
while dec:
x = dec % 2
dec //= 2
temp.append(x)
while temp:
result += str(temp.pop())
return result
print(Dec2Bin(10))
================= RESTART: C:UsersThinkPadDesktop est.py =================
1010
#递归形式
def Dec2Bin(dec):
result = ''
if dec:
result = Dec2Bin(dec//2)
return result + str(dec%2)
else:
return result
print(Dec2Bin(10))
================= RESTART: C:UsersThinkPadDesktop est.py =================
1010
>>> - 写一个函数get_digits(n)，将参数n分解出每个位的数字并按顺序存放到列表中。举例：
get_digits(12345) ==> [1,2,3,4,5]
result = []
def get_digits(n):
if n > 0:
result.insert(0,n%10)
get_digits(n//10)
#result.sort()
get_digits(512364)
print(result)
================= RESTART: C:UsersThinkPadDesktop est.py =================
[5, 1, 2, 3, 6, 4]- 还记得求回文联字符串那道题吗？现在让你使用递归的方式求解？
def is_palindrome(n, start, end):
if start > end:
return 1
else:
return is_palindrome(n, start+1, end-1) if n[start] == n[end] else 0
string = input('请输入一串字符串：')
length = len(string)-1
if is_palindrome(string, 0, length):
print('"%s"是回文字符串!' % string)
else:
print('"%s"不是回文字符串!' % string)
使用递归编程求解以下问题：
有5个人坐在一起，问第五个人多少岁？他说比第4个人大2岁。问第4个人岁数，他说比第三个人大2岁。问第三个人，又说比第二个人大2岁。问第2个人，说比第一个人大2岁。最后问第一个人，他说是10岁。请问第五个人多大？
def age(n):
if n == 1:
return 10
else:
return age(n-1) + 2
print('哈哈，我知道了，第五个人的年龄是 %d 岁，啵啵脆！' % age(5))