[已解决]鱼C论坛python精英挑战赛（04期）

jerryxjr1220

由于论坛遭恶意攻击导致上次发布的挑战帖丢失，现在重新发布挑战。
截止日期：延长至7月3日24时
挑战评选规则：解题正确，运算效率高，代码简洁优雅。
优胜者奖励100鱼币，为了鼓励新人参赛，本次评选将从普通鱼油中产生，版主和管理员不计算在内。

本期题目：回型矩阵的质数邻居
定义n x m的回型矩阵是按数字（1 ~ n*m）从小到大按顺时针旋转排列后得到的二维矩阵。
例如，在4x4的回型矩阵中，其分布如下：
  1   2   3   4
12 13 14  5
11 16 15  6
10   9   8   7

矩阵中的数字i的8个方位的邻近数字，我们称作i的“数字邻居”。当然，在矩阵四周的数的数字邻居不足8个。
例如，在4x4的矩阵中，当i=14时，i的数字邻居有2,3,4,5,6,13,15,16，其中质数有4个数，分别是2,3,5,13。i=14是所有的16个数字中质数邻居最多的数。
现在给定n（表示行数）和m（表示列数），求哪个数字拥有的质数邻居最多？它有多少个质数邻居？如果有多个数字，选取数字最小的那个。
n和m的取值范围：1<=n, m<=100。特例，当m=n=1时，矩阵中仅有数字1，它的质数邻居的个数是0。

@SixPy @冬雪雪冬 @～风介～

最佳答案

月排行榜 / 总排行榜

wangzhenas

2017-6-30 08:18:16

参与一下
可以通过改文件头部col， row计算其他情况

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Sat Jul  1 23:25:32 2017
   
4. 
   
5. @author: wangz
   
6. """
   
7. 
   
8. row, col = 30, 15
   
9. 
   
10. #code to generate a dict to indicate if a number is prime
    
11. primes_dict = {i:True for i in range(1,col*row+1)}
    
12. primes_dict[1] = False
    
13. for fac in range(2,col*row//2+1):
    
14.     if primes_dict[fac]:
    
15.         i = 2
    
16.         while i*fac <= col*row:
    
17.             primes_dict[i*fac], i = False, i+1
    
18. 
    
19. #function to generate the matrix
    
20. def make_matrix(max_row, max_col):
    
21.     directions = [(0,1),(1,0),(0,-1),(-1,0)]
    
22.     matrix = [[0 for i in range(max_col)] for i in range(max_row)]
    
23.     acc_pos, acc_num, acc_dir =(0,0),1,directions[0]
    
24. 
    
25.     while True:
    
26.         matrix[acc_pos[0]][acc_pos[1]], next_dir = acc_num, acc_dir   
    
27. 
    
28.         while True:
    
29.             next_row, next_col = acc_pos[0]+next_dir[0], acc_pos[1]+next_dir[1]
    
30.             if next_col in range(max_col) and next_row in range(max_row):
    
31.                 if matrix[next_row][next_col] == 0:
    
32.                     acc_pos, acc_num, acc_dir =(next_row,next_col),acc_num+1,next_dir
    
33.                     break
    
34.                                     
    
35.             next_dir = directions[(directions.index(next_dir) + 1)%4]
    
36.             if next_dir == acc_dir:
    
37.                 return matrix        
    
38. 
    
39. def check_matrix(max_row=row, max_col=col):
    
40.     matrix = make_matrix(max_row, max_col)
    
41.     check_result = dict()
    
42.     for col in range(1,max_col-1):
    
43.         for row in range(1, max_row-1):
    
44.             numbers = matrix[row-1][col-1:col+2] +\
    
45.                       matrix[row][col-1:col+2:2] +\
    
46.                       matrix[row+1][col-1:col+2]
    
47.             nearby_prime_numbers = len(list(filter(lambda n: primes_dict[n], numbers)))
    
48.             if nearby_prime_numbers not in check_result:
    
49.                 check_result.update({nearby_prime_numbers:[matrix[row][col]]})
    
50.             else:
    
51.                 check_result[nearby_prime_numbers].append(matrix[row][col])
    
52.     return check_result
    
53. 
    
54. result = check_matrix()
    
55. print("Answer is {} with {} primes nearby".format(min(result[max(result)]), max(result)))
    

复制代码

跳转到最佳答案楼层

wangzhenas

参与一下
可以通过改文件头部col， row计算其他情况

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Sat Jul  1 23:25:32 2017
   
4. 
   
5. @author: wangz
   
6. """
   
