1 函数相关概念

学习要点

理解函数及过程、函数的参数、匿名函数等概念。

对标内容

理解函数及过程、函数的参数等概念。

1.1 函数的相关概念

知识点详解

1.1.1 函数的意义

• 函数是一段可以重复使用的代码，用来实现特定的功能。
• 在写一段程序的时候，需要多次用到同样的功能，如果每次都要重复写相同的代码，不仅会增加代码量，而且阅读与修改极不方便。如果把实现相同功能的代码作为一个代码块封装在一起，形成一个函数，每次需要时调用这个函数，就很方便了！
• 定义函数的代码如下所示

  def 函数名(参数列表):
      函数体
      return 返回值

  • 函数的定义包括函数名、参数列表、函数体和返回值。
  • 函数名是函数的标识符，用来调用函数。
  • 详细举例

    def add(x, y):
        num_add = x + y
        return num_add

    • 上述代码定义了一个名为add的函数，该函数接受两个参数x和y，并返回它们的和。
    • 运行结果

      >>> add(1, 2)
      3
      >>> add(3, 4)
      7

1.1.2 形参和实参

1. 形参是函数定义时的参数，用于接收调用函数时传入的参数。
2. 实参是函数调用时传入的参数，用于传递给函数。

• 从名字就可以看出，实参（实际参数）是一个实实在在存在的参数，是实际占用内存地址的；而形参（形式参数）只是意义上的一种参数，在定义时是不占用内存地址的。
  • 位置实参：在调用函数时，必须将每个实参都关联到函数定义中的每一个形参，最简单的关联方式就是基于实参的位置（顺序）。

    def f(x,y,z):     # 首先在定义函数时传入3个形参x y z
        print(x,y,z)
    f(3,2,1)　　　　　
    #在调用该函数时，通过位置实参的方式，将实参映射到形参，一一对应.
    # 即x=3，y=2，z=1

    • 运行结果

      3 2 1

  • 关键字实参：关键字实参是传递给函数的名称-值对。直接在实参中将名称和值关联起来了，因此向函数传递实参时不会混淆。

    def f(x,y,z):
        print(x,y,z)
    f(x=3,y=2,z=1)

    • 运行结果

      3 2 1

  • 混合使用

    def f(x,y,z):
        print(x,y,z)
    f(1,z=3,y=2)

    • 运行结果

      1 2 3

  • 默认值：编写函数时，可给每个形参指定默认值。在调用函数中给形参提供了实参时，Python将使用指定的实参值；否则，将使用形参的默认值。

    def f(x,y,z=1):
        print(x,y,z)
    f(1,2)

    • 运行结果

      1 2 1

    • 注意
      • 有默认值的形参必须放在形参列表的末尾。
      • 调用函数时，如果为形参提供了实参，那么Python将使用指定的实参值；否则，将使用该形参的默认值。
      • 在函数调用中，必须按顺序提供实参。
      • 可以混合使用位置实参和关键字实参，但必须先提供所有位置实参，再提供关键字实参。
  • 列表和字典：当不确定需要传入的值是多少时，在定义形参时，可以使用*args（列表）、**kwargs（字典）来表示。

    def f(*args,**kwargs):
        print(args)
        print(kwargs)
    f(*[1,2,3,4,5],**{"y":1})   
    # 如果想让传入的值以列表或字典的形式显示出来，就需要在元素前加上*或**

    • 运行结果

      (1, 2, 3, 4, 5)
      {'y': 1}

  • 注意：函数的定义必须在主程序调用语句之前出现。

1.1.3 匿名函数

• 匿名函数是一种没有名字的函数，它可以在需要函数的地方直接定义和使用。
• 匿名函数的定义格式如下：

  lambda 参数列表: 表达式

  • 其中，lambda是关键字，参数列表是函数的参数，表达式是函数的返回值。
  • 匿名函数的使用方式如下：

    f = lambda x, y: x + y
    print(f(1, 2))

    • 运行结果

      3

• 匿名函数通常用于需要一个函数作为参数的场合，例如map()、filter()、sorted()等函数。

  a = [1, 2, 3, 4, 5]
  b = list(map(lambda x: x * 2, a))
  print(b)

  • 运行结果

    [2, 4, 6, 8, 10]

  • 上述代码中，map()函数的第一个参数是一个匿名函数，第二个参数是一个列表。map()函数将列表中的每个元素都应用到匿名函数中，并返回一个新的列表。
• 匿名函数也可以作为函数的返回值使用。

  def f(x):
      return lambda y: x + y
  g = f(1)
  print(g(2))

  • 运行结果

    3

  • 上述代码中，f()函数返回一个匿名函数，该匿名函数接受一个参数y，并返回x+y的值。g()函数是f()函数的返回值，它接受一个参数y，并返回1+y的值。
• 匿名函数的优点是简洁，缺点是可读性差，不适合复杂的逻辑。
• 匿名函数使用关键字lambda, 冒号之前的部分表示匿名函数的参数列表，冒号之后的部分表示匿名函数的返回值，但是请注意，这部分只能为表达式，不能为赋值语句，否则会出现“can't assign to lambda”错误。
• 匿名函数不需要用return 来返回值，表达式本身的结果就是返回值。
• 在定义匿名函数时，需要将它直接赋值给一个变量，然后再像一般函数一样调用。

易错点

1. 函数的参数传递是本节重点，知识点容易混淆，要重点学习。
2. 函数的定义必须在主程序调用语句之前出现，这是由Pyhton是解释性语言的特性决定的。

