【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所示。

 

Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