Python第二周周报
上机题目题解
命题生成器
a=input()
b=input()
print('If ',a,', then ',b,'.',sep='')
通过sep设置输出的各个内容之间用什么隔开,默认是空格,这里方便起见改成了空字符串.
关于print,默认在输出多个内容时用空格隔开,你可以用+来避免这个情况,也可以用sep来把分隔符置为空.
奖状密码
a=int(input())
b=int(input())
print('--------------------')
print('-------- ')
print('------ ')
print('---- -')
print('-- %s --'%(chr(a&b)))
print('- ----')
print(' ------')
print(' --------')
print('--------------------')
从题目描述中不难得出,每一门成绩优秀才算整体优秀,对应的是位运算中的与运算.所以这里使用了与运算符&.并不需要把每一位都拆开来计算.
有一些同学可能被指导书中的bin函数弄迷了,把整数又转化成二进制,然后按位算,再转化回去,写的很麻烦.其实没有必要,Python中的位运算符在进行计算时,会自动把十进制数转化为二进制,进行位运算,再自动转化成十进制,然后返回给你.所以直接a&b就行了.
注意一下输出格式,有的同学在第二行输入后面少了空格,或者是某一行空格少数了一个.像这种输出格式比较麻烦的题目,推荐直接把样例输出粘贴进来,然后在样例的基础上稍作修改转化为输出语句.
估计自然常数e
import math
n = float(input())
e = math.e
ans = (1+1/n)**n
print ("%.6f"%ans)
print ("%.6f"%e)
print ("%.12f"%abs(ans-e))
注意最后一个输出需要加上绝对值函数abs.
如果你import了math但是在下面暂时没有用到它,Spyder会在import那一行标出一个黄色的警告标记.这个并不用在意.写代码的时候一般不用管这种Warning内容.
四元数乘法
a,b,c,d=map(float,input().split(","))
A,B,C,D=map(float,input().split(","))
print("%.2f,%.2f,%.2f,%.2f"%(a*A-b*B-c*C-d*D,b*A+a*B+c*D-d*C,c*A+a*C+d*B-b*D,d*A+a*D+b*C-c*B))
按照指导书中的公式直接计算即可.
因为输入数据是由逗号隔开的,这里的split里也需要填上一个逗号,表示按照逗号分隔.输出的时候也要看清楚,题目中要求输出也要用逗号隔开.
净化网络环境
import math
x=ord(input())
a,b,c=map(int,input().split())
ans=math.ceil(a*math.log(x)-math.log(b))+c
ans%=26
print(chr(ans+65))
凡是题目中提到A-Z对应某个数字区间的,肯定是让你使用ASCII码来做.
需要熟练记住的几个ASCII码的值:
0:48
A:65
a:97
求平方根
n=float(input())
a=1
b=0
sum=0
while 1:
b=(a+n/a)/2
sum+=1
if (abs(b-a) < 0.00001):
print("%.3f"%b)
print(sum)
break
a=b
因为不确定迭代的次数,这里使用了while循环.b用来储存当次计算结果,a储存上一次的计算结果.当发现绝对值之差小于要求的值之后,输出并break出去.
关于平方根计算有个很有趣的故事.传统的迭代算法在计算平方根的时候,都是先找平方根倒数的近似值,然后走牛顿迭代计算.通常这个值是查表得到的.某一天,有人在《雷神之锤III竞技场》的源代码中找到了这么一段算近似值的代码:
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
return y;
}
大致意思就是把一个整数先转化为浮点数,除以2,然后拿0x5f3759df减一下,迭代一次,算完了.第二次迭代被注释掉了,因为一次迭代后的精度已经足够高.这段代码公布的时候掉了一地眼镜,0x5f3759df这个数也被称为魔数.这个数是怎么选出来的目前仍是个迷,有猜测是泰勒展开+二分答案找到的,但尚无定论.
关于比赛的补充内容
很多人在实验的时候发现进不去比赛页面,主要原因是因为网络好像刚好在维护,访问不是很稳定.如果是打开比赛页面发现是空白页的,需要换个浏览器(这里实名Diss360浏览器),换成火狐或者Chrome都可以解决这个问题.
然后是关于比赛排名机制的一个解释.比赛时如果一道题拿到了100分,视为是通过,否则是不通过.罚时的计算规则是,你的每一道题目的通过时间之和加上你在通过这些题目之前错误的次数*20min.举个例子,你在1小时和2小时的时候分别通过了一道题,然后之前在第二道题上WA了三次,在第三道题上WA了5次但是一直没过.那么你的罚时就是4小时.计算式就是1小时+2小时+3乘以20分钟.因为第三题没有通过,所以再多的错误提交也不会计入罚时.一旦通过了,之前的错误提交就会被计入.
OJ的排名机制是以你的得分为第一关键字,得分最高的在前面;得分一样看罚时,罚时少的在前面.平时成绩在计算时只会考虑你的得分,不会考虑你的罚时以及排名.不过在平时练习时还是建议尽可能控制错误提交次数,多在本地测试几次.
还有很多人问为什么样例过了但是OJ上过不去,这里再强调一次,样例通过不能说明任何问题,你的代码可能仍存在一些Bug.样例通过后,建议在本地造几组数据测试一下,确定没有什么问题后再提交.
如果发生了PE,说明你的输出和标准答案很接近,只是多或少了几个空格,这时需要检查输出格式;
如果发生了CE,说明发生了编译错误.这种情况一般是你在提交的时候忘记了选择编程语言.在提交时一定要记得把编程语言选成Python 3.
如果发生了WA,说明你的计算结果和答案有一些差异,这时需要检查你的计算式,或是检查一下输出形式.
如果发生了TLE,下面的时间复杂度内容会介绍原因及解决方案.
知识补充
for循环
for循环有两种常见的使用情景,一种是对某个可迭代对象进行遍历,例如:
a='asdf'
for i in a:
print(i)
a=[5,4,3,2,1]
for i in a:
print(a)
第二种情况是将某一段代码执行指定次数.在题目中,经常会见到第一行一个整数n,接下来n行每行一个整数这样的输入形式.在这种输入数量未知的时候,也会使用for循环
n=int(input())
for i in range(n):
x=int(input())
......
还有一些比较少见的用法,比如:
n=int(input())
for i in range(2,n):
if n%i==0:
print(i)
break
else:
print("Prime!")
这段代码是判断n是不是质数,如果不是,则输出其最小的质因子.否则输出'Prime!'.for...else的用法就是,如果for循环正常执行完毕,也就是中间没有通过break跳出,就执行else中的语句.否则不执行.利用这个写法,我们就不需要手动判断是不是break出了循环了.
while循环
while循环通常用于循环次数未知的情况.即我们无法提前预知,也无法通过输入数据得到确定的循环执行次数,就需要用到while循环.典型的例子是冰雹猜想这道题.
while循环的重点是终止条件的设置.如果条件设置的不正确,有时还会出现死循环的情况.在本地编程调试的时候尤其要小心.但有时候,也会故意写成类似死循环样式的代码,比如:
while 1:
......
这并不代表着我们放弃治疗写题了,其实在循环内部是有对终止情况的判断的,里面一般会有数条if语句来判断是不是具备break出去的条件.这种写法个人命名为循环条件内置.一般用在循环终止条件比较复杂的情况.
当然,你也可以在这个基础上把代码写的可爱一些:
_=1
while (0^_^0):
......
这个和上面那段代码的效果是等价的.(在考试的时候请避免这种写法)
时间复杂度理论
写在最前面的话
学习这部分内容之前需要熟悉for,while循环.下面主要是根据我自己的理解,以一种通俗易懂的方式进行讲解的(也就是说我会抛弃一些严谨性和证明过程),想要了解完整的时间复杂度理论体系请阅读《算法导论》第三章与第十七章,网上也有很多相关的教程.
为什么要研究时间复杂度
计算机的运算能力是有上限的,计算机每秒能够执行多少次运算是可以根据其软硬件条件估计出来的.通常情况下的一台计算机每秒大约能执行10^{7}次基础运算,OJ上的评测机也是这个水平.
在做题的时候会发现每道题都会给出一个时间限制,1s居多.这就意味着你提交的程序必须在1s的时间内计算出一个测试数据点的结果,代表着你的程序至多执行10^{7}次计算就必须得到答案.超过这个次数就会得到TLE的反馈.
所以,为了避免TLE的情况,或者在TLE之后优化算法,甚至根据数据规模以及可能的时间复杂度反向猜正解,都需要熟练掌握时间复杂度的知识.
基本概念
要明确的第一个概念是基础运算.在Python中,我们认为变量赋值,+,-,*,/,//,%,位运算及其有限次复合运算等都是基础运算.比如下面这个例子:
a=0
for i in range(100):
a=a+1
里面有一句赋值语句和一个100的循环,每一次循环执行了一次加法运算,所以我们认为上面这段代码包含了101次基础运算.
但是,在很多情况下,循环的次数我们是不知道的,比如:
n=int(input())
for i in range(n):
a=1
这里执行了n次循环,我们就认为这段代码要执行n次运算,n取决于数据的输入(输入和输出的过程一般不会参与时间复杂度的考虑,下面的所有例子也都会忽略他们).
在学习了循环之后,经常可以发现题目中要求你读入n个数,然后算个什么东西出来,你的代码里就会频繁出现类似上面这样的循环.所以,你的程序执行的基础运算次数一般是一个和n有关的函数,记为f(n).程序的时间复杂度就可以表示为O(f(n)),代表着随着问题规模n的变化,需要的运算次数也会随之变化.
有时f(n)长的并不整齐,比如f(n)=n^{2}+2n+3这样,我们为了方便,在记录时间复杂度时会进行简化,下面是简化规则.
- $f(n)=c$,$c$是一个常数,这时我们把时间复杂度记为$O(1)$
例如:
a,b,c=map(float,input().split())
x=(a+b+c)/3
s=(a-x)**2+(b-x)**2+(c-x)**2
s=(s/2)**0.5
print("%.2f %.2f"%(x,s))
这段代码里没有循环,除了输入输出外,只有三句计算式,f(n)=3,这个次数相对于10^{7}是可以忽略不计的.所以我们不再记录这个常数具体是多少,而是直接记为O(1),代表着小规模的有限次运算,计算机可以瞬间完成.
- $f(n)=kn^{2}$,$k$是一个常数,这时我们把时间复杂度记为$O(n^{2})$
例如:
for i in range(n):
for j in range(n):
ans+=i+j
cnt-=i+j
总共有2n^{2}次运算.时间复杂度的数量级主要取决于n的大小,所以我们会忽略掉前面乘的任何常数.哪怕前面是100也照样忽略,统统记为O(n^2)
- $f(n)=n^{3}+n^{2}$,这时我们把时间复杂度记为$O(n^{3})$
显然,在上面这个多项式中,前一项基本决定了时间复杂度的数量级,所以我们只保留次数最高的项.
综上,我们可以总结出一个规则:保留最高次项,抹掉前面的常数,放到O里面,就得到了时间复杂度.$f(n)$不是多项式的时候,保留对数量级影响最大的一项,并去掉前面的常数.
常见的情况
含有多个未知数:
for i in range(0,n):
for j in range(0,m):
ans+=i+j
类似的,我们记为O(nm)
含有分支:
n=int(input())
if n==1:
print(1)
else:
ans=0
for i in range(n):
ans+=i
print(ans)
这个时候按照最坏情况考虑,也就是取两个分支中时间复杂度最大的一项,所以上面代码的时间复杂度是O(n).这个规则也适用于多个循环并列的情况.
带有函数:
def cal(x):
global ans
for i in range(x):
ans+=i
ans=0
n=int(input())
for i in range(n):
cal(i)
这类情况稍微复杂一些,我们的原则是由内而外分析.首先看函数内部,执行了x次循环.然后看外面的循环,对于每一个i,调用了一次函数,传进去的参数是i,代表着会执行i次操作.不难算出总共执行了\frac{n(n+1)}{2}次运算,故时间复杂度为O(n^{2})
带break的特殊情况:
n=int(input())
k=int(input())
ans=0
for i in range(n):
ans+=i
if (ans==k):
break
这种是循环里带break的.如果我们能知道break出去时,循环已执行次数的均值,那么就按照均值计算;否则一律按最坏情况算.上面的代码里循环次数取决于数据给出的k,所以我们按照最坏情况算,记为O(n).在不确定执行次数时,按照最坏情况估计也是一条基本原则.
while循环的计算:
n=int(input())
while n>0:
x=n%10
n//=10
print(x)
while循环不像for循环那样有明确的执行次数,这时需要我们进行估计.首先,该循环内部只有一处地方对n进行了修改,n的值逐渐减小.我们发现这段代码是把n的十进制位倒序输出,执行次数取决于n的十进制位有多长.于是,我们就可以近似记为O(log_{10}{n}).
在计算机科学中,时间复杂度中的对数式的底数我们一般不写出来,所以正确的记法是O(log \ n).这时有一个问题,底数抹去了还怎么估计运行时间?其实这里还有一个约定,因为底数对log的值的影响不是很大,在估计的时候我们都默认所有对数是以2为底.真正的估计过程是:O(log_{10}{2}log_{2}{n}).前面那个看做常数,抹去,得到O(log \ n).
应用
讲了那么多,下面介绍怎么利用时间复杂度写题.
我们可以利用时间复杂度,估算出在最大规模数据下程序大约执行了多少次计算,并和时间限制乘以10^{7}进行比较,借此判断是不是会发生超时.
比如题目中问题规模是n,n \leq 100000.然后你的代码的时间复杂度是O(n^{2}).这时就不用再问助教为什么你的代码会超时了,因为当n取到最大值时,你的程序大约需要执行10^{10}次运算,远远大于1s内的10^{7},当然会超时了.(典型例子就是后面要讲的筛质数问题)
所以当你发现你的代码的时间复杂度不对的时候,就需要进一步优化代码,更换算法.
再举个例子,题目中让你找1-n中满足某个条件的数有多少个(类似于水仙花数),然后n \leq 10^{8}.显然,这道题明显不是让你用for循环去枚举判断的,这么大规模的数据说明一定有规律,你就可以直接去推式子而不是交一发注定会TLE的代码浪费时间,增加罚时了.
其他
- Python语言自带大常数
前面有说计算机每秒能执行10^{7}次左右的运算,代码中的+,-,*,/这类都看做一次.但是,对C/C++语言是这样,对Python并不是.Python为了满足科学计算的需要,底层封装了大量功能,例如几乎没有上限的整形,例如list自带的一系列函数.这些功能虽然方便,但是维护起来过于复杂,导致Python的一次基础运算相当于其他语言的好几次.一般我们认为Python的运算次数要乘以2-10左右,才是真正的运算次数.
这也就意味着,如果时间限制是1s,你的代码就必须在5 \times 10^{6}左右次的运算内算出答案.所以,写题时请尽量把最坏情况下运算次数控制在10^{6}这个数量级上.
- 自己的代码常数大的问题
同样是O(n^{2})的代码,别人的可以通过,但是你的代码却会TLE.这种情况发生时,说明你的程序的常数很大.前面讲过在估计时间复杂度的时候会忽略掉常数,但是有时候常数就是从AC变成TLE的原因.O(2n^{2})和O(10n^{2})都会记为O(n^2),但是后者的运算次数明显比前者大了5倍,也就意味着时间消耗也是5倍,很有可能发生一个AC,一个TLE的情况.
解决办法是尽量减少冗余运算,别人1,2步算出的结果,就不要把代码写成非要10步才能算出来.减小常数的这个过程被称为卡常数.
- 时间复杂度算不出来的情况
这种情况比较少见,像前面讲的数字拆位勉强算半个,后面要学的递归算法算一个.这时需要引入一些新的计算方法了,比如均摊分析,势能分析等.在后面的实验中碰见相关题目后我会结合题目进行讲解.
筛法求质数
前置知识
必备:质数的定义及性质,算术基本定理.
推荐学习:同余的定义及基本性质,费马小定理,欧拉函数,欧拉定理,辗转相除法.后面的题目可能会涉及到数论相关的知识,所以需要大家有一个简单地了解.而且学习了这部分知识对理解高代中的多项式也很有帮助.
基本算法及改进
根据质数的定义,我们可以通过如下方法判断一个数是不是质数:
flag=0
n=int(input())
for i in range(2,n):
if (n%i==0):
flag=1
break
if (flag==1):
print("No")
else:
print("Yes")
而且不难分析得到,该方法的时间复杂度是O(n).
下面将会逐步改进这个算法.首先,假如n是一个合数,那么,它一定有一个小于等于\sqrt{n}的因子.这一结论是显然的,因为因子一定会成对出现.根据这一性质,我们可以得到下面的优化版代码:
flag=0
n=int(input())
for i in range(2,int(sqrt(n))+1):
if (n%i==0):
flag=1
break
if (flag==1):
print("No")
else:
print("Yes")
这时,时间复杂度变成了O(\sqrt{n}).如果判断少量的数,这个复杂度完全可以接受了.
OJ上有道题是质数求和.需要求至多5 \times 10^{5}内的质数和.如果我们仍使用上面的方法对每一个数进行判断,时间复杂度将会是O(n\sqrt{n}).经过估算不难发现,会TLE.
对单个数的判断算法我们几乎已经优化到了极致,所以想要改进就要把所有要被判断的数一起考虑.假如说p是质数,那么它的倍数显然不是质数.根据这个原理,我们就可以通过筛法把质数筛出来.示例代码如下:
for i in range(2,n+1):
if (v[i]==0):
for j in range(2*i,n+1,i):
v[j]=1
使用v数组来记录一个数是不是质数.v[x]=1表示x是合数,否则就是质数.从2开始筛,假如当前这个数是质数,就把它的倍数全部筛去,这里注意第二个循环的步长是i;否则就什么都不做.
经过上面的操作,我们就可以通过v数组知道1-n中哪些数是质数了.这种筛法也被称为埃氏筛法.下面为时间复杂度证明.根据分析,只有质数的倍数会贡献出一次运算,所以,总的运算次数为
\sum_{p}\frac{n}{p}=n\sum_{p}\frac{1}{p}
后一项为质数倒数和,欧拉证明了其是发散的,而且近似为ln(ln \ n)+O(1).这是一个很著名的结论,证明见这里
综上,埃氏筛法的时间复杂度为O(nlog(log \ n))
埃氏筛法还有一个优化版本:
for i in range(2,n+1):
if (v[i]==0):
for j in range(i*i,n+1,i):
v[j]=1
和上面唯一不同的地方是内部循环从i^{2}开始,这是因为,假如i是质数,其倍数的形式为ai,假如a最小的质因子比i小,说明这个数在之前已经被筛去了,这次就不需要再筛一次.如果比i大,这就是i^{2}之后的情况,需要在这次筛法中筛去.
除此之外,还有时间复杂度为O(n)的欧氏筛法,这里就不再过多介绍.感兴趣的同学可以自行学习.在实际使用中,稍简便的埃氏筛法基本可以满足所有需求,一般不会刻意选择欧氏筛法.
质数求和那道题的示例代码如下:
a,b=map(int,input().split())
v=[0 for i in range(500010)]
v[1]=1
for i in range(2,b+1):
if (v[i]==0):
for j in range(2*i,b+1,i):
v[j]=1
ans=0
for i in range(a,b+1):
if (v[i]==0):
ans+=i
print(ans)
思维拓展
和筛质数经常一起出现的是分解质因数.学习了埃氏筛之后,可以把一定范围内的质数先筛出来放到一个列表里,然后用这些去试除被分解的数.使用这种方法分解单个数的质因数,时间复杂度是O(\frac{\sqrt{n}}{log \ n})的(先不考虑筛法的时间复杂度).其实可以对埃氏筛稍作修改,优化分解质因数.
修改版代码:
for i in range(2,n+1):
if (v[i]==0):
v[i]=i
for j in range(i*i,n+1,i):
if (v[j]==0):
v[j]=i
这时v数组的含义改变了,v[x]里储存的是x最小的质因数的值.如果恰好为x说明x是质数.利用此可以在O(log \ {n})的时间复杂度内完成质因数分解.示例代码如下:
while n>1:
ans.append(v[n])
n//=v[n]
借助埃氏筛优化后,单个数质因数分解的时间复杂度为O(nlog(log \ n) + log\ n)=O(nlog(log \ n))
关于判断单个数是不是质数的算法,前面的说法是几乎优化到了极致,也就代表着其实还有优化空间,单个数质因数分解同样也有.基于费马小定理和二次剩余定理的Miller-Rabin质数测试可以做到在O(log\ n)的时间内给出是不是质数的猜测,正确率极高.基于Miller-Rabin及生日悖论的Pollard-Rho质因数分解算法,同样可以以一个极高的正确率分解质因数,时间复杂度可以达到O(p^{\frac{1}{4}}).关于这两种算法,感兴趣的同学可以移步这篇文章.这两个算法是彻底的超纲内容,不要求掌握,仅供参考.
本文地址: Python第二周周报