1.2 模拟考题-函数的相关概念

考题1 单选题

以下选项中，哪一个不属于函数的作用？（ ）

• A. 提高代码的执行速度
• B. 提高代码的重复利用率
• C. 增强代码的可读性
• D. 降低编程的复杂度

考题2 单选题

关于计算圆面积的匿名函数的定义，以下哪一个语法格式是正确的？ （ ）

• A. lambda r:3.1415926*r*r
• B. result=lambda r:3.1415926*r*r
• C. lambda r,3.1415926*r*r
• D. result=lambda r,3.1415926*r*r

考题3 判断题

代码：

myFun=lambda a,b=2:a*b 
print(myFun(4)) 
print(myFun(5,3))

运行结果为：

8 
15

（ ）

2 自定义函数的创建与调用

学习要点

1. 能够创建简单的自定义函数。
2. 掌握自定义函数的调用方法。
3. 理解函数的返回值。
4. 理解变量作用域、全面变量与局部变量。

对标内容

1. 能够创建简单的自定义函数，掌握自定义函数的调用。
2. 理解函数的返回值、变量作用域等概念。

2.1 函数的返回值

知识点详解

2.1.1 函数的返回值

• 函数不是直接显示输出的，它会处理一些数据并返回一个或一组值。函数用return 语句将值返回调用函数的代码行，返回值能将程序大部分繁重的工作移交到函数中去完成，从而简化主程序。
• 1. 下面是一个简单的程序，用于接收姓氏和名字，然后返回完整的人名信息。

  def get_formatted_name(first_name, last_name):
      """返回整洁的姓名"""
      full_name = first_name + ' ' + last_name
      return full_name.title()
  musician = get_formatted_name('jimi', 'hendrix')
  print(musician)

  • 运行结果

    Jimi Hendrix

  • 上述代码中，get_formatted_name()函数接受两个参数，即名字和姓氏，并将它们合并成一个字符串。然后，该函数返回这个字符串。在主程序中，我们调用get_formatted_name()函数，并将返回值赋给变量musician。最后，我们打印musician的值，以确认它包含了正确的姓名。
• 2. 函数可以返回任何类型的值，包括字典、列表这样较复杂的数据结构。还是上面的例子，这次返回一个表示人的字典。

  def build_person(first_name, last_name):
      """返回一个字典，其中包含有关一个人的信息"""
      person = {'first': first_name, 'last': last_name}
      return person
  musician = build_person('jimi', 'hendrix')
  print(musician)

  • 运行结果

    {'first': 'jimi', 'last': 'hendrix'}

2.1.2 函数传递列表

• 传递列表在函数中很有用，列表中包含数字、名字甚至更复杂的对象，如下例所示。

  def greet_users(names):
      """向列表中的每位用户都发出简单的问候"""
      for name in names:
          msg = "Hello, " + name.title() + "!"
          print(msg)
  usernames = ['hannah', 'ty', 'margot']
  greet_users(usernames)

  • 运行结果

    Hello, Hannah!
    Hello, Ty!
    Hello, Margot!

  思考:对于带返回值的函数与对于带默认值的函数
  • 对于带返回值的函数，输入并运行以下代码。

    def fact(n):
        factorial=1
        for counter in range(1,n+1):
            factorial *=counter
        return factorial
    n=int(input('calculate n! Enter n=?'))
    print(n,'!=',fact(n))

  • 对于带默认值的函数，输入并运行以下代码。

    def rt1(a=3):
    for n in range(a):
        for m in range(n+1):
            print('*',end='')
        print()
    rt1()
    rt1(5)

易错点

1. 比对带返回值与不带返回值的自定义函数的差别，理解它们的含义。
2. 在函数中用return语句将值返回调用函数的代码行。

2.1.3 模拟考题-函数的返回值

考题1 单选题

关于以下程序，下列表述中错误的一项是（ ）。

def demo(n): 
    s=1 
    for i in range(1,n): 
        s*=i 
return s

• A. demo(n) 函数的功能是求n的阶乘
• B. s是局部变量
• C. n是形参
• D. range() 函数是Python内置函数

考题2 单选题

运行以下程序，输出结果正确的是（ ）。

def demo(x): 
    return x*2; 
print(demo(demo(demo(1))))

• A. 1    B. 2    C. 4    D. 8

考题3 判断题

函数体中必须包含return语句。（ ）

2.2 全局变量和局部变量

知识点详解

• 一般定义在程序最开始处的变量称为全局变量，而在函数中定义的变量称为局部变量。可以简单理解为，无缩进的为全局变量，有缩进的是局部变量。
• 全局变量的作用域是整个程序，而局部变量的作用域是函数内部。
• 当程序运行时，首先会找程序内部有没有局部变量，如果有，则调用；如果没有，才去调用全局变量。

  name='zhang'    # 全局变量
  def f():
      name="li"   # 局部变量 
      print(name)
  f()

  • 运行结果

    li

    • 调用f()函数，程序会先在函数内部找有没有name这个变量，如果有，就会使用该name的值；而如果没有定义局部变量name，函数再去找全局变量name。
