做公司网站 需要注意什么,汕尾市住房和城建设局网站,江苏优质网站制作公司,网站建设技术合作合同书一、每日一题
蓝桥杯真题之互质数的个数 我的解法#xff1a;
两个数互质#xff0c;说明两个数的最大公约数是1#xff0c;定义了一个函数判断两个数的最大公约数#xff0c;再在循环中判断#xff0c;并实现计数。可以实现运行#xff0c;缺点是时间复杂度很高#…一、每日一题
蓝桥杯真题之互质数的个数 我的解法
两个数互质说明两个数的最大公约数是1定义了一个函数判断两个数的最大公约数再在循环中判断并实现计数。可以实现运行缺点是时间复杂度很高运行时间慢。
a,b map(int, input().split()) # 实现在一行中输入两个数据
s a ** b
count 0def gcd(m, n): # 定义判断最大公约数的函数while n ! 0:m, n n, m % nreturn mfor i in range(s1): # 在循环中判断这两个数的最大公约数是否为1if gcd(i, s) 1:count 1print(count) # 最后输出结果
二、堆排序的实现
向下调整的实现
有详细的注释但是还是不好理解确实是挺难挺复杂的建议大家是去b站找视频仔细看看讲解并自己动手实践如果我有时间了话会再出详细的图解或者视频。
def sift(li, low, high)::param li: 用列表存放树结构:param low: 堆的根节点位置:param high: 堆的最后一个元素的位置:return:i low # i最开始指向根节点j 2 * i 1 # j最开始指向左孩子tmp li[low] # 将栈顶保存起来while j high: # 循环条件为只要j不越过列表的界if j 1 high and li[j] li[j1]: # 如果右孩子有并且比左孩子大j j1 # 那么把指针指向数字大的右孩子if li[j] tmp:li[i] li[j] # 将i位置赋值为较大的数i j # 并将ij指针向下移动j 2 * i 1else: # 如果tmp更大将tmp放到i的位置上li[i] tmp # 把tmp放到某个子树的根节点上breakelse:li[i] tmp # 把tmp放到叶子节点上堆排序函数
def heap_sort(li):n len(li)for i in range((n-2)//2, -1, -1):# i 表示建堆的时候调整的堆的下标sift(li, i, i-1)# 建堆完成了for i in range(n-1, -1, -1):# i指向当前堆的最后一个元素li[0], li[i] li[i], li[0]sift(li, 0, i-1) # i-1是新的high
实现过程真的不好写不好理解多加练习
