若某单位剩余员工人数为k,则分配方法为:在已建的小组中查找空位数(该小组还可容纳的人数)大于或等于k的小组,如果找到的小组有多个,则选择空位数最少的小组,将此k人分配到该小组中;如果没有找到,则新建一个小组,将此k人分配到该小组中。
设n为5,m为20,各单位员工人数及单位内部的分组过程如图a所示,各单位剩余员工的分组过程如图b所示。
编写程序:给定各单位编号及员工人数,根据上述方法进行分组处理,按单位编号次序输出各单位所分配的分组编号。请回答下列问题:
def bubble_sort(lst):
n=len(lst)
for i in range(0, n-1):
return
调用该函数,若 lst 为[[1,0],[2,0],[3,18],[4,0],[5,19],[6,17]],请回答①和②两个问题。
①虚线框中的程序段第 1 次执行后,关于 lst 中的剩余员工人数,下列说法正确的是(单选,填字母)。
A.lst[0][1]数值最小 B.lst[0][1]数值最大
C.lst[5][1]数值最小 D.lst[5][1]数值最大
②虚线框中的程序段执行的次数为。
函数与方法 | 功能 |
w.append(x) | 在列表 w 末尾添加元素 x |
x.w.pop() | 将列表 w 末尾元素赋值给 x,并将其从 w 中删除 |
def group(data, m):
n=len(data)
a=[]
for i in range(n+1):
a.append([]) # a[i]初始化为空列表,存放编号为 i 的单位所分配的分组编号
gnum=0
for i in range(n): #各单位内部分组
while data[i][1]>=m:
gnum+=1
k=data[i][0]
a[k].append(gnum)
bubble_sort(data) #根据每个单位的剩余员工人数,对 data 进行降序排序
b=[]
for i in range(m):
b.append([])
i=0 #对剩余员工分组
while i<n and data[i][1]!=0:
while j<m and len(b[j])==0:
j+=1
if j<m:
v=b[j].pop()
else:
gnum+=1
v=gnum
a[data[i][0]].append(v)
i+=1
#输出各单位的分组编号,代码略
'''
读取小组人数上限存入 m;读取 1 至 n 号单位的数据,依次存入列表 data 的 data[0]至 data[n-1]中。
Data[i]包含 2 个数据项,data[i][0],data[i][1]分别存放单位编号及员工人数,代码略
'''
group(lst, m)
图 a | 图 b |
t=h
p=d[h][1]
while p != -1 :
q=d[p][1]
p=q
d[t][-1]=-1
d[q][1]=p
d[t][1]=q
else:
d[h][1]=q
h=p
B . if d[p][0]>0:d[t][1]=q
t=q
else:
h=p
d[p][1]=t
C . if d[p][0]>0:d[t][1]=p
t=p
else:
d[p][1]=h
h=p
D . if d[p][0]>0:d[t][1]=q
d[q][1]=p
else:
d[p][1]=h
h=q
第一步:将经纬度转换为二进制
编码规则为:先将纬度范围(-90, 90)平分成两个区间(-90, 0)和(0, 90),如果目标维度位于前一个区间,则编码为 0,否则编码为 1,然后根据目标纬度所落的区间再平均分成两个区间进行编码,以此类推,直到精度满足要求,经度也用同样的算法。
序号 | 纬度范围 | 划分区间0 | 划分区间1 | 31.192932所属区间 |
1 | (-90,90) | (-90,0) | (0,90) | 1 |
2 | (0,90) | (0,45) | (45,90) | 0 |
3 | (0,45.0) | (0,22.5) | (22.5,45.0) | 1 |
4 | (22.5,45.0) | (22.5,33.75) | (33.75,45.0) | 0 |
5 | (22.5,33.75) | (22.5,28.125) | (28.125,33.75) | 1 |
…… | …… | …… | …… | …… |
最后得到纬度的二进制编码为:101011000101110, 用同样的方式可以得到经度(121.43737)的二进制编码:110101100101101
第二步:将经纬度的二进制编码合并,从偶数 0 开始,经度占偶数位,纬度占奇数位。经度
110101100101101,纬度 101011000101110,得到的二进制编码为:111001100111100000110011110110
偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | … | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | 偶 | 奇 | |
索引 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | … | 12 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
经纬度 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | … | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
第三步:将合并后的二进制数做 Base32 编码
按照每 5 位一组,分成 6 组,每组计算其对应的十进制数值,按照 Base32 表进行编码。
11100 11001 11100 00011 00111 10110 转换成十进制是 28 25 28 3 7 22,查表编码得到最终结果,wtw37q。
林老师想编写一个 Python 程序,输入编码后的字符串,输出该编码对应的经纬度范围,运行结果如图 a 所示:
图a |
def qj(l,r,a): #将二进制 a 转成对应的经纬度范围#该代码省略
def find(c): #在 base32 表中查找对应的十进制数
for i in :
if base32[i]==c:
return i base32="0123456789bcdefghjkmnpqrstuvwxyz" s=input("请输入编码:")
res="" jd=[]
wd=[]
for i in range(len(s)):
ans=""
j=0
while:
ans=
n=n//2
j+=1
res=res+ans
for i in range(len(res)):
if i%2==0:
jd+=res[i]
else:
wd+=res[i]
print("经度对应的二进制:",jd,"纬度对应的二进制:",wd)
print("经度范围:",qj(-180,180,jd),"纬度范围:",qj(-90,90,wd))