• 可以通过global关键字，通过局部变量修改全局变量的值，如下例所示。

  name='zhang'    # 全局变量
  def f():
      global name
      name="li"   # 局部变量
      print(name)
  f()
  print(name)

  • 运行结果

    li
    li

    • 上述代码中，在函数f()中使用global关键字，声明name是全局变量，这样就可以在函数内部修改全局变量的值了。
    • 注意：在函数内部修改全局变量的值时，要使用global关键字，否则会创建一个新的局部变量。
    • global 与 nonlocal 的区别：
      • global 关键字用来在定义局部变量的同时，修改全局变量的值；
      • nonlocal关键字用来在函数或局部作用域使用外层（非全局）变量。

        def outer():
            x = "outer"
            def inner():
                nonlocal x
                x = "inner"
            inner()
            print("outer:", x)
        outer()

        • 运行结果

          outer: inner

          • 上述代码中，在函数inner()中使用nonlocal关键字，声明x是外层变量，这样就可以在函数内部修改外层变量的值了。

2.2.1 思考

1. 对于局部变量作用域，输入下列代码，并运行试试。

   def f1():
       x=5
       y=6
       print(x+y)
   def f2():   # 改为 (x)
       y=1
   print(x+y)  # 出错！不能引用 f1（）中的x
   f1()
   f2(5)

   • 调用f2(5)时出错了，处理办法有以下两种。 方法1：将“def f2():”改为“def f2(x):”。 方法2：将“x=5”从f1()中移出来，使x变为全局变量。
2. 如果在函数中定义的局部变量与全局变量同名，则调用函数时，局部变量屏蔽全局变量。输入下列代码，并运行试试。

   x='outside'
   y='global'
   def f():
       x='inside'
       print(x)
       print(y)
   f()
   print(x)

   • 运行结果

     inside
     global
     outside

易错点

1. 理解global与nonlocal关键字的区别和它们各自的用法。
2. 如果在函数中定义的局部变量与全局变量同名，则调用函数时，局部变量屏蔽全局变量。

2.2.2 模拟考题-全局变量和局部变量

考题1 单选题

运行以下程序，输出的结果是（ ）。

x=1
def demo(): 
    global x 
    x=2 
    print(x) 
demo() 
print(x)

• A.

1
1

• B.

2
1

• C.

1
2

• D.

2
2

考题2 单选题

运行以下代码，正确的结果是（ ）。

def f(s):
    t=0
    max=0
    for i in s:
        if i>="0" and i<="9":
            t=t+1
        else:
            if t>max:
                max=t
            t=0
     print(max)
list="123ab45cd6d"
f(list)

• A. 0    B. 1    C. 2    D. 3

考题3 判断题

调用嵌套函数outer()，两次输出变量x的值是不一样的。（ ）

def outer():
     x = "local"
     def inner():
         x = 'nonlocal' 
         print("inner:", x)
     inner()
     print("outer:", x)。

2.3 为函数的参数和返回值指定类型

知识点详解

• Python 是动态类型语言，新建变量时不需要声明与指定类型，自定义函数时也是如此。
• 但是，Python 3.5之后的版本就新增了对函数参数和返回值的类型指定和检查，新建变量时也可以指定类型。
• 例如下面这个函数，指定了输入参数a的类型为int，而b的类型为str，并且返回值的类型为srt。
• 可以看到，调用此函数，最终返回了一个字符串。

  def add(a: int, b: str) -> str:
      return str(a) + b
  print(add(1, '2'))

  • 运行结果

    12

  • 当我们调用这个函数时，如果参数a输入的是字符串，实际上运行不会报错，毕竟Python的本质还是动态类型语言。

    def f(a: int, b: str) -> str:
        print(a,b)
        return 500
    f('1','2')

    • 运行结果

      1 2

易错点

1. Python 3.5之后的版本新增了对函数参数和返回值的类型指定和检查，新建变量时也可以指定类型。
2. 如果参数a输入的类型不匹配，实际上运行时不会报错。

2.3.1 模拟考题-为函数的参数和返回值制定类型

考题1 编程题

• 设计一个算法，根据邮件的重量和用户是否选择加急计算邮费。
• 计算规则：
  • 重量在1000克以内（含1000克），基本邮费8元。
  • 超过1000克的部分，每500克加收超重费4元，不足500克部分按500克计算。
  • 如果用户选择加急，多收5元。
• 根据上述计算规则，编写自定义函数完成程序功能，或补全代码。
• 描述：根据邮件的重量和用户是否选择加急计算邮费。
• 函数名：postage(w:int, f:str)->int
• 参数表：w代表邮件的重量（整数）。f是表示是否加急的字符串，其中'y'和'n' 分别表示加急和不加急。
• 返回值：返回邮费（整数）。
• 示例：当w=1200，f='y'时，返回17。

待补全

def postage(w:int, f:str)->int:
    if f == 'y':
        cost =   ①  
    else:
        cost =  ②  
    if w > 1000:
        cost +=  ③  
        if w % 500 > 0:
            cost += 4
    return cost 
w = int(input(' 邮件的重量：'))
f = input(' 是否加急：')
print(postage(w, f))

Python

def postage(w:int, f:str)->int:
    if f == 'y':
        cost = 13    # 加急：基本邮费8元 + 加急费5元
    else:
        cost = 8     # 不加急：只收基本邮费8元
    if w > 1000:
        cost += ((w - 1000) // 500) * 4    # 超过1000克的部分，每500克加收4元
        if w % 500 > 0:
            cost += 4    # 不足500克按500克计算，也要加收4元
    return cost 

w = int(input(' 邮件的重量：'))
f = input(' 是否加急：'))
print(postage(w, f))

3 递归与递推

学习要点

1. 通过自定义函数的调用，实现递归方法。
2. 掌握由递归变递推的方法。

对标内容

1. 理解基本算法中递归的概念，实现基本算法中的递归方法，掌握基本算法中由递归变递推的方法。

