零基础学Python(24)

递归:汉诺塔

汉诺塔

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

mark

解题思路：

1. mark

2. mark

代码实现

def hanoi(n, x, y, z):
    if n == 1:
        print(x,'>',z)
    else:
        hanoi(n-1,x,z,y)# 将前n-1个盘子从x移动到y上
        hanoi(1,x,y,z)  # 将最底下的最后一个盘子从x移动到z上
        hanoi(n-1,y,x,z)# 将y上的n-1个盘子移动到z上

n = int(input('请输入汉诺塔层数：'))
hanoi(n, 'x','y','z')

思考

代码实际上是将游戏中三根柱子简化为x,y,z三个字母，并通过python函数将x,y,z进行无限循环替换，并利用递归思想，将问题简化为一元整体问题，从而利用递归代码实现求解。

课后作业：

0.使用递归编写一个十进制转换为二进制的函数（要求采用“取2取余”的方式，结果与调用bin()一样返回字符串）

答案：

def Dec2Bin(dec):
    result = ''

    if dec:
        result = Dec2Bin(dec//2)
        return result + str(dec%2)
    else:
        return result

1.写一个函数get_digit(n),将参数分解出每个位的数字并按1顺序存放到列表中。举例：get_digits(12345) ==>[1,2,3,4,5]

我的答案：

def get_digit(n):
    result = []
    if n:
        result = get_digit(n//10)
        return result + [n%10]
    else:
        return result

参考答案：

mark

2.如何利用递归法实现回文判断字符串？

我的答案：

def is_palindrome(string,start,end):
    if start > end:
        return True
    else:
        if string[start] == string[end]:
            return is_palindrome(string,start+1,end-1)
        else:
            False

string = input ('请输入一串字符串：')
start = 0
end = len(string)-1

if is_palindrome(string,0,end):
    print('\"%s\"是回文字符串！' % string)
else:
    print('\"%s\"不是回文字符串！' % string)

3. mark

我的答案：

def age(n):
    if n == 1: #不用从0开始
        return 10
    else:
        if n > 0:
           return age(n-1) + 2

PREVIOUS零基础学Python(25)

NEXT零基础学Python(23)