精华内容
下载资源
问答
  • 棋盘覆盖
    2020-04-30 11:46:32

    棋盘覆盖:用4种不同的L型骨牌覆盖一个给定的特殊棋盘(即特殊方格的位置已经确定了)上除去特殊方格外的所有方格,且任何两个L型骨牌不得重复覆盖,按照规则,我们很容易知道,在2k*2k的棋盘覆盖中,用到的L型骨盘数恰为(4^k-1)/3,即(所有方格个数-特殊方格个数)/3

    实现这种算法的分析:每次都对分割后的四个小方块进行判断,判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标,然后再与特殊方格坐标进行比较,就可以知道特殊方格是否在该块中。如果特殊方块在里面,这直接递归下去求即可,如果不在,这根据分割的四个方块的不同位置,把右下角、左下角、右上角或者左上角的方格标记为特殊方块,然后继续递归。在递归函数里,还要有一个变量s来记录边的方格数,每次对方块进行划分时,边的方格数都会减半,这个变量是为了方便判断特殊方格的位置。

    #include<bits/stdc++.h>
    using namespace std;
    int tile=1;                   //L型骨牌的编号(递增)
    int board[100][100];  //棋盘
    void chessBoard ( int tr, int tc, int dr, int dc, int size )
    {
        if ( size==1 )    //棋盘方格大小为1,说明递归到最里层
            return;
        int t=tile++;     //每次递增1
        int s=size/2;    //棋盘中间的行、列号(相等的)
        //检查特殊方块是否在左上角子棋盘中
        if ( dr<tr+s && dc<tc+s )              //在
            chessBoard ( tr, tc, dr, dc, s );
        else         //不在,将该子棋盘右下角的方块视为特殊方块
        {
            board[tr+s-1][tc+s-1]=t;
            chessBoard ( tr, tc, tr+s-1, tc+s-1, s );
        }
        //检查特殊方块是否在右上角子棋盘中
        if ( dr<tr+s && dc>=tc+s )               //在
            chessBoard ( tr, tc+s, dr, dc, s );
        else          //不在,将该子棋盘左下角的方块视为特殊方块
        {
            board[tr+s-1][tc+s]=t;
            chessBoard ( tr, tc+s, tr+s-1, tc+s, s );
        }
        //检查特殊方块是否在左下角子棋盘中
        if ( dr>=tr+s && dc<tc+s )              //在
            chessBoard ( tr+s, tc, dr, dc, s );
        else            //不在,将该子棋盘右上角的方块视为特殊方块
        {
            board[tr+s][tc+s-1]=t;
            chessBoard ( tr+s, tc, tr+s, tc+s-1, s );
        }
        //检查特殊方块是否在右下角子棋盘中
        if ( dr>=tr+s && dc>=tc+s )                //在
            chessBoard ( tr+s, tc+s, dr, dc, s );
        else         //不在,将该子棋盘左上角的方块视为特殊方块
        {
            board[tr+s][tc+s]=t;
            chessBoard ( tr+s, tc+s, tr+s, tc+s, s );
        }
    }
    
    int main()
    {
        int size;
        cin>>size;
        int index_x,index_y;
        cin>>index_x>>index_y;
        chessBoard ( 0,0,index_x,index_y,size );
        for ( int i=0; i<size; i++ )
        {
            for ( int j=0; j<size; j++ )
                cout<<board[i][j]<<"\t";
            cout<<endl;
        }
    }
    
    更多相关内容
  • U91193 棋盘覆盖 ▲ 有个重要的思想:为了达成分治的目的,要在没有真正特殊点的子棋盘内假设一个特殊点,以此出发才能继续分治 ▲ 此外,注意到在不同层函数(即不同大小的棋盘)之间,L型块编号应是递增的,但在同...
  • 主要介绍了Python3解决棋盘覆盖问题的方法,简单描述了棋盘覆盖问题的概念、原理及Python相关操作技巧,需要的朋友可以参考下
  • 棋盘覆盖算法python

    2019-11-15 21:16:22
    实现有面板,可输入边值然后根据边值生成棋盘
  • 在一个2^k*2^k个方格组成的棋盘中,恰有一个方格与其他方格不同...棋盘覆盖问题要求下图四种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任意2个L型骨牌不得重叠覆盖。 (仅供参考,请独立完成实验)
  • 完整代码可运行,有用户登录界面,登陆界面是可进行注册账号的登录界面,然后成功登录后可通过输入棋盘大小和特殊棋盘的位置点击create按钮,弹出新的窗口动态展示棋盘覆盖的过程
  • 贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告 课程...- 棋盘覆盖问题 二实验目的及要求 1熟悉递归算法编写 2理解分治算法的特点 3掌握分治算法的基本结构 三实验环境 Visual C++ 四实验内容 根据教材
  • 算法设计第三章棋盘覆盖问题设计报告,以规模K=3,下标x,y分别为1,2,进行展开设计,当然K,x,y值可以取其它的数值,完整运行代码,在我的博客文章里面,这里是设计,只给出核心代码
  • 主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
  • 棋盘覆盖的python实现

    2018-10-04 16:45:33
    棋盘覆盖问题是指,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
  • 利用Java编写的一款桌面应用,目的在于模拟和演示分治算法在残缺棋盘覆盖问题中的计算过程。该应用能调整棋盘大小和覆盖速度,每一类模块都有单独的颜色,4类模块的配色方案随机生成,而且还可以选择手动覆盖。
  • 之前做了一个算法作业,叫做棋盘覆盖,本来需要用c语言来编写的,但是因为我的c语言是半桶水(哈哈),所以索性就把网上的c语言写法改成JavaScript写法,并且把它的覆盖效果显示出来 二、关键代码 <!DOCTYPE ...
  • python实现棋盘覆盖图形界面,供大家参考,具体内容如下 一、解决方案和关键代码 工具: python tkinter库 问题描述:   在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格...
  • 功能包括: 1.自定义棋盘大小 2.随机产生残缺块位置(用特殊颜色标识) 3.用4种不同颜色标识不同的三角板(一种模板用一种颜色) 4.自动给出覆盖过程(速度可调) 5.对各种三角板进行自动计数和显示
  • 实验报告 学号 课程 0107 算法分析与设计 姓名 高行行 实验日期 专业班级 移动互联网实验时间 14-01 8:00-9:00 实验情况 备注 棋盘覆盖问题算法 #include> int tile=1; int board[100][100]; void ChessBoard(int tr...
  • 棋盘覆盖问题(C++版)

    2015-03-12 11:40:23
    用C++实现的棋盘覆盖问题,可以运行,应用到了面向对象的思想、算法设计、程序系统设计方法等,内含源代码。
  • 带界面的棋盘覆盖算法,很好的参考价值,有封装,需要解码一下。
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 棋盘覆盖算法代码

    2017-12-29 09:59:38
    棋盘覆盖方块版输出Java和棋盘覆盖数字版输出Java 问题描述 在一个2^k×2^k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种...
  • 棋盘覆盖算法.zip

    2019-11-09 10:25:07
    棋盘覆盖算法的C++实现源码, 包括一个Class类和一个主函数, 程序开始时,输入棋盘规格和特殊方格位置。 程序将输出覆盖棋盘的详细步骤。
  • 棋盘覆盖带界面的示例程序,采用java语言编写,用分治法的思想实现。 本人也是菜鸟一枚借鉴了别人的思想希望不要介意,共同学习,一起进步
  • 棋盘覆盖的代码

    2018-03-14 19:55:15
    算法课上讲的棋盘覆盖的代码,用于了解并掌握递归这一算法
  • 残缺棋盘覆盖问题的VC源代码及完整的实验报告
  • 描述棋盘覆盖算法的演示程序,辅助理解!
  • 棋盘覆盖(非递归)

    2014-09-07 16:57:35
    棋盘覆盖问题的非递归方法源代码,输出为棋盘格,C++,可运行
  • 分治法实现棋盘的“3-L形”完全覆盖,java实现。
  • 棋盘覆盖问题

    千次阅读 2022-03-12 12:28:30
    棋盘覆盖三种实现方法详解

    棋盘覆盖问题详解

       1.问题描述:
        请添加图片描述请添加图片描述

    方法一 分治法

    • 首先回忆一下分治法的适用条件
    • 1.问题规模缩小到一定程度后容易解决(当棋盘只有一个方格,则该方格必为特殊方格无需处理)。
    • 2.问题能够被划分为若干个规模较小的相同子问题(我们考虑将大棋盘划分为四个大小相同的小棋盘,但是存在一个问题划分后只有一个小棋盘内含有特殊方格为和原问题相同的子问题,其余三个不含有特殊方格,不能使用分治方法解决。稍后解释~~~)。
    • 3.子问题的解能够合并成为原问题的解(当小棋盘全部覆盖完毕,则原问题得到解决)。
    • 4.不存在相同子问题(每次划分得到的小棋盘各不相同)。

         解释2中的问题:
          当k>0时,我们把规模为2k * 2k的大棋盘划分为2(k-1) * 2(k-1)的四个小棋盘。
    请添加图片描述
          则此时的特殊方格位于四个棋盘其中之一,为了将其余的三个棋盘也同样转化成和原问题相同的棋盘,我们只需要根据划分后特殊棋盘的位置选择合适的骨牌放置在大棋盘的汇合处。如图:
    请添加图片描述
          这样就得到了四个和原问题相同的规模更小的子问题,再将子问题进行相同的处理,直到问题规模变为1直接返回。

    代码分析

    #include<bits/stdc++.h>
    #include<windows.h> 
    using namespace std;
    const int N=1100;
    int g[N][N]; //棋盘数组 
    int title=1; //骨牌编号 
    void SetColor(int fore = 7, int back = 0)
    {
    	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (back << 4) + fore);
    }//背景颜色 
    void solve(int tr,int tc,int dr,int dc,int size){
    	/*tr棋盘左上角行号,tc棋盘左上角列号,size棋盘宽度,dr特殊位置行号,dc特殊位置列号*/ 
    	if(size==1) return; //递归出口 
    	int t=title++; 
    	int s=size/2; //分割棋盘
    	//处理左上角部分 
    	if(dr<tr+s&&dc<tc+s){
    		solve(tr,tc,dr,dc,s);
    	}else{
    		g[tr+s-1][tc+s-1]=t;
    		solve(tr,tc,tr+s-1,tc+s-1,s);
    	}
    	//处理右上角部分 
    	if(dr<tr+s&&dc>=tc+s){
    		solve(tr,tc+s,dr,dc,s);
    	}else{
    		g[tr+s-1][tc+s]=t;
    		solve(tr,tc+s,tr+s-1,tc+s,s);
    	}
    	//处理右下角部分 
    	if(dr>=tr+s&&dc>=tc+s){
    		solve(tr+s,tc+s,dr,dc,s);
    	}else{
    		g[tr+s][tc+s]=t;
    		solve(tr+s,tc+s,tr+s,tc+s,s);
    	}
    	//处理左下角部分 
    	if(dr>=tr+s&&dc<tc+s){
    		solve(tr+s,tc,dr,dc,s);
    	}else{
    		g[tr+s][tc+s-1]=t;
    		solve(tr+s,tc,tr+s,tc+s-1,s);
    	}
    }
    int main(){
    	int a,b,legth;
    	cin>>a>>b>>legth;
    	solve(1,1,a,b,legth);
    	for(int i=1;i<=legth;i++){
    		for(int j=1;j<=legth;j++){
    			if(g[i][j]){
    				SetColor(0, g[i][j]);
    				printf("%4d",g[i][j]);
    			}
    			else{
    				printf("%4d",g[i][j]);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }
    

    代码思路:
      输入棋盘左上角的坐标(此处为(1,1))和棋盘的宽度,然后借助solve函数进行处理,每次将原棋盘分割为4个小棋盘,然后根据左上、右上、右下、左下的顺时针顺序进行处理,如果特殊方格存在于该小棋盘则直接递归处理该小棋盘。否则,先将该小棋盘的指定位置覆盖上骨牌转换成和原问题相同的问题后在进行分割处理。

    方法二 非递归化

    借助队列实现

    实现思路
      借助结构体存储棋盘相关信息(左上角的坐标,特殊方格的位置坐标,棋盘的宽度),先将原棋盘入队列,每次取出队首的元素,当队首元素的规模不为1时,对其进行处理,再将分割后的子棋盘入队,不断循环直至队列为空。

    #include<bits/stdc++.h>
    #include<windows.h>
    void SetColor(int fore = 7, int back = 0)
    {
    	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (back << 4) + fore);
    }//背景颜色 
    using namespace std;
    const int N=1100;
    int g[N][N];
    int title=1;
    struct Point{
    	int x;
    	int y;
    	int tx;
    	int ty;
    	int size;
    }p;
    queue<Point> q;
    int main(){
    	int a,b,length;
    	cin>>a>>b>>length;
    	q.push({1,1,a,b,length});
    	while(!q.empty()){
    		Point c=q.front(); //取出队首元素 
    		int tr,tc,dr,dc;
    		if(c.size!=1){
    			int s=c.size/2;
    			int t=title++;
    			tr=c.x;
    			tc=c.y;
    			dr=c.tx;
    			dc=c.ty;
    		if(dr<tr+s&&dc<tc+s){
    			q.push({tr,tc,dr,dc,s});
    	}else{
    		g[tr+s-1][tc+s-1]=t;
    		q.push({tr,tc,tr+s-1,tc+s-1,s});
    	}
    	
    	if(dr<tr+s&&dc>=tc+s){
    		q.push({tr,tc+s,dr,dc,s});
    	}else{
    		g[tr+s-1][tc+s]=t;
    		q.push({tr,tc+s,tr+s-1,tc+s,s});
    	}
    	
    	if(dr>=tr+s&&dc>=tc+s){
    		q.push({tr+s,tc+s,dr,dc,s});
    	}else{
    		g[tr+s][tc+s]=t;
    		q.push({tr+s,tc+s,tr+s,tc+s,s});
    	}
    	
    	if(dr>=tr+s&&dc<tc+s){
    		q.push({tr+s,tc,dr,dc,s});
    	}else{
    		g[tr+s][tc+s-1]=t;
    		q.push({tr+s,tc,tr+s,tc+s-1,s});
    	}
    			q.pop();
    		}else{
    			//q.pop();
    			break; 
    		}
    	}
    	
    	for(int i=1;i<=length;i++){
    		for(int j=1;j<=length;j++){
    			if(g[i][j]){
    				SetColor(0, g[i][j]);
    				printf("%4d",g[i][j]);
    			}
    			else{
    				printf("%4d",g[i][j]);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }
    

    注: 在处理时发现,只要此时队首元素的规模为1,则队列中其余元素的规模全为1都无需进行处理,因此当出现队首元素为1时可以直接终止循环,无需等到队列为空。

    借助栈实现

    实现思路
      借助结构体存储棋盘相关信息(左上角的坐标,特殊方格的位置坐标,棋盘的宽度),先将原棋盘入栈,每次取出栈顶的元素,当栈顶元素的规模不为1时,对其进行处理,再将分割后的子棋盘入栈,不断循环直至栈为空。

    #include<bits/stdc++.h>
    #include<windows.h> 
    using namespace std;
    const int N=1100;
    int g[N][N];
    int title=1;
    void SetColor(int fore = 7, int back = 0)
    {
    	SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (back << 4) + fore);
    }//背景颜色 
    struct Point{
    	int x;
    	int y;
    	int tx;
    	int ty;
    	int size;
    }p;
    stack<Point> st;
    int main(){
    	int a,b,length;
    	cin>>a>>b>>length;
    	st.push({1,1,a,b,length});
    	
    	while(!st.empty()){
    		Point c=st.top();
    		int tr,tc,dr,dc;
    		if(c.size!=1){
    			int s=c.size/2;
    			int t=title++;
    			tr=c.x;
    			tc=c.y;
    			dr=c.tx;
    			dc=c.ty;
    			st.pop();
    		if(dr<tr+s&&dc<tc+s){
    			st.push({tr,tc,dr,dc,s});
    	}else{
    		g[tr+s-1][tc+s-1]=t;
    		st.push({tr,tc,tr+s-1,tc+s-1,s});
    	}
    	
    	if(dr<tr+s&&dc>=tc+s){
    		st.push({tr,tc+s,dr,dc,s});
    	}else{
    		g[tr+s-1][tc+s]=t;
    		st.push({tr,tc+s,tr+s-1,tc+s,s});
    	}
    	
    	if(dr>=tr+s&&dc>=tc+s){
    		st.push({tr+s,tc+s,dr,dc,s});
    	}else{
    		g[tr+s][tc+s]=t;
    		st.push({tr+s,tc+s,tr+s,tc+s,s});
    	}
    	
    	if(dr>=tr+s&&dc<tc+s){
    		st.push({tr+s,tc,dr,dc,s});
    	}else{
    		g[tr+s][tc+s-1]=t;
    		st.push({tr+s,tc,tr+s,tc+s-1,s});
    	}
    		}else{
    			st.pop();
    			//break;
    		}
    	}
    	
    	for(int i=1;i<=length;i++){
    		for(int j=1;j<=length;j++){
    			if(g[i][j]){
    				SetColor(0, g[i][j]);
    				printf("%4d",g[i][j]);
    			}
    			else{
    				printf("%4d",g[i][j]);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }
    

    附加
      为了帮助大家清晰的理解棋盘覆盖,三种实现方法的具体步骤,笔者采用python编写了可视化的小工具。
    棋盘覆盖工具.

    展开全文
  • 【算法】棋盘覆盖详解,基础教程~

    千次阅读 2021-11-25 18:20:26
    简单讲解棋盘覆盖的基本原理,另附实现代码。

    棋盘覆盖分析与实现

    一、什么是棋盘覆盖?

       在一个 2^k * 2^k 个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为一个特殊方格,且称该棋盘为一个特殊棋盘。显然,特殊方格在棋盘上出现的位置有 4^k 种情况,即k>=0,有4^k种不同的特殊棋盘。

        棋盘覆盖:用4种不同形态的L型骨牌覆盖一个给定的特殊棋盘(即特殊方格的位置已经确定了)上除特殊方格外的所有方格,且任何两个L型骨牌不得重复覆盖。按照规则,我们很容易知道,在2^k*2^k的棋盘覆盖中,用到的L型骨盘数恰为(4^k-1)/3,即(所有方格个数-特殊方格个数)/3。  

       如下图,为k=2时的一个特殊棋盘(相同颜色的三个小方格组成一个L型骨牌)和4种不同形态的L型骨牌,蓝色的为特殊方格:

    在这里插入图片描述
                                                                                 k=2时的一个特殊棋盘

    在这里插入图片描述

    二、实现棋盘覆盖的思路和方法

          棋盘覆盖实现的基本方法为分治法,是设计棋盘覆盖的一个简捷的算法,那什么是分治法?

          分治法的基本思路:将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归地解决这些子问题,然后将各个子问题的解合并得到原问题的解。简单地说,就是将规模为n的问题自顶向下分解,直到子问题分解到足够小,可以容易解决时,再自底向上合并,从而得到原来的解。

          分析思路:当k>0时,将2^k*2^k棋盘分割为4个2^(k-1)*2^(k-1)子棋盘,如图所示:

    在这里插入图片描述

           特殊方格必定位于这四个小棋盘中,其余三个子棋盘没有特殊方格,为了将这三个无特殊方格的子棋盘转换为特殊棋盘,我们可以用一个L型骨盘覆盖这三个较小棋盘的会合处,如图所示:

    在这里插入图片描述

          从图上可以看出,这三个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将问题分解为4个较小规模的棋盘覆盖问题。递归地使用这种分割方法,直至棋盘简化为1*1棋盘,就结束递归。

          实现这种算法的分析:每次都对分割后的四个小方块进行判断,判断特殊方格是否在里面。这里的判断的方法是每次先记录下整个大方块的左上角方格的行列坐标,然后再与特殊方格坐标进行比较,就可以知道特殊方格是否在该块中。如果特殊方块在里面,这直接递归下去求即可,如果不在,这根据分割的四个方块的不同位置,把右下角、左下角、右上角或者左上角的方格标记为特殊方块,然后继续递归。在递归函数里,还要有一个变量s来记录边的方格数,每次对方块进行划分时,边的方格数都会减半,这个变量是为了方便判断特殊方格的位置。

    三、棋盘覆盖的具体实现代码

    #include <stdio.h>
    #include <stdlib.h>
    
    int num = 0;
    int Matrix[100][100];
    void chessBoard(int tr, int tc, int dr, int dc, int size);
    int main()
    {
        int size,r,c,row,col;
        printf("请输入棋盘的行列号");
        scanf("%d",&size);
        printf("请输入特殊方格的行列号");
        scanf("%d %d",&row,&col);
        chessBoard(0,0,row,col,size);
    
        for (r = 0; r < size; r++)
        {
            for (c = 0; c < size; c++)
            {
                printf("%2d ",Matrix[r][c]);
            }
            printf("\n");
        }
    
        return 0;
    }
    
    void chessBoard(int tr, int tc, int dr, int dc, int size)
    {
        if (size==1) 
        	return;
        int s = size/2;     //分割棋盘
        int t = ++num;      //L型骨牌号
        
        //覆盖左上角子棋盘
        if (dr < tr + s && dc < tc +s)                
        {
            //特殊方格在此棋盘中
            chessBoard(tr,tc,dr,dc,s);
        }
        else            //此棋盘中无特殊方格
        {
            //用t号L型骨牌覆盖右下角
            Matrix[tr+s-1][tc+s-1] = t;
            //覆盖其余方格
            chessBoard(tr,tc,tr+s-1,tc+s-1,s);
        }
        
        //覆盖右上角子棋盘
        if (dr < tr + s && dc >= tc + s )           
        {
            //特殊方格在此棋盘中
            chessBoard(tr,tc+s,dr,dc,s);
        }
        else            //此棋盘中无特殊方格
        {
            //用t号L型骨牌覆盖左下角
            Matrix[tr+s-1][tc+s] = t;
            //覆盖其余方格
            chessBoard(tr,tc+s,tr+s-1,tc+s,s);
        }
        
         //覆盖左下角子棋盘
        if (dr >= tr + s && dc < tc + s)
        {
            //特殊方格在此棋盘中
            chessBoard(tr+s,tc,dr,dc,s);
        }
        else
        {
            //用t号L型骨牌覆盖右上角
            Matrix[tr+s][tc+s-1] = t;
            //覆盖其余方格
            chessBoard(tr+s,tc,tr+s,tc+s-1,s);
        }
        
         //覆盖右下角子棋盘
        if (dr >= tr + s && dc >= tc + s)
        {
              //特殊方格在此棋盘中
            chessBoard(tr+s,tc+s,dr,dc,s);
        }
        else
        {
            //用t号L型骨牌覆盖左上角
            Matrix[tr+s][tc+s] = t;
            //覆盖其余方格
            chessBoard(tr+s,tc+s,tr+s,tc+s,s);
        }
    
    }
    

    运行结果如下图:
    在这里插入图片描述
    上述算法中用一个二维整型数组 Matrix 表示棋盘,Matrix[0][0]是棋盘的左上角方格。num 是一个全局整型变量,用来表示 L 型骨牌的编号,其初始值为1。算法的输入参数是:

    tr棋盘左上角方格的行号
    tc棋盘左上角方格的列号
    dr特殊方格的行号
    dc特殊方格的列号
    sizesize=2^k,棋盘规格为 2^k * 2^k

    Reference:
    1、https://www.cnblogs.com/crx234/p/5988055.html
    2、计算机算法设计与分析王晓东第五版。(如果需要对应课后习题答案的话可以评论区留言,我会发链接哒)

    展开全文
  • 棋盘覆盖问题详解(递归)

    千次阅读 2022-03-22 11:24:35
    棋盘覆盖问题详解(java,分治,递归,非递归)

    棋盘覆盖问题详解(分治,非递归)

    (代码由 java 编写)

    1.问题描述

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gU5PZFCa-1647919462709)(file:///C:\Users\27699\AppData\Local\Temp\ksohtml\wpsA0F9.tmp.jpg)]
    如图(a)所示,k>0时,有一个2k×2k的棋盘,棋盘中任意位置有一个特殊的方格,要求利用图(b)中的4中L型骨牌覆盖图(a)除特殊方格以外的区域,要求所有区域都要覆盖,并且骨牌不能重叠。

    2.解题思路

    可将2k×2k的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后,由于原棋盘只有一个特殊方格,所以,这4个子棋盘中只有一个子棋盘包含该特殊方格,其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘,以便采用递归方法求解,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如图(b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略,直至将棋盘分割为1×1的子棋盘。

    这一大堆文字是不是看着就很难受,那就别看了,

    假设有一个8*8的棋盘,初始位置(2,7)处有一个棋子,那么如何填充呢,简单点说对于一共就三步

    ①:把nn的棋盘分成四个n/2 * n/2的小棋盘(例子中也就是分成四个44的棋盘)
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-V6eCYZzl-1647919462711)(C:\Users\27699\AppData\Roaming\Typora\typora-user-images\image-20220321115103750.png)]
    ②:把没有棋子的棋盘块上放上棋子,放到四个棋盘块接壤的角落(本例中也就是(4,4)(5,4)(5,5))
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-deDMCOnn-1647919462711)(C:\Users\27699\AppData\Roaming\Typora\typora-user-images\image-20220321115431127.png)]

    ③:再把分出的小棋盘块再次调用上面两步,如果子棋盘长宽=2,那么直接填满
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KluAEpx7-1647919462712)(C:\Users\27699\AppData\Roaming\Typora\typora-user-images\image-20220321115942321.png)]

    听懂了那我就直接上代码

    import java.util.Scanner;
    
    public class 棋盘覆盖 {
        public static int i=1;
        public static int QP[][];
        public static void main(String[] args) {
            Scanner scanner=new Scanner (System.in);
            int size = scanner.nextInt ();
            QP=new int[size][size];
            int ZuoBiaoX = scanner.nextInt ()-1;
            int ZuoBiaoY = scanner.nextInt ()-1;
            棋盘覆盖 (0,0,ZuoBiaoX,ZuoBiaoY,size);
            Print (QP);
        }
        public static void 棋盘覆盖(int tx,int ty ,int qx ,int qy,int size){
            int numqxqy=QP[qx][qy];
            if (size==2){
                QP[tx][ty]=i;
                QP[tx+1][ty]=i;
                QP[tx][ty+1]=i;
                QP[tx+1][ty+1]=i;
                QP[qx][qy]=numqxqy;
                i++;
                return;
            }
            else {
                int sizeA=size/2;
                int qx1 = tx+sizeA-1, qx2 = tx+sizeA, qx3 = tx+sizeA-1, qx4 = tx+sizeA, qy1 = ty +sizeA-1, qy2 = ty +sizeA-1, qy3 = ty +sizeA, qy4 = ty +sizeA;
                if (qx<=tx+sizeA-1){
                    if (qy<=ty+size-1){
                        qx1=qx;
                        qy1=qy;
                        QP[qx2][qy2]=i;
                        QP[qx3][qy3]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                    else {
                        qx3=qx;
                        qy3=qy;
                        QP[qx2][qy2]=i;
                        QP[qx1][qy1]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                }
                else {
                    if (qy<=ty+size-1){
                        qx2=qx;
                        qy2=qy;
                        QP[qx1][qy1]=i;
                        QP[qx3][qy3]=i;
                        QP[qx4][qy4]=i;
                        i++;
                    }
                    else {
                        qx4=qx;
                        qy4=qy;
                        QP[qx2][qy2]=i;
                        QP[qx3][qy3]=i;
                        QP[qx1][qy1]=i;
                        i++;
                    }
                }
                棋盘覆盖 (tx,ty,qx1,qy1,sizeA);
                棋盘覆盖 (tx+sizeA,ty,qx2,qy2,sizeA);
                棋盘覆盖 (tx,ty+sizeA,qx3,qy3,sizeA);
                棋盘覆盖 (tx+sizeA,ty+sizeA,qx4,qy4,sizeA);
            }
        }
        public static void Print(int Num[][]){
            for (int i =0;i<Num.length;i++){
                for (int j =0;j<Num[0].length;j++){
                    System.out.print (Num[i][j]+"\t");
                }
                System.out.println ();
            }
        }
    }
    
    

    接下来我们解释一下这个代码

    首先创建一个全局变量QP,这个二维数组代表着我们的棋盘,二维数组上相同的数字就是我们的L形骨牌,i代表着我们填入期盼的棋子,一般三个一填,因为三个棋子构成一个L型骨牌。

    public static int i=1;
    public static int QP[][];
    

    获取输入,size就是棋盘大小,ZuoBiaoX就是初始棋子的横坐标,ZuoBiaoY就是初始棋子的纵坐标。为什么要-1呢,在数组中是从0开始,实际我们习惯的计数是从1开始。

    Scanner scanner=new Scanner (System.in);
    int size = scanner.nextInt ();
    QP=new int[size][size];
    int ZuoBiaoX = scanner.nextInt ()-1;
    int ZuoBiaoY = scanner.nextInt ()-1;
    

    之后调用我们的棋盘覆盖方法,这个方法遵循了刚才说的三步

    如果size==2,那就直接给棋盘剩下的三个格子填满i,然后return。

    if (size==2){
        QP[tx][ty]=i;
        QP[tx+1][ty]=i;
        QP[tx][ty+1]=i;
        QP[tx+1][ty+1]=i;
        QP[qx][qy]=numqxqy;
        i++;
        return;
    }
    

    否则我们把棋盘分成四块,先把中心接壤部分填上L型骨牌

    int sizeA=size/2;
    int qx1 = tx+sizeA-1, qx2 = tx+sizeA, qx3 = tx+sizeA-1, qx4 = tx+sizeA,
    qy1 = ty +sizeA-1, qy2 = ty +sizeA-1, qy3 = ty +sizeA, qy4 = ty +sizeA;
    if (qx<=tx+sizeA-1){
        if (qy<=ty+size-1){
            qx1=qx;
            qy1=qy;
            QP[qx2][qy2]=i;
            QP[qx3][qy3]=i;
            QP[qx4][qy4]=i;
            i++;
        }
        else {
            qx3=qx;
            qy3=qy;
            QP[qx2][qy2]=i;
            QP[qx1][qy1]=i;
            QP[qx4][qy4]=i;
            i++;
        }
    }
    else {
        if (qy<=ty+size-1){
            qx2=qx;
            qy2=qy;
            QP[qx1][qy1]=i;
            QP[qx3][qy3]=i;
            QP[qx4][qy4]=i;
            i++;
        }
        else {
            qx4=qx;
            qy4=qy;
            QP[qx2][qy2]=i;
            QP[qx3][qy3]=i;
            QP[qx1][qy1]=i;
            i++;
        }
    

    然后分别对四个子棋盘递归,也就是16 * 16变四个 8 * 8,然后变16个4 * 4,然后变32个2 * 2,然后这32个2 * 2分别填满。

    棋盘覆盖 (tx,ty,qx1,qy1,sizeA);
    棋盘覆盖 (tx+sizeA,ty,qx2,qy2,sizeA);
    棋盘覆盖 (tx,ty+sizeA,qx3,qy3,sizeA);
    棋盘覆盖 (tx+sizeA,ty+sizeA,qx4,qy4,sizeA);
    

    最后调用函数输出

    public static void Print(int Num[][]){
        for (int i =0;i<Num.length;i++){
            for (int j =0;j<Num[0].length;j++){
                System.out.print (Num[i][j]+"\t");
            }
            System.out.println ();
        }
    }
    

    我们来看一下输出,基本上没什么问题,如果看了我的帖子还是没看明白,搞个4*4的棋盘按照上面的几步走一遍就懂了。
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-mxZxf4Cn-1647919462714)(C:\Users\27699\AppData\Roaming\Typora\typora-user-images\image-20220321122845470.png)]

    3.时间复杂度

    这个的时间复杂度还是挺难算的

    首先假设来了的2k*2k的棋盘,设T(k)是覆盖一个2^k * 2^k棋盘所需的时间,则从算法的分治策略可知,T(k)满足如下递归方程:
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kBx8XmDb-1647919462714)(file:///C:\Users\27699\AppData\Local\Temp\ksohtml\wps373B.tmp.jpg)]

    当k=1就是1*1的棋盘时间复杂度就是1,所以时间复杂度就是4^k

    那么在看k*k的棋盘上,时间复杂度就是4log2k=2k

    4.棋盘覆盖非递归算法

    Hanoi塔问题是经典的递归算法,按照栈内元素出一进三的思想(具体解题方法可以参考{(27条消息) 汉诺塔Java递归和非递归算法解析_Addam Holmes的博客-CSDN博客})那么我们的棋盘覆盖问题可以用栈模拟递归吗。

    Of course Yes!!!!!!!!

    先上代码

    import java.util.Scanner;
    import java.util.Stack;
    
    public class 棋盘覆盖非递归 {
        public static int i=1;
        public static int QP[][];
        public static void main(String[] args) {
            Scanner scanner=new Scanner (System.in);
            int size = scanner.nextInt ();
            QP=new int[size][size];
            int ZuoBiaoX = scanner.nextInt ()-1;
            int ZuoBiaoY = scanner.nextInt ()-1;
            Stack<QPState> stack = new Stack<> ();
            QPState QP1 = new QPState (0,0,ZuoBiaoX,ZuoBiaoY,size);
            stack.push (QP1);//首元素入栈
            while (stack.size ()>0){
                QPState QPLinShi = stack.pop ();
                if(QPLinShi.size==2){
                    int numqxqy=QP[QPLinShi.qx][QPLinShi.qy];
                    QP[QPLinShi.tx][QPLinShi.ty]=i;
                    QP[QPLinShi.tx+1][QPLinShi.ty]=i;
                    QP[QPLinShi.tx][QPLinShi.ty+1]=i;
                    QP[QPLinShi.tx+1][QPLinShi.ty+1]=i;
                    QP[QPLinShi.qx][QPLinShi.qy]=numqxqy;
                    i++;
                }
                else {
                    int sizeA=QPLinShi.size/2;
                    int qx1 = QPLinShi.tx+sizeA-1;
                    int qx2 = QPLinShi.tx+sizeA;
                    int qx3 =QPLinShi. tx+sizeA-1;
                    int qx4 = QPLinShi.tx+sizeA;
                    int qy1 = QPLinShi.ty +sizeA-1;
                    int qy2 = QPLinShi.ty +sizeA-1;
                    int qy3 = QPLinShi.ty +sizeA;
                    int qy4 = QPLinShi.ty +sizeA;
                    if (QPLinShi.qx<=QPLinShi.tx+sizeA-1){
                        if (QPLinShi.qy<=QPLinShi.ty+size-1){
                            qx1=QPLinShi.qx;
                            qy1=QPLinShi.qy;
                            QP[qx2][qy2]=i;
                            QP[qx3][qy3]=i;
                            QP[qx4][qy4]=i;
                            i++;
                        }
                        else {
                            qx3=QPLinShi.qx;
                            qy3=QPLinShi.qy;
                            QP[qx2][qy2]=i;
                            QP[qx1][qy1]=i;
                            QP[qx4][qy4]=i;
                            i++;
                        }
                    }
                    else {
                        if (QPLinShi.qy<=QPLinShi.ty+size-1){
                            qx2=QPLinShi.qx;
                            qy2=QPLinShi.qy;
                            QP[qx1][qy1]=i;
                            QP[qx3][qy3]=i;
                            QP[qx4][qy4]=i;
                            i++;
                        }
                        else {
                            qx4=QPLinShi.qx;
                            qy4=QPLinShi.qy;
                            QP[qx2][qy2]=i;
                            QP[qx3][qy3]=i;
                            QP[qx1][qy1]=i;
                            i++;
                        }
                    }
                    QPState QPLinShi1 = new QPState (QPLinShi.tx,QPLinShi.ty,qx1,qy1,sizeA);
                    QPState QPLinShi2 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty,qx2,qy2,sizeA);
                    QPState QPLinShi3 = new QPState (QPLinShi.tx,QPLinShi.ty+sizeA,qx3,qy3,sizeA);
                    QPState QPLinShi4 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty+sizeA,qx4,qy4,sizeA);
                }
            }
            for (int i =0;i<QP.length;i++){
                for (int j =0;j<QP[0].length;j++){
                    System.out.print (QP[i][j]+"\t");
                }
                System.out.println ();
            }
        }
    }
    class QPState{
        int tx;
        int ty;
        int qx;
        int qy;
        int size;
        public QPState(int tx,int ty ,int qx ,int qy,int size){
            this.tx = tx;
            this.ty = ty;
            this.qx = qx;
            this.qy = qy;
            this.size = size;
        }
    }
    

    解释一下这个代码吧,作为一个面向对象语言,学java不会用对象那毫无疑问,学的毫无意义,对象使得java在某些地方变得非常适合写算法。在这个题我们也用到这个方法,要用栈模拟递归,所以我们需要对栈内元素进行某些设定。设置一个类QPState,这个类代表着一个原棋盘的子棋盘。tx,ty是子棋盘左下角在原来的大棋盘上的坐标,qx,qy是子棋盘上已有棋子的坐标,size是子棋盘的大小。

    class QPState{
        int tx;
        int ty;
        int qx;
        int qy;
        int size;
        public QPState(int tx,int ty ,int qx ,int qy,int size){
            this.tx = tx;
            this.ty = ty;
            this.qx = qx;
            this.qy = qy;
            this.size = size;
        }
    }
    

    继续啊,定义一个栈,获取到的元素封装成刚才定义的QPState,然后入栈

    int size = scanner.nextInt ();
    QP=new int[size][size];
    int ZuoBiaoX = scanner.nextInt ()-1;
    int ZuoBiaoY = scanner.nextInt ()-1;
    Stack<QPState> stack = new Stack<> ();
    QPState QP1 = new QPState (0,0,ZuoBiaoX,ZuoBiaoY,size);
    

    之后当有size=2的子棋盘就输出,否则就按照之前说多的方式一变四。

     while (stack.size ()>0){
                QPState QPLinShi = stack.pop ();
                if(QPLinShi.size==2){
                    int numqxqy=QP[QPLinShi.qx][QPLinShi.qy];
                    QP[QPLinShi.tx][QPLinShi.ty]=i;
                    QP[QPLinShi.tx+1][QPLinShi.ty]=i;
                    QP[QPLinShi.tx][QPLinShi.ty+1]=i;
                    QP[QPLinShi.tx+1][QPLinShi.ty+1]=i;
                    QP[QPLinShi.qx][QPLinShi.qy]=numqxqy;
                    i++;
                }
                else {
                    int sizeA=QPLinShi.size/2;
                    int qx1 = QPLinShi.tx+sizeA-1;
                    int qx2 = QPLinShi.tx+sizeA;
                    int qx3 =QPLinShi. tx+sizeA-1;
                    int qx4 = QPLinShi.tx+sizeA;
                    int qy1 = QPLinShi.ty +sizeA-1;
                    int qy2 = QPLinShi.ty +sizeA-1;
                    int qy3 = QPLinShi.ty +sizeA;
                    int qy4 = QPLinShi.ty +sizeA;
                    if (QPLinShi.qx<=QPLinShi.tx+sizeA-1){
                        if (QPLinShi.qy<=QPLinShi.ty+size-1){
                            qx1=QPLinShi.qx;
                            qy1=QPLinShi.qy;
                            QP[qx2][qy2]=i;
                            QP[qx3][qy3]=i;
                            QP[qx4][qy4]=i;
                            i++;
                        }
                        else {
                            qx3=QPLinShi.qx;
                            qy3=QPLinShi.qy;
                            QP[qx2][qy2]=i;
                            QP[qx1][qy1]=i;
                            QP[qx4][qy4]=i;
                            i++;
                        }
                    }
                    else {
                        if (QPLinShi.qy<=QPLinShi.ty+size-1){
                            qx2=QPLinShi.qx;
                            qy2=QPLinShi.qy;
                            QP[qx1][qy1]=i;
                            QP[qx3][qy3]=i;
                            QP[qx4][qy4]=i;
                            i++;
                        }
                        else {
                            qx4=QPLinShi.qx;
                            qy4=QPLinShi.qy;
                            QP[qx2][qy2]=i;
                            QP[qx3][qy3]=i;
                            QP[qx1][qy1]=i;
                            i++;
                        }
                    }
                    QPState QPLinShi1 = new QPState (QPLinShi.tx,QPLinShi.ty,qx1,qy1,sizeA);
                    QPState QPLinShi2 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty,qx2,qy2,sizeA);
                    QPState QPLinShi3 = new QPState (QPLinShi.tx,QPLinShi.ty+sizeA,qx3,qy3,sizeA);
                    QPState QPLinShi4 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty+sizeA,qx4,qy4,sizeA);
                }
            }
    
    }
                }
                QPState QPLinShi1 = new QPState (QPLinShi.tx,QPLinShi.ty,qx1,qy1,sizeA);
                QPState QPLinShi2 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty,qx2,qy2,sizeA);
                QPState QPLinShi3 = new QPState (QPLinShi.tx,QPLinShi.ty+sizeA,qx3,qy3,sizeA);
                QPState QPLinShi4 = new QPState (QPLinShi.tx+sizeA,QPLinShi.ty+sizeA,qx4,qy4,sizeA);
            }
        }
    
    
    最后输出。
    ```for (int i =0;i<QP.length;i++){
                for (int j =0;j<QP[0].length;j++){
                    System.out.print (QP[i][j]+"\t");
                }
                System.out.println ();
            }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,262
精华内容 4,904
关键字:

棋盘覆盖

友情链接: math.rar