【100个python算法超详细讲解】@谷哥技术

1．问题描述
编程实现将输入的整数逆序输出。
2．问题分析
前面我们已经接触过很多的递归问题了，这些递归问题可以简单
地分成两类：一类可以归结为数值问题，还有一类为非数值问题。
数值问题的递归是指可以表达为数学公式的问题，如9.1节的猴子
吃桃问题，9.4节的求年龄问题。
非数值问题的递归是指问题本身难以用数学公式来表达的问题，
如9.3节的汉诺塔问题。
对于数值问题，由于本身可以表达为数学公式，所以可以从数学
公式入手来推导出问题的递归定义，然后确定问题的边界条件，从而
最终确定递归函数和递归结束条件。
对于非数值问题，由于其本身不能用数学公式来表达，因此其求
解的一般方法是要自行设计一种算法，进而找到解决问题的一系列操
作步骤。如果能够找到解决问题的一系列递归操作步骤，则非数值问
题也可以使用递归方法来求解。
本节我们要讨论的逆序输出数字就是一个数值问题的递归。问题
本身并不复杂，但通过该问题我们可以对这一类递归问题的编程方法
进行总结和比较，以便于读者在遇到相似的问题时能参照解决。
3．算法设计
该问题要求任意输入一个整数，实现它的逆序输出。因此，首先
要判断输入的整数是正整数还是负整数。无论正负，程序都应该能处
理。如果是负整数，则在逆序输出前应先打印出负号。
接着解决整数的逆序问题。
假设输入的整数保存在变量num中，我们以输入4位的正整数为
例，其他位数的整数可类似地分析。假设输入的4位正整数为abcd。我
们可以这样思考：
1）如果三位数abc已经实现了逆序，则只需打印d与abc逆序后的三
位数即可。
2）如果两位数ab已经实现了逆序，则只需打印c与ab逆序后的两位
数即可。
3）如果一位数a已经实现了逆序，则只需打印b与a逆序后的一位
数即可。显然，a逆序后还是它本身，因此此步可直接打印结果：ba。
4）接着再由第3步向前递推，则可以实现逆序输出abcd这个4位整
数。
由刚才的分析过程可知，显然这是一个递归问题，将大问题逐渐
细化，递归的出口就是对一位数进行逆序操作的结果仍是它本身。
4．确定程序框架
根据算法分析过程，我们可以写出逆序的递归函数reverse()，代码
如下：

