鱼C论坛

 找回密码
 立即注册
查看: 2975|回复: 10

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

[复制链接]
发表于 2017-6-30 08:18:15 | 显示全部楼层 |阅读模式
100鱼币
本帖最后由 jerryxjr1220 于 2017-7-2 20:54 编辑

由于论坛遭恶意攻击导致上次发布的挑战帖丢失,现在重新发布挑战。
截止日期:延长至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 @冬雪雪冬 @~风介~
最佳答案
2017-6-30 08:18:16
本帖最后由 wangzhenas 于 2017-7-2 06:17 编辑

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

  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Sat Jul  1 23:25:32 2017

  4. @author: wangz
  5. """

  6. row, col = 30, 15

  7. #code to generate a dict to indicate if a number is prime
  8. primes_dict = {i:True for i in range(1,col*row+1)}
  9. primes_dict[1] = False
  10. for fac in range(2,col*row//2+1):
  11.     if primes_dict[fac]:
  12.         i = 2
  13.         while i*fac <= col*row:
  14.             primes_dict[i*fac], i = False, i+1

  15. #function to generate the matrix
  16. def make_matrix(max_row, max_col):
  17.     directions = [(0,1),(1,0),(0,-1),(-1,0)]
  18.     matrix = [[0 for i in range(max_col)] for i in range(max_row)]
  19.     acc_pos, acc_num, acc_dir =(0,0),1,directions[0]

  20.     while True:
  21.         matrix[acc_pos[0]][acc_pos[1]], next_dir = acc_num, acc_dir   

  22.         while True:
  23.             next_row, next_col = acc_pos[0]+next_dir[0], acc_pos[1]+next_dir[1]
  24.             if next_col in range(max_col) and next_row in range(max_row):
  25.                 if matrix[next_row][next_col] == 0:
  26.                     acc_pos, acc_num, acc_dir =(next_row,next_col),acc_num+1,next_dir
  27.                     break
  28.                                     
  29.             next_dir = directions[(directions.index(next_dir) + 1)%4]
  30.             if next_dir == acc_dir:
  31.                 return matrix        

  32. def check_matrix(max_row=row, max_col=col):
  33.     matrix = make_matrix(max_row, max_col)
  34.     check_result = dict()
  35.     for col in range(1,max_col-1):
  36.         for row in range(1, max_row-1):
  37.             numbers = matrix[row-1][col-1:col+2] +\
  38.                       matrix[row][col-1:col+2:2] +\
  39.                       matrix[row+1][col-1:col+2]
  40.             nearby_prime_numbers = len(list(filter(lambda n: primes_dict[n], numbers)))
  41.             if nearby_prime_numbers not in check_result:
  42.                 check_result.update({nearby_prime_numbers:[matrix[row][col]]})
  43.             else:
  44.                 check_result[nearby_prime_numbers].append(matrix[row][col])
  45.     return check_result

  46. result = check_matrix()
  47. print("Answer is {} with {} primes nearby".format(min(result[max(result)]), max(result)))
复制代码

最佳答案

查看完整内容

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

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-6-30 08:18:16 | 显示全部楼层    本楼为最佳答案   
本帖最后由 wangzhenas 于 2017-7-2 06:17 编辑

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

  1. # -*- coding: utf-8 -*-
  2. """
  3. Created on Sat Jul  1 23:25:32 2017

  4. @author: wangz
  5. """

  6. row, col = 30, 15

  7. #code to generate a dict to indicate if a number is prime
  8. primes_dict = {i:True for i in range(1,col*row+1)}
  9. primes_dict[1] = False
  10. for fac in range(2,col*row//2+1):
  11.     if primes_dict[fac]:
  12.         i = 2
  13.         while i*fac <= col*row:
  14.             primes_dict[i*fac], i = False, i+1

  15. #function to generate the matrix
  16. def make_matrix(max_row, max_col):
  17.     directions = [(0,1),(1,0),(0,-1),(-1,0)]
  18.     matrix = [[0 for i in range(max_col)] for i in range(max_row)]
  19.     acc_pos, acc_num, acc_dir =(0,0),1,directions[0]

  20.     while True:
  21.         matrix[acc_pos[0]][acc_pos[1]], next_dir = acc_num, acc_dir   

  22.         while True:
  23.             next_row, next_col = acc_pos[0]+next_dir[0], acc_pos[1]+next_dir[1]
  24.             if next_col in range(max_col) and next_row in range(max_row):
  25.                 if matrix[next_row][next_col] == 0:
  26.                     acc_pos, acc_num, acc_dir =(next_row,next_col),acc_num+1,next_dir
  27.                     break
  28.                                     
  29.             next_dir = directions[(directions.index(next_dir) + 1)%4]
  30.             if next_dir == acc_dir:
  31.                 return matrix        

  32. def check_matrix(max_row=row, max_col=col):
  33.     matrix = make_matrix(max_row, max_col)
  34.     check_result = dict()
  35.     for col in range(1,max_col-1):
  36.         for row in range(1, max_row-1):
  37.             numbers = matrix[row-1][col-1:col+2] +\
  38.                       matrix[row][col-1:col+2:2] +\
  39.                       matrix[row+1][col-1:col+2]
  40.             nearby_prime_numbers = len(list(filter(lambda n: primes_dict[n], numbers)))
  41.             if nearby_prime_numbers not in check_result:
  42.                 check_result.update({nearby_prime_numbers:[matrix[row][col]]})
  43.             else:
  44.                 check_result[nearby_prime_numbers].append(matrix[row][col])
  45.     return check_result

  46. result = check_matrix()
  47. print("Answer is {} with {} primes nearby".format(min(result[max(result)]), max(result)))
复制代码

评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-6-30 17:02:25 | 显示全部楼层
本帖最后由 WelanceLee 于 2017-6-30 17:04 编辑

  1. def p_m(n, m):
  2.     matrix = [[0 for _ in range(m)] for _ in range(n)]
  3.     ## bound
  4.     i = 1
  5.     ul = 0
  6.     uh = m
  7.     rl = 1
  8.     rh = n
  9.     dl = 0
  10.     dh = m-1
  11.     ll = 1
  12.     lh = n-1
  13.     while i <= m*n:
  14.         for r in range(ul, uh):
  15.             matrix[ll-1][r] = i
  16.             i += 1
  17.         if i > m*n:
  18.             break
  19.         ul += 1
  20.         uh -= 1
  21.         for d in range(rl, rh):
  22.             matrix[d][uh] = i
  23.             i += 1
  24.         if i > m*n:
  25.             break
  26.         rl += 1
  27.         rh -= 1
  28.         for l in range(dh-1, dl-1, -1):
  29.             matrix[rh][l] = i
  30.             i += 1
  31.         if i > m*n:
  32.             break
  33.         dl += 1
  34.         dh -= 1
  35.         for u in range(lh-1, ll-1, -1):
  36.             matrix[u][dl-1] = i
  37.             i += 1
  38.         if i > m*n:
  39.             break
  40.         ll += 1
  41.         lh -= 1
  42.     return matrix

  43. def pprint(x):
  44.     for each in x:
  45.         print(each)

  46. ## get prime list
  47. def p(n):
  48.     p = [True for i in range(n+1)]
  49.     p[:2] = [False, False]
  50.     for i in range(2, n+1):
  51.         if p[i]:
  52.             for j in range(i**2, n+1, i):
  53.                 p[j] = False
  54.     primes = [i for i in range(n+1) if p[i]]
  55.     return primes

  56. ## judge number of primes
  57. def f(x, y):
  58.     a = 0
  59.     for each in around:
  60.         nx = x + each[0]
  61.         ny = y + each[1]
  62.         if -1 < nx < n and -1 < ny < m and matrix[nx][ny] in l:
  63.             a += 1
  64.     return a

  65. n = int(input('input the numeber of rows: '))
  66. m = int(input('input the number of columns: '))
  67. l = p(n*m)
  68. matrix = p_m(n, m)
  69. around = [(-1,-1), (0,-1), (1,-1), (-1, 0), (1,0), (-1,1), (0,1), (1,1)]
  70. mmax = 0
  71. num = 1
  72. for i in range(n):
  73.     for j in range(m):
  74.         if f(i, j) > mmax:
  75.             num = matrix[i][j]
  76.             mmax = f(i, j)
  77.         if f(i, j) == mmax and num > matrix[i][j]:
  78.             num = matrix[i][j]      
  79. print(num, mmax)
复制代码

评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-1 10:58:45 | 显示全部楼层
  1. import time


  2. def isin(n,m):
  3.     return jz[n][m] if 0<=n<r and 0<=m<c and jz[n][m] in zs else 0

  4. def lg(n,m):#测试周围8个数是否是质数
  5.     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)))
  6.     if 0 in q :#移除0
  7.         q.remove(0)
  8.     return q


  9. while True:#循环测试
  10.    
  11.     te=input('请输入行(空格)列').split()
  12.     tt=time.time()
  13.    
  14.     if te=='0' or len(te)!=2:break
  15.    
  16.     r,c=[int(i) for i in te]#输入矩阵行列

  17.     zs=[0,0]+[1]*(r*c-2)#生成质数列表
  18.     for i,j in enumerate(zs):
  19.         if j:
  20.             for k in range(i*i,r*c,i):
  21.                 zs[k]=0
  22.     zs=set([i for i,j in enumerate(zs) if j])

  23.     jz=[[0]*c for j in range(r)]#生成矩阵
  24.     m,n,fx,x=0,0,0,0
  25.     while x<r*c:
  26.         x+=1
  27.         jz[m][n]=x
  28.         if fx==0:#向右
  29.             if n+1==c or jz[m][n+1]!=0:
  30.                 m,n,fx=m+1,n,1#向下
  31.             else:
  32.                 m,n,fx=m,n+1,0#向右
  33.         elif fx==1:#向下
  34.             if m+1==r or jz[m+1][n]!=0:
  35.                 m,n,fx=m,n-1,2#向左
  36.             else:
  37.                 m,n,fx=m+1,n,1#向下
  38.         elif fx==2:#向左
  39.             if n==0 or jz[m][n-1]!=0:
  40.                 m,n,fx=m-1,n,3#向上
  41.             else:
  42.                 m,n,fx=m,n-1,2#向左
  43.         elif fx==3:#向上
  44.             if m==0 or jz[m-1][n]!=0:
  45.                 m,n,fx=m,n+1,0#向右
  46.             else:
  47.                 m,n,fx=m-1,n,3#向上


  48.     if  c<=30:
  49.         t=""
  50.         y=""
  51.         for i in jz:
  52.             for j in i:
  53.                 t+='%4d ' % j
  54.                 y+='%4d ' % j if j in zs else '%4d ' % 0
  55.             t+='\n'
  56.             y+='\n'
  57.         print(t)
  58.         print(y)

  59.     minn=[0,0,0]#
  60.     for i in range(r):
  61.         for j in range(c):
  62.             ls=lg(i,j)#邻居,返回所有质数邻居
  63.             if (jz[i][j]<minn[0] and len(ls)==minn[1]) or len(ls)>minn[1] or i==j==0:
  64.                 minn[0],minn[1],minn[2]=jz[i][j],len(ls),list(ls)
  65.     minn[2]=0 if minn[2]==[]  else minn[2]
  66.     print('数字%s有%s个质数邻居,分别是%s' % (minn[0],minn[1],minn[2]))
  67.     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所有的矩阵统计出来

评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-1 23:06:15 | 显示全部楼层
python学了好几年,最近刚好不进入状态,没几天又卡住了,来做做任务:
变量名不会取名,把鸣人的姓拿来用了
能实现功能就已经很开心了

上代码
  1. #!/usr/bin/python
  2. # -*- coding: UTF-8 -*-
  3. __author__ = "Sigai"

  4. import itertools, math
  5. from operator import itemgetter


  6. def spiral(n, m):
  7.     _status = itertools.cycle(['right', 'down', 'left', 'up'])  # 用于状态周期性的切换
  8.     _movemap = {
  9.         'right': (1, 0),
  10.         'down': (0, 1),
  11.         'left': (-1, 0),
  12.         'up': (0, -1),
  13.     }
  14.     pos2no = dict.fromkeys([(x, y) for x in range(n) for y in range(m)])  # 生成字典键值是向量元组
  15.     _pos = (0, 0)
  16.     _st = next(_status)
  17.     for i in range(1, n * m + 1):
  18.         _oldpos = _pos
  19.         _pos = tuple(map(sum, zip(_pos, _movemap[_st])))  # 根据状态进行移动
  20.         if (_pos not in pos2no) or (pos2no[_pos]):  # 当超出范围或遇到障碍时切换方向
  21.             _st = next(_status)
  22.             _pos = tuple(map(sum, zip(_oldpos, _movemap[_st])))
  23.         pos2no[_oldpos] = i
  24.     return pos2no


  25. def prime(n):
  26.     if n is None:
  27.         return False
  28.     if n % 2 == 0:
  29.         return n == 2
  30.     if n % 3 == 0:
  31.         return n == 3
  32.     if n % 5 == 0:
  33.         return n == 5
  34.     for p in range(7, int(math.sqrt(n)) + 1, 2):  # 只考虑奇数作为可能因子
  35.         if n % p == 0:
  36.             return False
  37.     return True


  38. class Uzimaki(object):
  39.     def __init__(self, n, m):
  40.         self.n = n
  41.         self.m = m
  42.         self.spiral = spiral(self.n, self.m)

  43.     def display_spiral(self):
  44.         pos2no = spiral(self.n, self.m)
  45.         for i in range(self.m):
  46.             for j in range(self.n):
  47.                 print(pos2no[(j, i)], end='\t', )
  48.             print('\n')
  49.         print('-' * 5 * self.n)

  50.     def neighbors(self, n):
  51.         # print(self.spiral)
  52.         n_pos = {v: (x, y) for (x, y), v in self.spiral.items()}[n]
  53.         nbs_pos = [(x, y) for x in [-1, 0, 1] for y in [-1, 0, 1] if x != 0 or y != 0]
  54.         nbs = []
  55.         for x, y in nbs_pos:
  56.             nbs.append(self.spiral.get((n_pos[0] + x, n_pos[1] + y), None))
  57.         result = list(set(nbs))
  58.         # print(result)
  59.         return result

  60.     def get_prime_neighbors(self, n):
  61.         tmp = []
  62.         for i in self.neighbors(n):
  63.             if prime(i):
  64.                 tmp.append(i)
  65.         # print(tmp)
  66.         return tmp

  67.     def get_most_prime_neighbors(self):
  68.         rank = []
  69.         for i in range(1, self.n * self.m):
  70.             rank.append((i, len(self.get_prime_neighbors(i))))
  71.         rank = sorted(rank, key=itemgetter(1), reverse=True)
  72.         print("在给定%d行和%d列的螺旋矩阵中,%d拥有的质数邻居最多,它有%d个质数邻居."%(self.n,self.m,rank[0][0],rank[0][1]))
  73.         return rank[0]


  74. Uzimaki(4, 4).display_spiral()
  75. Uzimaki(4, 4).neighbors(14)
  76. Uzimaki(4, 4).get_prime_neighbors(14)
  77. Uzimaki(4, 4).get_most_prime_neighbors()
复制代码

04.py.zip

1.31 KB, 下载次数: 0

第4期

评分

参与人数 1鱼币 +5 收起 理由
SixPy + 5 热爱鱼C^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-3 00:19:35 | 显示全部楼层
抗议,最佳答案在输入行列小于3的时候出错
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-3 02:40:33 | 显示全部楼层
达锅 发表于 2017-7-3 00:19
抗议,最佳答案在输入行列小于3的时候出错

好吧 木有注意这一点,可以在check函数里面先判断一下初始值
不过小于3的时候这个题的前提条件也不成立啊。。没有8个相邻的数
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-3 07:35:54 From FishC Mobile | 显示全部楼层
wangzhenas 发表于 2017-7-3 02:40
好吧 木有注意这一点,可以在check函数里面先判断一下初始值
不过小于3的时候这个题的前提条 ...

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

题目原话
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2017-7-3 08:58:02 From FishC Mobile | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-7-3 09:08 编辑
达锅 发表于 2017-7-3 00:19
抗议,最佳答案在输入行列小于3的时候出错


确实,是我疏忽了,我再补你100鱼币,你们的程序都不错,并列获胜吧!
请到这个帖子下回复,补充领奖!http://bbs.fishc.com/thread-90068-1-1.html
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-3 09:56:18 From FishC Mobile | 显示全部楼层
jerryxjr1220 发表于 2017-7-3 08:58
确实,是我疏忽了,我再补你100鱼币,你们的程序都不错,并列获胜吧!
请到这个帖子下回复,补充领奖 ...


我也要继续努力
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-7-5 15:48:52 | 显示全部楼层
鱼币怎么得啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 00:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表