文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

python怎么实现棋盘覆盖问题及可视化

2023-06-13 05:49

关注

这篇文章主要介绍“python怎么实现棋盘覆盖问题及可视化”,在日常操作中,相信很多人在python怎么实现棋盘覆盖问题及可视化问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”python怎么实现棋盘覆盖问题及可视化”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

问题介绍

棋盘覆盖问题,是一种编程问题。

python怎么实现棋盘覆盖问题及可视化

如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题。k>0时,可将2k×2k的棋盘划分为4个2(k-1)×2(k-1)的子棋盘。这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘,以便采用递归方法求解,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略,直至将棋盘分割为1×1的子棋盘。

问题解释来源 百度

原网页

效果展示

k=1
python怎么实现棋盘覆盖问题及可视化
k=2
python怎么实现棋盘覆盖问题及可视化

代码实现

借助numpy处理数据,plot实现可视化。

使用面向对象的方法设计了棋盘类。

一步步将棋盘分为小区块,指导区块的边长为1,退出递归。

import numpy as npimport matplotlib.pyplot as pltclass Board: def __init__(self, size, x, y):  '''  初始化棋盘  :param size: 棋盘边长  :param x: 特殊点横坐标  :param y: 特殊点纵坐标  '''  self.special_block = (x, y)  self.board = np.zeros((size, size), dtype=int)  self.board[x][y] = (size * size - 1) / 3 + 1  self.t = 1  self.size = size def visualize(self):  '''  可视化函数  :return: None  '''  plt.imshow(self.board, cmap=plt.cm.gray)  plt.colorbar()  plt.show() def fill_block(self, x, y):  '''  填充点(x, y)  :param x: x  :param y: y  :return: None  '''  if self.board[x][y] == 0:   self.board[x][y] = self.t  else:   raise Exception def fill(self, s_x, s_y, size, c_x, c_y):  '''  递归函数填充棋盘或子棋盘(下文称区块)  :param s_x: 区块左上角x  :param s_y: 区块左上角y  :param size: 区块边长  :param c_x: 区块特殊点坐标x  :param c_y: 区块特殊点坐标x  :return: None  '''  if size == 1:   return  pos = (round((c_x - s_x + 1) / size), round((c_y - s_y + 1) / size))  center = (round(s_x + size / 2 - 1), round(s_y + size / 2 - 1))  ls = [(0, 0), (0, 1), (1, 0), (1, 1)] # 代表四个子区块  for i in ls:   if i != pos: # 如果不是原有特殊点所在区块,则构造特殊点并填充    x = center[0] + i[0]    y = center[1] + i[1]    self.fill_block(x, y)  self.t += 1 # 标记号加一,标记下一骨牌  for i in ls:   if i != pos: # 如果不是原有特殊点所在区块    # 所构造特殊点位置(x, y)    x = center[0] + i[0]    y = center[1] + i[1]    x1 = s_x + i[0] * (size / 2)    y1 = s_y + i[1] * (size / 2)    self.fill(x1, y1, size / 2, x, y)   else: # 如果是原有特殊点所在区块    x1 = s_x + i[0] * (size / 2)    y1 = s_y + i[1] * (size / 2)    self.fill(x1, y1, size / 2, c_x, c_y)

主函数

if __name__ == '__main__': k = eval(input("请输入正整数K(棋盘大小2^2k,2^2k):\n")) loc_x = eval(input("请输入特殊点横坐标:\n")) loc_y = eval(input("请输入特殊点纵坐标:\n")) size = 2 ** (2 * k) b = Board(size, loc_x, loc_y) b.fill(0, 0, size, loc_x, loc_y) b.visualize() print(b.board)

GitHub链接

总结

到此,关于“python怎么实现棋盘覆盖问题及可视化”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注编程网网站,小编会继续努力为大家带来更多实用的文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