# 逆序函数
def reverse(n):
if n != 0:
print("%d" % (n % 10), end="") # 输出正整数n当前的最高位
reverse(n // 10) # 递归调用

上面的代码中加粗的部分表示去掉当前正整数n中的最高位，将剩
下的正整数作为递归函数的实际参数。
5．完整的程序
根据上面的分析，编写程序如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 逆序输出数字
# 逆序函数
def reverse(n):
if n != 0:
print("%d" % (n % 10), end="") # 输出正整数n当前的最高位
reverse(n // 10) # 递归调用
if __name__ == "__main__":
num = int(input("请输入一个整数："))
# 如果num小于0，就先把num转化字符串，截取第一位 -号，然后将数字逆序，再拼接上
符号输出
if num < 0:
str_num = str(num)
num = str_num[1:] # 剪切掉符号位
print("-", end="")
reverse(int(num))
else:
reverse(num)

6．运行结果
在PyCharm下运行程序，结果如图9.15所示。由图9.15可见，程序
可以正确地将输入的整数逆序输出。

7．问题拓展
（1）逆序输出字符串
与逆序输出数字类似的问题还有逆序输出字符串。下面我们先直
接给出使用递归来逆序输出字符串的完整代码，再进行分析。
逆序输出字符串的完整代码如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 逆序输出字符串
递归函数
# 递归函数
def rvstr(s):
if len(s) <= 1:
return s
return rvstr(s[1:]) + s[0]
if __name__ == "__main__":
str = str(input("请输入一个字符串："))
str_result = rvstr(str)
print("%s 逆序后： %s" % (str, str_result))

 在上面的代码中，当输入时按Enter键，表示字符串输入结束，可
以开始逆序打印。
在递归函数rvstr(s)中，我们用到了字符串的分片功能，通过递归
调用字符串s的分片剪切实现字符串的逆序功能。
在PyCharm下运行程序，运行结果如图9.16所示。

在Python中，一个字符串相当于一个不可改变序列的列表。一旦这
个字符串被定义了，则该字符串中的每个字符都有了自己确定的位
置，也有了自己的下标，不可改变。
在Python中，可以使用“[]”来访问字符串中指定位置上的字符，这
种方式类似于C语言或Java语言中的数组。在Python语言的字符串中，
字符的序号也是从0开始的，即str[0]表示字符串str中的第1个字符。
与C语言或Java语言不同的是，Python允许以负数表示字符的序
号，负数表示从字符串的末尾处开始计算，字符串的最后一个字符序
号为-1，而不是-0。
上面提到的字符序号也可以理解为是索引，索引用来对单个元素
进行访问。在Python语言中，对一个序列一定范围内的元素进行访问的
技术叫作分片技术，分片是通过冒号相隔的两个索引实现的。分片操
作既支持正数索引，又支持负数索引，这对于访问一个序列的部分元
素很方便。分片操作的实现需要提供序列的两个索引作为边界值，第
一个索引的元素包含在分片内，第二个索引的元素不包含在分片内。
下面提供一个实例代码以帮助读者理解分片，代码如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 序列分片
if __name__ == "__main__":
str = "abcdefghijklmnopqrstuvwxyz" # 定义字符串
print(str[4]) # 取字符串中序号为4的字符，也就是第5个字符串
print(str[-3]) # 从字符串的尾部开始计算，取字符串的倒数第3个字符
print(str[-0]) # -0即是0，也就是取字符串的第一个字符
print(str[-1]) # 取字符串的倒数第一个字符，也就是最后一个字符
#分片
print(str[2:8]) # 取字符串中从第3个字符到第9个字符的内容，不包含第9个字符
print(str[1:1]) # 不包含第2个字符，这里为空
print(str[1:-1]) # 从第2个字符开始到最后一个字符，不包含最后一个字符
print(str[0:-1]) # 从第1个字符到倒数第1个字符，不包含最后一个字符
print(str[-8:-2]) # 从倒数第9个到倒数第2个字符，不包含倒数第9个字符
# 打印为空，在分片中最左边的索引比它右边的索引晚出现在序列中，结果就是一个空值
print(str[-8:0])
print(str[:10]) # 从第1个字符取到第11个字符，不包含第11个字符
print(str[12:]) # 从第13个字符取到最后一个字符
print(str[-9:]) # 从倒数第9个字符开始取
print(str[:-4]) # 从第1个字符取到倒数第4个字符，不包含倒数第4个
print(str[:]) #取出整个字符串

 在PyCharm下运行程序，结果如图9.17所示。

（2）其他数值问题的递归
其他一些数值问题还有求n！、求斐波拉切数列、求最大公约数等
问题。下面我们再介绍使用递归求最大公约数的方法。
用辗转相除法求出两个整数m与n的最大公约数。
本题要求我们使用辗转相除法（也称欧几里德算法或欧式算法）
来求解m和n的最大公约数。辗转相除法的公式如下：

 

由上述公式可知，求m与n的最大公约数问题可以等价于求n与
(m%n)的最大公约数问题。因此，可以把n当作新的m，把(m%n)当作新
的n，则问题再次转换为求新的m与新的n的最大公约数。而求新的m与
新的n的最大公约数又等价于求新的n与(m%n)的最大公约数，如此继续
下去，直到新的n为0，则所求的最大公约数就是当前的m值，这就是利
用辗转相除法求m与n的最大公约数的过程。
例如：求gcd(70,30)。
1）当前m=70，n=30，m%n=10。
2）转换成求gcd(30,10)，此时m=30，n=10，由于m%n=0，故结
束，gcd(70,30)=n=10。
根据上面的描述，列出递归算法的步骤：
1）求r=m%n。
2）判断r是否为0。若r=0，则n为所求的最大公约数，输出n。
3）若r!=0，则令m=n，n=r。
4）转到步骤1。
根据上述分析，编写递归函数gcd()如下：

# 递归函数 求最大公约数
def gcd(m , n):
if n == 0:
g = m
else:
g = gcd(n, m % n) # 递归调用
return g

 还可以在递归函数中加入对特殊情况的处理，如m、n为负数的情
况。此时递归函数代码如下：

# 递归函数 求最大公约数
def gcd(m , n):
if m < 0:
m = -m
if n < 0:
n = -n
if n == 0:
g = m
else:
g = gcd(n, m % n) # 递归调用
return g

上面函数中加粗的代码表示如果m、n为负数，则先将其转化为正
整数，再进行下面的操作。
还可以使用条件表达式来简化递归函数的书写，具体代码如下：

# 递归函数 求最大公约数
def gcd(m , n):
if m < 0:
m = -m
if n < 0:
n = -n
return m if n==0 else gcd(n, m%n) # 递归调用

函数中加粗的代码使用了条件表达式，它的执行效果与使用
if...else...结构的效果相同。
完整的程序代码如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 递归求最大公约数
# 递归函数 求最大公约数
def gcd(m , n):
if n == 0:
g = m
else:
g = gcd(n, m % n) # 递归调用
return g
if __name__ == "__main__":
print("请输入两个正整数：")
m = int(input("m = "))
n = int(input("n = "))
g = gcd(m, n) # 调用递归函数
print("%d和%d的最大公约数是：%d" %(m, n,
g));

在PyCharm下运行程序，结果如图9.18所示。