“提取数字串算法”教学思路-技术圈

说在前面

“提取数字串并求和”是一个经典的算法问题：从键盘读取一串文本，提取其中的连续数字串，转换为正整数后累加起来，输出结果。

例1，输入：abc101defg92h，输出：193。因为101+92=193。

例2，输入：abc101defg925，输出：1026。因为101+925=1026。

要求编写一段Python程序，实现上述功能。

教学思路

“提取数字串并求和”涉及遍历字符串、判断数字字符、提取字符串和数字串转整数等问题，头绪较多，直接分析代码的话，容易陷入细节的泥淖，很难突出重点。最好是分解知识点，先从简单的问题开始，由浅入深，逐层递进，突出算法本质，磨砺学生思维。

铺垫一：累积单个数字和。

（1）编写Python程序实现如下功能：从键盘读取一串文本，将其中的单个数字累加起来，并输出结果。例如，输入：abc101defg925，输出：18。因为1+0+1+9+2+5=18。

参考代码如下，请将缺失的代码补充完整：

text = input('输入一串文本:')

s = 0

for ch in text:

if 填空1:

s += 填空2

print("数字和: " + str(s))

答案：填空1："0" <= ch <= "9"；填空2：int(ch)。

解析：通过此题让学生掌握遍历字符串和判断数字字符的方法，并注意先使用int()函数将数字字符转换成整数再求和。

铺垫二：提取数字串并求和。

（2）已知字符串text = "abc101defg925"，则int(text[3:6]) + int(text[10:])的值为多少？

答案：1026。

解析：通过此题让学生掌握使用切片提取连续数字串的方法，明白数字串切片中起点和终点坐标（左右边界）的含义，由此引出对于任意字符串，如何定位并提取其中连续数字串的方法。

重点一：对于任意字符串，如何提取其中连续数字串并求和？

（3）自定义函数d_sum(text)能够提取文本text中的连续数字串，并返回累加后的结果。

例1，若text = "abc101defg92h"，则返回193；

例2，若text = "abc101defg925"，则返回1026。

请编程实现函数d_sum()的功能。

下列代码意图实现函数d_sum()的功能，请将缺失的代码补充完整：

def d_sum(text):

s = 0

i = 0

while i < len(text):

if "0" <= text[i] <= "9":

j = i + 1

while 填空1:

j += 1

s = 填空2

i = 填空3

else:

i = 填空4

return s

答案：填空1：j < len(text) and "0" <= text[j] <= "9"；填空2：s + int(text[i:j])；填空3：j + 1或j；填空4：i + 1。

解析：提取连续数字串的关键在于找到数字串的左右边界。程序使用变量i来定位数字串的左边界，一旦找到首数字，即让i停止扫描，同时定义变量j来定位数字串的右边界，让j从i+1处开始扫描该连续数字串，直到text[j]为非数字为止，则text[i:j]就是要提取的数字串。填空3和4，分别对应text[i]为数字和非数字两种情形下，变量i向右移动的方法。

此题第1空容易错填为"0" <= text[j] <= "9"，这是没有考虑下标是否越界；另一个容易错填的答案为"0" <= text[j] <= "9" and j < len(text)，这是不理解逻辑运算符的运算规则。

铺垫三：累乘相加算法。

（4）阅读如下Python程序段，猜测程序输出结果：

def f(s):

num = 0

for ch in s:

num = num * 10 + int(ch)

return num

print(f("101")+f("92"))

答案：193。

解析：函数f(s)的作用是把数字串s转换成十进制整数num，其采用了著名的累乘相加算法。使用累乘相加算法的前提条件是字符串s为纯数字串，那么对于任意字符串，能否使用累乘相加算法计算其中连续数字串的值并求和呢？

重点二：使用累乘相加算法，计算任意文本中连续数字串的值并求和。

（5）自定义函数d_sum2(text)能够提取文本text中的连续数字串，并返回累加后的结果。

例1，若text = "abc101defg92h"，则返回193；

例2，若text = "abc101defg925"，则返回1026。

下列代码意图使用累乘相加算法实现函数d_sum2()的功能，请将缺失的代码补充完整：

def d_sum2(text):

num = s = 0

for ch in text:

if "0" <= ch <= "9":

num = 填空1

else:

s += num

num = 填空2

填空3

return s

答案：填空1：num * 10 + int(ch)；填空2：0；填空3：s += num。

解析：程序使用累乘相加算法计算数字串的值。变量num用来存储当前数字串的值，一旦遇到非数字字符，即将num的值累加到s中，并将num归零，以便处理下一个数字串。

当尾字符也是数字时，for循环体内没有机会把num累加到s中，故需要在循环体外执行语句s += num；若尾字符不是数字，则num=0，循环体外执行语句s += num，也不会改变s的值。故无论尾字符是否为数字，都应该在循环体外执行语句s += num。

课后作业

自定义函数d_sum(text)定义了两个变量i和j分别表示数字串的左右边界，并使用了二重循环来遍历字符串，以提取并累加所有的数字串，那么，该程序的时间复杂度是多少呢？O(n^2)还是O(n)？

自定义函数d_sum2(text)只有一重for循环，它的功能和函数d_sum(text)是一样的，那么，能否也使用一重for循环来改写函数d_sum(text)呢？

下列代码意图实现函数d_sum()的功能，请将缺失的代码补充完整：

def d_sum(text):

s = 0

i = 0 #数字字符左边界

for j in range(len(text)):

if not "0" <= text[j] <= "9":

if i < j: #左右边界不相等，说明text[i:j]是数字串

s = 填空1

i = 填空2 #更新左边界

if 填空3:

s += int(text[i:])

return s

需要本文word文档、源代码和课后思考答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类