贪吃蛇在𝑛×𝑛(1≤𝑛≤10)的方阵中游走，它可以往上下左右四个方向游走，当穿越方阵的边界时还可以从该边界的对立面继续进入方阵。初始时你可以任意安排贪吃蛇的起点位置，并且选择一个方向一直走𝑛步。方阵中“.”表示空位置，数字表示可以吃的食物，每吃到一个数字时，这个数字便会附着到贪吃蛇的尾部，同时方阵中该数字会消失。问：在某个时刻，贪吃蛇身上会不会出现我们想要的某个整数；若有，会有多少个数会小于该整数。例如，在右侧5×5的方阵中可以产生[1,3,4,12,21,234,243,324,342,423,432]共11个数。其中数“234”的产生过程可以是：选择第4行第2列为起点，第一步吃掉2，接着往右走三步吃掉3，再往右走一步穿越到对面的4，吃掉它成为“234”，共五步。其中“1234”或“123”等整数是不可能出现的。请回答以下问题。

0 返回首页

1. 贪吃蛇在𝑛×𝑛(1≤𝑛≤10)的方阵中游走，它可以往上下左右四个方向游走，当穿越方阵的边界时还可以从该边界的对立面继续进入方阵。初始时你可以任意安排贪吃蛇的起点位置，并且选择一个方向一直走𝑛步。方阵中“.”表示空位置，数字表示可以吃的食物，每吃到一个数字时，这个数字便会附着到贪吃蛇的尾部，同时方阵中该数字会消失。问：在某个时刻，贪吃蛇身上会不会出现我们想要的某个整数；若有，会有多少个数会小于该整数。

例如，在右侧5×5的方阵中可以产生[1,3,4,12,21,234,243,324,342,423,432]共11个数。其中数“234”的产生过程可以是：选择第4行第2列为起点，第一步吃掉2，接着往右走三步吃掉3，再往右走一步穿越到对面的4，吃掉它成为“234”，共五步。其中“1234”或“123”等整数是不可能出现的。

请回答以下问题。

(1) 输入方阵保存至数组𝑎，然后将贪吃蛇所有可能吃到的所有数字组合保存到数组𝑏中，请补充完该算法程序。

dx = [0, 1, 0, -1] # 模拟贪吃蛇往四个方向游走时行号变化的数组

dy = [1, 0, -1, 0] # 列号变化数组

n = int(input()) # 方阵的大小

a, b = [], []

for i in range(n):

s = input().strip().split() #方阵中的一行数据，“.”号和数字字符都以空格分隔

a.append(s)

def calc(i, j, p):

x, y, res = i, j, 0

if '0' <= a[x][y] <= '9':

res = int(a[x][y])

for i in range(n-1):

x = # 产生新的行号

y = # 产生新的列号（与行号类似），代码略

if '0' <= a[x][y] <= '9':

res = res * 10 + int(a[x][y])

return res

for i in range(n):

for j in range(n):

for k in range(4):

num =

if num > 0:

b.append(num)

print(b) # 输出所有可能能产生的整数（可能会产生重复的整数）

(2) 若数组 a= [['.', '1', '.'], ['.', '2', '3'], ['.', '.', '.']]，上述程序处理完后𝑏数组中（选填：存在 / 不存在）整数2。

(3) 对𝑏数组中的所有整数进行升序排序，输入待查找的数据，输出小于等于该数字的数有多少个。请补充完该算法程序。

b = [1, 12, 23, 23, 23, 35, 35,146]

输入输出示例：

请输入待查找的整数：23

小于等于23的数共有5个

请输入待查找的整数：31

小于等于31的数共有5个

bn = len(b)

for i in range(bn-1):

for j in range( ):

if b[j] > b[j+1]:

b[j], b[j+1] = b[j+1], b[j]

key = int(input("请输入待查找的整数："))

i, j = 0, bn-1

while i <= j:

m = (i + j) // 2

if :

i = m + 1

else:

j = m - 1

print("小于等于", key, "的数共有", i, "个")

【考点】

过程与自定义函数; 排序算法及程序实现; 查找算法及程序实现;

【答案】

您现在未登录，无法查看试题答案与解析。登录

综合题困难

1. 某项活动有n个单位（编号1到n）参加，需将员工分成若干个小组，每个小组的人数上限为m，小组编号按新建次序从1开始编号。分组时，首先按单位编号次序依次在各单位内部分分组，每m人分配到一个新建小组中，不足m人的剩余员工暂不分配；然后按剩余员工人数由大到小的顺序，依次为各单位剩余员工分配小组。

若某单位剩余员工人数为k，则分配方法为：在已建的小组中查找空位数（该小组还可容纳的人数）大于或等于k的小组，如果找到的小组有多个，则选择空位数最少的小组，将此k人分配到该小组中；如果没有找到，则新建一个小组，将此k人分配到该小组中。

设n为5，m为20，各单位员工人数及单位内部的分组过程如图a所示，各单位剩余员工的分组过程如图b所示。

编写程序：给定各单位编号及员工人数，根据上述方法进行分组处理，按单位编号次序输出各单位所分配的分组编号。请回答下列问题：

