数据结构——残缺棋盘覆盖（问题+算法+UI界面）

2023-10-30 22:51
文章标签 算法 问题 数据结构 ui 界面 覆盖 棋盘 残缺

本文主要是介绍数据结构——残缺棋盘覆盖（问题+算法+UI界面），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

总述：这是山东大学软件学院AI班大二下学期的数据结构课程设计（假期完成课设，开学第一周演示），假期花了1天时间完成了这个课程设计，代码在下面的连接中
百度网盘链接：
链接：https://pan.baidu.com/s/1RdlO2fgefQIRixebHlr_Ow
提取码：95mh

花5天时间帮同学写的课程设计基于QT实现九大排序的动态演示

文章目录

    • 一.残缺棋盘问题
    • 二.算法
    • 三.UI界面

一.残缺棋盘问题

残缺棋盘是一个有 2 k × 2 k 2^{k}×2^{k} 2k×2k 个方格的棋盘，其中恰有一个方格残缺，如下图所示。在这里插入图片描述残缺棋盘的问题要求用三格板覆盖残缺棋盘。在此覆盖中两个三格板不能重叠，三格板不能覆盖残缺方格，但必须覆盖其他所有的方格。下图就是四种方向的三格板。
在这里插入图片描述
现在给出一个随机的残缺棋盘，用上述四种三格板覆盖，给出动态求解过程。

二.算法

使用分而治之法，可以很好地解决残缺棋盘问题。把 2 k × 2 k 2^{k}×2^{k} 2k×2k的残缺棋盘实例划分成为较小的残缺棋盘实例。一个自然的划分结果是4个 2 k − 1 × 2 k − 1 2^{k-1}×2^{k-1} 2k−1×2k−1棋盘，如下图所示。
在这里插入图片描述
注意，原来的 2 k × 2 k 2^{k}×2^{k} 2k×2k棋盘仅有一个残缺方格，因此划分之后，在4个小棋盘中仅仅有一个棋盘存在残缺方格。首先覆盖残缺方格的小棋盘。然后把剩下3个小棋盘转变为残缺棋盘，为此，将一个三格板放置由这3个小棋盘形成的角上，如下图所示。
在这里插入图片描述
其中，原 2 k × 2 k 2^{k}×2^{k} 2k×2k棋盘的残缺方格位于左上角的 2 k − 1 × 2 k − 1 2^{k-1}×2^{k-1} 2k−1×2k−1棋盘。递归地使用这种分割技术。当棋盘的大小减为 1 × 1 1×1 1×1时，递归过程终止。此时的 1 × 1 1×1 1×1棋盘仅仅包含一个方格且为残缺方格，无需覆盖三格板。
完整代码：
头文件

