资源简介

(共24张PPT)
八、 简单算法及其程序实现
信息技术 必修1 数据与计算
算法的程序实现
第三章
知识过关
1. 解析算法的基本思想
解析算法的基本思想是根据问题的前提条件与所求结果之间的关系,找出求解问题的数学表达式,并通过表达式的计算来实现问题的求解。
2. 设计解析算法的一般过程
(1)明确问题的前提条件。
(2)明确要求的解。
(3)寻找条件与结果之间的关系式,确保数学表达式的正确性。
(4)在编程中正确描述数学关系式。
3. 常见解析算法应用案例
解析算法是一种通用的算法思想,其应用范围非常广泛,有时候可能只需要一条简单的赋值语句,但更多的时候需要与分支结构和循环结构结合起来使用。分段函数通常属于解析算法,较为复杂的如辗转相除法求最大公约数、进制转换和牛顿迭代法等,也可以归为解析算法。
4. 用Python编写解析算法程序时,必须保证计算过程描述的正确性。特别是把数学表达式转换成Python表达式时,必须注意这种转换的正确性,否则容易导致运算结果错误或运行过程出错。
5. 枚举算法的基本思想
枚举算法的思想就是把问题所有可能的解一一罗列出来,并对每一个可能的解进行判断,以确定这个可能的解是否为问题的真正解,若是,就采纳这个解,否则就抛弃它。
6. 设计枚举算法的一般过程
(1)逐一列举可能解的范围。这个过程用循环结构实现。
(2)对每一个可能的解进行检验,判断其是否为问题的真正解。这个过程用分支结构实现。
7. 枚举算法的优缺点和注意事项
(1)优点:是对现实生活的直接描述,易于理解,容易证明算法的正确性。
(2)缺点:枚举算法需要考察多个变量的大量状态,因此效率比较低。
(3)注意事项:要做到既不遗漏任何一个解,也不重复枚举;尽可能结合解析算法,减少枚举变量的数量和枚举变量的范围,以提高效率。
8. Python文件的读写操作
(1)打开/读取文件
①以读(“r”) 的方式打开文件“test. txt”, 其他常见的文件模式还有写(“w”)、读写(“w＋”) 和追加(“a”) 等。例如:
f=open(“test.txt”,“r”) 　　
②每次读取整个文件,它通常将读取到的文件内容放到一个字符串变量中,方便一次性读取,返回字符串类型。例如:
f.read() 　　
③可以采用多次调用read(size)的方法,每次最多读取size个字节的内容,如果文件大小不确定,使用该方法较为安全。例如:
f.read(size) 　　
④函数每次只读取文件的一行,通常将读取到的一行内容放到一个字符串变量中,并按行返回list, 配置文件时使用该方法最方便。例如:
for line in f.readlines():
　　 print(line.strip("")) 　　
(2)写入文件
with open("test.txt","w")as f: 　　
　　 f.write(“需要写入的文字”)
①write() 需要传入一个字符串作为参数,否则会报错。
②写入文件与读取文件类似,只不过模式用“w”表示。写入模式中,若要写入的文件为空文件,则直接写入;若文件中已经存在内容,则旧内容将会被覆盖,若不想被覆盖,则需要将模式改为“a”。
(3)关闭文件的方法是f.close() 。
典例精选
【例1】 有如下Python程序,可实现计算s＝12－22＋32－42＋…＋992－1002的值:
s=0
for i in range(1, 101) :
　　　　　　　　　
print(s)
横线上应填入的代码为(　　)
A. s＋＝i**2 B. s＋＝(－1)**i*i**2
C. s＋＝(－1)**(i－1)*i*2 D. s＋＝(－1)**(i＋1)*i**2
【解析】 观察题目中的式子易知,奇数项符号为正,偶数项符号为负,只有D项符合题意。
D
【例2】 下面的Python程序可解决“鸡兔同笼”问题:笼中有鸡与兔若干只,鸡和兔共有120个头,共有350只脚,问:鸡与兔各几只 请在横线上填入合适的代码。
a=120;b=350
for x in range(1, a) :
y=a-x
if _____________________:
　　　　print("鸡有"＋str(x)＋"只,兔有"＋str(y)＋"只")
【解析】 算法符合列举可能解并验证的思路,是枚举算法。横线上是对x和y的数量是否符合条件的验证,所以可以使用脚的总只数为350这一关系列出数学表达式。
4*y＋2*x ＝ ＝ b
自我检测
1. 下列问题中,适合用解析算法求解的是(　　)
A. 从一大堆照片中找出小美和阿福的合影
B. 计算圆柱的表面积和体积
C. 全班同学按身高从低到高的顺序排队
D. 统计10000以内各数位上数字之和是18的偶数的个数
【解析】 解析算法是用解析的方法找出问题的已知条件与所求结果之间的数学表达式,并通过对表达式的计算来实现问题的求解。计算圆柱的表面积和体积可以使用数学公式,适合使用解析算法。
B
2. 我们都知道,每天进步一点点,一年后会有很大的进步,但对此并没有一个具体的概念。假定你昨天的基数为1,今天比昨天进步了0.01,明天又比今天进步了0.01,以此类推,365天后你的基数将变成多少 解决上述问题的Python程序如下,请在横线上填入合适的代码。
a=1
for i in range(365) :
a=__________
print(a)
【解析】 只要理解题意,就能写出正确的解析式a ＝ a*1.01,365天以后,基数由1变成了37.78。
a*1. 01
3. 某Python程序如下:
m=int(input())
s=""
flag=True
while m＞0:
　　r=m%10
　　m=m//10
　　if flag and r%2!=0:
　　　　s=str(r)+s
　　　　flag=not flag
print(flag, s)
程序运行后,输入m的值为5201314,输出的结果是(　　)
A. False 1 B. True 1
C. False 2 D. True 4
A
【解析】 该程序实现找到正整数的最后一位奇数并输出。当输入m的值为5201314时,进入while循环,r ＝ 4,m ＝ 520131,此时不满足条件r%2! ＝ 0,进行第二轮while循环,得到
r ＝ 1,m ＝ 52013,此时满足if条件,s ＝ “1”,flag ＝ False。后面继续完成剩下的while循环,由于flag的值为False,则if语句不会再被执行,最后输出的结果为False 1。
4. 一只小猴子某天摘了很多桃子,一口气吃掉了一半后还不过瘾,就又多吃了一个;第二天又吃掉剩下的桃子的一半多一个,以后每天都吃掉前一天剩余桃子的一半还多一个,到了第五天再想吃的时候发现只剩下一个桃子了。问:小猴子最初摘了多少个桃子 解决上述问题的Python程序如下,请在横线上填入合适的代码。
num=1
for n in range(4) :
　　_________________________
print(“摘桃子的总数为:”,num)
【解析】 由题可知,从最后一天的桃子数量推出倒数第二天的桃子数量,进而推出倒数第三天的桃子数量,以此类推,最后一天的桃子数量为num,则前一天的桃子数量为(num＋1) *2,故应填入的代码为num ＝(num＋1) *2。
num＝(num＋1) *2
5. 下列问题中,不.适.合.使用枚举算法来解决的是(　　)
A. 在一排柜门中找出某把储物柜钥匙能打开的柜门
B. 用砝码测试某款桥梁模型的最大承重量
C. 确定某个小区平均每天的用电量
D. 在一排连续的开关中找出能关闭某一盏灯的开关
【解析】 用钥匙一一尝试每一个柜门,直到找到能打开的为止,适合使用枚举算法;在桥梁模型上逐渐增加砝码数量直到桥梁模型无法承受为止,适合使用枚举算法;将小区每月用电总量除以每月天数算出平均每天用电量,适合使用解析算法;对所有开关一一进行尝试直到要关闭的灯对开关有反应为止,适合使用枚举算法。
C
6. 在使用枚举算法的过程中,可以结合解析思想来提高枚举算法的效率。使用枚举算法求解满足“各位上的数字之和等于8的三位数”条件的数时,下列枚举范围中,能够使算
法效率最高的是(　　)
A. [107, 800] B. [100, 999]
C. [0, 1000] D. [100, 800]
【解析】 通过分析条件“各位上的数字相加等于8”,可以从最小的满足条件的三位数开始,到最大的满足条件的三位数结束,再在此范围内一一进行枚举验证。各位上的数字相加等于8的最小的三位数是107,最大的是800,所以此范围既包含所有满足条件的数,且需列举验证的数最少。
A
7. 小李的姐姐将旅行箱的密码忘记了,旅行箱的密码由三个数字组成,前两个数字中有一个是2,第三个数字是7,小李编写了一个程序来帮助姐姐找到旅行箱的密码,程序代码如下:
for a in range(0, 10) :
　　for b in range(0, 10) :
　　　　if 　　　　　　:
　　　　　　x=str(a)+str(b)+"7"
　　　　　　print(x)
横线上应填入的代码是(　　)
A. a=2 and b=2 B. a=2 or b=2
C. a==2 and b==2 D. a==2 or b==2
【解析】 从题目可知,密码的前两个数字中有一个数字为2,第三个数字确定为7,所以只需列举出前两个数字中有一个包含数字2的所有可能项。故横线上的条件表达式应为判断a或b中有一个为2的语句。在Python中判断两个数据是否相等的符号是“＝＝”,赋值符号是“ ＝ ”。
D
8. 有如下程序:找出所有能满足“各位上的数字的立方和等于该数本身”条件的三位数
for n in range(100,1000,1):
　　b=n//100
　　s=n%100//10
　　g=　　　
　　if n==b**3+s**3+g**3:
　　　　print(n)
横线上应填入的代码是(　　)
A. n%10 B. n%100
C. n//10 D. n//100%10
【解析】 本题考查Python程序的执行。从题意可知,b、s、g分别为三位数的百位、十位和个位上的数字。n%10正是求个位上的数字,n%100是求三位数的后两位数,n//10是求三位数的前两位数,n//100%10是求百位上的数字。
A
9. 灯泡开关问题:n个灯泡排成一排,依次编号为1~n, 开始时都是熄灭的。现进行如下操作:
第1轮,所有灯泡的按钮被按动一次;第2轮,所有编号为2的倍数的灯泡的按钮被按动一次;第3轮,所有编号为3的倍数的灯泡的按钮被按动一次……第n轮,所有编号为n的倍数的灯泡的按钮被按动一次。问:最后哪些灯泡是亮的 分别使用模拟算法、枚举算法和解析算法解决上述问题,请在横线上填入合适的代码。
(1)模拟算法:分别用0和1表示灯泡的亮灭状态,然后模拟整个开关灯的过程,最后输出值为1的元素。
n=int(input("请输入灯泡的数量:"))
a=[0]*(n+1) #初始时所有灯泡均关闭
for i in range(1, n+1) :
　　for j in range(i, n+1, i) :
　　　　a[j]=1-a[j]
for i in range(n+1) :
　　if ________________:
　　　　print(i, end＝"")
a[i]＝＝1
(2)枚举算法:观察到切换编号为i的开关的次数恰好为i的因数个数,若因数个数为奇数,则最后该灯泡亮。因为只有完全平方数的因数个数为奇数,故只有编号为完全平方数的灯泡亮,因此只需枚举[1,n]范围内的完全平方数即可。
n=int(input("请输入灯泡的数量:"))
for i in range(1, n+1) :
　　sqr=int(__________)
　　if i＝＝sqr*sqr:
　　　　print(i, end＝"")
i**0. 5
(3)解析算法:枚举算法是通过枚举i来计算sqr, 然后利用i－sqr*sqr来验证i是否为完全平方数,但开平方依然是一个很烦琐的操作,需要进一步改进。我们可以运用逆向思维,直接列举完全平方数sqr*sqr, 其中sqr＝1, 2, 3, …。这样就把枚举算法改成了解析算法,从而大大提高效率。
n=int(input("请输入灯泡的数量:"))
sqr=1
while _________________:
　　print(sqr*sqr, end＝ "")
　　sqr＋＝1
【解析】 (1)列表a中元素的值表示灯泡的亮灭状态,最后输出值为1的元素表示灯泡亮,所以条件语句为a[i]＝＝1。(2)该处计算i的平方根,即i**0. 5。(3)列举完全平方数sqr*sqr,该数不能超过n,所以循环条件为sqr*sqr＜＝ n。
sqr*sqr＜＝n八、 简单算法及其程序实现
1. 解析算法的基本思想
解析算法的基本思想是根据问题的前提条件与所求结果之间的关系,找出求解问题的数学表达式,并通过表达式的计算来实现问题的求解。
2. 设计解析算法的一般过程
(1)明确问题的前提条件。
(2)明确要求的解。
(3)寻找条件与结果之间的关系式,确保数学表达式的正确性。
(4)在编程中正确描述数学关系式。
3. 常见解析算法应用案例
解析算法是一种通用的算法思想,其应用范围非常广泛,有时候可能只需要一条简单的赋值语句,但更多的时候需要与分支结构和循环结构结合起来使用。分段函数通常属于解析算法,较为复杂的如辗转相除法求最大公约数、进制转换和牛顿迭代法等,也可以归为解析算法。
4. 用Python编写解析算法程序时,必须保证计算过程描述的正确性。特别是把数学表达式转换成Python表达式时,必须注意这种转换的正确性,否则容易导致运算结果错误或运行过程出错。
5. 枚举算法的基本思想
枚举算法的思想就是把问题所有可能的解一一罗列出来,并对每一个可能的解进行判断,以确定这个可能的解是否为问题的真正解,若是,就采纳这个解,否则就抛弃它。
6. 设计枚举算法的一般过程
(1)逐一列举可能解的范围。这个过程用循环结构实现。
(2)对每一个可能的解进行检验,判断其是否为问题的真正解。这个过程用分支结构实现。
7. 枚举算法的优缺点和注意事项
(1)优点:是对现实生活的直接描述,易于理解,容易证明算法的正确性。
(2)缺点:枚举算法需要考察多个变量的大量状态,因此效率比较低。
(3)注意事项:要做到既不遗漏任何一个解,也不重复枚举;尽可能结合解析算法,减少枚举变量的数量和枚举变量的范围,以提高效率。
8. Python文件的读写操作
(1)打开/读取文件
①以读(“r”)的方式打开文件“test. txt”, 其他常见的文件模式还有写(“w”)、读写(“w＋”) 和追加(“a”) 等。例如:
f=open(“test.txt”,“r”)
②每次读取整个文件,它通常将读取到的文件内容放到一个字符串变量中,方便一次性读取,返回字符串类型。例如:
f.read()
③可以采用多次调用read(size)的方法,每次最多读取size个字节的内容,如果文件大小不确定,使用该方法较为安全。例如:
f.read(size)
④函数每次只读取文件的一行,通常将读取到的一行内容放到一个字符串变量中,并按行返回list, 配置文件时使用该方法最方便。例如:
for line in f.readlines():
　　 print(line.strip(""))
(2)写入文件
with open("test.txt","w")as f:
　　 f.write(“需要写入的文字”)
①write()需要传入一个字符串作为参数,否则会报错。
②写入文件与读取文件类似,只不过模式用“w”表示。写入模式中,若要写入的文件为空文件,则直接写入;若文件中已经存在内容,则旧内容将会被覆盖,若不想被覆盖,则需要将模式改为“a”。
(3)关闭文件的方法是f.close() 。
【例1】 有如下Python程序,可实现计算s＝12－22＋32－42＋…＋992－1002
的值:
s=0
for i in range(1, 101) :
　　　　　　　　　
print(s)
横线上应填入的代码为(　D　)
A. s＋＝i**2
B. s＋＝(－1)**i*i**2
C. s＋＝(－1)**(i－1)*i*2
D. s＋＝(－1)**(i＋1)*i**2
【解析】 观察题目中的式子易知,奇数项符号为正,偶数项符号为负,只有D项符合题意。
【例2】 下面的Python程序可解决“鸡兔同笼”问题:笼中有鸡与兔若干只,鸡和兔共有120个头,共有350只脚,问:鸡与兔各几只 请在横线上填入合适的代码。
a=120;b=350
for x in range(1, a) :
y=a-x
if 　4*y＋2*x ＝ ＝ b　:
　　　　print("鸡有"＋str(x)＋"只,兔有"＋str(y)＋"只")
【解析】 算法符合列举可能解并验证的思路,是枚举算法。横线上是对x和y的数量是否符合条件的验证,所以可以使用脚的总只数为350这一关系列出数学表达式。
1. 下列问题中,适合用解析算法求解的是(　B　)
A. 从一大堆照片中找出小美和阿福的合影
B. 计算圆柱的表面积和体积
C. 全班同学按身高从低到高的顺序排队
D. 统计10000以内各数位上数字之和是18的偶数的个数
【解析】 解析算法是用解析的方法找出问题的已知条件与所求结果之间的数学表达式,并通过对表达式的计算来实现问题的求解。计算圆柱的表面积和体积可以使用数学公式,适合使用解析算法。
2. 我们都知道,每天进步一点点,一年后会有很大的进步,但对此并没有一个具体的概念。假定你昨天的基数为1,今天比昨天进步了0.01,明天又比今天进步了0.01,以此类推,365天后你的基数将变成多少 解决上述问题的Python程序如下,请在横线上填入合适的代码。
a=1
for i in range(365) :
a=　a*1. 01　
print(a)
【解析】 只要理解题意,就能写出正确的解析式a ＝ a*1.01,365天以后,基数由1变成了37.78。
3. 某Python程序如下:
m=int(input())
s=""
flag=True
while m＞0:
　　r=m%10
　　m=m//10
　　if flag and r%2!=0:
　　　　s=str(r)+s
　　　　flag=not flag
print(flag, s)
程序运行后,输入m的值为5201314,输出的结果是(　A　)
A. False 1 B. True 1
C. False 2 D. True 4
【解析】 该程序实现找到正整数的最后一位奇数并输出。当输入m的值为5201314时,进入while循环,r ＝ 4,m ＝ 520131,此时不满足条件r%2! ＝ 0,进行第二轮while循环,得到r ＝ 1,m ＝ 52013,此时满足if条件,s ＝ “1”,flag ＝ False。后面继续完成剩下的while循环,由于flag的值为False,则if语句不会再被执行,最后输出的结果为False 1。
4. 一只小猴子某天摘了很多桃子,一口气吃掉了一半后还不过瘾,就又多吃了一个;第二天又吃掉剩下的桃子的一半多一个,以后每天都吃掉前一天剩余桃子的一半还多一个,到了第五天再想吃的时候发现只剩下一个桃子了。问:小猴子最初摘了多少个桃子 解决上述问题的Python程序如下,请在横线上填入合适的
代码。
num=1
for n in range(4) :
　　　num＝(num＋1) *2　
print(“摘桃子的总数为:”,num)
【解析】 由题可知,从最后一天的桃子数量推出倒数第二天的桃子数量,进而推出倒数第三天的桃子数量,以此类推,最后一天的桃子数量为num,则前一天的桃子数量为(num＋1) *2,故应填入的代码为num ＝(num＋1) *2。
5. 下列问题中,不适合使用枚举算法来解决的是(　C　)
A. 在一排柜门中找出某把储物柜钥匙能打开的柜门
B. 用砝码测试某款桥梁模型的最大承重量
C. 确定某个小区平均每天的用电量
D. 在一排连续的开关中找出能关闭某一盏灯的开关
【解析】 用钥匙一一尝试每一个柜门,直到找到能打开的为止,适合使用枚举算法;在桥梁模型上逐渐增加砝码数量直到桥梁模型无法承受为止,适合使用枚举算法;将小区每月用电总量除以每月天数算出平均每天用电量,适合使用解析算法;对所有开关一一进行尝试直到要关闭的灯对开关有反应为止,适合使用枚举算法。
6. 在使用枚举算法的过程中,可以结合解析思想来提高枚举算法的效率。使用枚举算法求解满足“各位上的数字之和等于8的三位数”条件的数时,下列枚举范围中,能够使算法效率最高的是(　A　)
A. [107, 800] B. [100, 999]
C. [0, 1000] D. [100, 800]
【解析】 通过分析条件“各位上的数字相加等于8”,可以从最小的满足条件的三位数开始,到最大的满足条件的三位数结束,再在此范围内一一进行枚举验证。各位上的数字相加等于8的最小的三位数是107,最大的是800,所以此范围既包含所有满足条件的数,且需列举验证的数最少。
7. 小李的姐姐将旅行箱的密码忘记了,旅行箱的密码由三个数字组成,前两个数字中有一个是2,第三个数字是7,小李编写了一个程序来帮助姐姐找到旅行箱的密码,程序代码如下:
for a in range(0, 10) :
　　for b in range(0, 10) :
　　　　if 　　　　　　:
　　　　　　x=str(a)+str(b)+"7"
　　　　　　print(x)
横线上应填入的代码是(　D　)
A. a=2 and b=2 B. a=2 or b=2
C. a==2 and b==2 D. a==2 or b==2
【解析】 从题目可知,密码的前两个数字中有一个数字为2,第三个数字确定为7,所以只需列举出前两个数字中有一个包含数字2的所有可能项。故横线上的条件表达式应为判断a或b中有一个为2的语句。在Python中判断两个数据是否相等的符号是“＝＝”,赋值符号是“ ＝ ”。
8. 有如下程序:找出所有能满足“各位上的数字的立方和等于该数本身”条件的三位数
for n in range(100,1000,1):
　　b=n//100
　　s=n%100//10
　　g=　　　
　　if n==b**3+s**3+g**3:
　　　　print(n)
横线上应填入的代码是(　A　)
A. n%10 B. n%100
C. n//10 D. n//100%10
【解析】 本题考查Python程序的执行。从题意可知,b、s、g分别为三位数的百位、十位和个位上的数字。n%10正是求个位上的数字,n%100是求三位数的后两位数,n//10是求三位数的前两位数,n//100%10是求百位上的数字。
9. 灯泡开关问题:n个灯泡排成一排,依次编号为1~n,开始时都是熄灭的。现进行如下操作:
第1轮,所有灯泡的按钮被按动一次;第2轮,所有编号为2的倍数的灯泡的按钮被按动一次;第3轮,所有编号为3的倍数的灯泡的按钮被按动一次……第n轮,所有编号为n的倍数的灯泡的按钮被按动一次。问:最后哪些灯泡是亮的 分别使用模拟算法、枚举算法和解析算法解决上述问题,请在横线上填入合适的代码。
(1)模拟算法:分别用0和1表示灯泡的亮灭状态,然后模拟整个开关灯的过程,最后输出值为1的元素。
n=int(input("请输入灯泡的数量:"))
a=[0]*(n+1) #初始时所有灯泡均关闭
for i in range(1, n+1) :
　　for j in range(i, n+1, i) :
　　　　a[j]=1-a[j]
for i in range(n+1) :
　　if 　a[i]＝＝1　:
　　　　print(i, end＝"")
(2)枚举算法:观察到切换编号为i的开关的次数恰好为i的因数个数,若因数个数为奇数,则最后该灯泡亮。因为只有完全平方数的因数个数为奇数,故只有编号为完全平方数的灯泡亮,因此只需枚举[1,n]范围内的完全平方数即可。
n=int(input("请输入灯泡的数量:"))
for i in range(1, n+1) :
　　sqr=int(　i**0. 5　)
　　if i＝＝sqr*sqr:
　　　　print(i, end＝"")
(3)解析算法:枚举算法是通过枚举i来计算sqr, 然后利用i－sqr*sqr来验证i是否为完全平方数,但开平方依然是一个很烦琐的操作,需要进一步改进。我们可以运用逆向思维,直接列举完全平方数sqr*sqr, 其中sqr＝1, 2, 3, …。这样就把枚举算法改成了解析算法,从而大大提高效率。
n=int(input("请输入灯泡的数量:"))
sqr=1
while 　sqr*sqr＜＝ n　:
　　print(sqr*sqr, end＝ "")
　　sqr＋＝1
【解析】 (1)列表a中元素的值表示灯泡的亮灭状态,最后输出值为1的元素表示灯泡亮,所以条件语句为a[i]＝＝1。(2)该处计算i的平方根,即i**0. 5。(3)列举完全平方数sqr*sqr,该数不能超过n,所以循环条件为sqr*sqr＜＝ n。

展开更多......

收起↑