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

相关文章

大数据小内存排序问题如何巧妙解决

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法：数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高；分治法高效但实现复杂；位图法可读性差,但存储空间受限... 目录三种方法：方法概要数据库排序（http://www.chinasem.cn对数据库设备要求较高）分治法（常
阅读更多...
Vue项目中Element UI组件未注册的问题原因及解决方法

Vue项目中Element UI组件未注册的问题原因及解决方法

《Vue项目中ElementUI组件未注册的问题原因及解决方法》在Vue项目中使用ElementUI组件库时,开发者可能会遇到一些常见问题,例如组件未正确注册导致的警告或错误,本文将详细探讨这些问题... 目录引言一、问题背景1.1 错误信息分析1.2 问题原因二、解决方法2.1 全局引入 Element
阅读更多...
关于@MapperScan和@ComponentScan的使用问题

关于@MapperScan和@ComponentScan的使用问题

《关于@MapperScan和@ComponentScan的使用问题》文章介绍了在使用`@MapperScan`和`@ComponentScan`时可能会遇到的包扫描冲突问题,并提供了解决方法,同时,... 目录@MapperScan和@ComponentScan的使用问题报错如下原因解决办法课外拓展总结@
阅读更多...
MybatisGenerator文件生成不出对应文件的问题

MybatisGenerator文件生成不出对应文件的问题

《MybatisGenerator文件生成不出对应文件的问题》本文介绍了使用MybatisGenerator生成文件时遇到的问题及解决方法,主要步骤包括检查目标表是否存在、是否能连接到数据库、配置生成... 目录MyBATisGenerator 文件生成不出对应文件先在项目结构里引入“targetProje
阅读更多...
C#使用HttpClient进行Post请求出现超时问题的解决及优化

C#使用HttpClient进行Post请求出现超时问题的解决及优化

《C#使用HttpClient进行Post请求出现超时问题的解决及优化》最近我的控制台程序发现有时候总是出现请求超时等问题,通常好几分钟最多只有3-4个请求,在使用apipost发现并发10个5分钟也... 目录优化结论单例HttpClient连接池耗尽和并发并发异步最终优化后优化结论我直接上优化结论吧，
阅读更多...
Java内存泄漏问题的排查、优化与最佳实践

Java内存泄漏问题的排查、优化与最佳实践

《Java内存泄漏问题的排查、优化与最佳实践》在Java开发中,内存泄漏是一个常见且令人头疼的问题,内存泄漏指的是程序在运行过程中,已经不再使用的对象没有被及时释放,从而导致内存占用不断增加,最终... 目录引言1. 什么是内存泄漏？常见的内存泄漏情况2. 如何排查 Java 中的内存泄漏？2.1 使用 J
阅读更多...
numpy求解线性代数相关问题

numpy求解线性代数相关问题

《numpy求解线性代数相关问题》本文主要介绍了numpy求解线性代数相关问题,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 在numpy中有numpy.array类型和numpy.mat类型，前者是数组类型，后者是矩阵类型。数组
阅读更多...
解决systemctl reload nginx重启Nginx服务报错:Job for nginx.service invalid问题

解决systemctl reload nginx重启Nginx服务报错:Job for nginx.service invalid问题

《解决systemctlreloadnginx重启Nginx服务报错:Jobfornginx.serviceinvalid问题》文章描述了通过`systemctlstatusnginx.se... 目录systemctl reload nginx重启Nginx服务报错:Job for nginx.javas
阅读更多...
Redis缓存问题与缓存更新机制详解

Redis缓存问题与缓存更新机制详解

《Redis缓存问题与缓存更新机制详解》本文主要介绍了缓存问题及其解决方案,包括缓存穿透、缓存击穿、缓存雪崩等问题的成因以及相应的预防和解决方法,同时,还详细探讨了缓存更新机制,包括不同情况下的缓存更... 目录一、缓存问题1.1 缓存穿透1.1.1 问题来源1.1.2 解决方案1.2 缓存击穿1.2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2