2.7 编程案例:查找问题

下面我们通过一个简单程序来综合应用本章所介绍的知识。

实际应用中经常遇到“查找”问题:即从一个数据集中查找我们需要的数据。查找技术 是程序设计的一个重要技术,存在着许多高效的查找算法。在此,我们考虑一种很简单的查 找问题。场景:下面我们编一个小程序。基本的 IPO 模式。

假如我们要编一个程序,它接收用户输入的月份数值(1~12),并输出对应月份的英文 缩写。例如,当用户输入 3,则程序输出 Mar。虽然我们还没有学习 Python 的控制流语句(见 下一章),但我们可以利用字符串操作来完成程序功能。

我们首先将所有月份的英文缩写保存在一个字符串之中:

  1. months = "JanFebMarAprMayJunJulAugSepOctNovDec"

此处的 months 相当于数据集,接着我们需要根据用户输入的月份数值从这个数据集中查 找相应的缩写(子串)。如何根据用户输入的 m 找到相应子串呢?

程序设计往往需要为应用问题建立数学模型。本查找问题的模型是很简单的,由于数据 集中每个月份名称缩写长度都是 3,因此只要找到相应月份的开始位置 pos,再截取长度为 3 的子串即可:

  1. monthAbbr = months[pos:pos+3]

于是问题演变成了如何根据用户输入的月份值 m 找到开始位置 pos。试着确定几个月 份的索引开始位置:

  1. m = 1 pos = 0
  2. m = 2 pos = 3
  3. m = 3 pos = 6

由此不难推知 m 月的索引开始位置是(m-1)*3。 通过以上分析,我们设计出程序的算法:

  1. 输入月份值 m
  2. 计算在数据集中的索引开始位置(m-1)*3 并取子串;
  3. 输出月份名称缩写。

这是最简单的 IPO 算法模式,即“输入-处理-输出”的模式。下面我们来实现这个 算法。

【程序 2.5】eg2_5.py

  1. months = "JanFebMarAprMayJunJulAugSepOctNovDec" m = input("Enter a month number (1-12): ")
  2. pos = (m-1) * 3
  3. monthAbbr = months[pos:pos+3]
  4. print "The month abbreviation is", monthAbbr + "."

下面是程序 2.5 的运行实例:

  1. >>> import eg2_5
  2. Enter a month number (1-12): 3
  3. The month abbreviation is Mar.