精华内容
下载资源
问答
  • 2021-09-18 18:07:35

    简单描述:一个棋盘,有$2^k$×$2^k$个方格,其中有一个特殊方格,我想用4种L型骨牌覆盖这个棋盘。

    先用数学归纳法:

    (1)k=1时,有2×2个方格,其中有一个特殊方格,直接放一个L型骨牌就行——问题解决。

    (2)k=2时,有4×4个方格,其中有一个特殊方格,自己画图想想,也可以解决。

    (3)k=k时,也能分析。

    以一个4×4的方格为例,board[1][1]代表特殊方格。

    首先定义一下变量,tr表示棋盘左上角方格的行号,tc表示棋盘左上角方格的列号,dr表示特殊方格的行号,dc表示特殊方格的列号,size表示棋盘的边,tile=0先置为零,表示L型骨牌的编号

     /   ///

    代码如下:

    int [][]board=new int[100][100];
    public void ChessBoard(int tr,int tc,int dr,int dc,int size){
            int tile =0;
            int t=tile++;
            int s=size/2;
            if(size==1){
                return;
            }
        //第二象限
            if(dr<tr+s &&dc<tc+s){切一刀,分成四个象限,看(tr,tc),所代表的定义,永远是左上角的点
                                    第一象限如果没有特殊方格,把左下角置为特殊
                                     第二象限如果没有特殊方格,把右下角置为特殊
                                     第四象限如果没有特殊方格,把右上角置为特殊,同理。
                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);
            //(tr,tc)一直都是定义在左上角的点,递归的时候也是,不过表示的话,以第一象限为例
                意义上第一象限的左上角是(tr,tc),但是用(tr,tc+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);
    }
    
    
    

    以上是算法的实现,以下是我在学习过程中的一些理解:

    (1)先用二分法:int s=size/2,对棋盘进行二分,二分十字交叉的位置,把一个棋盘(一次递归过程)分成了四个象限,可以在四个象限中操作。

    (2)每个方格上方的坐标点,代表这个方格。

    (3)重点:理解tr,tc的意思,是每个划分区域的左上方,递归之后也是如此,但是需要用整个棋盘的左上方(tr,tc)表示。

    (4)if条件中dr与tr+s作比较,用来确定(dr,dc)的位置,从而确定划分特殊方格在每一个象限中的位置。

    (5)调用函数进行递归,每个参数要传正确了。

    更多相关内容
  • 棋盘覆盖算法python

    2019-11-15 21:16:22
    实现有面板,可输入边值然后根据边值生成棋盘
  • 棋盘覆盖算法

    千次阅读 2020-09-27 13:07:17
    棋盘覆盖算法 问题阐述 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除...

    棋盘覆盖算法

    问题阐述

    在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

    在这里插入图片描述

    求:请给出相应的覆盖方式。

    解题思路

    当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。

    特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如 (b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘1×1。

    在这里插入图片描述

    编程要点

    分治法的解题思路

    • 分解规模较大的问题
    • 得到若干个规模较小的子问题问题
    • 求解每个子问题
    • 合并得到原问题的解

    本题的要点分析

    • 分解棋盘的时候需要知道特殊格子的位置。
    • 本题采用数字表示L型的骨牌
    • 设置局部变量作为L型骨牌的表示,随着递归的层数不断的增加
    • 递归出口为当分割出数组的大小为1*1时

    解题步骤

    • 传入数组的行列地址(棋盘的首个元素的地址),和特殊格子的行列地址以及数组的大小
    • 分割二维数组,形成四块棋牌(通过改变传入数组大小size实现)
    • 依次判断左上,右上,左下,右下的棋盘是否为特殊棋盘(即存在特殊格子)
    • 如果是特殊棋盘,则做递归调用,改变实参重新设置数组的行列地址(都作为一个棋盘的首个元素的地址)
    • 如果不是特殊棋盘,便在相应的位置(对角线位置,如左上的棋盘对应位置为右下)设置数值将其变为特殊棋盘并做递归调用,改变实参重新设置数组的行列地址特殊格子的行列地址以及数组的大小

    源程序代码

    #include <stdio.h>
    #include <stdlib.h>
    #define MAXSIZE 200
    
    //棋盘覆盖问题
    
    int chess[MAXSIZE][MAXSIZE];
    int title;
    void CoverChess(int h_ad,int d_ad,int  r_index,int c_index ,int size){
        if(size==1)return ;//如果棋盘的大小小于1时结束递归
        int t=title++;//采用数字作为L型骨牌填充
        int s=size/2;//分裂棋盘
        //如果特殊格子在棋盘的左上方
        if(c_index<h_ad+s && r_index<d_ad+s){
                //就继续解决这块左上方的棋盘(特殊棋盘)
            CoverChess(h_ad,d_ad,r_index,c_index,s);
        }else{
            //如果棋盘不是特殊棋盘(即没有特殊格子)
            chess[d_ad+s-1][h_ad+s-1]=t;
            //那就将其变为特殊棋盘后,递归解决左上方棋盘
            CoverChess(h_ad,d_ad,d_ad+s-1,h_ad+s-1,s);
        }
    
    
        //如果特殊格子在棋盘的右上方
        if(c_index>=h_ad+s && r_index<d_ad+s){
                //就继续解决这块右上方的棋盘(特殊棋盘)
            CoverChess(h_ad+s,d_ad,r_index,c_index,s);
        }else{
            //如果棋盘不是特殊棋盘(即没有特殊格子)
            chess[d_ad+s-1][h_ad+s]=t;
            //那就将其变为特殊棋盘后,递归解决右上方棋盘
            CoverChess(h_ad+s,d_ad,d_ad+s-1,h_ad+s,s);
        }
    
    
        //如果特殊格子在棋盘的左下方
        if(c_index<h_ad+s && r_index>=d_ad+s){
                //就继续解决这块左下方的棋盘(特殊棋盘)
            CoverChess(h_ad,d_ad+s,r_index,c_index,s);
        }else{
            //如果棋盘不是特殊棋盘(即没有特殊格子)
            chess[d_ad+s][h_ad+s-1]=t;
            //那就将其变为特殊棋盘后,递归解决左下方棋盘
            CoverChess(h_ad,d_ad+s,d_ad+s,h_ad-1+s,s);
        }
    
        //如果特殊格子在棋盘的右下方
        if(c_index>=h_ad+s && r_index>=d_ad+s){
                //就继续解决这块右下方的棋盘(特殊棋盘)
            CoverChess(h_ad+s,d_ad+s,r_index,c_index,s);
        }else{
            //如果棋盘不是特殊棋盘(即没有特殊格子)
            chess[d_ad+s][h_ad+s]=t;
            //那就将其变为特殊棋盘后,递归解决右下方棋盘
            CoverChess(h_ad+s,d_ad+s,d_ad+s,h_ad+s,s);
        }
    
    }
    int main()
    {
        int r_index,c_index;
        int size;
    //    size=8
        printf("输入棋盘大小,满足log2(size)为整数\n");
        scanf("%d",&size);
        printf("输入特殊格子的所在位置\n");
        scanf("%d%d",&r_index,&c_index);
    //    r_index=3;c_index=3;
        chess[r_index-1][c_index-1]=-1;
        CoverChess(0,0,r_index-1,c_index-1,size);
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++)
                printf("%3d",chess[i][j]);
            printf("\n");
        }
    
    
        return 0;
    }
    
    

    时间复杂度分析

    在这里插入图片描述

    最后的时间复杂度为

    在这里插入图片描述

    运行结果

    在这里插入图片描述

    展开全文
  • 棋盘覆盖算法代码

    2017-12-29 09:59:38
    棋盘覆盖方块版输出Java和棋盘覆盖数字版输出Java 问题描述 在一个2^k×2^k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种...
  • ** 问题描述:**将一个2k×2k单元格的棋盘用四种L型的图形进行完全覆盖(不能覆盖红色格子,不能发生重复覆盖)。** 思考:**1)如何能够让计算机实现这种算法?2)棋盘的大小为什么要为2k×2k的单元格大小?任意的大小...

    **   问题描述:**将一个2k×2k单元格的棋盘用四种L型的图形进行完全覆盖(不能覆盖红色格子,不能发生重复覆盖)。

    **   思考:**1)如何能够让计算机实现这种算法?

    2)棋盘的大小为什么要为2k×2k的单元格大小?任意的大小可以吗?

    format,png

    程序实现:我们先假设一种简单的情况:当棋盘为4×4的规格大小时。(如图)

    format,png

    如果我们现在从棋盘的中间四个开始填充,那么中间四个格子必定有一个不会被填充,那么这个格子是哪个呢?我们通过画图分析,发现这个不会被填充的格子是左上方的那个格子,不然的话,左上方红色格子周围的空白格子就不会被不重复的覆盖完。

    format,png(错误填充)

    format,png(正确填充)

    我们发现中间四个方格中缺失的那一个所在区域正是红色方格所在区域(是不是所有的棋盘图中间四个方格都遵循这个规律呢?还是说这只是一个巧合?)很明显这是一个规律。

    当我们进行多次实验后,发现这种现象并不是一个巧合。当我们填充表格时,先找到它中间的四个方块进行填充,之后根据这四个方块的中心x轴和y轴把整个棋盘分为4个子棋盘,四个子棋盘中始终只有一个被填充的格子,因为有红色方格的那个子棋盘不会再被覆盖,其他三个子棋盘都会被覆盖上一个黄色的格子。当我们将棋盘分开后,分别再填充四个子棋盘的时候,我们会发现其实该子棋盘只是缩小版的原棋盘,我们就可以用同样的方法找棋盘的中心线和中心四个方格进行填充,当最后棋盘变成2×2大小的时候,我们就可以完成棋盘的覆盖。

    我们在解决此棋盘问题的时候,将棋盘一分为四,由繁入简的思想是一种很重要的算法思想-----分治算法。(五大常用算法有:1.递归分治;2.动态规划;3.贪心算法;4.回溯法;5.分支限界法)分治算法可以将问题逐步简化,当简化到可以求解问题的时候得到解。我们熟悉的一个分治算法就是二分检索查找算法。

    算法复杂度分析:我们定义该算法的时间复杂度为T(n)。当执行一次算法后生成四个更小规模的子问题T(n)=4T(n-1)。根据给定棋盘的大小为2k×2k,每次进行一次算法执行后,棋盘的规模会变小一倍,所以算法复杂度与棋盘大小相关。T(n)=T(k),当k>0时,T(k)=4T(k-1);当k=0时,T(k)=1。综上棋盘整体的复杂度为T(k)=O(4k)。

    我们开篇提出的两个问题都迎刃而解了吧。棋盘问题就是用分治算法解决;为什么要用2的整数次幂作为棋盘的大小呢?是为了分治划分棋盘来解决问题。

    写在最后:这是本人进入IT圈写下的第一篇文章,作为初学者,也借鉴了很多前辈的想法和文章然后自己写下来的一篇小文章。如果文章有不合理的地方,恳请大家指正。欢迎大家留言或者私信交流学习心得!

    展开全文
  • 棋盘覆盖算法(C语言)

    千次阅读 2021-10-16 15:46:10
    棋盘覆盖(C语言) 参考博客:https://blog.csdn.net/qq_40274351/article/details/79643213 问题描述 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊...

    棋盘覆盖(C语言)

    参考博客:https://blog.csdn.net/qq_40274351/article/details/79643213

    问题描述

    在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

    可行性分析

    2k×2k大小的棋盘,除去1个特殊位置外,一共有(4k-1)个空位置,需要用(4k-1)/3个L型骨牌来覆盖。

    • (4k-1)一定能被3整除?

    4k-1 = (2k)2 – 1 = (2k - 1)(2k + 1)

    (2k - 1)、2k、(2k + 1)是3个连续的自然数,而2k不可能被3整除,所以(2k - 1)和(2k + 1)二者必有1个是3的倍数。

    • (4k-1)个空位置必能用(4k-1)/3个L型骨牌来覆盖?

    可用归纳法证明。
    k = 1时: 4k-1个位置本身就是一个L型骨牌。
    k = 2时:22×22大小的棋盘可以分成4个2×2大小的子棋盘,其中特殊位置位于某一个子棋盘中,用一个L型骨牌覆盖其 他3个子棋盘的会合处,则对4个子棋盘,剩余的空位置都是一个L型骨牌。

    当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1子棋盘(a)所示。

    特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,如(b)所示,从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割,直至棋盘简化为棋盘k = 1。

    程序实现

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #define MAXSIZE 8
    int Board[MAXSIZE][MAXSIZE];
    int title=1;//全局序号
    
    //tr:棋盘左上角方格的行号
    //tc:棋盘左上角方格的列号
    //dr:特殊方格所在的行号
    //dc:特殊方格所在的列号
    //size:size=2^k 棋盘规格为2^k*2^k
    void ChessBoard(int tr,int tc,int dr,int dc,int size)
    {
        if(size==1)
            return;
        int s = size/2;//分割棋盘
        int t = title++;
        //覆盖左上角子棋盘
        if(dr <tr+s && dc<tc+s) //特殊方格在此棋盘中
            ChessBoard(tr,tc,dr,dc,s);
        else//特殊方格不在棋盘中
        {
            Board[tr+s-1][tc+s-1]=t;//用t号L型骨牌覆盖右下角
            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;//用t号L型骨牌覆盖左下角
            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;//用t号L型骨牌覆盖右上角
            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;//用t号L型骨牌覆盖左上角
            ChessBoard(tr+s,tc+s,tr+s,tc+s,s);//覆盖其余方格
        }
    
    }
    int main()
    {
        int i ,j;
        Board[0][1]=0;
        ChessBoard(0,0,2,3,MAXSIZE);
        for (i = 0;i<MAXSIZE;i++)
        {
            for (j=0;j<MAXSIZE;j++)
                printf("%5d",Board[i][j]);
            printf("\n");
        }
        return 0;
    }
    
    

    结果展示:

    展开全文
  • 贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告 课程...- 棋盘覆盖问题 二实验目的及要求 1熟悉递归算法编写 2理解分治算法的特点 3掌握分治算法的基本结构 三实验环境 Visual C++ 四实验内容 根据教材
  • 棋盘覆盖_skinj9g_棋盘覆盖_棋盘覆盖算法_源码.zip
  • 棋盘覆盖算法流程.doc

    2022-05-07 22:26:08
    棋盘覆盖算法流程.doc
  • c++算法之棋盘覆盖算法
  • 棋盘覆盖算法.zip

    2019-11-09 10:25:07
    棋盘覆盖算法的C++实现源码, 包括一个Class类和一个主函数, 程序开始时,输入棋盘规格和特殊方格位置。 程序将输出覆盖棋盘的详细步骤。
  • 棋盘覆盖算法.doc.doc

    2022-05-30 14:24:19
    棋盘覆盖算法.doc.doc
  • 在一个2^k*2^k个方格组成的棋盘中,恰有一个方格与其他方格不同...棋盘覆盖问题要求下图四种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任意2个L型骨牌不得重叠覆盖。 (仅供参考,请独立完成实验)
  • 描述棋盘覆盖算法的演示程序,辅助理解!
  • 算法设计第三章棋盘覆盖问题设计报告,以规模K=3,下标x,y分别为1,2,进行展开设计,当然K,x,y值可以取其它的数值,完整运行代码,在我的博客文章里面,这里是设计,只给出核心代码
  • 棋盘覆盖算法实现

    2013-08-01 17:57:46
    C++实现的棋盘覆盖算法 经典算法之一 对初学算法者帮助很大
  • 棋盘覆盖问题要求用如图(b)所示的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且骨牌之间不得有重叠。 (a) k=2时的一种棋盘 (b) 4种不同形状的L型骨牌 分析题目: 当看k>0时,将2k×2k ...
  • qipan_棋盘覆盖算法.zip

    2021-04-01 20:22:35
    分治法
  • python实现棋盘覆盖算法

    千次阅读 2018-05-13 11:13:52
    # coding:utf-8 ...# 棋盘宽度 size1 = pow(2, k) # L形块的初始值 mark = 0 # table初始化 table = [[-1 for x in range(size1)] for y in range(size1)] def chess(tr, tc, pr, pc, size): global mar...
  • 这是由本人编写的棋盘覆盖算法,希望对各位有用,让各位能够了解其中的原理
  • 编译器:Microsoft Visual Studio 2008 实现功能:棋盘覆盖算法的图形展示。 涉及知识:定时器、STL、基本MFC画图API、双缓冲贴图 推荐资料:孙鑫的VC++ 深入详解
  • 残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注重当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - ...
  • 1毫居里(1mCi)=()Bq。A.3.7×107B.3.7×108C.3.7×109D.3.7×1010为了尽可能提高反应堆的总输出功率,就需要进行功率展平,功率展平主要措施有()。A.燃料元件分区布氡的测量方法有()。A.瞬时测量法B....
  • java 棋盘覆盖算法

    2021-04-17 10:06:00
    /** 棋盘覆盖 */ public class Arithmetic { /** 被覆盖后显示的数字,会根据覆盖的顺序有所递增 */ private int counter = 0; /** 当前棋盘是否已经存在 */ private boolean hasMap = false; /** 棋盘数组 */ ...
  • JAVA算法:棋盘覆盖算法(经典算法问题) 经典算法问题:在一个2^k×2^k (k≥0)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中可能出现的位置有4^k种,因而有4^k...
  • 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一...在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,404
精华内容 2,961
关键字:

棋盘覆盖算法

友情链接: PROGRAME.rar