#ifndef ALGORICODE_H
#define ALGORICODE_Hclass AlgoriCode
{
public:AlgoriCode(int k, int defectRow, int defectColumn);~AlgoriCode();void coverBoard();int **board; // 棋盘int size; // 棋盘大小int defectRow, defectColumn; // 残缺方格的位置(defectRow, defectColumn)private:int tile; // 当前使用的三格版void tileBoard(int topRow, int topColumn, int defectRow, int defectColumn, int size);};#endif // ALGORICODE_H

源文件

#include "algoricode.h"
#include <cmath>AlgoriCode::AlgoriCode(int k, int defectRow, int defectColumn)
{tile = 1; size = int(exp2(k));this->defectRow = defectRow;this->defectColumn = defectColumn;// 初始化二维数组board = new int*[size];for (int i = 0; i < size; i++)board[i] = new int[size];for (int i = 0; i < size; i++)for (int j = 0; j < size; j++)board[i][j] = 0;
}AlgoriCode::~AlgoriCode()
{// 释放二维数组所用内存空间for (int i = 0; i < size; i++)delete [] board[i];delete [] board;
}void AlgoriCode::coverBoard()
{tileBoard(0, 0, defectRow, defectColumn, size);
}void AlgoriCode::tileBoard(int topRow, int topColumn, int defectRow, int defectColumn, int size)
{// topRow 表示棋盘左上角方格的行号// topColumn 表示棋盘左上角方格的列号// defectRow 表示残缺方格的行号// defectColumn 表示残缺方格的列号// size 表示残缺棋盘的边长if (size == 1)return;int tileToUse = tile++; // 表示当前所使用的三格板int quadrantSize = size / 2; // 表示分割后小棋盘的边长// 覆盖左上角象限（第二象限）if (defectRow < topRow + quadrantSize &&defectColumn < topColumn + quadrantSize)// 残缺方格属于这个象限tileBoard(topRow, topColumn, defectRow, defectColumn,quadrantSize);else{// 这个象限无残缺方格// 在右下角放置一个三格板board[topRow + quadrantSize - 1][topColumn + quadrantSize - 1]= tileToUse;tileBoard(topRow, topColumn, topRow + quadrantSize - 1,topColumn + quadrantSize - 1, quadrantSize);}// 覆盖右上角象限（第一象限）if (defectRow < topRow + quadrantSize &&defectColumn >= topColumn + quadrantSize)// 残缺方格属于这个象限tileBoard(topRow, topColumn + quadrantSize, defectRow,defectColumn, quadrantSize);else{// 这个象限无残缺方格// 在左下角放置一个三格板board[topRow + quadrantSize - 1][topColumn + quadrantSize]= tileToUse;tileBoard(topRow, topColumn + quadrantSize, topRow +quadrantSize - 1, topColumn + quadrantSize, quadrantSize);}// 覆盖左下角象限（第三象限）if (defectRow >= topRow + quadrantSize &&defectColumn < topColumn + quadrantSize)// 残缺方格属于这个象限tileBoard(topRow + quadrantSize, topColumn, defectRow,defectColumn, quadrantSize);else{// place a tile in top-right cornerboard[topRow + quadrantSize][topColumn + quadrantSize - 1]= tileToUse;tileBoard(topRow + quadrantSize, topColumn, topRow + quadrantSize,topColumn + quadrantSize - 1, quadrantSize);}// 覆盖右下角象限（第四象限）if (defectRow >= topRow + quadrantSize &&defectColumn >= topColumn + quadrantSize)// 残缺方格属于这个象限tileBoard(topRow + quadrantSize, topColumn + quadrantSize,defectRow, defectColumn, quadrantSize);else{// 这个象限无残缺方格// 在左上角放置一个三格板board[topRow + quadrantSize][topColumn + quadrantSize]= tileToUse;tileBoard(topRow + quadrantSize, topColumn + quadrantSize,topRow + quadrantSize, topColumn + quadrantSize, quadrantSize);}
}

三.UI界面

先看一下总体效果
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这个才是重点，上面那个算法，很快就能搞完，不过这个我就花了很多时间
Qt版本：5.14.0
Qt Creator版本：4.11.0（Community）
第一步：File => New File or Project => 选择Application，再选择Qt Widgets Application，创建一个项目“BrokenChessBoard”。
在这里插入图片描述
第二步：选择基类QMainWindow，类名称为“ChessBoard”。
在这里插入图片描述
OK，现在项目创建完了
看一下项目的结构
在这里插入图片描述

chessboard.h头文件

#ifndef CHESSBOARD_H
#define CHESSBOARD_H#include <QMainWindow>
#include <algoricode.h>
#include <QLabel>QT_BEGIN_NAMESPACE
namespace Ui { class ChessBoard; }
QT_END_NAMESPACEclass ChessBoard : public QMainWindow
{Q_OBJECTprivate:AlgoriCode *code;// 状态栏的三个QLabelQLabel *Label_pos;QLabel *Label_pos_row;QLabel *Label_pos_col;QPixmap *map; // 在这里绘制棋盘qreal sizeW; // 单个方格的宽qreal sizeH; // 单个方格的高bool flag; // “覆盖棋盘”的标志bool cap; // “还原棋盘”的标志void paintEvent(QPaintEvent *);public:ChessBoard(QWidget *parent = nullptr);~ChessBoard();private slots:void on_Button_build_clicked(); // “初始化棋盘”按钮的槽函数void on_Button_cure_clicked(); // “覆盖棋盘”按钮的槽函数void on_Button_solve_clicked(); // “还原棋盘”按钮的槽函数private:Ui::ChessBoard *ui;
};
#endif // CHESSBOARD_H

chessboard.cpp源文件

#include "chessboard.h"
#include "ui_chessboard.h"
#include "algoricode.h"
#include <QPainter>
#include <QRandomGenerator>
#include <QMouseEvent>ChessBoard::ChessBoard(QWidget *parent): QMainWindow(parent), ui(new Ui::ChessBoard)
{ui->setupUi(this);this->setWindowTitle("残缺棋盘覆盖");this->setFixedSize(QSize(1300, 900)); // 固定界面的大小this->setWindowIcon(QIcon(":/images/BlackHole.ico"));code = new AlgoriCode(2, 0, 0);flag = false;cap = false;// 开始时设置为不可用，“初始化棋盘”后，设置为可用ui->Button_solve->setEnabled(false);ui->Button_cure->setEnabled(false);// 创建状态栏标签// 这个目前还没实现，我的想法是根据当前鼠标光标的位置实时显示当前方格的行号和列号Label_pos = new QLabel("当前方格坐标");Label_pos->setMinimumWidth(150);ui->statusbar->addWidget(Label_pos);Label_pos_col = new QLabel("行坐标：");Label_pos_col->setMinimumWidth(150);ui->statusbar->addWidget(Label_pos_col);Label_pos_row = new QLabel("列坐标：");Label_pos_row->setMinimumWidth(150);ui->statusbar->addWidget(Label_pos_row);
}ChessBoard::~ChessBoard()
{delete ui;
}void ChessBoard::paintEvent(QPaintEvent *)
{// 初始化棋盘map = new QPixmap(this->width()-450, this->height()-90); // 初始化QPixmap的大小map->fill(Qt::white); // 填充背景色为白色QPainter painter(map); // 指定绘图设备为map// 创建一个画笔QPen pen;pen.setWidth(1);pen.setColor(Qt::black);pen.setStyle(Qt::SolidLine);painter.setPen(pen); // 设置画笔sizeH = qreal(map->height()) / code->size;sizeW = qreal(map->width()) / code->size;// 绘制棋盘for (int i = 0; i <= code->size; i++)// 竖线painter.drawLine(QLineF(i*sizeW, 0, i*sizeW, map->height()));for (int i = 0; i <= code->size; i++)// 横线painter.drawLine(QLineF(0, i*sizeH, map->width(), i*sizeH));// 绘制残缺方格// 设置一个画刷QBrush brush;brush.setColor(QColor(0, 0, 0));brush.setStyle(Qt::SolidPattern);painter.setBrush(brush);QRect rect(code->defectColumn*sizeW, code->defectRow*sizeH, sizeW, sizeH);if (cap)painter.drawRect(rect);// flag为true，表示按下了“覆盖棋盘”if (flag){QRandomGenerator generator(10);int nums = (code->size*code->size-1)/3 + 1;QColor colors[nums];colors[0] = QColor(0, 0, 0); // 残缺棋盘的数字0，为黑色for (int i = 1; i < nums; i++)colors[i] = QColor(generator.bounded(80, 255), generator.bounded(80, 255),generator.bounded(60, 255));for (int i = 0; i < code->size; i++){for (int j = 0; j < code->size; j++){// 填充颜色int temp = code->board[i][j];QBrush brusher;brusher.setColor(colors[temp]);brusher.setStyle(Qt::SolidPattern);painter.setBrush(brusher);rect.setRect(j*sizeW, i*sizeH, sizeW, sizeH);painter.drawRect(rect);// 填写数字painter.drawText(QPoint(j*sizeW+sizeW/2, i*sizeH+sizeH/2), QString::number(temp));}}flag = false;}// 绘制所有的一切QPainter painterAll(this); // 指定绘图设备为界面，在界面上绘制mappainterAll.drawPixmap(QPoint(25, 50), *map);
}void ChessBoard::on_Button_build_clicked()
{// “初始化棋盘”按下后，初始化算法和棋盘// 初始化算法cap = true;int k = ui->Spin_input->value();int defectRow = ui->Spin_defectRow->value();int defectColumn = ui->Spin_defectColumn->value();delete code; // 清空原来的codecode = new AlgoriCode(k, defectRow-1, defectColumn-1);ui->Button_build->setEnabled(false);ui->Button_solve->setEnabled(true);ui->Button_cure->setEnabled(true);// 更新棋盘this->repaint();
}void ChessBoard::on_Button_solve_clicked()
{// “覆盖棋盘”按下后，用三格版覆盖棋盘// 三格板的颜色，可以通过随机数，指定从1开始到(size-1)/3的随机数// 通过生成的随机数确定颜色flag = true; // 表示更新棋盘时，将会画上所有三格板code->coverBoard(); // 调用覆盖棋盘的核心代码ui->Button_build->setEnabled(false);ui->Button_solve->setEnabled(false);ui->Button_cure->setEnabled(true);this->repaint();
}void ChessBoard::on_Button_cure_clicked()
{// “还原棋盘”按下后，还原棋盘到初始情况delete code;cap = false;code = new AlgoriCode(2, 0, 0);ui->Button_build->setEnabled(true);ui->Button_solve->setEnabled(false);ui->Button_cure->setEnabled(false);this->repaint();
}

最后，说一下我的这个程序的4个问题

  1. 多次运行后会产生下面的“问题”，Application Output中会输出以下的语句，界面会如下面这张图所示，显示不出棋盘并且无法继续运行。我尝试解决，但未成功。在这里插入图片描述在这里插入图片描述
  2. 菜单栏的功能没有实现，我的想法是，点击会出现一个窗口，介绍算法，或者提供截图功能、保存功能、打开功能。未尝试。
  3. 状态栏中，行列坐标的功能没有实现。我尝试实现，但未成功。
  4. 播放背景音乐的功能。未尝试。

2020年2月6日 更新：
我将这个程序打包成了软件。上述“问题1”仍然存在，关闭重新启动即可
百度网盘链接
链接：https://pan.baidu.com/s/1Q3yaxsJssPwoQcAfGiz4qA
提取码：wvhl

我发现这个程序在刚开始运行时内存占30MB左右，之后每一次点击都会增加几十个MB，我试过干到了1个G，这或许就是“问题1”的原因。当然，如果课程设计演示，演示几次是没有问题的，但不要演示太多次，演示时设置的数据也不要太大。

这篇关于数据结构——残缺棋盘覆盖（问题+算法+UI界面）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/311104。

相关文章

IDEA和GIT关于文件中LF和CRLF问题及解决

IDEA和GIT关于文件中LF和CRLF问题及解决

《IDEA和GIT关于文件中LF和CRLF问题及解决》文章总结：因IDEA默认使用CRLF换行符导致Shell脚本在Linux运行报错,需在编辑器和Git中统一为LF,通过调整Git的core.aut... 目录问题描述问题思考解决过程总结问题描述项目软件安装shell脚本上git仓库管理，但拉取后，上l
阅读更多...
深入理解Mysql OnlineDDL的算法

深入理解Mysql OnlineDDL的算法

《深入理解MysqlOnlineDDL的算法》本文主要介绍了讲解MysqlOnlineDDL的算法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小... 目录一、Online DDL 是什么？二、Online DDL 的三种主要算法2.1COPY（复制法）
阅读更多...
idea npm install很慢问题及解决(nodejs)

idea npm install很慢问题及解决(nodejs)

《ideanpminstall很慢问题及解决(nodejs)》npm安装速度慢可通过配置国内镜像源（如淘宝）、清理缓存及切换工具解决,建议设置全局镜像（npmconfigsetregistryht... 目录idea npm install很慢(nodejs)配置国内镜像源清理缓存总结idea npm in
阅读更多...
pycharm跑python项目易出错的问题总结

pycharm跑python项目易出错的问题总结

《pycharm跑python项目易出错的问题总结》：本文主要介绍pycharm跑python项目易出错问题的相关资料,当你在PyCharm中运行Python程序时遇到报错,可以按照以下步骤进行排... 1. 一定不要在pycharm终端里面创建环境安装别人的项目子模块等，有可能出现的问题就是你不报错都安装
阅读更多...
idea突然报错Malformed \uxxxx encoding问题及解决

idea突然报错Malformed \uxxxx encoding问题及解决

《idea突然报错Malformeduxxxxencoding问题及解决》Maven项目在切换Git分支时报错,提示project元素为描述符根元素,解决方法：删除Maven仓库中的resolv... 目www.chinasem.cn录问题解决方式总结问题idea 上的 maven China编程项目突然报错，是
阅读更多...
Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题

《Python爬虫HTTPS使用requests,httpx,aiohttp实战中的证书异步等问题》在爬虫工程里,“HTTPS”是绕不开的话题,HTTPS为传输加密提供保护,同时也给爬虫带来证书校验、... 目录一、核心问题与优先级检查（先问三件事）二、基础示例：requests 与证书处理三、高并发选型：
阅读更多...
前端导出Excel文件出现乱码或文件损坏问题的解决办法

前端导出Excel文件出现乱码或文件损坏问题的解决办法

《前端导出Excel文件出现乱码或文件损坏问题的解决办法》在现代网页应用程序中,前端有时需要与后端进行数据交互,包括下载文件,：本文主要介绍前端导出Excel文件出现乱码或文件损坏问题的解决办法,... 目录1. 检查后端返回的数据格式2. 前端正确处理二进制数据方案 1：直接下载（推荐）方案 2：手动构造
阅读更多...
Python绘制TSP、VRP问题求解结果图全过程

Python绘制TSP、VRP问题求解结果图全过程

《Python绘制TSP、VRP问题求解结果图全过程》本文介绍用Python绘制TSP和VRP问题的静态与动态结果图,静态图展示路径,动态图通过matplotlib.animation模块实现动画效果... 目录一、静态图二、动态图总结【代码】python绘制TSP、VRP问题求解结果图（包含静态图与动态图
阅读更多...
MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决

MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决

《MyBatis/MyBatis-Plus同事务循环调用存储过程获取主键重复问题分析及解决》MyBatis默认开启一级缓存,同一事务中循环调用查询方法时会重复使用缓存数据,导致获取的序列主键值均为1,... 目录问题原因解决办法如果是存储过程总结问题myBATis有如下代码获取序列作为主键IdMappe
阅读更多...
k8s容器放开锁内存限制问题

k8s容器放开锁内存限制问题

《k8s容器放开锁内存限制问题》nccl-test容器运行mpirun时因NCCL_BUFFSIZE过大导致OOM,需通过修改docker服务配置文件,将LimitMEMLOCK设为infinity并... 目录问题问题确认放开容器max locked memory限制总结参考：https://Access
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2