Python基础之综合练习⼀
第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）。
免备案空间
excel自动排名函数如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
python基础代码练习
预期输出：
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 Falsemesh函数matlab
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 = []
split名词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 *********#

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。