3.1 递归算法

情景导入

• 汉诺塔（Hanoi Tower），又称河内塔，源于印度的一个古老传说。
  • 大梵天创造世界的时候做了3根金刚石柱子，在一根柱子上从下往上按照从大到小的顺序摞着64片黄金圆盘。
  • 大梵天命人把圆盘从下往上按照从大到小的顺序重新摆放在另一根柱子上。
  • 并且规定，任何时候，在小圆盘上都不能放大圆盘，且在3根柱子之间一次只能移动一个圆盘。问应该如何操作？

    # 汉诺塔
    def hanoi(n, a, b, c):
        if n == 1:
            print(a, '-->', c)
        else:
            hanoi(n-1, a, c, b)
            print(a, '-->', c)
            hanoi(n-1, b, a, c)
    hanoi(3, 'A', 'B', 'C')

    • 运行结果

      A --> C
      A --> B
      C --> B
      A --> C
      B --> A
      B --> C
      A --> C

    • 汉诺塔的移动可以用递归函数非常简单地实现。

知识点详解

3.1.1 递归的概念

• 在定义一个函数或过程时，如果出现调用自身的成分，则称为递归。
  • 递归算法是一种直接或间接调用自身函数或过程的算法。
  • 递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。
  • 递归算法的特点是算法的结构清晰、可读性强，并且易于用数学归纳法来证明算法的正确性，因此它成为许多算法设计的优秀结构。
  • 递归算法解决问题的特点是，它把一个大规模的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
  • 递归算法的一般形式：

    def 函数名(参数):
        if 满足条件:
            return 结果
        else:
            return 函数名(参数)

  • 递归算法的一般步骤：
    1. 确定递归结束条件。
    2. 给出递归终止时的处理办法。
    3. 提取重复的逻辑，缩小问题规模。
    4. 递归调用。

1. 例如，使用以下程序计算fx=1+2+3+4+5的值。

   def f(x):
       if x==1:
           return 1
       else:
           return x+f(x-1)
   print(f(5))

   • 运行结果

     15

   • 上述程序中，函数f()的作用是计算1+2+3+4+5的值。
   • 程序中，当x=1时，返回1；当x>1时，返回x+f(x-1)。
2. 递归应用实例——阶乘计算
   • 阶乘是指从1乘以2乘以3乘以4一直乘到所要求的数。
   • 例如所要求的数是4，则阶乘式是1×2×3×4，得到的积是24。
   • 24就是4的阶乘。
   • 例如所要求的数是6，则阶乘式是1×2×3×4×5×6，得到的积是720。

   def factorial(n):
       if n == 1:
           return 1
       else:
           return n * factorial(n - 1)
   print(factorial(4))

   • 运行结果

     24

   • 上述程序中，函数factorial()的作用是计算n的阶乘。
   • 程序中，当n=1时，返回1；当n>1时，返回n*factorial(n-1)。

3.1.2 递归算法的实现要点

1. 递归算法有明确的结束递归的边界条件（又称终止条件）以及结束时的边界值，可以通过条件语句（if语句）实现。
2. 函数在它的函数体内调用自身，且向着递归的边界条件发展。

Python

# 递归算法
def f(n):
    if n == 1: # 终止条件
        return 1 # 边界值
    else:
        return n * f(n - 1) # 递归调用

3. 同学们会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就显现出了明显的优越性。

思考

3.1.3 关于递推算法的思考

1. 下列有关递归的说法，错误的是（ ）。

• A. 递归算法的代码一般较少
• B. 递归算法一定要有终止条件
• C. 递归算法体现了“大事化小”的思想
• D. 递归函数中可以不包含条件控制语句

2. 用递归算法求1～n个连续自然数的和的程序段代码如下：

def sum (n):
    if n ＝ 1 :
        return 1
    else:
        return (_____)        
pritn(sun(5))

• 请将代码补充完整。

易错点

1. 递归算法的实现要点需要识记。
2. 用分支结构描述边界条件与递归体。
3. 递归算法体现了“大事化小”的思想。
4. 递归函数中可以不包含条件控制语句。

3.1.4 模拟考题-递归算法

考题1 单选题

以下函数要实现5的阶乘，则应补充的选项为（ ）。

def function(a):
    if(___):
        return function(a+1)*a
    else:
        return 1
print(function(1))

A. a>6    B. a<6    C. a>5    D. a<5

考题2 单选题

斐波那契数列：数列从第3项开始，每一项都等于前两项之和。要计算数列第n 项的值，可以使用递归函数实现，代码如下。

def fn(n):
    if n==1:
        return 1
    elif n==2:
        return 1
    else:
        return

下画线上的代码可填充下列哪个？（ ）

• A. fn(n)+fn(n-1)    B. fn(n-1)+fn(n-2)    C. n+1    D. fn(n+1)+fn(n+2)

考题3 判断题

执行以下代码：程序输出的结果为2。（ ）

ans=0
def fu(a,b,x=1):
    if b==1:
        return 2
    global ans
    ans+=fu(a-x,b-1,2)
    return ans
print(fu(5,4,3))

3.2 递推算法

情景导入

• 莱昂纳多・斐波那契（Leonardo Fibonacci）
• 递推是序列计算中的一种常用方法。它是按照一定的规律来计算序列中的每一项，通常是通过计算前面的一些项来得出序列中指定项的值，如非常有名的斐波那契数列。
• 你会发现大多数花朵的花瓣数目是斐波那契数列中的某一项：3，5，8，13，21，34，55，89……
  • 例如百合花有3个花瓣；
  • 梅花有5个花瓣；
  • 飞燕草有8 个花瓣；
  • 向日葵不是有21个花瓣，就是有34个花瓣；
  • 雏菊有34、55或89个花瓣。
  • 其他花瓣数目则很少出现。你不妨留心数数看。
