数据结构——残缺棋盘覆盖（问题+算法+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。

相关文章

MySQL 设置AUTO_INCREMENT 无效的问题解决

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。
阅读更多...
关于跨域无效的问题及解决(java后端方案)

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》：本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig
阅读更多...
Go语言中泄漏缓冲区的问题解决

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例：泄漏缓冲区的产生项目场景：Web 服务器中的请求缓冲场景描述代码
阅读更多...
Java死锁问题解决方案及示例详解

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件：2、死锁示例代码3、如何检测死锁？3.1 使用 jstack3.2
阅读更多...
解决JSONField、JsonProperty不生效的问题

解决JSONField、JsonProperty不生效的问题

《解决JSONField、JsonProperty不生效的问题》：本文主要介绍解决JSONField、JsonProperty不生效的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录jsONField、JsonProperty不生效javascript问题排查总结JSONField
阅读更多...
github打不开的问题分析及解决

github打不开的问题分析及解决

《github打不开的问题分析及解决》：本文主要介绍github打不开的问题分析及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、找到github.com域名解析的ip地址二、找到github.global.ssl.fastly.net网址解析的ip地址三
阅读更多...
MySQL版本问题导致项目无法启动问题的解决方案

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案：调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因：解决方案第一个：第二种：容器启动mysql的坑两种修改时区的方法：本地
阅读更多...
springboot加载不到nacos配置中心的配置问题处理

springboot加载不到nacos配置中心的配置问题处理

《springboot加载不到nacos配置中心的配置问题处理》：本文主要介绍springboot加载不到nacos配置中心的配置问题处理,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录springboot加载不到nacos配置中心的配置两种可能Spring Boot 版本Nacos
阅读更多...
Java中JSON格式反序列化为Map且保证存取顺序一致的问题

Java中JSON格式反序列化为Map且保证存取顺序一致的问题

《Java中JSON格式反序列化为Map且保证存取顺序一致的问题》：本文主要介绍Java中JSON格式反序列化为Map且保证存取顺序一致的问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未... 目录背景问题解决方法总结背景做项目涉及两个微服务之间传数据时，需要提供方将Map类型的数据序列化为co
阅读更多...
如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socket read timed out的问题

如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socket read timed out的问题

《如何解决Druid线程池Cause:java.sql.SQLRecoverableException:IO错误:Socketreadtimedout的问题》：本文主要介绍解决Druid线程... 目录异常信息触发场景找到版本发布更新的说明从版本更新信息可以看到该默认逻辑已经去除总结异常信息触发场景复
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2