7. 
   
8. row, col = 30, 15
   
9. 
   
10. #code to generate a dict to indicate if a number is prime
    
11. primes_dict = {i:True for i in range(1,col*row+1)}
    
12. primes_dict[1] = False
    
13. for fac in range(2,col*row//2+1):
    
14.     if primes_dict[fac]:
    
15.         i = 2
    
16.         while i*fac <= col*row:
    
17.             primes_dict[i*fac], i = False, i+1
    
18. 
    
19. #function to generate the matrix
    
20. def make_matrix(max_row, max_col):
    
21.     directions = [(0,1),(1,0),(0,-1),(-1,0)]
    
22.     matrix = [[0 for i in range(max_col)] for i in range(max_row)]
    
23.     acc_pos, acc_num, acc_dir =(0,0),1,directions[0]
    
24. 
    
25.     while True:
    
26.         matrix[acc_pos[0]][acc_pos[1]], next_dir = acc_num, acc_dir   
    
27. 
    
28.         while True:
    
29.             next_row, next_col = acc_pos[0]+next_dir[0], acc_pos[1]+next_dir[1]
    
30.             if next_col in range(max_col) and next_row in range(max_row):
    
31.                 if matrix[next_row][next_col] == 0:
    
32.                     acc_pos, acc_num, acc_dir =(next_row,next_col),acc_num+1,next_dir
    
33.                     break
    
34.                                     
    
35.             next_dir = directions[(directions.index(next_dir) + 1)%4]
    
36.             if next_dir == acc_dir:
    
37.                 return matrix        
    
38. 
    
39. def check_matrix(max_row=row, max_col=col):
    
40.     matrix = make_matrix(max_row, max_col)
    
41.     check_result = dict()
    
42.     for col in range(1,max_col-1):
    
43.         for row in range(1, max_row-1):
    
44.             numbers = matrix[row-1][col-1:col+2] +\
    
45.                       matrix[row][col-1:col+2:2] +\
    
46.                       matrix[row+1][col-1:col+2]
    
47.             nearby_prime_numbers = len(list(filter(lambda n: primes_dict[n], numbers)))
    
48.             if nearby_prime_numbers not in check_result:
    
49.                 check_result.update({nearby_prime_numbers:[matrix[row][col]]})
    
50.             else:
    
51.                 check_result[nearby_prime_numbers].append(matrix[row][col])
    
52.     return check_result
    
53. 
    
54. result = check_matrix()
    
55. print("Answer is {} with {} primes nearby".format(min(result[max(result)]), max(result)))
    

复制代码

WelanceLee

1. 
   
2. def p_m(n, m):
   
3.     matrix = [[0 for _ in range(m)] for _ in range(n)]
   
4.     ## bound
   
5.     i = 1
   
6.     ul = 0
   
7.     uh = m
   
8.     rl = 1
   
9.     rh = n
   
10.     dl = 0
    
11.     dh = m-1
    
12.     ll = 1
    
13.     lh = n-1
    
14.     while i <= m*n:
    
15.         for r in range(ul, uh):
    
16.             matrix[ll-1][r] = i
    
17.             i += 1
    
18.         if i > m*n:
    
19.             break
    
20.         ul += 1
    
21.         uh -= 1
    
22.         for d in range(rl, rh):
    
23.             matrix[d][uh] = i
    
24.             i += 1
    
25.         if i > m*n:
    
26.             break
    
27.         rl += 1
    
28.         rh -= 1
    
29.         for l in range(dh-1, dl-1, -1):
    
30.             matrix[rh][l] = i
    
31.             i += 1
    
32.         if i > m*n:
    
33.             break
    
34.         dl += 1
    
35.         dh -= 1
    
36.         for u in range(lh-1, ll-1, -1):
    
37.             matrix[u][dl-1] = i
    
38.             i += 1
    
39.         if i > m*n:
    
40.             break
    
41.         ll += 1
    
42.         lh -= 1
    
43.     return matrix
    
44. 
    
45. def pprint(x):
    
46.     for each in x:
    
47.         print(each)
    
48. 
    
49. ## get prime list
    
50. def p(n):
    
51.     p = [True for i in range(n+1)]
    
52.     p[:2] = [False, False]
    
53.     for i in range(2, n+1):
    
54.         if p[i]:
    
55.             for j in range(i**2, n+1, i):
    
56.                 p[j] = False
    
57.     primes = [i for i in range(n+1) if p[i]]
    
58.     return primes
    
59. 
    
60. ## judge number of primes
    
61. def f(x, y):
    
62.     a = 0
    
63.     for each in around:
    
64.         nx = x + each[0]
    
65.         ny = y + each[1]
    
66.         if -1 < nx < n and -1 < ny < m and matrix[nx][ny] in l:
    
67.             a += 1
    
68.     return a
    
69. 
    
70. n = int(input('input the numeber of rows: '))
    
71. m = int(input('input the number of columns: '))
    
72. l = p(n*m)
    
73. matrix = p_m(n, m)
    
74. around = [(-1,-1), (0,-1), (1,-1), (-1, 0), (1,0), (-1,1), (0,1), (1,1)]
    
75. mmax = 0
    
76. num = 1
    
77. for i in range(n):
    
78.     for j in range(m):
    
79.         if f(i, j) > mmax:
    
80.             num = matrix[i][j]
    
81.             mmax = f(i, j)
    
82.         if f(i, j) == mmax and num > matrix[i][j]:
    
83.             num = matrix[i][j]      
    
84. print(num, mmax)
    

复制代码

达锅

1. import time
   
2. 
   
3. 
   
4. def isin(n,m):
   
5.     return jz[n][m] if 0<=n<r and 0<=m<c and jz[n][m] in zs else 0
   
6. 
   
7. def lg(n,m):#测试周围8个数是否是质数
   
8.     q= set((isin(n-1,m-1),isin(n-1,m),isin(n-1,m+1),isin(n,m-1),isin(n,m+1),isin(n+1,m-1),isin(n+1,m),isin(n+1,m+1)))
   
9.     if 0 in q :#移除0
   
10.         q.remove(0)
    
11.     return q
    
12. 
    
13. 
    
14. while True:#循环测试
    
15.    
    
16.     te=input('请输入行(空格)列').split()
    
17.     tt=time.time()
    
18.    
    
19.     if te=='0' or len(te)!=2:break
    
20.    
    
21.     r,c=[int(i) for i in te]#输入矩阵行列
    
22. 
    
23.     zs=[0,0]+[1]*(r*c-2)#生成质数列表
    
24.     for i,j in enumerate(zs):
    
25.         if j:
    
26.             for k in range(i*i,r*c,i):
    
27.                 zs[k]=0
    
28.     zs=set([i for i,j in enumerate(zs) if j])
    
29. 
    
30.     jz=[[0]*c for j in range(r)]#生成矩阵
    
31.     m,n,fx,x=0,0,0,0
    
32.     while x<r*c:
    
33.         x+=1
    
34.         jz[m][n]=x
    
35.         if fx==0:#向右
    
36.             if n+1==c or jz[m][n+1]!=0:
    
37.                 m,n,fx=m+1,n,1#向下
    
38.             else:
    
39.                 m,n,fx=m,n+1,0#向右
    
40.         elif fx==1:#向下
    
41.             if m+1==r or jz[m+1][n]!=0:
    
42.                 m,n,fx=m,n-1,2#向左
    
43.             else:
    
44.                 m,n,fx=m+1,n,1#向下
    
45.         elif fx==2:#向左
    
46.             if n==0 or jz[m][n-1]!=0:
    
47.                 m,n,fx=m-1,n,3#向上
    
48.             else:
    
49.                 m,n,fx=m,n-1,2#向左
    
50.         elif fx==3:#向上
    
51.             if m==0 or jz[m-1][n]!=0:
    
52.                 m,n,fx=m,n+1,0#向右
    
53.             else:
    
54.                 m,n,fx=m-1,n,3#向上
    
55. 
    
56. 
    
57.     if  c<=30:
    
58.         t=""
    
59.         y=""
    
60.         for i in jz:
    
61.             for j in i:
    
62.                 t+='%4d ' % j
    
63.                 y+='%4d ' % j if j in zs else '%4d ' % 0
    
64.             t+='\n'
    
65.             y+='\n'
    
66.         print(t)
    
67.         print(y)
    
68. 
    
69.     minn=[0,0,0]#
    
70.     for i in range(r):
    
71.         for j in range(c):
    
72.             ls=lg(i,j)#邻居，返回所有质数邻居
    
73.             if (jz[i][j]<minn[0] and len(ls)==minn[1]) or len(ls)>minn[1] or i==j==0:
    
74.                 minn[0],minn[1],minn[2]=jz[i][j],len(ls),list(ls)
    
75.     minn[2]=0 if minn[2]==[]  else minn[2]
    
76.     print('数字%s有%s个质数邻居，分别是%s' % (minn[0],minn[1],minn[2]))
    
77.     print(time.time()-tt)

复制代码

请输入行(空格)列1 1
   1

   0

数字1有0个质数邻居，分别是0
0.031193256378173828
请输入行(空格)列2 2
   1    2
   4    3

   0    2
   0    3

数字1有2个质数邻居，分别是[2, 3]
0.021895408630371094
请输入行(空格)列50 50
数字198有4个质数邻居，分别是[2, 3, 197, 199]
0.012151479721069336
请输入行(空格)列100 100
数字1237有4个质数邻居，分别是[1607, 1609, 857, 859]
0.11562013626098633
请输入行(空格)列

不明白测试数据是随机给出，还是要把n从1-100，m从1-100所有的矩阵统计出来

sky

python学了好几年，最近刚好不进入状态，没几天又卡住了，来做做任务：
变量名不会取名，把鸣人的姓拿来用了
能实现功能就已经很开心了

上代码

1. #!/usr/bin/python
   
2. # -*- coding: UTF-8 -*-
   
3. __author__ = "Sigai"
   
4. 
   
5. import itertools, math
   
6. from operator import itemgetter
   
7. 
   
8. 
   
9. def spiral(n, m):
   
10.     _status = itertools.cycle(['right', 'down', 'left', 'up'])  # 用于状态周期性的切换
    
11.     _movemap = {
    
12.         'right': (1, 0),
    
13.         'down': (0, 1),
    
14.         'left': (-1, 0),
    
15.         'up': (0, -1),
    
16.     }
    
17.     pos2no = dict.fromkeys([(x, y) for x in range(n) for y in range(m)])  # 生成字典键值是向量元组
    
18.     _pos = (0, 0)
    
19.     _st = next(_status)
    
20.     for i in range(1, n * m + 1):
    
21.         _oldpos = _pos
    
22.         _pos = tuple(map(sum, zip(_pos, _movemap[_st])))  # 根据状态进行移动
    
23.         if (_pos not in pos2no) or (pos2no[_pos]):  # 当超出范围或遇到障碍时切换方向
    
24.             _st = next(_status)
    
25.             _pos = tuple(map(sum, zip(_oldpos, _movemap[_st])))
    
26.         pos2no[_oldpos] = i
    
27.     return pos2no
    
28. 
    
29. 
    
30. def prime(n):
    
31.     if n is None:
    
32.         return False
    
33.     if n % 2 == 0:
    
34.         return n == 2
    
35.     if n % 3 == 0:
    
36.         return n == 3
    
37.     if n % 5 == 0:
    
38.         return n == 5
    
39.     for p in range(7, int(math.sqrt(n)) + 1, 2):  # 只考虑奇数作为可能因子
    
40.         if n % p == 0:
    
41.             return False
    
42.     return True
    
43. 
    
44. 
    
45. class Uzimaki(object):
    
46.     def __init__(self, n, m):
    
47.         self.n = n
    
48.         self.m = m
    
49.         self.spiral = spiral(self.n, self.m)
    
50. 
    
51.     def display_spiral(self):
    
52.         pos2no = spiral(self.n, self.m)
    
53.         for i in range(self.m):
    
54.             for j in range(self.n):
    
55.                 print(pos2no[(j, i)], end='\t', )
    
56.             print('\n')
    
57.         print('-' * 5 * self.n)
    
58. 
    
59.     def neighbors(self, n):
    
60.         # print(self.spiral)
    
61.         n_pos = {v: (x, y) for (x, y), v in self.spiral.items()}[n]
    
62.         nbs_pos = [(x, y) for x in [-1, 0, 1] for y in [-1, 0, 1] if x != 0 or y != 0]
    
63.         nbs = []
    
64.         for x, y in nbs_pos:
    
65.             nbs.append(self.spiral.get((n_pos[0] + x, n_pos[1] + y), None))
    
66.         result = list(set(nbs))
    
67.         # print(result)
    
68.         return result
    
69. 
    
70.     def get_prime_neighbors(self, n):
    
71.         tmp = []
    
72.         for i in self.neighbors(n):
    
73.             if prime(i):
    
74.                 tmp.append(i)
    
75.         # print(tmp)
    
76.         return tmp
    
77. 
    
78.     def get_most_prime_neighbors(self):
    
79.         rank = []
    
80.         for i in range(1, self.n * self.m):
    
81.             rank.append((i, len(self.get_prime_neighbors(i))))
    
82.         rank = sorted(rank, key=itemgetter(1), reverse=True)
    
83.         print("在给定%d行和%d列的螺旋矩阵中，%d拥有的质数邻居最多,它有%d个质数邻居."%(self.n,self.m,rank[0][0],rank[0][1]))
    
84.         return rank[0]
    
85. 
    
86. 
    
87. Uzimaki(4, 4).display_spiral()
    
88. Uzimaki(4, 4).neighbors(14)
    
89. Uzimaki(4, 4).get_prime_neighbors(14)
    
90. Uzimaki(4, 4).get_most_prime_neighbors()
    

复制代码

达锅

抗议，最佳答案在输入行列小于3的时候出错

wangzhenas

达锅 发表于 2017-7-3 00:19
抗议，最佳答案在输入行列小于3的时候出错

好吧 木有注意这一点，可以在check函数里面先判断一下初始值
不过小于3的时候这个题的前提条件也不成立啊。。没有8个相邻的数

达锅

wangzhenas 发表于 2017-7-3 02:40
好吧 木有注意这一点，可以在check函数里面先判断一下初始值
不过小于3的时候这个题的前提条 ...

当然，在矩阵四周的数的数字邻居不足8个。

题目原话

jerryxjr1220

达锅 发表于 2017-7-3 00:19
抗议，最佳答案在输入行列小于3的时候出错

确实，是我疏忽了，我再补你100鱼币，你们的程序都不错，并列获胜吧！
请到这个帖子下回复，补充领奖！http://bbs.fishc.com/thread-90068-1-1.html

达锅

jerryxjr1220 发表于 2017-7-3 08:58
确实，是我疏忽了，我再补你100鱼币，你们的程序都不错，并列获胜吧！
请到这个帖子下回复，补充领奖 ...

我也要继续努力

q960126

鱼币怎么得啊