Python基础之综合练习一
第1关:最小公倍数算法任务描述本关任务:编写一个能计算给定的所有正整数的最小公倍数的小程序。相关知识为了完成本关任务,你需要掌握:如何求任意两个正整数的最大公约数;如何求任意两个正整数的最小公倍数。如何求任意两个正整数的最大公约数最大公约数(GCD, Greatest Common Divisor),也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。比如数12和数18的最大公约数是
第1关:最小公倍数算法
任务描述
本关任务:编写一个能计算给定的所有正整数的最小公倍数的小程序。
相关知识
为了完成本关任务,你需要掌握:
如何求任意两个正整数的最大公约数;
如何求任意两个正整数的最小公倍数。
如何求任意两个正整数的最大公约数
最大公约数(GCD, Greatest Common Divisor),也称最大公因数、最大公因子,指两个或多个整数共有约数中最大的一个。
比如数12和数18的最大公约数是6,因为12的约数有1、2、3、4、6、12,而18的约数有1、2、3、6、9、18,通过比较,显然6是数12和数18的最大公约数。
通过上述过程,显然我们可以通过枚举这两个数的所有约数,考虑这两个数共有的约数,然后选择最大的就是这两个数的最大公约数。因为一个数的约数必然是不大于该数的,所以我们可以通过枚举不超过这两个数中的最大者的正整数,来达到上述效果,具体代码如下述所示:
def gcd_1(x, y):
ed = max(x, y)+1
divisor = 1
for i in range(2, ed):
if x % i == 0 and y % i == 0:
divisor = i
return divisor
其实在古代就有能求解出最大公约数的算法了,《九章算术》是中国古代的数学专著,其中的“更相减损术”就可以用来求两个数的最大公约数,原文是:“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”大致所描述的算法步骤是:
任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步;
以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止;
第一步中约掉的若干个2与第二步中最后得到的差(或减数)的乘积就是所求的最大公约数。
实际编程中,我们可以省略第一步,这样第二步最后得到的差(或减数)就是这两个数的最大公约数,其具体实现如下述代码所示:
def gcd_2(x, y):
while True:
if x < y:
x, y = y, x
elif x == y:
return x
x -= y
尽管前面已经介绍了两种求最大公约数的方法,但实际生活中,我们更倾向于使用辗转相除法,来求解任意两个正整数的最大公约数,以求解30和12的最大公约数为例,按gcd_2代码,其过程为:
30 - 12 = 18 -> 18 - 12 = 6 -> 12 - 6 = 6
最后因为减数和差相等,即6 - 6 = 0,故6就是30和12的最大公约数,仔细观察上述过程,我们可以发现第一步和第二步实际上就是被减数30减了2次12,然后在第三步,用上次计算的余数6继续与12进行比较。显然,我们可以通过整数求余运算,直接一步求得30和12的余数6,此时余数绝对是比除数小的,那么则将除数代替被除数的位置,余数代替除数的位置,然后重复上述过程,直至余数为0,那么此时的除数就是原来两个数的最大公约数了。上述过程用递归方式实现的话,代码是非常简短的,具体代码如下:
def gcd(x, y):
return x if y == 0 else gcd(y, x%y)
最后,推荐大家也去实现下求解任意两正整数的最大公约数的非递归版本。
如何求任意两个正整数的最小公倍数
几个数共有的倍数叫做这几个数的公倍数,其中除0以外最小的一个公倍数,叫做这几个数的最小公倍数(LCM,Least Common Multiple)。
如3和7的最小公倍数是21,因为不存在一个比21还小的正整数,既是3的倍数,也是7的倍数。
显然对任意两个正整数a和b,a*b必是他们的公倍数。假设g为a和b的最大公约数,那么a、b可以分别写成一个正整数与他们最大公约数的乘积的形式,即a = p * g,b = q * g。那么显然c = p * q * g,是a和b的一个公倍数,而且是最小公倍数。因为p和q必定不共有大于1的公约数,所以若减小p、q、g这三个任意一个数的话,都不能使其乘积还是a和b的倍数。
编程要求
根据提示,在右侧编辑器Begin-End区间补充代码,计算并输出给定的所有正整数的最小公倍数,参数x为整数列表。
本关涉及的代码文件src/step1/lcm_stu.py,请读者仔细阅读并完成空缺代码的填写。
测试说明
本关的测试文件是src/step1/main.py。
读者将src/step1/lcm_stu.py中的代码补充完毕,然后点击评测,平台自动编译运行src/step1/main.py,并以标准输入方式提供测评输入;
平台获取程序的输出,然后将其与预期输出对比,如果一致则测试通过;否则测试失败。
平台会对你编写的代码进行测试:
测试输入:
1,2,3,4,5
预期输出:
60
测试输入:
15,25,20
预期输出:
300
开始你的任务吧,祝你成功!
参考代码:
class Solution():
def get_lcm(self, x):
#请在此添加代码,实现求出给定的所有正整数的最小公倍数,并将其返回
#********** Begin *********#
def gcd(n1,n2):
return gcd(n2, n1 % n2) if n2 > 0 else n1
def lcm(n1,n2):
return n1 * n2 // gcd(n1, n2)
ans = x[0]
for index in range(len(x)-1):
x[index+1] = lcm(x[index], x[index+1])
ans = max(ans, x[index+1])
return ans
#********** End **********#
pass
第2关:输出指定范围内的素数
任务描述
本关任务:编写一个能输出指定范围内的素数的小程序。
相关知识
为了完成本关任务,你需要掌握:如何判断一个正整数是否是素数。
如何判断一个正整数是否是素数
素数(Prime Number),又称质数,一个大于1的自然数,除了1和它自身外,不能整除其他自然数的数叫做质数;否则,称为合数(Composite Number)。1既不是素数,也不是合数。
如2、3、5、7、11都是素数,因为找不到除了1和其本身之外的约数;而4、6、8都是合数,因为4可以整除2,6可以整除2和3,8可以整除2和4。
根据上述定义,我们很容易写出判断一个素数是否是素数的代码:
def is_prime_1(x):
if x == 1:
return False
for i in range(2, x):
if x % i == 0:
return False
return True
假设一个正整数a,则其可以被写成任意两个正整数之积,即a = p * q,假设p < q,那么正整数p和q都是a的约数,注意到,如果我们知道p是a的约数,那么可以通过q = a / p快速求得另外一个约数q。所以,我们在判断质数的时候,只需要枚举2到不大于sqrt(a)的正整数即可。
虽然通过上述方法,已经能让我们在根号级别的复杂度内,判断一个正整数是否是素数,但如果我们要判断很多个数是否为素数呢?是否每次都需要枚举int(sqrt(a)+1)个数呢?回到我们最初的起点,我们之所以要枚举这些数,就是想找出原数的约数。然后除1外,任何一个正整数都能写成多个素数的乘积的形式,那么我们枚举特定范围内的所有素数,也能达到相同的效果,而且在判断多个正整数是否是素数的时候,我们只需要枚举更少的质因数与其比较。大家可以看下面不同区间内的素数统计结果:
从上图的统计结果我们可以发现,当区间越来越大,里面的素数个数和区间内所有数字的个数差距也越来越大。所以,我们用区间内的素数,去判断一个整数是不是素数,比较的次数将更少。
而求不超过某个正整数x内的所有素数,有一个著名的算法——埃拉托斯特尼筛法。其算法描述为:
先用一个数组vis,把不大于该正整数x的所有正整数标记为0,表示没有访问;
然后从第一个素数2开始遍历整个区间,如果当前访问的数没有访问过,则可以认为它是一个素数,那么就将它在该区间内所有的倍数全部标记为已访问,这样就保证外部的循环发现的没有访问过的数都是素数。
其具体实现如下述代码所示:
def sieve(x):
vis = [0 for i in range(x+1)]
prime_table = []
for i in range(2, x+1):
if vis[i] == 0:
prime_table.append(i)
for j in range(i*2, x+1, i):
vis[j] = 1
return prime_table
然而,除了上述筛法,还有其他高效的筛法,比如欧拉筛法,这里只给出其代码实现,希望大家能仔细去体会。
def ouler(x):
vis = [0 for i in range(x+1)]
prime_table = []
ln = 0
for num in range(2, x+1):
if vis[num] == 0:
prime_table.append(num)
ln += 1
for j in range(ln):
if num * prime_table[j] > x:
break
vis[num * prime_table[j]] = 1
if num % prime_table[j] == 0:
break
return prime_table
编程要求
根据提示,在右侧编辑器Begin-End区间补充代码,计算并输出指定范围内的所有素数。
本关涉及的代码文件src/step2/is_prime_stu.py,请读者仔细阅读并完成空缺代码的填写。
测试说明
本关的测试文件是src/step2/main.py。
读者将src/step2/is_prime_stu.py中的代码补充完毕,然后点击评测,平台自动编译运行src/step2/main.py,并以标准输入方式提供测评输入;
平台获取程序的输出,然后将其与预期输出对比,如果一致则测试通过;否则测试失败。
平台会对你编写的代码进行测试:
第一行输入正整数n,表示测试样例组数,接下来输入n行,每行输入两个正整数a和b,要求输出a和b之间(包括a和b)所有的素数,保证a<b,且b不超过10^7
测试输入:
2
30,100
999670,1000000
预期输出:
[31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
[999671, 999683, 999721, 999727, 999749, 999763, 999769, 999773, 999809, 999853, 999863, 999883, 999907, 999917, 999931, 999953, 999959, 999961, 999979, 999983]
开始你的任务吧,祝你成功!
参考代码:
class Solution():
def solve(self, l, r):
'''
:type l, r: int
:rtype : list
'''
#请在此添加代码,实现求得[l, r]范围内的所有素数,并将其返回
#********** Begin *********#
from math import sqrt
#通过素数表判断整数是不是素数
def is_prime(x):
if x == 1:
return False
for num in prime_table:
if num * num > x:
return True
if x % num == 0:
return False
#欧拉筛法
def ouler(x):
vis = [0 for i in range(x+1)]
prime_table = []
ln = 0
for num in range(2, x+1):
if vis[num] == 0:
prime_table.append(num)
ln += 1
for j in range(ln):
if num * prime_table[j] > x:
break
vis[num * prime_table[j]] = 1
if num % prime_table[j] == 0:
break
return prime_table
prime_table = ouler(10000)
ans = []
for num in range(l, r+1):
if is_prime(num):
ans.append(num)
return ans
#********** End *********#
第3关:Python对文件的操作
任务描述
本关任务:编写一个能将不同文件中的所有数字,按从小到大的顺序写入新的文件中的小程序。
相关知识
为了完成本关任务,你需要掌握:
Python 如何进行读写文件操作;
Python 内置函数sorted的使用。
Python对文件的读写操作
通常,Python 对文件的操作大致可分为下列三步:
通过open函数打开指定文件,并且获得文件的句柄;
通过上一步的文件句柄,对文件进行读(read)、写(write)操作;
通过文件句柄的close函数关闭文件句柄。
其中,对于open函数,我们至少得知道其前2个参数以及encoding参数的含义(其他参数在生活中使用得并不多,有兴趣的可以查阅相关文档)。
第一个参数是文件路径,这个地方需要注意下使用的是绝对路径还是相对路径;
第二个参数是指明本次操作的模式,常用的可分为“读”、“写”和“读写”3种,分别对应字母r、w和r+(w+)。如果要对文件进行读操作,即指明模式值为r,那么必须保证该文件路径正确(即文件存在),并且禁止程序对该文件进行写操作;如果对文件进行写操作,即指明模式值为w,那么 Python 会打开这样一个文件,并且清空里面的内容,如果不存在,则会自动创建,同时,不允许程序对该文件进行读操作。r+和w+模式虽说既可以进行读操作,又可以进行写操作,但是前者打开后文件内容还在,后者打开文件的同时清空了里面的数据,所以有关w的操作请慎用!如果我们想在文件内容末位添加数据,可以指明模式值为a,其他更多参数可以参考下图。
在Python 3 中,程序执行环境采用的是Unicode编码,而网络上还有诸如UTF-8、ASCII和UTF-16等等编码格式,对于一种编码写入的数据,必须要用同样的编码方式进行解码并读取数据,否则就会出现乱码的情况。一般来说这个参数是可选参数,我们不必刻意去设置,但是当我们有某种需求,特别是爬虫工作者,这个编码可真的是一个要特别注意的问题。
打开文件后,我们即可通过read和write函数对文件进行读写,read函数是一次性将文件中的所有内容都读取出来。但如果文件内容一大,这对计算机可是一个不小的负荷,更何况我们往往一次不需要这么多数据。为解决上述问题,我们可以用readline函数去一行一行地读取文件。读操作还有一个函数readlines,他是将文件所有数据,按行读取出来形成一个list,效果和read一样,不过这里将其按行顺序处理了。
示例程序:
‘’’
假设文件ceshi.txt,内容如下:
python
读写文件
原来可以这样玩
‘’’
#获取文件句柄
f = open(“ceshi.txt”)
#一次性读取文件内容
print(f.read())
#使用完一定要记得关闭句柄
f.close()
示例输出:
python
读写文件
原来可以这样玩
写操作的话,主要通过write函数完成,使用与上述read函数的调用类似,这里不再演示。不过这里可以把需要写的内容,直接作为write函数的参数,传递过去即可。但要注意的是,用写模式打开文件,会清空文件原有的数据!
Python内置函数sorted的使用
给定一个数组,对其按照某种顺序排序,比如将数字从小到大排序,我们很容易写出一个冒泡排序的代码:
ls1 = [1, 5, 4, 3, 2]
def bubble_sort(ls):
for i in range(len(ls)-1):
for j in range(len(ls)-i-1):
if ls[j] > ls[j+1]:
ls[j], ls[j+1] = ls[j+1], ls[j]
return ls
我们知道还有诸如快速排序、堆排序更加快的排序方法,而且书写这么一个排序算法代码量又比较大。这时候我们可以考虑用 Python 中内置的排序函数——sorted函数,我们只需要提供排序关键字的转换函数即可,如我们想对Alice、Bob和qwer这四个字符串按长度大小,从小到大排序,可以这么写:
ls = [‘Alice’, ‘Bob’, ‘qwer’]
def func(key):
return len(key)
print(sorted(ls, key=func))
示例输出:
[‘Bob’, ‘qwer’, ‘Alice’]
如果熟悉lambda表达式的话,简单的排序规则将会表现得更加简洁,如上述代码可以表示为sorted(ls, key=lambda x:len(x))。有关lambda表达式的更多使用,请有兴趣的同学自行学习。
编程要求
根据提示,在右侧编辑器Begin-End区间补充代码,实现将file_1和file_2文件中的数字,按从小到大的顺序排序,并将结果写入file_3文件中。
提示:可以新建空列表,将读取的文件内容通过extend方法,添加到空列表,通过sort排序,然后将列表写入file_3文件。
测试说明
平台会对你编写的代码进行测试:
每次测试输入3行,分别表示file_1文件的路径、file_2文件的路径和file_3文件的路径。
测试输入:
second_task/step4/test_a_1.txt
second_task/step4/test_b_1.txt
second_task/step4/output/out.txt
预期输出(学员只需完成将结果写入文件中的操作即可):
0
1
2
开始你的任务吧,祝你成功!
参考代码:
class Solution():
def solve(self, file_1, file_2, file_3):
'''
:type file_1, file_2, file_3: str
:rtype : None
'''
#请在此添加代码,实现将文件file_1和file_2中的数字按从小到大的顺序,写入文件file_3中
#********** Begin *********#
ls1 = []
with open(file_1, "r") as f:
ls1.extend(list(map(lambda x:int(x), f.readlines())))
with open(file_2, "r") as f:
ls1.extend(list(map(lambda x:int(x), f.readlines())))
ls1.sort()
with open(file_3, "w") as f:
for line in ls1:
f.write(str(line)+'\n')
##********** End *********#
更多推荐
所有评论(0)