• 斐波那契和花朵的关系，就是著名的斐波那契数列。
• 这种现象并非巧合，而是植物在长期进化过程中形成的一种优化策略，与植物生长过程中能量的分配、花瓣的生长方式以及空间的利用等因素有关，使得植物能够以最有效、最稳定的方式生长和发育。

知识点详解

1. 递归与递推的对比：有5个人坐在一起
   • 问第5个人多少岁，他说比第4个人大1岁；
   • 问第4个人多少岁，他说比第3个人大1岁；
   • 问第3个人多少岁，他说比第2个人大1岁；
   • 问第2个人多少岁，他说比第1个人大1岁；
   • 问第1个人多少岁，他说他8岁。

• 请问第5个人多少岁？以下是Python程序。

  def age(n):
      if n==1:
          return 8
      else:
          return age(n-1)+1
  print(age(5))

  • 运行结果

    13

  • 上述程序中，函数age()的作用是计算第n个人的年龄。
  • 该程序采用的是递归算法

2. 儿童节那天，有6位同学参加了钓鱼比赛，他们每个人钓到的鱼的数量都各不相同。

   问第1位同学钓了多少条鱼时，他指着第2位同学说比他多钓了2条；
   问第2位同学，他又说比第3位同学多钓了2条鱼……
   大家都说比下一位同学多钓了2条鱼。
   最后问到第6位同学时，他说自己钓了3条鱼。

   • 请问第1位同学钓了多少条鱼？

   假设第1位同学钓了x条鱼，第2位同学钓了x+2条鱼，第3位同学钓了x+4条鱼……
   则第6位同学钓了x+10条鱼。
   因此，第1位同学钓了x+10-6×2=10条鱼。

   • 这就是递推算法-通过多次计算就可求出问题答案，以下为流程图示

     i=1         i=2        i=3        i=4        i=5        i=6
     第1位同学  第2位同学  第3位同学  第4位同学  第5位同学  第6位同学
     x          x+2        x+4        x+6        x+8        x+10

   • 递推算法程序的实现如下所示

     def fish(n):
         x=0
         for i in range(1,n+1):
             x+=2
         return x
     print(fish(6))

     • 运行结果

       10

     • 上述程序中，函数fish()的作用是计算第n位同学钓了多少条鱼。
     • 该程序采用的是递推算法。

例题

3.2.1 例题-递推算法

1. 用递推算法求斐波那契数列的前n项。斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34……其第1项、第2项为1，从第3项开始，每一项是前两项之和。
   • 分析：
     • 第1项、第2项为1，从第3项开始，每一项是前两项之和。
     • 第3项=第1项+第2项=1+1=2
     • 第4项=第2项+第3项=1+2=3
     • 第n项=第n-1项+第n-2项
     • 假设a为n-1,b为n-2,则第三项为a+b=1+2=c
   • 递推算法实现程序如下所示

     a = 1
     b = 1
     n = int(input('请输入n的值：'))
     for i in range(3, n + 1):
         c = a + b # 第三项为a+b
         a = b
         b = c
     print(c)

     • 运行结果

       请输入n的值：10
       55

     • 上述程序中，变量a为n-1项，变量b为n-2项，变量c为n项。

易错点

1. 理解递归算法与递推算法的区别。
2. 能够用递归算法或递推算法解决实际问题。

3.2.2 模拟考题-递推算法

考题1 单选题

设有一个共有n级台阶的楼梯，某人每步可走1级，也可以走2级，用递推的方式可以计算出某人从底层开始走完全部台阶的走法。例如，当n=3时，共有3 种走法，即1+1+1、1+2、2+1。当n=6时，从底层开始走完全部台阶的走法共有多少种？（ ）

• A. 12    B. 13    C. 14    D. 15

考题2 单选题

若一个问题的求解既可以使用递归算法，也可以使用递推算法，则往往采用以下哪一种算法？（ ）

• A. 递归    B. 递推    C. 分治    D. 排序

4 分治算法

学习要点

1. 理解基本算法中的分治算法。
2. 能够用分治算法实现简单的Python程序。

对标内容

• 理解基本算法中的分治算法，能够用分治算法实现简单的Python程序。

4.1 分治算法

情景导入

• 理解基本算法中的分治算法，能够用分治算法实现简单的Python程序。假设你正在爬楼梯，需要n步才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到顶部？

