精华内容
下载资源
问答
  • 2021-05-25 08:42:31

    摘要:针对算法设计与分析课程难度较大、对学生编程能力要求较高的现状,通过对棋盘覆盖问题的分治算法求解过程进行互动教学设计,引导学生进行问题理解、算法设计、算法实现。特别是在算法实现环节,一行一行地动态展示程序的编写过程,同时充分考虑学生现有的编程基础,采用程序填空的形式降低学生编程难度,有助于消除学生的畏难心理,有效提高了学生的学习兴趣,同时锻炼了学生的计算思维。

    关键词:棋盘覆盖;递归;分治;互动教学

    中图分类号:TP301 文献标识码:A 文章编号:1009-3044(2016)35-0146-02

    Interactive Teaching Procedure of the “Divide and Conquer” Algorithm with the Problem of “Chess Board”

    LV Lan-lan, LI Ming

    (Department of Software Engineering, College of Electronic and Information Engineering, Hunan University of Science and Engineering, Yongzhou 425100, China)

    Abstract:The course of algorithm design and analysis is difficult to those students with poor programming ability. This paper describes the interactive teaching design of the “divide and conquer” algorithm with the problem of “chess board”, which includes directing students to understand the problem, design and implement the algorithm. Especially during the phase of algorithm implementation, we show the procedure of programming to students line by line. At the same time, we use “program completion” to make programming easy for students. It is help to eliminate students’ fear, inspire their interest and train their computational thinking.

    Key words: chess board; recursion; divide and conquer; interactive teaching

    1 引言

    λ惴ǖ难芯恳丫被公认为是计算机科学的基石,算法设计与分析课程也是我校软件工程专业的一门专业核心课程,学习算法的重要性毋庸置疑。但算法设计与分析课程具有难度大,对学生编程能力要求高的特点,不少学生望而却步。在教学过程中我们发现,虽然大部分学生能正确理解算法的思路,但是却不能以某种高级程序设计语言实现算法。针对学生这种“眼高手低”的现状,本文提出将“程序填空”这一程序设计类课程考试中常用的题型,应用到算法设计与分析课程日常教学中,通过实施互动教学降低课程难度、激发学生兴趣。我们以分治法求解棋盘覆盖问题为例,逐步引导学生完成从算法的思路解析到完整实现的全过程,聚焦从算法到程序的“最后一公里”。

    2 棋盘覆盖问题

    2.1 问题描述

    棋盘覆盖问题是许多国内教材[1-2]在阐述分治法时使用的一个经典案例,具体描述如下:

    在一个个方格组成的棋盘中,若恰有一个方格与其它方格不同,则称该方格为一特殊方格,称该棋盘为一特殊棋盘。图1为k=2时的一个特殊棋盘,其中特殊方格的位置是(1,2),用阴影表示。

    在棋盘覆盖问题中,要用图2中4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

    图棋盘覆盖问题的已知条件是在一个的棋盘上有一个特殊方格,因此算法的输入可以用来表示棋盘的大小,用(dr, dc)来表示特殊方格在棋盘中的位置。棋盘覆盖问题的输出结果是一个覆盖了L形骨牌的棋盘,如何表示三个方格被同一个L形骨牌覆盖称为关键。学生比较容易想到的方法是使用同一种颜色来填充被同一个L形骨牌覆盖的三个方格,这是一种形象化的思维方式。为了将数据抽象成程序设计语言方便处理的形式,可以从颜色在计算机中的存储形式(整数)出发,引导学生直接使用整数来填充表示被同一个L形骨牌覆盖的三个方格。这样就完成了棋盘覆盖问题中输入/输出数据的抽象,并且可以得到函数的原型:void ChessBoard(int size, int dr, int dc, int **board)。

    3.3.2 C++实现

    根据3.3.1中的数据抽象结果得到函数原型后,进行算法实现时,还有2个待解决的关键问题。第一,如何确定递归函数ChessBoard的停止条件。大部分学生认为是最简单的情况是当的时候,即:的棋盘中有一个特殊方格,此时剩余的3个方格刚好可以用一个L形骨牌来覆盖。但事实上更简单的情况是当的时候,即:的棋盘中有一个特殊方格,此时根本无需任何覆盖。因此可以通过提问的方式启发学生思考当的时候是不是最简单的情况。第二,在函数原型void ChessBoard(int size, int dr, int dc, int **board)中,仅有size这个参数并不能确定当前正在处理的是哪个子棋盘。虽然教材上给出的函数原型是void ChessBoard(int size, int tr, int tc, int dr, int dc, int **board),使用了每个子棋盘的左上角方格的位置(tr, tc)来标识当前所处理的子棋盘。但是要想到这一点其实并不容易,这是算法实现时的一个难点。

    目前,针对该难点我们在教学中采用的处理步骤是:(1)根据函数原型void ChessBoard(int size, int x, int y, int **board)实现算法,经测试程序运行结果不正确。(2)通过输出每一个L形骨牌覆盖后的棋盘,指导学生使用单步执行的调试方式查找出错原因。然后,根据出错原因在函数ChessBoard的参数表中增加标识子棋盘位置的参数tr和tc。(3)使用更新后的函数原型void ChessBoard(int size, int tr, int tc, int dr, int dc, int **board)重新实现算法,经测试程序运行结果正确。上述教学步骤的执行难点在于要求学生具有较强的程序调试能力和程序分析能力,但是相对教材中直接给出更新后的函数原型及源代码,上述处理步骤方法对学生来说过渡更自然、更符合学生的从易到难的认知规律。

    在第(1)、(3)步中实现算法时,在教学中我们采用了“程序填空”这一程序设计类课程期末考试试卷中常见的题型,来提供尽可能多的提示信息帮助学生完成从算法伪码到C++程序的过程,消除部分基础较差学生的畏难心理。下面仅给出当特殊方格位于右下角子棋盘时的“程序填空”范例,学生可依据填好空之后的程序快速写出处理其它3种情况的程序。其中,在学生进行程序填空时可以提供作为辅助信息。

    4 教学效果

    通^实施上述互动教学设计,在教学过程中引导学生进行问题理解、算法设计、算法实现。特别是在算法实现环节,有别于传统的将程序一次性展示在学生面前,手把手带领学生一行一行将程序写出来,顺应学生的思维方式来讲解,使学生能够看到算法实现的全过程,而不仅仅是算法实现的结果。同时,充分考虑学生现有的编程能力,采用程序填空的形式,既能激发学生兴趣,打破课堂沉闷,也能降低编程难度,有助于消除学生的畏难心理,让学生获得学习的成就感,有效提高了学生的学习兴趣,同时锻炼了学生的计算思维。

    5 结论

    分治算法采用“分而治之”的策略,将问题分解为规模较小的子问题,这些子问题互相独立且与原问题形式相同。分治策略递归地求解这些子问题,然后将各子问题的解合并得到原问题的解。其中的难点在于递归求解子问题,递归函数原型的设计成为关键,学生学习存在一定的困难。以棋盘覆盖这一较为形象的问题作为实例进行分析,对分治算法求解该问题的教学过程进行互动设计,能够深入浅出、形象地展现求解的方方面面,加深学生对于分治算法的理解,为学生进一步应用算法解决实际问题奠定基础,具有较好的教学效果。

    参考文献:

    [1] 王晓东. 计算机算法设计与分析[M].第4版. 北京:电子工业出版社,2012.

    [2] 赵端阳,刘福庆,石洗凡. 算法设计与分析――以ACM大学生程序设计竞赛在线题库为例[M]. 北京:清华大学出版社,2015.

    更多相关内容
  • 主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下
  • 用Visual C++6.0实现棋盘覆盖分治算法.txt
  • 分治算法求解棋盘覆盖问题

    1. 问题描述:

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

    2. 题解:

    在这里插入图片描述
    划分问题:将 2k∗2k的棋盘划分为 2k−1∗2k−1这样的子棋盘4块。
    递归求解:递归填充各个格子,填充分为四个情况,在下面会有解释,递归出口为 k=0也就是子棋盘方格数为1。
    递归填充的分为以下四种情况:
    (1)如果黑方块在左上子棋盘,则递归填充左上子棋盘;否则填充左上子棋盘的右下角,将右下角看做黑色方块,然后递归填充左上子棋盘。
    (2)如果黑方块在右上子棋盘,则递归填充右上子棋盘;否则填充右上子棋盘的左下角,将左下角看做黑色方块,然后递归填充右上子棋盘。
    (3)如果黑方块在左下子棋盘,则递归填充左下子棋盘;否则填充左下子棋盘的右上角,将右上角看做黑色方块,然后递归填充左下子棋盘。
    (4)如果黑方块在右下子棋盘,则递归填充右下子棋盘;否则填充右下子棋盘的右下角,将左上角看做黑色方块,然后递归填充右下子棋盘。
    详细过程如下图所示:
    在这里插入图片描述
    在这里插入图片描述

    // tr,tc分别表示正方形中最左上角的元素位置,dr,dc是黑块的位置,size为边长
    void chessBoard(int tr, int tc, int dr, int dc, int size)
    {
        if (size == 1) return;
        int t = tile++, // L型骨牌号
        s = size/2; // 分割棋盘
        // 覆盖左上角子棋盘
        if (dr < tr + s && dc < tc + s)
            // 特殊方格在此棋盘中
            chessBoard(tr, tc, dr, dc, s);
        else {// 此棋盘中无特殊方格
            // 用 t 号L型骨牌覆盖右下角
            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 {// 此棋盘中无特殊方格
            / 用 t 号L型骨牌覆盖左下角
            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 {// 用 t 号L型骨牌覆盖右上角
            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 {// 用 t 号L型骨牌覆盖左上角
            board[tr + s][tc + s] = t;
            / 覆盖其余方格
            chessBoard(tr+s, tc+s, tr+s, tc+s, s);
        }
    }
    

    3. 代码:

    参考链接:https://blog.csdn.net/q547550831/article/details/51541527

    #include <iostream>
    
    using namespace std;
    
    const int maxNum = 1 << 10;
    // 棋盘
    int chess[maxNum][maxNum];
    // L型牌编号
    int number;
    
    void chessBoard(int row, int column, int x, int y, int siz) {
        // 递归出口
        if(siz == 1) {
            return;
        }
    
        // 对半划分成2^(siz - 1) * 2^(siz - 1)的棋盘
        int s = siz / 2;
        // L型牌编号自增
        int t = ++number;
        // 中间点,以此判别(x,y)在哪个子棋盘中
        int centerRow = row + s;
        int centerColumn = column + s;
        // 黑色方格在左上子棋盘
        if(x < centerRow && y < centerColumn) {
            chessBoard(row, column, x, y, s);
        } else {
            // 不在则填充左上子棋盘的右下角
            chess[centerRow - 1][centerColumn - 1] = t;
            // 然后覆盖其他格子,注意这时(x,y)要看做已填充位置
            chessBoard(row, column, centerRow - 1, centerColumn - 1, s);
        }
    
        // 黑色方格在右上子棋盘
        if(x < centerRow && y >= centerColumn) {
            chessBoard(row, centerColumn, x, y, s);
        } else {
            // 不在则填充右上子棋盘的左下角
            chess[centerRow - 1][centerColumn] = t;
            // 然后覆盖其他格子,注意这时(x,y)要看做已填充位置
            chessBoard(row, centerColumn, centerRow - 1, centerColumn, s);
        }
    
        // 黑色方格在左下子棋盘
        if(x >= centerRow && y < centerColumn) {
            chessBoard(centerRow, column, x, y, s);
        } else {
            // 不在则填充左下子棋盘的右上角
            chess[centerRow][centerColumn - 1] = t;
            // 然后覆盖其他格子,注意这时(x,y)要看做已填充位置
            chessBoard(centerRow, column, centerRow, centerColumn - 1, s);
        }
    
        // 黑色方格在右下子棋盘
        if(x >= centerRow && y >= centerColumn) {
            chessBoard(centerRow, centerColumn, x, y, s);
        } else {
            // 不在则填充右下子棋盘的左上角
            chess[centerRow][centerColumn] = t;
            // 然后覆盖其他格子,注意这时(x,y)要看做已填充位置
            chessBoard(centerRow, centerColumn, centerRow, centerColumn, s);
        }
    
    }
    
    int main() {
        // 大小,黑色方格位置
        int siz, x, y;
        while(true) {
            cout << "(x,y)从(0,0)开始,输入数据为0 0 0即结束程序。" << endl;
            cout << "请输入棋盘大小和黑色方格位置(x,y):";
            cin >> siz >> x >> y;
            // 退出条件
            if(siz == 0) {
                break;
            }
            // 涂黑(x,y),初始化L型牌编号
            chess[x][y] = number = 1;
    
            // 分治法填满棋盘
            chessBoard(0, 0, x, y, siz);
    
            // 输出该棋盘
            for(int i = 0; i < siz; i++) {
                for(int j = 0; j < siz; j++) {
                    cout << chess[i][j] << "\t";
                }
                cout << endl << endl << endl;
            }
        }
    
        return 0;
    }
    
    展开全文
  • 分治算法棋盘覆盖问题(完整代码实现)我在这里是用了一个简化的方式,只是代码简化,还是分治递归思想。一分为4,直至2*2时可直接解决。四种骨牌的摆放刚好对应:dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1...

    分治算法之 棋盘覆盖问题(完整代码实现)

    我在这里是用了一个简化的方式,只是代码简化,还是分治递归思想。一分为4,直至2*2时可直接解决。

    四种骨牌的摆放刚好对应:dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 0 } }; 这四个方向。

    而这4个方向,又可用来判断残缺位置的 4个方向(左上,右上,右下,左下)。

    因此可以用循环,而不是依次判断四个方向,简化代码。

    也可以用一个全局变量title 表示第几个骨牌,然后输出的时候可以用一个title代替ABCD.

    copy:

    【解题思路】:将2^k x 2^k的棋盘,先分成相等的四块子棋盘,其中特殊方格位于四个中的一个,构造剩下没特殊方格三个子棋盘,将他们中的也假一个方格设为特殊方格。如果是:

    左上的子棋盘(若不存在特殊方格)----则将该子棋盘右下角的那个方格假设为特殊方格

    右上的子棋盘(若不存在特殊方格)----则将该子棋盘左下角的那个方格假设为特殊方格

    左下的子棋盘(若不存在特殊方格)----则将该子棋盘右上角的那个方格假设为特殊方格

    右下的子棋盘(若不存在特殊方格)----则将该子棋盘左上角的那个方格假设为特殊方格

    当然上面四种,只可能且必定只有三个成立,那三个假设的特殊方格刚好构成一个L型骨架,我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似,我们就可以用递归算法解决。

    //============================================================================

    // Name : 棋盘覆盖.cpp

    // Author : gaotong

    // Version :

    // Copyright : Your copyright notice

    // Description : A,B,C,D分别表示四种类型的骨牌.即

    // A B CC DD

    //AA BB C D

    //============================================================================

    #include

    using namespace std;

    int N, X, Y; //棋盘大小, 残缺位置 X,Y

    char map[1000][1000]; //棋盘数组

    int dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 0 } }; //四种L棋的放置

    char pieces[4] = { 'A', 'B', 'C', 'D' }; //4种表示

    int title = 0;

    //style 表示那种类型的骨牌; r,t表示放置骨牌的区域(2*2)的左上角位置

    void set_piece(int style, int r, int c) {

    title++;

    for (int i = 0; i < 4; i++)

    if (i == style) { //每种style 对用dir中的摆放方式

    for (int j = 0; j < 4; j++)

    if (i != j)

    map[r + dir[j][0]][c + dir[j][1]] = pieces[i];

    }

    }

    //startR,starC(行,列)区域的左上角位置; dr,dc(行,列)残缺位置; 区域大小

    void chessBoard(int startR, int startC, int dr, int dc, int size) {

    if (size == 1)

    return;

    int s = size / 2;

    int rr = dr >= startR + s; //rr 为1 表示在右方

    int cc = dc >= startC + s; //cc 为1表示在下方

    for (int i = 0; i < 4; i++) {

    if (dir[i][0] == rr && dir[i][1] == cc) {

    //根据残缺的位置,在区域中间放置一个骨牌.

    //例:如果是 rr=0 cc=0 即残缺位置在左上方,对应 dir[0] = {0,0}

    //即style=0, 第一种骨牌

    set_piece(i, startR + s - 1, startC + s - 1);

    for (int j = 0; j < 4; j++) {

    if (j == i) //摆放有残缺位置的 1/4

    chessBoard(startR + s * dir[j][0], startC + s * dir[j][1],

    dr, dc, s);

    else {

    //分别摆放余下的3/4. 残缺位置即在区域中央放置的骨牌 在当前区域的位置 (例:对于右上角区域,残缺位置在坐下角位置)

    chessBoard(startR + s * dir[j][0], startC + s * dir[j][1],

    startR + s - 1 + dir[j][0],

    startC + s - 1 + dir[j][1], s);

    }

    }

    }

    }

    }

    int main() {

    cout << "欢迎使用棋盘覆盖程序:" << endl;

    cout << "分别A,B,C,D代表4种不同方向的骨牌:" << endl << endl;

    cout << " A B CC DD" << endl;

    cout << "AA BB C D" << endl << endl;

    cout << "输入3个数,分别为棋盘大小N(小于1000),残缺位置X,Y(1到N之间):" << endl;

    cin >> N >> X >> Y;

    //判断N是否为2的n次方

    if ((N & (N - 1)) || X > N || X < 1 || Y < 1 || Y > N) {

    cout << "输入不合法" << endl;

    } else {

    chessBoard(0, 0, X - 1, Y - 1, N);

    for (int i = 0; i < N; i++) {

    for (int j = 0; j < N; j++) {

    cout << map[i][j];

    }

    cout << endl;

    }

    }

    return 0;

    }

    输出:

    欢迎使用棋盘覆盖程序:

    分别A,B,C,D代表4种不同方向的骨牌:

    A B CC DD

    AA BB C D

    输入3个数,分别为棋盘大小N(小于1000),残缺位置X,Y(1到N之间):

    4 2 3

    CCDD

    CB D

    BBBA

    BBAA

    这是书上的代码(不全):

    void ChessBoard(int tr, int tc, int  dr,int dc, int size)

    { if (size==1) return;

    int t=tile++,// L型骨牌数

    s=size/2; // 分割棋盘

    //覆盖左上角子棋盘

    if (dr< tr +s && dc < tc+S)

    //特殊方格在此棋盘中

    ChessBoard(tr, tc, dr,dc,S);

    else{//此棋盘中无特殊方格

    //用t号L型骨牌覆盖右下角

    Board[tr+s-1][tc+s-1]=t;

    //覆盖其余方格

    Chessboard(tr,tc,tr+s-1,tc+s-l,s);}

    //覆盖右上角子棋盘

    if (dr <= tr +s && dc >= tc+S)

    //特殊方格在此棋盘中

    ChessBoard(tr,tc+s ,dr,dc,S);

    else{//此棋盘中无特殊方格

    //用t号骨牌覆盖左下角

    Board[tr+s-1][tc+s]=t;

    //覆盖其余方格

    Chessboard(tr,tc+s,tr+s-1,tc+s,s);}

    ………………...

    void outputBoard( int size)

    { for inti=0;i

    for intj=0 ;j

    cout<

    cout<

    展开全文
  • 算法分治法之棋盘覆盖

    千次阅读 2020-11-05 12:43:38
    有关分治算法思想文章指路:【算法】分治算法 什么是棋盘覆盖问题? (1)在一个2k×2k2^k×2^k2k×2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。 (2)在...


    前言

    1. 有关分治算法思想文章指路:【算法】分治算法
    2. 什么是棋盘覆盖问题?
      (1)在一个 2 k × 2 k 2^k×2^k 2k×2k 个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。
      (2)在棋盘覆盖问题中,要用以下4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
      在这里插入图片描述
      (3)例如:在这里插入图片描述
      我们需要用上面4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖,如下图:在这里插入图片描述

    算法实现思想

    1. 问题分析:

    (1)当k>0时,将 2 k × 2 k 2^k×2^k 2k×2k棋盘分割为4个 2 k − 1 2^{k-1} 2k1× 2 k − 1 2^{k-1} 2k1小棋盘:在这里插入图片描述
    (2)特殊方格必位于4个小棋盘之一中,其余3个小棋盘中无特殊方格,为了将这3个无特殊方格的小棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个小棋盘的会合处:
    在这里插入图片描述
    (3)将原问题转化为4个较小规模的棋盘覆盖问题
    (4)递归地使用这种分割,直至棋盘简化为1×1棋盘

    1. 分治算法思想:
      我们把一个 2 k × 2 k 2^k×2^k 2k×2k有一个特殊方格的棋盘分成了4个都有一个特殊方格 2 k − 1 2^{k-1} 2k1× 2 k − 1 2^{k-1} 2k1小棋盘,然后递归分解,直至棋盘简化为1×1棋盘。

    2. 具体过程:

    (1)Step1:将大棋盘分成四个小棋盘
    在这里插入图片描述
    (2)Step2:四个小棋盘中必定有3个没有特殊方格,我们可以用一个L型骨牌覆盖这3个小棋盘的会合处构造出特殊方格。
    在这里插入图片描述
    (3)Step3:现在我们将一个大问题分解成了四个小问题,都有特殊方格,重复Step1和Step2,直到棋盘简化为1×1棋盘
    在这里插入图片描述
    (4)最终结果:
    在这里插入图片描述

    代码实现

    1. 实现思路
      根据棋盘特殊方格的位置我们可以分成4种情况,也就是我们把大棋盘分成4个小棋盘的时候判断:

    (1)如果特殊方格在左上角小棋盘中,我们可以直接以左上角的特殊方格继续分解覆盖,特殊方格没有在左上角中,我们是不是需要覆盖左上角棋盘与其他小棋盘汇合处的方格,然后以这个方格作为特殊方格继续分解覆盖,左上角棋盘与其他小棋盘汇合处的方格就是左上角棋盘最右下角的方格。

    (2)如果特殊方格在右上角小棋盘中,我们可以直接以右上角的特殊方格继续分解覆盖,特殊方格没有在右上角中,我们是不是需要覆盖右上角棋盘与其他小棋盘汇合处的方格,然后以这个方格作为特殊方格继续分解覆盖,右上角棋盘与其他小棋盘汇合处的方格就是右上角棋盘最左下角的方格。

    (3)如果特殊方格在左下角小棋盘中,我们可以直接以左下角的特殊方格继续分解覆盖,特殊方格没有在左下角中,我们是不是需要覆盖左下角棋盘与其他小棋盘汇合处的方格,然后以这个方格作为特殊方格继续分解覆盖,左下角棋盘与其他小棋盘汇合处的方格就是左下角棋盘最右上角的方格。

    (4)如果特殊方格在右下角小棋盘中,我们可以直接以右下角的特殊方格继续分解覆盖,特殊方格没有在右下角中,我们是不是需要覆盖右下角棋盘与其他小棋盘汇合处的方格,然后以这个方格作为特殊方格继续分解覆盖,右下角棋盘与其他小棋盘汇合处的方格就是右下角棋盘最左上角的方格。

    结束条件是棋盘大小为1×1棋盘。

    1. 代码实现:
    public class Demo {
        public static int num = 0;
    
    
        public static void main(String[] args) {
            int[][] board = {{0,-1,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}};
            System.out.println("需要覆盖的棋盘:");
            for (int[] ints : board) {
                for (int anInt : ints) {
                    System.out.print(anInt+" ");
                }
                System.out.println();
            }
    
            chessBoard(board,0,0,0,1,4);
            System.out.println("覆盖后的棋盘:");
            for (int[] ints : board) {
                for (int anInt : ints) {
                    System.out.print(anInt+" ");
                }
                System.out.println();
            }
    
        }
    
        /**
         *
         * @param board 棋盘
         * @param tr 棋盘的最左上角方格的 x坐标
         * @param tc  棋盘的最左上角方格的 y坐标
         * @param dr  特殊方格的 x坐标
         * @param dc   特殊方格的 y坐标
         * @param size  棋盘的大小
         */
        public static void chessBoard(int[][] board,int tr, int tc, int dr, int dc, int size){
    
    
            //棋盘大小为1 x 1 ==》结束
            if (size == 1){
                return;
            }
    
            //棋盘大小的一半:
            int s = size/2;
    
            //覆盖的号码:
            int t = ++num;
    
            //左上角的判断:
            if (dr < tr+s && dc < tc+s){
                chessBoard(board,tr, tc, dr, dc, s);
            }else {
                board[tr+s-1][tc+s-1] = t;
                chessBoard(board,tr,tc,tr+s-1,tc+s-1,s);
            }
    
            //右上角
            if (dr < tr+s && dc >= tc+s){
                chessBoard(board,tr, tc+s, dr, dc, s);
            }else {
                board[tr+s-1][tc+s] = t;
                chessBoard(board,tr,tc+s,tr+s-1,tc+s,s);
            }
    
            //左下角的判断:
            if (dr >= tr+s && dc < tc+s){
                chessBoard(board,tr+s, tc, dr, dc, s);
            }else {
                board[tr+s][tc+s-1] = t;
                chessBoard(board,tr+s,tc,tr+s,tc+s-1,s);
            }
    
            //右下角
            if (dr >= tr+s && dc >= tc+s){
                chessBoard(board,tr+s, tc+s, dr, dc, s);
            }else {
                board[tr+s][tc+s] = t;
                chessBoard(board,tr+s,tc+s,tr+s,tc+s,s);
            }
    
        }
    }
    
    

    输出:我们把特殊方格放在了(0,1)位置

    需要覆盖的棋盘:
    0 -1 0 0 
    0 0 0 0 
    0 0 0 0 
    0 0 0 0 
    覆盖后的棋盘:
    2 -1 3 3 
    2 2 1 3 
    4 1 1 5 
    4 4 5 5 
    

    时间复杂度

    可以用分治法的主定律公式,每次分解成4个小规模的问题:
    在这里插入图片描述
    我们这里k = l o g 2 n log_{2}n log2n ,因为我们把n x n的棋盘看成 2 k × 2 k 2^k×2^k 2k×2k ,自然k = l o g 2 n log_{2}n log2n

    展开全文
  • 棋盘覆盖问题-分治算法

    千次阅读 2020-05-17 12:03:53
      棋盘覆盖问题。有一个2k∗2k的方格棋盘,恰有一个方格是黑色的,其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖,且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为...
  • 整个题目还是分治的思想,由于棋盘是2^k*2^k的,所以我们可以把他平均分成4份,每一份再递归的调用覆盖函数,直到需要覆盖的边长为1,说明只有一个位置,并且该位置放置的是特殊方格。 传入的参数中,tr,tc是棋盘...
  • //用L型骨牌覆盖在3个子棋盘汇合处。 int tile = 1; int Board[8][8]; void ChessBoard(int tr, int tc, int dr, int dc, int size) { //tr棋盘左上角方格的行号 //tc棋盘左上角方格的列号 //dr特殊方格的行号 /...
  • 分治算法——附棋盘覆盖问题的java代码实现

    千次阅读 多人点赞 2018-04-30 15:51:34
    分治算法基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的...
  • 棋盘覆盖问题中,要用到 4 种不同形态的 L 型骨牌覆盖特殊棋盘中出去特殊方格的所有方格,并且任意两个骨牌不能有任何重叠部分。因此,在任意一个2^k × 2^k的特殊棋盘中,要用到的 L 型骨牌个数恰为(4^k-1)/3。...
  • 残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的方格用阴影表示。注重当k= 0时,仅存在一种可能的残缺棋盘(如图1 4 - ...
  • 算法思想参考 https://www.cnblogs.com/Jason-Damon/archive/2013/06/14/3136893.html https://wenku.baidu.com/view/e331f06c336c1eb91a375d75.html C语言代码实现 #include&lt;stdio.h&gt; int ...
  • 残缺棋盘覆盖分治算法仿真软件及源码新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  • 棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘,特殊方格必位于4个较小子棋盘之一...
  • 棋盘覆盖带界面的示例程序,采用java语言编写,用分治法的思想实现。 本人也是菜鸟一枚借鉴了别人的思想希望不要介意,共同学习,一起进步
  • 分治,字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 循环赛日常表 ...
  • 算法棋盘覆盖详解,基础教程~

    千次阅读 2021-11-25 18:20:26
    简单讲解棋盘覆盖的基本原理,另附实现代码。
  • 分治算法就是将原问题划分成n个规模较小的,并且结构与原问题详细的子问题。递归地解决这些子问题,然后再合并其结果,就可以得出问题的解。 分治算法的递归实现中,每一层递归都会涉及这样的三个操作: 分解:将...
  • 棋盘覆盖问题-分治

    万次阅读 多人点赞 2018-06-06 20:28:42
    什么是棋盘覆盖方法? 我去找其他人的解释,恰恰发现一个矛盾的地方,就是看解释比较难理解,但是看解决棋盘覆盖的过程,就很容易理解什么是棋盘覆盖问题了。所以这里就不解释了,直接给一个解决16*16的棋盘解决...
  • 棋盘覆盖(分治算法)

    2019-08-28 10:38:14
    这个题的核心就是分治算法,把棋盘分割为四块,判断特殊块是否在这四个分盘上,如果在, 直接递归,把这个分盘当作整盘,如果不在,则把分盘交界处的那个块标记为特殊块,并赋值为temp,然后这个分盘就有了特殊块,...
  • 算法——分治法之棋盘覆盖

    千次阅读 2017-03-12 01:45:39
    棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 解题思路 分析:当k>0时,将2k×2k棋盘分割为4个2^k-1×2^k-1 子棋盘...
  • 棋盘覆盖分治法是建立在递归上的。 递归之老和尚给小和尚讲故事。 从前有座山,山里有座庙,庙里有个老和尚, 老和尚正在给小和尚讲故事。从前有座山,山里有座庙,庙里有个老和尚, 老和尚正在给小和尚讲故事...
  • 经典算法棋盘覆盖问题 --分治

    万次阅读 多人点赞 2016-09-29 11:44:51
    棋盘覆盖问题要求在2^k * 2^k 个方格组成的棋盘中,你给定任意一个特殊点,用一种方案实现对除该特殊点的棋盘实现全覆盖。 建立模型如图: 解决方案就是利用分治法,将方形棋盘分成4部分,如果该特殊点在某一部分,...
  • 棋盘覆盖问题(分治法)

    千次阅读 2020-04-18 16:33:22
    0)的棋盘,恰好有一个方格与其他方格不同,称之为特殊方格,并且称该棋盘为一特殊棋盘。现在要用4种不同形状的三格骨牌覆盖除了特殊方格外的其他全部方格,并且任何两个三格骨牌不能重叠。请给出一种覆盖方案 特殊...
  • 问题描述: 在一个由✖个方格组成的棋盘中,有一个方格与...要求使用不同形态的L型骨牌(四种)覆盖给定的棋盘上除特殊方格以外的所有方格,且骨牌之间不能重叠。 概要设计:使用分治思想将问题规模缩小: ...
  • 分治法】棋盘覆盖问题java实现

    千次阅读 2020-05-14 10:25:29
    覆盖是指,用L型骨牌覆盖残缺棋盘上所有方格,覆盖是要求二任何两个L型骨牌不能重叠。 问题分析 首先分析一下用于覆盖的骨牌的情况,那么L型骨牌有几种了? 观察发现,L型骨牌是可以旋转的。经过旋转后有四种情况,...
  • 棋盘覆盖问题分治递归求解

    千次阅读 多人点赞 2019-10-04 14:30:39
    棋盘覆盖问题描述 在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊...
  • 分治法实现棋盘的“3-L形”完全覆盖,java实现。
  • 算法分析 | 分治策略算法设计之棋盘覆盖 C语言版 声明:凡代码问题,欢迎在评论区沟通。承蒙指正,一起成长!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,063
精华内容 1,225
关键字:

棋盘覆盖分治算法