(1) 由题意可知，若仅将图a中1号单位的员工人数修改为25，然后对图中5个单位重新分组，则1号单位所分配的分组编号为。

(2) 定义如下bubble_sort(lst)函数，参数lst的每个元素由单位编号和剩余员工人数2个数据项组成。函数的功能是根据每个单位的剩余员工人数，对lst进行降序排序。

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]数值最大

②虚线框中的程序段执行的次数为。

(3) 实现分组功能的部分 Python 程序如下，程序中用到的列表函数与方法如图 c 所示，请在程序中划线处填入合适的代码。

函数与方法	功能
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)

综合题困难

2. 小胡公司组织四人制篮球赛（2人对2人），现已报名n（n为偶数）人，根据这n人个人篮球赛成绩降序排序后存于单向链表a中，为使每队实力尽量均衡，将a中第1人和最后一人组队，第2人和倒数第2人组队，以此类推。例如有6名编号为T01、T02、T03、T04、T05、T06的队员报名参赛，按个人篮球赛成绩降序排序后的次序为：T05、T06、T02、T03、T04、T01，经过分组后分组情况如下图所示：

具体算法为：

⑴找到链表的中点

⑵将链表的右半段反转

⑶将链表左半段和反转后的右半段合并

⑷按顺序输出每组队员编号

小胡编写程序实现将这n人进行分组并输出每组队员编号，请在划线处填入合适的代码。

# 找到原链表的中点

def middleNode(head):

slow = fast = head

while a[fast][1] != -1 and a[a[fast][1]][1] != -1:

slow =

fast = a[a[fast][1]][1]

return slow

# 将原链表的右半段反转

def reverseList(head):

pre = -1

cur = head

while cur != -1:

nextTemp = a[cur][1]

a[cur][1] = pre

cur = nextTemp

return pre

# 将原链表的两段合并

def mergeList(h1, h2):

while h1 != -1 and h2 != -1:

h1_tmp = a[h1][1]

h2_tmp = a[h2][1]

h1 = h1_tmp

a[h2][1] = h1

h2 = h2_tmp

# 输出分组情况

def show():

head = 0

i = 0

print('分组情况：')

while head != -1:

if i % 2 == 0:

print('第', , '组：', a[head][0], '和 ', end='')

else:

print(a[head][0])

i += 1

head = a[head][1]

# 读入n人编号，并按个人篮球赛成绩降序排序后依次将编号存入a中并输出a（代码略）

mid = middleNode(0)

head1 = 0

head2 = a[mid][1]

head2 = reverseList(head2)

mergeList(head1, head2)

show()

综合题困难

3. 小明所在的班级共有 20 名男生，要参加学校举办的拔河比赛，赛前根据体重分成 AB 两组进行训练，要求每组 10 人，且每组男生的体重之和尽量接近。小明设计了如下算法：

①初步分组：将所有男生按体重从高到低排序，并以 ABAB…进行初步分组；

②计算体重差：计算每组对应两个男生的体重差；

③交换学生：按体重差从高到低判断是否交换学生。

例如 20 名男生的体重(单位： kg)从高到低为：

95, 93, 93, 90, 90, 90, 84, 83, 83, 78, 77, 75, 74, 69, 64, 61, 61, 60, 56, 55。

步骤		体重											体重和
初步分组	A 组	95	93	90	84	83	77	74	64	61	56	777
初步分组	B 组	93	90	90	83	78	75	69	61	60	55	754
体重差		2	3	0	1	5	2	5	3	1	1	23
交换学生		否	否	否	是	是	否	是	否	否	否
最终分组	A 组	95	93	90	83	78	77	69	64	61	56	766
最终分组	B 组	93	90	90	84	83	75	74	61	60	55	765

小明按照以上算法编写Python程序如下，请在划线处填入合适的代码。

def group(student): #初步分组

a=[];b=[]

i=0

while i<len(student):

a.append(student[i])

b.append(student[i+1])

return a,b

def cal_diff(a,b): #计算体重差并降序排序

d=[]

for i in range(len(a)):

d.append([i,a[i]-b[i]])

for i in range(len(d)-1):

for j in range(0,len(d)-i-1):

if :

d[j],d[j+1]=d[j+1],d[j]

return d

def change(d,a,b): #标记是否交换

k=(sum(a)-sum(b))//2

f=[0]*len(d)

ssum=0

for i in range(len(d)):

ssum+=d[i][1]

if ssum>k:

ssum-=d[i][1]

else:

if ssum==k:

break

return f

student=[95, 93, 93, 90, 90, 90, 84, 83, 83, 78, 77, 75, 74, 69, 64, 61, 61, 60, 56, 55]

qA,qB=group(student)

print("初步分组后 A 组体重： ",qA,"和为：",sum(qA))

print("初步分组后 B 组体重： ",qB,"和为：",sum(qB))

diff=cal_diff(qA,qB)

flag=

for i in range(len(flag)): #交换

if flag[i]==1:

qA[i],qB[i]=qB[i],qA[i]

print("交换后 A 组体重：",qA,"和为：",sum(qA))

print("交换后 B 组体重：",qB,"和为： ",sum(qB))

综合题普通