def climb_stairs(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return climb_stairs(n-1) + climb_stairs(n-2) # 等价于斐波那契数列
print(climb_stairs(4))

• 运行结果

  5

知识点详解

4.1.1 分治算法的概念

• 分：将一个复杂的问题分成两个或更多个相同或相似的子问题，再把子问题 分成更小的子问题。
• 治：最后子问题可以简单地直接求解。
• 合：将所有子问题的解合并起来就是原问题的解。

4.1.2  分治算法的特征

1. 该问题的规模缩小到一定的程度就可以容易地解决。
2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3. 该问题分解出的子问题的解可以合并为该问题的解。
4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

• 第一条特征是绝大多数问题可以满足的，因为问题的计算复杂性一般随着问题规模的增加而增加。
• 第二条特征是应用分治算法的前提，大多数问题也可以满足，此特征反映了递归思想的应用。
• 第三条特征是关键，能否利用分治算法完全取决于问题是否具有这一条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
• 第四条特征涉及分治算法的效率，如果各个子问题不是相互独立的，则分治算法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治算法，但一般用动态规划法会更好。

4.1.3  分治算法的实例

1. 例题1 对数组进行快速排序
   • 快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是通过一遍排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，最终使所有数据变成有序序列。
   • 快速排序算法通过多次比较和交换来实现排序，其排序流程如下。
     1. 首先设定一个分界值，通过该分界值将序列数据分成左、右两部分。
     2. 将大于或等于分界值的数据集中到右边，小于分界值的数据集中到左边。此时，左边各元素的值都小于或等于分界值，而右边各元素的值都大于或等于分界值。
     3. 然后，左边和右边的数据可以独立排序。对于左边的数据，又可以取一个分界值，将该部分数据再分成左、右两部分，同样在左边放置较小值，右边放置较大值。右边的数据也可以做类似处理。
     4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左边排好序后，再通过递归将右边排好序。当左、右两部分分别排序完成后，整个序列数据的排序也就完成了。
   • 快速排序的排序步骤：设要排序的数据是A[0]…A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一遍快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时发生变动。
   • 快速排序算法的实现如下所示。
     伪代码

     算法 快速排序(数组 arr)
         如果 数组长度 <= 1 则
             返回 arr
         否则
             选择基准值 = arr[0]
             创建空数组 left
             创建空数组 right
     
             对于 i 从 arr[1] 到 arr[末尾] 执行
                 如果 i < 基准值 则
                     将 i 添加到 left
                 否则
                     将 i 添加到 right
             
             返回 快速排序(left) + [基准值] + 快速排序(right)
     结束算法
     
     调用示例：
     输入数组 = [1, 4, 2, 3, 6, 5]
     输出 快速排序(输入数组)

     Python

     def quick_sort(arr): # 快速排序
         if len(arr) <= 1: # 如果数组长度小于等于1，则直接返回
             return arr
         else: 
             pivot = arr[0] # 选择基准值
             left = [] # 创建分治左空数组
             right = [] # 创建分治右空数组
             for i in arr[1:]: # 遍历数组
                 if i < pivot:
                     left.append(i)
                 else:
                     right.append(i)
             return quick_sort(left) + [pivot] + quick_sort(right) # 返回分治左数组+基准值+分治右数组
     print(quick_sort([1, 4, 2, 3, 6, 5]))

     Python

     # 划分分区（非就地划分）
     # 这个实现使用了额外的空间来存储分区结果
     def partition(nums=list):
         # 选择第一个元素作为基准值（pivot）
         pivot = nums[0]                    
         
         # 使用列表推导式创建小于基准值的子列表
         # nums[1:]表示从第二个元素开始遍历，避开基准值
         lo = [x for x in nums[1:] if x < pivot]     
     
         # 使用列表推导式创建大于等于基准值的子列表
         hi = [x for x in nums[1:] if x >= pivot]    
         
         # 返回三元组：小于基准值的列表、基准值、大于等于基准值的列表
         return lo, pivot, hi
     
     # 快速排序主函数
     def quick_sort(nums):
         # 基本情况：如果列表长度小于等于1，直接返回
         # 这是递归的终止条件
         if len(nums) <= 1:
             return nums
             
         # 调用partition函数进行分区
         # 获取小于基准值的列表(lo)、基准值(pivot)和大于等于基准值的列表(hi)
         lo, pivot, hi = partition(nums)
         
         # 递归地对左右两个子列表进行排序，并将结果与基准值合并
         # 最终返回完整的排序列表
         return quick_sort(lo) + [pivot] + quick_sort(hi)
     
     # 测试代码
     lis = [7, 5, 0, 6, 3, 4, 1, 9, 8, 2]  # 创建测试列表
     print(quick_sort(lis))                 # 打印排序后的结果

     Python

     # 使用了原地排序（in-place sorting），不需要额外的存储空间
     # 快速排序主函数
     # list: 待排序的列表
     # p: 排序的起始位置
     # r: 排序的结束位置
     def quicksort(list, p, r):
         if p < r:  # 当起始位置小于结束位置时才需要排序
             q = partion(list, p, r)  # 获取分区点
             quicksort(list, p, q)    # 递归排序左半部分
             quicksort(list, q+1, r)  # 递归排序右半部分
     
     # 分区函数：将列表分成两部分，左边部分的值都小于等于基准值，右边部分的值都大于基准值
     # list: 待分区的列表
     # p: 分区的起始位置
     # r: 分区的结束位置（也是基准值的位置）
     def partion(list, p, r):
         i = p - 1  # i 用于记录小于等于基准值的元素的最后一个位置
         
         # 遍历从p到r-1的所有元素
         for j in range(p, r):
             # 如果当前元素小于等于基准值
             if list[j] <= list[r]:
                 i += 1  # 小于等于基准值的元素数量加1
                 # 将当前元素与第i个位置的元素交换
                 list[i], list[j] = list[j], list[i]
         
         # 将基准值放到正确的位置（i+1）
         list[i+1], list[r] = list[r], list[i+1]
         return i  # 返回基准值的最终位置
     
     # 测试代码
     list1 = [5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8]  # 创建测试列表
     quicksort(list1, 0, len(list1)-1)  # 调用快速排序函数
     print(list1)  # 打印排序后的列表

快速排序可视化

全屏查看

易错点

1. 在理解递归算法的基础上理解分治算法。
2. “分”“治”的概念必须理解。

4.1.4  模拟考题-分治算法

考题1 单选题

以下函数是将一个整数划分为若干个正整数相加的例子，如4=4，1+3=4，1+1+2=4，2+2=4，1+1+1+1=4共5种，则if条件里应补充的选项为（ ）。

def function(b,a):  #b 为待划分的整数，a为正整数加数的个数上限
    if(_______):
        return 1
    elif a==b and b>1:
        return function(b,b-1)+1
    elif b<a:
        return function(b,b)
    elif b>a:
        return function(b,a-1)+function(b-a,a)

• A. a==1 or b ==1    B. a==0 or b ==1
• C. a==1 or b ==0    D. a==1 and b ==1

考题2 单选题

一个袋子里有128枚硬币，其中一枚是假币，并且假币和真币外观一模一样，仅凭肉眼无法区分，仅知道假币比真币轻一些，我现在借助天平来查找假币，最多称几次可以找到假币？

• A. 5    B. 6    C. 7    D. 8

考题3 判断题

使用分治算法分解的子问题是相互独立的、无关联的，子问题的解可以合并为原问题的解。（ ）

5 算法优化

学习要点

1. 掌握算法以及算法性能、算法效率的概念。
2. 理解算法的时间复杂度与空间复杂度。

对标内容

• 理解算法以及算法性能、算法效率的概念，初步了解算法优化效率的方法。

应用while语句解决实际问题

5.1 应用while语句解决实际问题

5.1.1  for、while循环复习

1. 求1+3+5+7+9+11+13的和，用for循环和while循环实现的程序分别如下所示。
   for循环

   sum = 0
   for i in range(1,14,2):
       sum = sum + i
   print(sum)

   while循环

   sum = 0
   i = 1
   while i <= 13:
       sum = sum + i
       i = i + 2
   print(sum)
2. 有30名男生和20名女生，平均分成若干个小组参加户外CS活动，要使每个小组内的男生人数相同，女生人数也相同，可以分成几个小组？有几种分法？
   优化前代码

   nan = 30
   nv = 20
   i = 2
   n = 0
   while i <= 30:
       if nan % i == 0 and nv % i == 0 :
           print( str(i) + " 个小组 ")
           n += 1
       i = i + 1
   print( str(n) + " 种分法 ")

   优化后代码

   nan = 30
   nv = 20
   i = 2
   n = 0
   while i <= min(nan, nv): # 优化循环次数，只需要循环到男生和女生人数的较小值即可
       if nan % i == 0 and nv % i == 0 : # 判断男生人数和女生人数是否都能被i整除
           print( str(i) + " 个小组 ")
           n += 1
       i = i + 1
   print( str(n) + " 种分法 ")
3. 从6月1日起，小明的妈妈要每工作3天休息1天，爸爸要每工作4天休息1天，请你帮忙计算一下小明一家在6月里可以选择哪几天共同休息的日子去奶奶家玩。
   优化前代码

   t = 1
   n=0
   s = ""
   while t <= 30:
       if t % 3 == 0 and t % 4 == 0:
           s = s + "6 月 " + str(t) + "日  “
           n=n+1
       t = t + 1
   print( s,n)

   优化后代码

   t = 4
   n=0
   s = ""
   while t <= 30:
       if t % 3 == 0 and t % 4 == 0:
           s = s + "6 月 " + str(t) + "日  “
           n=n+1
       t = t + 4  # 优化循环步长，只需要循环到30天即可
   print( s,n)

• 小结：优化while程序,可以考虑优化循环条件、循环控制变量。

易错点

1. 枚举范围应尽可能小，但又不能遗漏。
2. 循环的步长应尽可能大。

5.1.2  模拟考题-for、while循环

考题1 单选题

用枚举算法求解“找出所有满足各位数字之和等于7的三位数”时，在下列数值范围内，算法执行效率最高的是（ ）。

• A. 0~999    B. 100~999    C. 100~700    D. 106~700

考题2 判断题

描述算法可以有不同的方式，可用自然语言,也可以用流程图等。（ ）

5.2 时间复杂度与空间复杂度

知识点讲解

5.2.1  时间复杂度的概念

• 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n), 算法的时间度量记作T(n)=O(f(n))，它表示随问题规模n 的增大，算法执行时间的增长率和f(n)的增长关系，称作算法的渐进时间复杂度,简称时间复杂度。时间复杂度T(n)按数量级递增顺序为下表所示：

