高效作业11 第11课 简单算法及其程序实现-【精彩三年】2024-2025学年高中信息技术必修第一册课程探究与巩固PPT课件（浙教版2019）

高效作业11[第11课　简单算法及其程序实现] 1 2 3 4 5 6 7 8 9 10 11 1．编写程序，实现如下功能：有一个五位数，此五位数的最高位和最低位数字分别是2和5，而且这个五位数是一个完全平方数(一个数能表示成某个整数的平方的形式)。现要输出符合上述要求的所有五位数，并统计共有几个数。程序运行界面如图所示： 请回答下列问题。 (1)解决这个问题采用的算法是_______________(选填：解析算法/枚举算法)。 (2)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 枚举算法 import math c＝0 for i in range(1000)：#循环变量i由0至999 x＝20005＋i*10 if①________________________________________： print(x) ②____________ print('共有： '，c，'个') int(math.sqrt(x))＝＝math.sqrt(x) c＋＝1 【解析】 (1)该五位数首位为2，末位为5，中间三位从000到999遍历分析，为枚举算法。 (2)①该五位数为完全平方数，即其开方后为整数。②c为计数器。 1 2 3 4 5 6 7 8 9 10 11 2．鸡兔同笼：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？以此为例，已知笼中有a个头，b只脚，求鸡、兔各有几只。程序运行界面如图所示： 请回答下列问题。 (1)解决这个问题采用的算法是____________(选填：解析算法/枚举算法)。 (2)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 a＝int(input('请输入头的数量： ')) b＝int(input('请输入脚的数量： ')) 解析算法 t＝① _________________________ j＝②____________________ print('鸡有'，j，'只') print('兔有'，t，'只') 【解析】 (1)解决这个问题需要通过表达式的计算来实现，属于解析算法。 (2)由题干可得a＝j＋t和b＝2j＋4t，通过解方程组，将其转换成Python表达式形式。 b/2－a或(b－2*a)/2 a－t或2*a－b/2 1 2 3 4 5 6 7 8 9 10 11 3．小金编写了一个求最小公倍数的程序，他先借鉴了更相减损术求出最大公约数，再求出最小公倍数(最小公倍数等于两数的乘积除以最大公约数)。更相减损术是出自《九章算术》的一种求最大公约数的算法，其原理是当两个数不都是偶数时，用大数减去小数，把所得的差与小数比较，并以大数减小数，继续这个操作，一直到减数与差相等为止。程序运行界面如图所示： 实现上述功能的Python程序段如下： a＝int(input(”请输入第一个正整数： ”)) b＝int(input(”请输入第二个正整数： ”)) m＝a；n＝b #计算最大公约数 i＝1 while a%2＝＝0 and b%2＝＝0： a/＝2 b/＝2 ①___________ i*＝2 while a！＝b ： if a>b： a＝a－b else： ②______________ x＝b*i c＝③_____________ b＝b－a m*n//x print(”最小公倍数是： ”，c) 请回答下列问题。 (1)若输入的第一个正整数为24，第二个正整数为18，则执行该程序段后，语句“a＝a－b” 共被执行了_____次。 (2)请在横线处填入合适的代码。 【解析】 程序通过更相减损术求出最大公约数。首先将a、b除2操作，使a或b不再能被2整除，再通过更相减损术求出最大公约数，最后求出最大公倍数。 1 1 2 3 4 5 6 7 8 9 10 11 4．查找100 以内的素数对。素数是指除了1 和它本身之外不再有其他因数的数。若两个素数的差为2，则称这两个素数为素数对。下列Python 程序的功能是找出100 以内的素数对，成对输出并统计对数。请在横线处填入合适的代码。 def Isprime(m): #判断是否为素数 flag＝True for i in range(2，m)： if m%i＝＝0： 11 flag＝False break ①_______________ #end Isprime cnt＝0 p1＝Isprime(3) ②_________ return flag i＝5 while i<100： p2＝Isprime(i) if p1 and p2： print(str(i－2)＋” ”＋str(i)) cnt＝cnt＋1 ③______________________________ i＝i＋2 print(”共找到”＋str(cnt)＋”对”) p1＝p2或p1＝Isprime(i) 【解析】 ①根据主程序中相关自定义函数Isprime()的调用语句可知，函数返回的是一个逻辑值。再分析自定义函数前面部分代码，变量flag 已经保存了素数判断的逻辑值(True 或False)，那么，函数的最后一个语句直接返回变量flag 的值即可。 ②根据前后语句的关系，判断的第一组数是3 和5，故i＝5。 ③判断完一组相邻数后，接下来应该判断下一组，循环体内判断的始终是变量p1 和p2，根据i＝i＋2，p2＝Isprime(i)，③处应该对变量p1 进行迭代更新。 1 2 3 4 5 6 7 8 9 10 11 5．2024·新阵地联盟检测有一个数字集合，所有数字按从小到大的顺序排成规律的数列，即a1＝3，a2＝5，a3＝6，a4＝9，…小明同学将所有数字按照左小右大、上小下大的原则写成如图1所示的三角表的形式。 请回答下列问题。 (1)小明发现图1中的数据很有规律，根据这一规律可以推出a(13)＝_______。 　　　　　　　图1　　　　　　　　　 　图2 36 (2)小明编写了一个Python程序，用来求该数列第n项数值以及前n项和，程序运行界面如图2所示。实现上述功能的Python程序段如下，请在横线处填入合适的代码。 num＝int(input(”请输入数列的项数： ”)) n＝num i，sum＝1，0 while n>i： for j in range(i)： ①_______________________ ②________________ i＋＝1 if n！＝0： for j in range(n)： sum＋＝2**i＋2**j ③_______________________________________ sum＋＝2**i＋2**j n＝n－i b＝2**i＋2**(n－1)或b＝2**i＋2**j print(”a(”＋str(num)＋”)＝”，b) print(”集合前”＋str(num)＋”项和为： ”，sum) 【解析】 (1)观察图中数据可以得出规律：第i行有i个数字，且每个生成的数有如下规律： a(13)在表中是第5行第3列的位置，因此a(13)＝2**5＋2**(3－1)＝36。 第5行的数据为：“第5行　33　34　36　40　48”。 (2)①利用for循环生成i行的i个数据，j的值从0开始，对应列索引，结合第(1)小题推导出的规律，每一项的数字为2**i＋2**j，又结合下方代码sum＋＝2**i＋2**j 以及输出语句可知，sum用于存储前n 项和， 因此①处填sum＋＝2**i＋2**j。 ②for循环生成了i行的i个数字，则项数n要减少i项，因此②处填n＝n－i。 ③当剩余项数n不足以生成i行的i个数字时，则单独生成剩余的n项并累 加到前n项和sum中，即if结构的语句内容，完成后i和j即为第num项的所在位置。结合输出结果可知第num项的数字存储在变量b中，因此③处填写生成第num项的代码，b＝2**i＋2**j或b＝2**i＋2**(n－1)。 1 2 3 4 5 6 7 8 9 10 11 【B级　素养形成与评价】 6．针对选考 2024·舟山中学检测公因数只有1 的两个非零自然数，叫做互质自然数。王老师编写了一个Python 程序，程序的功能是随机产生5 个1 到20 之间的整数，找出其中和最大的互质数对。程序运行界面如图所示： 实现上述功能的Python程序如下： import random def gcd(a，b): #gcd函数的作用是求a 和b 的最大公因子 　　　if a<b： 　 a，b＝b，a 　　　while a%b！＝0： 　 a，b＝b，a%b 　　　return b a＝[] for i in range(5)： 　a．append(①__________________________ print(”产生的5 个随机数是： ”，a) max＝0 result＝”” for i in range(len(a))： 　　　for j in range(i＋1，len(a))： 　 random.randint(1，20) if ②_______________________ and a[i]＋a[j]>max： 　　max＝a[i]＋a[j] 　　result＝str(a[i])＋” ”＋str(a[j]) if result！＝””： 　　　print(”最大的互质数对是： ”，result) else： print(”找不到互质数对”) gcd(a[i]，a[j])＝＝1 请回答下列问题。 (1)寻找互质数对的算法属于________(选填：枚举/解析)算法。 (2)若产生的5 个随机数是20，16，12，6，14，则输出的结果是 __________________________。 (3)请在横线处填入合适的代码。 枚举 找不到互质数对 【解析】 (1)罗列列表中的各个数字对，并判断是否为真正解，属于枚举算法。 (2)产生的5个随机数有公因子2，找不到互质数对。 (3)①空随机产生1 到20 之间的整数，使用randint函数；②空调用gcd()函数判断公因子是否是1。 1 2 3 4 5 6 7 8 9 10 11 7．回文素数： 素数：指整数在一个大于1 的自然数中，除了1 和此整数自身外，没法被其他自然数整除的数。例如11，它只能被1 和11 整数，所以11 是素数。 回文数：正读和反读都一样的数字，例如12321。 编写Python 程序，功能为：找出100～n 中的所有的回文素数(n 为大于或等于100 的正整数)。 实现上述功能的Python程序段如下： import math def prime(n): # 判断n 是否是素数 i＝2 k＝int(math.sqrt(n)) while i<＝k： if ①_______________： break i＝i＋1 n%i＝＝0 return i>k def rev(n)：# 倒转数字 t＝0 while ②_______________： t＝t*10＋n%10 n＝n//10 return t n>0或n>＝1 n＝int(input('请输入整数n: ')) L＝[] for i in range(100，n＋1)： if ③_________________： 　 if prime(i)＝＝True： L＝L＋[i] print('100 到n 中的回文素数： '，L) rev(i)＝＝i 请回答下列问题。 (1)如果n＝1000, 并在最后添加语句“print(151 in L)”，该语句输出的结果是__________。 (2)请在横线处填入合适的代码。 【解析】 (1)100～1000中的回文素数包含151，print(151 in L)输出的结果为True。(2)程序通过函数调用分别判断n是否是回文数或素数。函数prime()中，①处判断n是否能被i整除，若n能被i整除，即n不是素数，循环结束。主程序调用函数，②处判断是否为回文数，若数字倒转与该数字本身相同，则为回文数。 True 1 2 3 4 5 6 7 8 9 10 11 8．一个数，求它的所有数位(digits)的平方和，得到的新数再次求其所有数位的平方和，如此重复，最终结果为1，则该数为快乐数。如正整数129，求得其每个位置上的数字的平方和，重复过程如下： 12＋22＋92＝86 82＋62＝100 12＋02＋02＝1 129是一个快乐数 请回答下列问题。 (1)根据以上规则，数19______(选填：是/不是)快乐数。 (2)实现上述功能的Python程序段如下，请在横线处填入合适的代码。 def sqrare_sum(n)： temp＝0 while n>0: ①___________________________ n//＝10 temp＋＝(n%10)**2 是 return temp res＝[] num＝int(input(”请输入一个正整数： ”)) ②_____________ while n！＝1： res.append(n) #将 n 的值添加到列表res 的尾部 n＝③______________________ if n in res： n＝num sqraresum(n) break if n＝＝1： print(num，”是快乐数！ ”) else： print(num，”不是快乐数”) 【解析】 (1)结合题干，分析19是否为快乐数的过程如下： 12＋92＝82，82＋22＝68，62＋82＝100，12＋02＋02＝1，所以19是快乐数。 (2)①函数sqrare_sum(n)的功能是依次提取数字n每位上的数字，并累加其平方。 ②空是将输入的数值num转存到变量n中。 ③利用函数sqrare_sum(n)求得数字n每个位置上的数字的平方和。 1 2 3 4 5 6 7 8 9 10 11 9．将数字1～9分成4组，分别组成3个三位数，且使这3个三位数构成1∶2∶3的比例，试求出所有满足条件的3个三位数。现用Python编程解决这个问题，程序运行界面如图所示： 实现上述功能的Python程序段如下，请在横线处填入合适的代码。 def f(x)：　#分解整数x，将每1位数字添加到list列表中 　list＝[] while x！＝0： r＝x%10 x＝x//10 ①_____________________________________________ return list c＝0 for i in range(123，330)：　 #枚举第一个三位数 ②___________ #计算第二个三位数 k＝i*3 #计算第三个三位数 li＝f(i) list.append(r)或list＋＝[r]或list＝list＋[r] j＝i*2 lj＝f(j) lk＝f(k) d＝li＋lj＋lk s＝0 for a in range(1，10)：　 #统计1～9数字在 列表d中是否出现 　　　if a in d： s＝s＋1 h＝True if ③_____________：#判断是否是符合题意的三位数 　　　h＝False if h： c＝c＋1 print(”第%d组： ”%c，i，j，k) s！＝9 【解析】 ①函数f()的作用是将三位数各个数位上的值分离出来，添加到列表中并返回；②计算第2个三位数，将3个三位数的列表合并为一个大列表，再逐一判断是否符合要求；③通过“for a in range(1，10)”循环判断是否符合要求，如果s＝9，则符合要求。 1 2 3 4 5 6 7 8 9 10 11 10．针对选考2024·宁波中学检测寻找金蝉素数。素数是指大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。金蝉素数是指由1、3、5、7、9这5个奇数排列组成不重复的五位素数，它的中间三位数和最中间的一位数也都是素数的自然数，如“13597”是素数，“359”和“5”也是素数，则“13597”是金蝉素数。小乐编写了一个Python程序寻找金蝉素数，运行结果如图所示： 实现上述功能的Python程序段如下： import math def isprime(n)： 　　　for i in range( )： 　 if n%i＝＝0： 　　　　 break 　　　else： return True 　　　return False cicada＝[] c＝0 for i in range(13579，99999，2)： 　　　a＝[0]*10 　　　temp＝i 　　　while temp！＝0： 　 ①____________________ 　 a[temp%10]＝1 temp//＝10 　　　if a[1]＋a[3]＋a[5]＋a[7]＋a[9]＝＝5： x＝i//100%10 　 y＝②________________________________________________ 　　　if ③ ____________________________________________________ and isprime(y) and isprime(i)： 　　　　cicada.append(i) 　　　　c＋＝1 i//10%1000或i%10000//10 或其他等价答案 x！＝1 andx！＝9或isprime(x)andx！＝1或其他等价答案 print(”金蝉素数有： ”，cicada) print(”共有： ”，c，”个”) 请回答下列问题。 (1)请在横线处填入合适的代码。 (2)上述程序段中加框处应填入的代码为____________(多选，填字母)。 A．2，n B．2，n＋1 C．2，int(math.sqrt(n))＋1 D．2，n/2＋1 E.2，n//2＋1 ACE 【解析】 (1)①由“a[1]＋a[3]＋a[5]＋a[7]＋a[9]＝＝5”可知，此处将temp每个位置上的数字作为索引，并将该位置设为1；②a[1]＋a[3]＋a[5]＋a[7]＋a[9]＝＝5，表示每个奇数都在，可以判断是否为素数，x是中间1位数，y是中间3位数；③判断x是否为素数，但1不是素数。 (2)函数isprime()判断n是否为素数，选项B，因数应除了它本身，不符合；选项D，n是奇数，应该用整除，不符合。 1 2 3 4 5 6 7 8 9 10 11 11．2024·慈溪中学检测某国研发出一种导弹拦截系统，但存在缺陷，第一次发射能拦截任意高度的导弹，以后每一次拦截的高度都不能高于前一次拦截的高度。现输入导弹依次飞来的高度，计算至少需要配备多少套拦截系统才能拦截所有飞来的导弹。 例如，导弹飞来的高度依次为“293 287 295 286 292”，第1 套拦截系统拦截的导弹高度分别为“293 287 286”，第2 套拦截系统拦截的导弹高度分别为“295 292”，因此至少需要2 套拦截系统才能拦截所有导弹。 请回答下列问题。 (1)若导弹飞来的高度依次为“389 207 300 155 299 170 170 65”，则至少需要_______套拦截系统才能拦截所有导弹。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 dd＝input(”请输入导弹依次飞来的高度，以空格间隔开： ”) h＝list(map(int，dd.split())) #将字符串转换为列表，例如“2 4 5”，转换为[2，4，5] xt＝[h[0]] n＝1 2 for i in h： ①_________________ for j in range(len(xt))： if i<＝xt[j]： ②______________ flag＝True break flag＝False xt[j]＝i if not flag： xt.append(i) ③___________________ print(”至少需要”，n，”套拦截系统”) 【解析】 从“一个拦截系统，每次拦截高度都不能高于前一次拦截的高度”可以看出，一个拦截系统拦截的导弹高度，应该是一个递减子序列。拦截系统的数量，即最长递减子序列的个数。 (1)“389 207 155 65”和“300 299 170 170 ”构成2 个递减子序列，需要2套拦截系统才能拦截所有导弹。 (2)要统计所有数据可以形成的递减子序列数量，本题的基本思想是利用一个列表xt，保存每个递减子序列的最小值。具体做法如下： 外循环遍历所有的导弹高度i，内循环遍历列表xt； 若i<＝xt[j]，即当前导弹高度不大于xt 中的值，可以构成递减子序列，此时替换xt[j]＝i，始终让xt 中保存当前子序列中的最小值。这样下一个新值只需要与x[j]做比较，若更小则替换； 若i>xt[j]，说明无法与前面的导弹构成递减子序列，此时序列数n 加1，同时将新序列的高度追加到列表xt 中； 变量flag 用来标记导弹高度i 与xt 中已有元素是否构成递减，①处设置flag 的初值，填flag＝False。若i<＝xt[j]，构成递减，则替换xt[j]的值，②处填xt[j]＝i。若与xt 中的值不能构成递减，此时xt 中新增元素，同时序列数量要加1，从最后的输出可以看出，n为计数器，③处填n＋＝1。 感谢聆听，再见！ $$