1000字范文 > 算法分析与设计实验报告——实现分治法求解棋盘覆盖问题

算法分析与设计实验报告——实现分治法求解棋盘覆盖问题

时间：2024-03-19 18:54:20

一、实验目的

掌握分治法的基本思想，建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求

用c++语言实现棋盘覆盖问题，分析时间复杂性，体会分治法解决问题的基本思路和步骤。

三、实验原理

划分问题：将2k x 2k的棋盘划分为2(k-1) x 2(k-1)这样的子棋盘4块。

递归求解：递归填充各个棋子，填充分为四个情况，递归的出口为k=0，也就是子棋盘的方格数为1。递归填充的四种情况：如果特殊方格在左上子棋盘，则递归填充左上子棋盘；否则填充左上子棋盘的右下角，将右下角看作特殊方格，然后递归填充左上棋盘。如果特殊方格在右上子棋盘，则递归填充右上子棋盘；否则填充右上子棋盘的左下角，将左下角看作特殊方格，然后递归填充右上棋盘。如果特殊方格在左下子棋盘，则递归填充左下子棋盘；否则填充左下子棋盘的右上角，将右上角看作特殊方格，然后递归填充左下棋盘。如果特殊方格在右下子棋盘，则递归填充右下子棋盘；否则填充右下子棋盘的左上角，将左上角看作特殊方格，然后递归填充右下棋盘。

四、实验过程(步骤)

见附件一

实验步骤、特点

重要源代码（流操作的部分要醒目的提示并注释）

五、运行结果

见附件二

六、实验分析与讨论

开始实验时，并没有注意到棋盘的大小问题，错误的设置了一个9 x 9的棋盘，结果就是输出多了一行一列的0.后来查阅课本才发现棋盘的大小必须为2k x 2k，所以就修改为8 x 8大小的棋盘了，从而顺利的完成了实验。

遇到的问题，及解决方案

七、实验特色与心得

本次实验让我对分治法思想有了更深的了解，而且建立了算法复杂度的理论分析与实验分析的联系，进一步锻炼了自己的能力。

附件一实验过程(步骤)

#include <bits/stdc++.h>using namespace std;#define maxn 8int Board[maxn][maxn];//初始化8x8的棋盘static int tile=0;void ChessBoard(int ch,int cl,int th,int tl,int size){if(size==1)return ;int t=tile++;// L型骨牌号int s=size/2;// 分割棋盘// 覆盖左上角子棋盘if(th<ch+s&&tl<cl+s)// 特殊方格在此棋盘中ChessBoard(ch,cl,th,tl,s);else // 此棋盘中无特殊方格{// 用 t 号L型骨牌覆盖右下角Board[ch+s-1][cl+s-1]=t;ChessBoard(ch,cl,ch+s-1,cl+s-1,s);// 覆盖其余方格}// 覆盖右上角子棋盘if(th<ch+s&&tl>=cl+s)// 特殊方格在此棋盘中ChessBoard(ch,cl+s,th,tl,s);else// 此棋盘中无特殊方格{// 用 t 号L型骨牌覆盖左下角Board[ch+s-1][cl+s]=t;ChessBoard(ch,cl+s,ch+s-1,cl+s,s);// 覆盖其余方格}// 覆盖左下角子棋盘if(th>=ch+s&&tl<cl+s)// 特殊方格在此棋盘中ChessBoard(ch+s,cl,th,tl,s);else// 此棋盘中无特殊方格{// 用 t 号L型骨牌覆盖右上角Board[ch+s][cl+s-1]=t;ChessBoard(ch+s,cl,ch+s,cl+s-1,s);// 覆盖其余方格}// 覆盖右下角子棋盘if(th>=ch+s&&tl>=cl+s)// 特殊方格在此棋盘中ChessBoard(ch+s,cl+s,th,tl,s);else// 此棋盘中无特殊方格{// 用 t 号L型骨牌覆盖左上角Board[ch+s][cl+s]=t;ChessBoard(ch+s,cl+s,ch+s,cl+s,s);// 覆盖其余方格}}int main(){int x,y;cout<<"请输入特殊方格坐标:";cin>>x>>y;Board[x-1][y-1]=99;//将特殊方格标记为99ChessBoard(0,0,x-1,y-1,maxn);//输出棋盘for(int i=0; i<maxn; i++){for(int j=0; j<maxn; j++){cout<<setw(2)<<setfill('0')<<Board[i][j]<<' ';}cout<<endl;}return 0;}