任务1：求解汉诺塔问题
下面代码用于求解汉诺塔问题：
def hanoi(n,a,b,c):
if n==1:
print(a,'->',c)
else:
hanoi(n-1,a,c,b) #将a上面n-1个盘子经c移到b
print(a,'->',c) #将a最后1个盘子移到c
hanoi(n-1,b,a,c) #将b上n-1个盘子经a移到c
n=int(input("输入盘子数量："))
hanoi(n,'A','B','C')
1、调试、理解代码，程序保存到s8A.py
2、编写程序s8B.py，根据盘子数量输出需移动的步数。
输入输出格式：
输入盘子数量：3
输出：需移动步数=7
"""
（1）递归调用（教材P72）
函数在执行的过程中直接或间接调用自己本身，称为递归调用。其特点是：①直接或间接调用自身；②有明确的边界条件。
例如，计算n的阶乘。其数学模型为：
fac(n)=1 (n=1)
fac(n)=n*fac(n-1) (n>1)
#程序代码：
def fac(n):
if n == 1: #②边界条件
return 1
else:
return n * fac(n-1) #①调用fac函数本身
#主程序
print(fac(5))
（2）变量作用域（教材P70）
变量的作用域是指变量的作用范围。
① 局部变量
局部变量是在函数内定义的变量，只在定义它的函数内生效。它们与函数外具有相同名称的其他变量，没有任何关系。
所有局部变量的作用域，是它们被定义的块，从它们的名称被定义处开始。函数结束时，其局部变量被自动删除。
def fun( ):
count = 10 #局部变量
print(count) #函数内访问
fun( )
print(count) #NameError: name 'count' is not defined
② 全局变量：
全局变量是在函数外定义的变量，它在程序中任何位置都可以被访问。
count =10 # 全局变量
def fun( ):
print(count) # 函数内访问全局变量
fun( )
print(count) # 函数外访问全局变量
函数中只能访问全局变量，但不能修改全局变量。因为在函数内部给变量赋值，默认为定义新的变量。局部变量和全局变量同名时，优先使用局部变量。
若要在函数内部修改全局变量的值，需先在函数内使用关键字“global”进行声明。
count =10 # 全局变量
def fun( ):
global count #函数内声明全局变量
count+=1 #函数内修改全局变量
fun( )
print(count) # 函数外访问全局变量
输出结果： 11
（3）汉诺塔移动步数
汉诺塔的问题，从小学、中学，一直到大学，老师都在讲。并且有不同的版本。一般汉诺塔问题，都是ABC三根柱子，小盘在上，大盘在下。
方法①：
小学老师：1个盘子，移1步；2个盘子移3步，3个盘子移7步。n个盘子，共移动多少步？？
学生A：移动步数，等于2的n次方，再减1。
方法②：
中学老师：将n个盘子，从A柱移动到C柱。可简化为：
(a) n-1个盘子从A柱移动到B柱，借助C柱；
(b) 第n个盘子，从A柱移动到C柱；
(c) n-1个盘子从B柱移动到C柱，借助A柱；
假设，步骤(a)移动的步数为f(n-1)，将n个盘子，从A柱移动到C柱，需要多少步？？
学生A：2*f(n-1)+1。因为步骤(a)和步骤(c)移动的步数，是一样的！
学生B：那不和前面求阶乘的数学模型，是一样的！
fun(n)=1 (n=1)
fun(n)=2*fun(n-1)+1 (n>1)
方法③：
大学老师：刚才s8A.py的练习，程序的功能是什么？
学生A：输出汉诺塔问题盘子移动的动态过程。
大学老师：n个盘子，从A柱移动到C柱，需要移动多少步？
学生B：函数调用了多少次，就移动了多少步！
大学老师：怎么知道函数调用了多少次？
学生A：在函数定义中，加入变量count计数，在主程序中输出count就可以了。
学生B：如果只想输出移动步骤，不想输出那些动态过程。怎么办？
大学老师：将print语句屏蔽，或者用pass语句置换就可以了。
任务2：斐波那契数列
斐波那契数列的第1项和第2项均为1，从第3项起，每项为前2项的和。
编写程序s8C.py，要求：
1、编写函数fib(n)，返回斐波那契数列的第n项
2、程序运行效果：
输入项数：120
输出：第120个斐波那契数=5358359254990966640871840
"""
递归方法与非递归方法比较：
以教材P72为例，计算500阶乘。
import time
def fac(n): #递归方法
if n == 1:
return 1
else:
return n * fac(n - 1)
def fun(n): #非递归方法
result = 1
for i in range(1, n + 1):
result *= i
return result
#递归方法优点： 代码少，逻辑清晰，可读性强，易于维护。
#主程序（以下代码，参考教材P98）：
before = time.perf_counter( )
x = fac(500) #调用函数fac( )，递归方法
after = time.perf_counter( )
interval = after - before
print(f" 递归方法，运行时间为{interval:.6f}秒")
before = time.perf_counter( )
x = fun(500) #调用函数fun( )，非递归方法
after = time.perf_counter( )
interval = after - before
print(f"非递归方法，运行时间为{interval:.6f}秒")
#程序运行结果：
递归方法，运行时间为0.000711秒
非递归方法，运行时间为0.000168秒
"""
#递归方法缺点：耗费时间更多，递归深度越大越明显。因为递归需要不断地回溯与递推。
注意，不能重复的无限制的对自身进行调用，这会引发异常。Python中默认递归次数为1000次。调用fac(1000)会出错，而调用fun(1000)不会出错。
任务3：质数搜索
编写程序s8D.py，要求：
1、定义函数isp(n)，用于判断n是否为质数。
2、输出[m,n]上质数的个数。m,n从键盘输入。
3、程序运行效果：
输入m,n的值：3,100
输出：[3,100]上共有24个质数
"""
函数方法与非函数方法比较
参考实验四任务4，s4D.py。输出【m,n】范围内质数个数。
#以下为非函数方法
s = input("输入m,n的值：")
s = s.split(",")
m, n = map(int, s)
count = 0
for k in range(m, n + 1): # 遍历【m,n】
flag = True #变量flag=True，假设k是质数
for j in range(2, k): # 遍历【2,k-1】
if k % j == 0:
flag = False
break
if flag == True:
count += 1
print(f"[{m},{n}]上共有{count}个质数")
#以下为函数方法
def isp(n): #函数定义（要考虑形参n为1或0，甚至负数的情况）
....
#主程序
s = input("输入m,n的值：")
s = s.split(",")
m, n = map(int, s)
count = 0
for k in range(m, n + 1):
if isp(k) == True: #调用函数isp(k)，返回值为True，则k为质数
count += 1
print(f"[{m},{n}]上共有{count}个质数")
"""
① 函数主要作用是将复杂问题简单化。方法2和方法1相比，主程序更加简单，程序结构更清晰。前提是，已经有人替你把isp( )函数编好了（这里可没人替你编写）。
② 函数的特点是模块化。如果isp( )函数已经有人替你编好。你不需要关心函数具体是如何编写的。但你得知道怎么用，也就是函数的入口和出口！怎么调用，函数返回值是什么。
③ isp( )函数返回值，可以设为“True/Flase”，可以设为“1/0”，也可以设为“Y/N”，还可以是其他值！！主程序 if 调用语句，作相应修改就可以了。
上面的“if isp(k) == True:”语句， 修改为 “if isp(k):”，可不可以？？可以！前面实验4的s4D.py中已经讲了，“if isp(k) == True”和“if isp(k)”，都可用来作为条件判断。老师这里明确规定，不要用后者。
附加练习：
编写一个函数，求满足以下条件的最大的n值：
1^2+2^2+3^2+4^2+…+n^2<1000 （这里n^2，表示n的2次方）
输出结果：
13
