上机题目题解
利息计算
n=int(input())
t=int(input())
I=float(input())
ans=0
res=n
for i in range(t):
ans+=res*I/100+n/t
res-=n/t
print("%.2f"%ans)
按照题意直接计算即可
首先要注意利率可能是小数，所以int(input())读入I肯定会有问题。然后要用/而不是//
有一些同学是这么写的：
a=n/t
while n!=0:
n-=a
......
因为这里使用的是浮点数的减法运算，Python的浮点运算是有误差的,所以最后n的结果可能会非常接近0但不是0.用while循环就会出现TLE的情况。在明确知道了循环次数后，尽量不要使用while循环，用for更好一些。
快速傅里叶变换
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
for i in range(100):
a.append(0)
b.append(0)
c=[0 for i in range(300)]
for i in range(0,n+m-1):
for j in range(i+1):
c[i]+=a[j]*b[i-j]
print(c[i],end=' ')
这道题很容易出现list越界的情况，所以我的代码直接在每个list后面添加了足够多的0避免这个情况发生。最后根据公式直接计算答案。
很多同学WA的原因都是因为list下标越界.解决的方法其实很简单粗暴:
for i in range(100):
a.append(0)
b.append(0)
在后面疯狂补0就可以了.不用恰好补类似n-m个0这样的,只要补的足够多就肯定没问题.
还有的同学的读入是这么写的:
a=list(input().split())
for i in range(len(a)):
int(a[i]).......
这么写严格来说并没有错,但是很麻烦.当输入的数据很多时,每次使用list里的数据前都要通过int转换,会带来很大的时间消耗,数据很大时甚至可能导致TLE.所以,推荐的写法是这样:
a=list(map(int,input().split()))
一步到位,最简单省事.
变量命名
a=input()+'%'
l=[]
x=''
for i in a:
if (i.isalpha()):
x+=i#字母组成单词
else:
if (x!=''):
l.append(x)#这个特殊字符前有单词
x=''
if (i.isdigit()):
l.append(i)#数字直接存进去
if (len(l)==0):
print('WaiBiBaBo')#全是特殊字符的情况
else:
for i in l:
if (len(i)==1 and i[0].isdigit()):
print(i,end='')#输出数字
else:
print(i[0].upper(),end='')#首字母大写
for j in range(1,len(i)):
print(i[j].lower(),end='')#其他字母小写
这道题和上周的对话过滤有些像。大致的思路是，通过变量x记录单词，当检测到特殊字符时，说明之前的字母构成了一个单词，就把x放到list中，然后清空x方便下次记录。当发现是数字的时候也直接放到list里面。最后统一输出单词。
这道题有一些坑点，比如最后一个单词后面可能没有特殊字符，需要手动补充上一个（不然会漏掉一个单词）。还有就是首字母大写，其他字母小写的条件，首字母后面的字母是有可能也是大写的，不能直接输出，需要转换一下。很多同学90分PE都是这个原因.
二进制数密文系统
使用字典的解法：
n=int(input())
d={}
for i in range(2**n):
s=bin(i)[2:]
while (len(s)<n):
s='0'+s
d[s]=input()
a=input()
if (len(a)%n != 0):
print('Type Error,Please Check!')
else:
flag=0
s=''
ans=''
for i in a:
if (i!='0' and i!='1'):
flag=-1
break
s+=i
if (len(s)==n):
ans+=d[s]+' '
s=''
if (flag==0):
print(ans)
else:
print('Type Error,Please Check!')
这道题稍微复杂一些,拆开来看
输入部分:
n=int(input())
d={}
for i in range(2**n):
s=bin(i)[2:]#去掉前面的0b
while (len(s)<n):
s='0'+s#手动补0
d[s]=input()
a=input()
首先创建一个空字典(不使用题目中的函数也可以做,而且更简单一些),然后得到二进制,使用字符串切片去掉0b.这时遇到了第一个问题:前面少0.解决的思路很简单,发现长度小于n时,手动往前面补就行了.处理完毕后,在字典中构建一个二进制和明文的映射.预处理环节完毕.
转换部分:
a=input()
if (len(a)%n != 0):
print('Type Error,Please Check!')
else:
flag=0#合法性标记
s=''#用来记录二进制数
ans=''#最后的答案
for i in a:
if (i!='0' and i!='1'):
flag=-1#不合法
break
s+=i
if (len(s)==n):#当攒够n位二进制数后,可以转换了
ans+=d[s]+' '#统计答案
s=''#清空,继续转换
if (flag==0):
print(ans)
else:
print('Type Error,Please Check!')
最后的转换方法有很多,字符串切片直接转可以,一位位二进制累加到一起转也可以.这里采用的是后一种方法.
很多同学陷入了一个误区,二进制数的长度不一定是3.要根据输入数据判断.很多人WA在了这上面.
不使用字典的解法：
n=int(input())
l=[0 for i in range(200)]
for i in range(2**n):
l[i]=input()
a=input()
ans=''
s=x=0
if (len(a)%n != 0):
print('Type Error,Please Check!')
else:
for i in a:
if (i!='0' and i!='1'):
print('Type Error,Please Check!')
break
x=x*2+int(i)
s+=1
if (s==n):
ans+=l[x]+' '
x=s=0
else:
print(ans)
这种写法仅供参考,不推荐同学们使用.思路是,明文存到list里,下标就是二进制数所对应的十进制数.需要进行的是把密文序列中的二进制转化为十进制.这里使用的是较为原始的方法,其实可以通过函数直接完成这一过程:
a=int('1010',2)
构造
n=int(input())
a='2'+'3'*(n-1)
print(a)
23333333333333333
技能加点
T=int(input())
while (T):
T-=1
n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0 for i in range(50)]#用来统计k进制每一位的值
ans='YES'
if (k==1):
print('YES')
continue#特殊情况直接处理
for i in range(n):
x=a[i]
w=0#k进制的位数,从0开始计数
while x:
y=x%k#当前位的值
if (y>0):
l[w]+=1#不是0,统计
if (l[w]>1 or y>1):#有多个数的k进制的同一位不为0,或者这个数的当前位不为1
ans='NO'#不合法
x//=k
w+=1#k进制的下一位
print(ans)
思路是,a_{i}对应的k进制数中,不能含有除0,1外的数.而且每一位上,至多有一个a_{i}的值为1.
数据有个坑点是,$k$可以为1.如果不处理,进制转换的while循环会TLE.
调试技巧分享
运行时出错
这部分内容刘泽群助教专门写了一篇详细的文章,见这里.推荐同学们仔细阅读.
然后再分享一篇文章:
当本地运行时发生错误,无法正常运行代码时,需要通过Spyder右下角的报错提示,找到错误的类型,进而分析原因,进行修改.报错的信息可以在上面的文章中找到对应的说明和示例.
运行结果出错
这种情况最为常见.下面介绍几个常见的处理方法.
以这次实验第一题为例,有同学是通过while循环计算的:
a=n/t
while n>0:
n-=a
......
然后本地运行一直不出结果,可以断定是发生了死循环的情况.但是理论上这种写法是不会出现死循环的,现在发生了,那就说明n的值有问题.我们希望找到n的值一直没有减到0的原因.这时可以在循环里加一句输出:
a=n/t
while n>0:
n-=a
print(n)
......
这样直接输出问题变量,通过观察输出结果,可以发现n好像没有真正减到0.于是就可以选择换个思路,把while替换成for.
这种输出变量的方法同样适用于本地运行结果WA的情况.当发现结果不对时,可以输出一下中间的计算数据,根据数据寻找出错的位置.
下面这篇文章讲解了如何使用Spyder自带的调试工具检查代码的运行情况.合理运用断点调试和变量监控,可以更加快速,方便地找出问题所在.希望同学们认真阅读下面这篇文章.
在期中期末考试时,助教的工作只有监考,不负责解答与代码相关的问题.所以,在平时一定要着重锻炼代码调试和查错能力,平时代码在本地运行出错后不要着急找助教询问,先尽可能自己尝试解决.
OJ上报错
以上图片仅供娱乐
在之前的三次周报中,都强调了本地能够通过样例是说明不了任何问题的.但是这次实验中还是有很多同学问为什么本地可以过,OJ不能过.这里再次说明一下,OJ上的数据会很全面,会有极限数据,也会有特殊性质的数据.这些数据的任务就是测出样例没测出来的漏洞.样例仅仅是一个参考,说明不了任何问题.
下面会分OJ上的错误类型讲解调试技巧.
WA
WA是最常见的情况,可能的原因非常多.发生这种情况后,首先要检查代码中的计算式,看有没有式子打错了,是否有变量未清零,输出格式是否正确.检查不能只用肉眼,需要自己手动造一些和样例不同的数据测试.
以这次实验第三题为例,假如发生了WA,而且自己看代码没有发现问题,就要通过数据测试.下面是一些测试的例子以及测这些数据的原因:
a++ #只有一个字母搭配特殊符号
++a #换一种形式
a2 #单个字母+单个数字
13a #换一种形式
AAA #纯字母,全大写
上面这些测试数据补充了样例中没有的几个类型.自己造数据时首要原则就是全面,尽可能构造所有合法的情况.如果都能顺利通过,再向助教求助(不过这时一般就能测出来问题了).
PE
PE发生的原因是多余的空格回车或是大小写错误.
还是以第三题为例,假如发生了PE,首先检查自己的输出格式,有没有多余的空格回车.如果没有,那就很有可能是大小写的问题.回过头仔细读一下题目描述中关于大小写的部分,发现不仅首字母要大写,后面的字母还需要小写.问题到这里就解决了.
PE发生后的解决流程:检查空格回车,和题目要求的格式比较->检查大小写,再仔细阅读一遍题目->基本所有的PE问题都能解决.
TLE
TLE发生的原因是时间复杂度错误或是死循环,偶尔会有常数过大的问题.
以第五题为例,很多同学交了一份枚举的代码,枚举10^{n}大小的数进行检查.发生TLE后,首先验算一下时间复杂度,当n取到最大值的时候,大约需要检查10^{100000}个数.学校的评测机不是神威·太湖之光,这么大的运算量1s内肯定出不来.这说明你的算法有问题,需要换一个思路解决.
第六题也有很多人TLE.验算时间复杂度:O(Tnlogn).代入最大的数据估算一下,1s内完全应该跑出来的.这时说明程序内部发生了死循环,需要着重检查while循环,思考while循环会在什么条件下发生死循环.分析后不难发现,k=1时会死循环.再看一眼数据范围:1 \leq k \leq 20.破案了.
当上述两种情况都不符合时,说明代码的常数比较大,需要压常数.
常见的手段包括:频繁使用的运算结果开一个变量存一下
for i in range(n):
ans+=p/t*i
#改为
a=p/t
for i in range(n):
ans+=a*i
频繁的类型转换要提前转换好.
for i in range(n):
for j in range(m):
ans+=int(a[i])*int(b[j])
#改为
for i in range(n):
a[i]=int(a[i])
for j in range(m):
b[j]=int(b[j])
for i in range(n):
for j in range(m):
ans+=a[i]*b[j]
TLE发生时的检查流程:验算时间复杂度,如果不对就换算法->再检查一下while循环,看是否计算式有误或漏了题目条件->都不符合就压一下常数
CE
这种情况发生时,100%是提交的时候忘了选语言,重新交一遍就可以解决.
在班群里问题的时候,推荐使用Ubuntu Paste.使用方法见第一周周报或是这里.因为有时助教仅仅根据你的代码截图可能不会一下就看出问题所在,又不可能对着截图一行行把代码抄下来运行,毕竟时间上不允许.如果能粘下来代码的话就会很方便.
洛谷题单
很多人在做题的时候感觉缺少思路,或是调试技巧不够熟练.有一个通用的解决方法:刷题.
之前给大家推荐的训练场因为一些原因被洛谷永久关闭了,取而代之的是题单功能.在这里推荐一下洛谷的题单:网页链接.如果时间充裕的话,最好从第一个题单开始往后刷.时间紧的话就优先刷刚刚学过的知识点对应的题目.
下面列举了课程内的知识点所对应的题单名称:
【入门1】顺序结构
【入门2】分支结构
【入门3】循环结构
【入门4】数组
【入门5】字符串
【入门6】函数与结构体
【算法1-2】排序(不需要做快速排序和归并排序部分)
【算法1-3】暴力枚举
【算法1-4】递推与递归
【算法1-5】贪心
【数学1】基础数学问题
【动态规划1】动态规划的引入
还有一些不在教学内容内,但是做了会对考试很有帮助的题单:
【算法1-1】模拟与高精度(高精度部分不需要做)
【算法1-7】搜索
【算法2-1】前缀和与差分
题单中的题目不用全部做完,每一个知识点做代表性的几道题目就可以了.
本文地址: Python第四周周报