函数阶数	非正式术语	复杂度高低
1	常数阶	O(1)
log2n	对数阶	O(logn)
n	线性阶	O(n)
nlog2n	线性对数阶	O(nlogn)
n^2	平方阶	O(n^2)
n^3	立方阶	O(n^3)
2^n	指数阶	O(2^n)
n!	阶乘阶	O(n!)

1. 计算时间复杂度的步骤
   • 找到执行次数最多的语句。
   • 衡量执行语句的数量级。
   • 用O()表示结果。
   • 然后用常数1取代运行时间中的所有加法常数。
   • 在修改后的运行次数函数中，只保留最高阶项。
   • 如果最高阶项存在且不是1，那么就去除与这个项相乘的常数，比如3n2 就取n2。最后即可得到想要的结果。
   • 举例：
     • 例1：

       sum = 0
       for i in range(1,n+1):
           sum = sum + i
       print(sum)

       该程序的时间复杂度为O(n)。
     • 例2：

       sum = 0
       for i in range(1,n+1):
           for j in range(1,n+1):
               sum = sum + i * j
       print(sum)
       该程序的时间复杂度为O(n^2)。
     • 例3：

       sum=0
       for i in range(100):
           for j in range(i,100):
               sum+=j
       print(sum)
       该程序的时间复杂度为O(n^2)。

