浙教版（2019）高中信息技术必修二 常用基础算法 知识点复习

一轮复习专题三：常用基础算法
一、算法概念
1.广义的讲，“算法”指的是解决问题或完成任务的一系列步骤。在计算机科学领域内，“算法”指的是计算机解决问题的步骤，是为了解决问题而需要让计算机有序执行的，无歧义的，有限步骤的集合。
2.算法的特征：
(1)有穷性：一个算法的处理步骤必须是有限的。
(2)可行性：每一步的操作与要求都是可行的，并且能够在有限时间内完成。
(3)确定性：每一步的执行描述必须是明确的
(4)0个或多个输入
(5)1个或多个输出
3.描述算法的方法：1.自然语言描述；2.流程图描述；3.伪代码描述；4.用程序设计语言描述
4.编程解决问题的一般过程：1.抽象与建模；2.设计算法；3.编写程序；4.调试运行程序
二、流程图
三、解析算法和枚举算法
鸡兔同笼问题：今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何
1.解析写法
head,foot = eval(input("请输入头和足的数量，格式是:头,足"))
rabbit = (foot-head*2)/2
chick = head-rabbit
print("兔子有{}只，鸡有{}只".format(rabbit,chick))
解析算法：用数学公式或解题步骤计算结果
2.枚举写法
head,foot = eval(input("请输入头和足的数量，格式是:头,足"))
for rabbit in range(foot//4):
if rabbit*4+(head-rabbit)*2==foot:
print("兔子有{}只，鸡有{}只".format(rabbit,head-rabbit))
枚举算法：按一定的顺序一一列举所有可能解
四、常见数据处理程序
1.用辗转相除法(欧几里得算法)求最大公约数
def gcd(m,n):
while n != 0:
r = m%n
m = n
n = r
return m
print(gcd(24,15))
注：m为两数中的较大值，n为两数中的较小值；通过m%n不断取余和交换，当余数为零时，最后的较小值就是原数的最大公约数。
2.求素数
def prime_number(num):
for i in range(2,int(num**0.5)):
if num%i==0:
return False
return True
print(prime_number(15))
注：素数只能被1和它本身整除，不能被其他自然数整除。
3.进制转换
1)n进制转十进制(2<=n<=16)
def n_to_shi(n,str):
num = 0
for ch in str:
if n>10:
if "A"<=ch<="F":
num = num*n+(ord(ch)-ord("A")+10)
elif "a"<=ch<="f":
num = num*n+(ord(ch)-ord("a")+10)
else:
return "输入错误"
else:
if "0"<=ch<="9":
num = num*n+ch
else:
return "输入错误"
return num
print(n_to_shi(16,"FF"))
2)十进制转n进制(2<=n<=16)
def shi_to_n(num,n):
str = ""
while num>0:
r=num%n
if r<10:
str += str(r)
else:
str += chr(ord("A")+r-10)
num //= n
return str[::-1] #取倒余
print(shi_to_n(15,16))
4.十进制拆解各个位
例题：小智编写了一个”神奇序列”程序，功能如下：在程序开始输入[100,500]范围内的正整数，程序输出5个该神奇序列的数字，神奇序列的生成规则为：该项的数字+该数百位上的数+该数十位上的数+该数个位上的数=下一项数字。例如321+1+2+3=327。程序运行样例如:
输入：123
输出：第1项为129,第2项为141,第3项为147,第4项为159,第5项为174,
n = eval(input())
if 100<=n<=500:
for i in range(5):
a = n // 100 #百位
b = n // 10 % 10 #十位
c = n % 10 #个位
n = n + a + b + c
print("第"+str(i+1)+"项为"+str(n),end=",")
else:
print("输入有误！")
5.凯撒加密(替代加密)
def encrypt(code,key): #加密过程
code_new = ''
for s in code:
if 'A' <= s <= 'Z':
s_new = (ord(s)-ord('A')+key)%26+ord('A')
code_new += chr(s_new)
elif 'a' <= s <= 'z':
s_new = (ord(s)-ord('a')+key)%26+ord('a')
code_new += chr(s_new)
else:
code_new += s
return code_new
def decrypt(code,key): #解密过程
code_new = ''
for s in code:
if 'A' <= s <= 'Z':
s_new = (ord(s)-ord('A')-key)%26+ord('A')
code_new += chr(s_new)
elif 'a' <= s <= 'z':
s_new = (ord(s)-ord('a')-key)%26+ord('a')
code_new += chr(s_new)
else:
code_new += s
return code_new
s = input("code=")
s1 = encrypt(s,3) #加密
print(s1)
print(decrypt(s1,3)) #解密
6.英文字符的大小写转换
def change(str):
ans = ""
for ch in str:
if "a"<=ch<="z": #ch.islower()
ch = chr(ord(ch)-32) #ch.upper()
elif 'A'<=ch<='Z': #ch.isupper()
ch = chr(ord(ch)+32) #ch.lower()
ans += ch
return ans
print(change("Ab1Cd2EFG3hij"))
7.字符串切片(以身份证号处理为例)
例题：十八位居民身份证号码由六位数字地址码、八位数字出生日期码、三位数字顺序码和一位校验码组成。其中倒数第二位是性别码，男单女双。请编程识别身份证号码中包含的生日和性别信息。身份证有效性验证暂不做要求。
def cut(id_num):
year = id_num[6:10]
month = id_num[10:12]
day = id_num[12:14]
sex = "男" if int(id_num[-2])%2==1 else "女" #行if语句
print("您的出生日期为:"+year+"年"+month+"月"+day+"日,性别为:"+sex)
idnum = "330326199807071166"
print(cut(idnum))
注：身份证号只能使用字符串存储，因为最后一位的校验码有可能为X。
五、必修书本上的例子
1.角谷猜想。以一个正整数n为例，当n是奇数时，下一步变为3n+1；当n是偶数时，下一步变为n/2。不断重复这样的运算，经过有限步后，一定可以得到1。请编程验证角谷猜想，随机生成一个正整数并输出验证的完整过程。
def conjecture(num):
s = str(num)+"->"
while True:
if num == 1:
break
elif num%2==1:
num = num*3+1
else:
num = num/2
s = s + str(num)+"->"
return s[:-2]
import random
print(conjecture(random.randint(0,1000)))
2.百钱百鸡、韩信点兵（枚举算法）
(1)百钱百鸡：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，问翁、母、雏各几何？
(2)韩信带1500名士兵打仗，战死四五百人，剩下士兵排队：站3人一排多2人；站5人一排多4人；站7人一排多6人。求士兵人数。
3.图像字符画
ascil_char = list('"$_&WM#*oahkbdpqwmZO0QLCJUYXzcvunxrjft/\|()1{}[] -/+@<>i!:;,\^`.')
def toText():
im = Image.open('二哈.jpg')
im.resize((100,100)) #修改图像大小
txt =' '
for i in range(im.size[1]): #垂直方向
for j in range(im.size[0]): #水平方向
r,g.b=im.getpixel((j, i))
gray = int(0.2126 * r + 0.7152 * g + 0.0722 * b)
unit = 256 / len (ascil_char)
txt += ascil_char[int(gray//unit)]
txt += '\n'
fo = open('pic_char.txt', 'w')
fo.write(txt)
fo.close()
toText()
4.jieba分词并制作词云
import jieba
from wordcloud import WordCloud
import matplotlib.pyplot as plt
txt = open("你是我的荣耀.txt",'r',encoding='utf-8').read()
words = jieba.lcut(txt) #使用jieba库函数分词
counts = {}
for word in words:
if len(word) == 1: #排除长度为1的字符分词结果
continue
else:
counts[word] = counts.get(word,0)+1 #新词需要先新建，所以用get方法
items = list(counts.items()) #将字典中的键值对转为元组
items.sort(key=lambda x:x[1],reverse=True) #按照统计结果降序排序
ciyun = []
for i in range(50):
word,count = items[i]
print(word,count)
ciyun.append(word)
text_cut = ' '.join(ciyun) #转为字符串，并用空格分隔
wordscloud = WordCloud(background_color='white',font_path = '汉仪乐喵体.ttf',width=1000,height=1000,margin=2).generate(text_cut)
wordscloud.to_file("词云.png")
plt.imshow(wordscloud)
plt.axis('off') #关闭坐标轴
plt.show()
运行结果：
5.Image模块(老虎图片)
from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
choice=128
img=np.array(Image.open("lena.jpg").convert('L'))
rows,cols=img.shape #图像尺寸分别赋值
for i in range(rows): #依次取每个像素的坐标
for j in range(cols):
if (img[i,j]<=choice): #像素值小于等于指定值，赋值1，否则为0
img[i,j]=0
else:
img[i,j]=1
plt.figure("lena") #指定当前绘图对象
plt.imshow(img,cmap='gray') #显示灰度图像
plt.axis('off') #关闭图像坐标
plt.show() #弹出包含了图片的窗口
6.答题卡处理
from PIL import Image
x_start = 11 # 起始点坐标
y_start = 92
fill_width = 24 # 信息点宽度
fill_height = 10 # 信息点高度
space_width = 15 # 间隔宽度
space_height = 12 # 间隔高度
num_length = 9 # 准考证号长度
def bw_judge(R, G, B): # bw_judge 用于判断一个像素的填涂情况
Gray_scale = 0.299 * R + 0.587 * G + 0.114 * B
return Gray_scale < 132
def fill_judge(x, y): # fill_judge 用于判断信息点的填涂情况
count = 0
for i in range(x, x+fill_width):
for j in range(y, y+fill_width):
R, G, B = pixels[i, j]
if bw_judge(R, G, B) == True:
count = count + 1
if count >= fill_width * fill_height * 0.64:
return True
total_width = fill_width + space_width
total_height = fill_height + space_height
image = Image.open("答题卡.bmp")
pixels = image.load()
num = ""
for col in range(num_length):
for row in range(10):
x = x_start + total_width * col
y = y_start + total_height * row
if fill_judge(x, y) == True:
num = num+str(row)
break
else: #十个点检查完都没有填涂for...else...特殊用法
num = num+"#"
print(num)
7.Base64编码
(21.11七彩阳光期中)Base64编码是计算机常见的一种编码方式，规则是把3个字节(24位)的数据按6位一组分成4组(24÷6=4)，然后将每组数据分别转换为十进制，根据表15.1 将这些十进制数所对应的字符连接，即为Base64编码。
以编码字符”Web”为例，如表15.2所示，字符”Web”对应的ASCII编码分别是87，101，98，分别转换为8位二进制数，按6位二进制数分组后再转换成十进制，查找它们对应的字符，得到”Web”得Base64编码为”V2Vi”。
编码字符”Wea”的Base4编码为:
实现上述功能的Python代码如下，请在划线处填入合适代码
s1=input('请输入编码字符:')
s=""
tmp=0
ans=''
txt='ABCDEFGHIJKLMNOPQRSTUVWSXYabcdefghijklmnopqrstuvwxyz012345678+/'
for c in s1:
n=
t = ''
for i in range(8): #将十进制n转换为8位二进制
r=n%2
t= +t
n=n//2
s=s+t
for i in range(len(s)): #6位二进制一组分组再转换成十进制，查找它们对应的字符

if i%6==5:
ans=ans+txt[tmp]
tmp=0
print("Base64编码:",ans)
8.(2021.1学考相似、必修一P101)某小球从100米高度自由落下，每次落地后反弹回原高度的一半，再落下。编程求出第10次落地时，共经过多少米？第十次反弹高度是多少？
请将代码写在下方空白处
9.文本文件处理
(必修一P101)文本文件“score.txt”中保存着30个学生某次测试的成绩，请编写一段程序，从该文件中读取每个学生的分数，统计并输出各等级的学生人数。分数判断等级如下表。请在划线处填上合适的代码。
分数段 90~100 80~89 70~79 60~69 60以下
等级 A B C D E
#随机生成成绩并写入txt
import random
f = open("score.txt",'w')
s = ''
for i in range(30):
s = s + str(i) + ' ' + str(random.randint(40,100)) + "\n"
f.write(s)
f.close()
#统计等第
grade = 'EDCBA'
sum = {}
f = open("score.txt",'r')
line = f.readline()
while line:
l = line.split()
n = int(l[1])//10-5
if n==5:

sum[grade[n]] = sum.get(grade[n],0)+1

print(sum)
f.close()
六、真题链接
(2018.6学考题改编)素数只能被1和它本身整除，不能被其他自然数整除。编写Python程序完成如下功能：随机生成一个三位正奇数，判断该数是否是素数并输出判断结果。
程序运行案例：
输入：无 ； 输出：953是素数
(1)请在划线处填上合适的代码
(2)下列选项中，与加框处表达式”n%i==0”等价的是 (单选,填字母)
A. n//i == int(n/i) B. n//i=n/i C.n%i==n//i
import random
falg = True #flag用于标记是否为素数
n = random. *2+1
i = 3
while i<=n-1 and flag:
if n % i == 0:
flag=False
i += 2
if :
print(str(n)+"是素数")
else:
print(str(n)+"不是素数")
(2019.1学考题改编)小红编写了一个将5位以内的十六进制正整数转换成十进制数的Python程序。程序功能如下：输入一个十六进制正整数，程序输出转换后的结果。
程序运行示例：
输入：1A； 输出：26
(1)请在划线处填上合适的代码
(2)若输入内容为”5+9”,输出结果是：
x =
result = 0
flag = True
for ch in x:
if "0"<=ch<="9":
result = result * 16 + int(ch)
elif "A"<=ch<="F":
result = result * 16 + (ord(ch)-ord("A")+10)
elif "a"<=ch<="f":
result =
else:
flag=False
if flag:
print(result)
else:
print("输入错误")
(2019.6学考真题改编)小宇为选定班级参赛作品编写了一个Python程序，设计如下：输入5位评委对3个作品的评分数据(评委对作品的评分数据由3位十进制数组成，第1位对应作品编号，第2、3位对应作品得分，分值范围为[60,99]。如“275”表示2号作品得分为75分)。程序输出3个作品的平均分和最高分的作品编号(若最高平均分存在并列，则从并列作品中随机抽取)。
程序运行示例：
输入：180/283/385/170/276/384/180/285/380/190/295/390/170/272/372
输出：作品1平均分为:78.0作品2平均分为:82.2作品3平均分为:82.2
最高分不止一个,随机选取最高分编号为:2
(1)请在划线处填上合适的代码
(2)打乱输入顺序，如180/283/170/276/180/285/190/295/170/272/385/384/384/390/372,程序输出结果是否会发生改变__________(A.会发生改变 B.不会发生改变)
import random
s = input()
i = 0
f1=f2=f3=0
while :
d = s[i:i+3]
if d[0] == "1":
f1 = f1 + int(d[1:3])
elif d[0] == "2":
f2 = f2 + int(d[1:3])
else:
f3 = f3 + int(d[1:3])
i =
aver = [f1/5,f2/5,f3/5]
print("作品1平均分为:"+str(aver[0])+"作品2平均分为:"+str(aver[1])+"作品3平均分为:"+str(aver[2]))
i = 0
Max = 0
zdbh = []
while i if aver[i] > Max:
Max = aver[i]

zdbh.append(i)
if aver[i] == Max:
zdbh.append(i)
i+=1
if len(zdbh)==1:
print("最高分编号为:"+str(zdbh[0]+1))
else:
print("最高分不止一个,随机选取最高分编号为:"+str(random.choice(zdbh)+1))
(2020.1学考真题改编)某密文是由一串数字加密得到，其解密规则是：1.对连续重复的大写字母，仅保留1个；2.在去重后的文本中，从首字母开始间隔5个字符取一个，依次连续取出的字符即为明文。
编写解密的Python程序，功能如下：程序开始获取密文，运行程序后程序输出去重后的文本和最后的明文，程序输出输出样例如下：
输入：
AAAAA00121BBBAAAAA0z19$mj0XX478W(@9123pPPPPP
输出：
A00121BA0z19$mj0X478W(@9123pP
1949
(1)请在划线处填上合适的代码
s1 = input()
s2 = s1[0]
for i in range(1,len(s1)):
c = s1[i]
if 'A'<=c<='Z':
if 1 :
s2=s2+c
else:
2
print(s2)
mw = ''
for i in range( 3 ):
mw = mw + s2[i]
print(mw)
(2020.7学考真题改编)用英文字母A~D对数字字符0-9进行编码，规则如下表所示：
例如，数字字符串“709”的编码为“BDAACB”。用Python程序实现上述编码，功能如下，输入需要编码的一串数字字符，程序运行后输出编码结果。程序运行样例如下：
输入：1705
输出：ABBDAABB
(1)请在划线处填上合适的代码
s1 = input()
code = "ABCD"
flag = True
result= ''
for c in s1:
if c<"0" or c>"9":
1
break
else:
numL = 2
numR = eval(c)%4
result = result + code[numL] + code[numR]
if flag:
print(result)
else:
print("输入错误")