5.2.2  空间复杂度的概念

• 空间复杂度是指算法被编写成程序后，在计算机中运行时所需存储空间大小的度量，记作S(n)=O(f(n))，其中n 为问题的规模或大小。
• 存储空间一般包括3个部分：
  1. 输入数据所占用的存储空间；
  2. 指令、常数、变量所占用的存储空间；
  3. 辅助（存储）空间。
• 算法的空间复杂度一般指的是辅助空间。
• 一维数组a[n]的空间复杂度为O(n)。
• 二维数组a[n][m]的空间复杂度为O(n*m) 。

时间复杂度与空间复杂度易错点

1. 熟记时间复杂度与空间复杂度的计算实例。
2. 理解时间复杂度与空间复杂度的概念。

5.2.3  模拟考题-时间复杂度与空间复杂度

考题1 单选题

在使用Python编写程序时，提到的“时间复杂度”中的“时间”一般是指 （ ）。

• A. 算法执行过程中所需要的基本运算时间
• B. 算法执行过程中编译代码所花时间
• C. 算法执行过程中所需要的基本运算次数
• D. 程序代码的复杂程度

考题2 判断题

如果执行算法所需的临时空间不会随变量的变化而变化，那么该算法的空间复杂度为一个常量。（ ）

6 第三方库（模块）的获取、安装与调用

学习要点

1. 理解模块化架构和包的管理，了解pip命令、集成安装方法和文件安装方法。
2. 掌握import和from方式。

对标内容

• 掌握第三方库（模块）的功能、获取、安装、调用等。

6.1 第三方库的获取、安装与调用

扩展

6.1.1  第三方库的获取、安装方法

安装Python第三方库的3种方法

1. 使用pip命令；
2. 集成安装方法；
3. 文件安装方法。

1. 使用pip命令
   • pip是Python的包管理工具，用于安装和管理Python包。
   • 可以使用pip命令来安装第三方库，例如：

     pip install numpy

     这将安装名为numpy的第三方库。
2. 集成安装方法
   • 可以使用集成开发环境（IDE）来安装第三方库，例如：
     • PyCharm：在PyCharm中，可以使用“File”>“Settings”>“Project Interpreter”来安装第三方库。
     • Visual Studio Code：在Visual Studio Code中，可以使用“View”>“Command Palette”>“Python: Install Package”来安装第三方库。
3. 文件安装方法
   • 可以将第三方库的安装文件下载到本地，然后使用pip命令来安装，例如：

     pip install C:\Users\username\Downloads\numpy-1.20.

   • 可以将第三方库的安装文件下载到本地，然后使用pip命令来安装，例如：

     pip install C:\Users\username\Downloads\numpy-1.20.8-win_amd64.whl

     这将安装名为numpy的第三方库。

6.2 第三方库的导入方法

• 使用Python进行编程时，有些功能没必要自己实现，可以借助 Python现有的标准库或者其他人提供的第三方库，如下例所示。

  import numpy
  import matplotlib.pyplot as plt

  • 第一行代码使用import语句导入了numpy库，第二行代码使用import语句导入了matplotlib库中的pyplot模块。
  • 其中，numpy库提供了大量的数学函数和数组操作函数，matplotlib库提供了大量的绘图函数。

6.2.1  import 模块名1 [as 别名1], 模块名2 [as 别名2]，…

• 使用import语句导入模块的语法格式如下：

  import 模块名1 [as 别名1], 模块名2 [as 别名2], ...

  • 其中，模块名1、模块名2等是要导入的模块的名称，as关键字后面的别名1、别名2等是模块的别名，用于在程序中引用模块时使用。
  • 例如，要导入numpy库和matplotlib库中的pyplot模块，可以使用以下代码：

    import numpy as np
    import matplotlib.pyplot as plt

    这将导入名为numpy的库，并将其别名设置为np；导入名为matplotlib的库中的pyplot模块，并将其别名设置为plt。

6.2.2  from 模块名 import 函数名1 [as 别名1], 函数名2 [as 别名2],…

• 使用from语句导入模块中的函数的语法格式如下：

  from 模块名 import 函数名1 [as 别名1], 函数名2 [as 别名2],...

  • 其中，模块名是要导入函数所在的模块的名称，函数名1、函数名2等是要导入的函数的名称，as关键字后面的别名1、别名2等是函数的别名，用于在程序中引用函数时使用。
  • 例如，要导入numpy库中的sin函数和pi常量，可以使用以下代码：

    from numpy import sin, pi

    这将导入名为numpy的库中的sin函数和pi常量。
  • 注意，使用from语句导入函数时，只能导入函数本身，而不能导入整个模块。如果要导入整个模块，可以使用import语句。
  • 例如，要导入numpy库，可以使用以下代码：

    import numpy

    这将导入名为numpy的库。

第三方库的获取、安装与调用易错点

1. 熟记第三方库的获取、安装方法。
2. 理解第三方库的导入方法。
3. 注重实操体验。
4. 记忆相关的操作语句的语法。

6.3 模拟考题-第三方库的获取、安装与调用

考题1 单选题

用于安装Python第三方库的工具是（ ）。

• A. install    B. pip    C. wheel    D. setup

考题2 判断题

使用“pip install-upgrade numpy”命令能够升级numpy科学计算扩展库。