精华内容
下载资源
问答
  • 2021-10-14 14:36:53
    //chessboard covering divide and conquer method
    #include <iostream>
    #define Maxnum 1001
    using namespace std;
    int chessboard[Maxnum][Maxnum];//chessboard max num
    int Order = 0;//The order of filling dominoes is not the execution order of code filling
    // 以左上角为坐标 零点,向下为 x的正轴,向右为 y的正轴 
    void divide_conquer(int ox,int oy,int x,int y,int size)
    {
    	if(size <= 1)
    	{
    		return;
    	}
    	
    	size = size / 2;
        Order ++;
    	int order = Order;
    	if(x <= ox + size - 1 && y <= oy + size - 1)//top left corner
    	{
    		divide_conquer(ox,oy,x,y,size);
    	}
    	else
    	{
    		chessboard[ox + size - 1][oy + size - 1] = order;
    		divide_conquer(ox,oy,ox + size - 1,oy + size - 1,size);
    	}
    	
    	if(x <= ox + size - 1 && y > oy + size - 1)//upper right corner
    	{
    		divide_conquer(ox,oy + size,x,y,size);
    	}
    	else
    	{
    		chessboard[ox + size - 1][oy + size] = order;
    		divide_conquer(ox,oy + size,ox + size - 1,oy + size,size);
    	}
    	
    	if(x > ox + size - 1 && y <= oy + size - 1)//down left quarter
    	{
    		divide_conquer(ox + size,oy,x,y,size);
    	}
    	else
    	{
    		chessboard[ox + size][oy + size - 1] = order;
    		divide_conquer(ox + size,oy,ox + size,oy + size - 1,size);
    	}
    	
    	if(x > ox + size - 1 && y > oy + size - 1)//lower right corner
    	{
    		divide_conquer(ox + size,oy + size,x,y,size);
    	}
    	else
    	{
    		chessboard[ox + size][oy + size] = order;
    		divide_conquer(ox + size,oy + size,ox + size,oy + size,size);
    	}
    	
    }
    
    int main()
    {
    	int x,y,size;
    	
    	while(1)
    	{
    		cout << "Coordinates of special points,then (X,Y),size :";
    		cin >> x >> y >> size;
    		
    		if(size <= 0 || x >= size || y >= size)//0 <= x,y < size !!size 必须是 4的k倍数 (1 < k < +∞) 
    		{
    			cout << "size or x,y is error" << endl;
    			continue;
    		}
    		break;
    	}
    	
    	divide_conquer(0,0,x,y,size);
    	
    	for(int i = 0;i < size;i ++)//print chessboard's result
    	{
    		for(int j = 0;j < size;j ++)
    		{
    			cout << chessboard[i][j] << "\t";
    		}
    		cout << endl;
    	}
    	return 0;	
    }
    

     

     

    更多相关内容
  • 分治法实现棋盘的“3-L形”完全覆盖,java实现。
  • 棋盘覆盖问题要求用图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 二、问题分析 首先,从最简单的情况开始考虑,如果只是一个2x2的棋盘,那么肯定是有解...

    一、问题描述

    在一个2k×2 k(k≥0)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。 棋盘覆盖问题要求用图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
    请添加图片描述

    二、问题分析

    首先,从最简单的情况开始考虑,如果只是一个2x2的棋盘,那么肯定是有解的,因为这就是最基本的情况。

    但是当n很大的时候,该问题还有解吗?这是我们需要考虑的问题。

    这个我们可以利用数学归纳法来证明:

    假设当n = k的时候该问题有解,那么如何证明当n = k + 1的时候也有解呢?

    证明过程如下:

    我们可以n = k + 1的棋盘的正中央的2x2的方格中放置一个L型骨牌,使得剩下的三个子棋盘都具有自己的特殊方格。
    那么此时该问题就被划分成了四个子问题。
    而根据假设:当n = k的时候该问题有解。
    所以当n = k + 1的时候,也相应有解。

    请添加图片描述
    请添加图片描述

    三、数据结构设计

    经过上述的分析之后,我们就可以利用分治的方法来解决这个问题。

    通过上述分析我们即可知道,在分治的过程中,遇到子棋盘没有特殊方格的时候,我们就给予这个棋盘的父棋盘中心点处给予一个特殊方格,从而三个组合在一起就是一个完整的L型骨牌。

    那么我们就可以进行数据结构的设计了:

    如下图所示:

    请添加图片描述
    请添加图片描述

    四、算法设计

    请添加图片描述

    请添加图片描述

    五、代码分析

    观察上述代码可以发现,算法的整个部分采用了四个递归,分成了四种情况:

    1. 特殊方格在第1象限
    2. 特殊方格在第2象限
    3. 特殊方格在第3象限
    4. 特殊方格在第4象限

    如果特殊方格在第二象限,就继续对第二象限进行划分,直到划分为4个1x1的小方格。

    当划分到没有特殊方格的时候,就需要补方格了。

    这时要注意,每一层的递归,L型骨牌的数量也要随之递增。

    而当第二象限被填满的时候,递归就要往回走了。一直走到最开始的第一层函数调用,开始走第二个if判断,发现第一象限没有特殊方格,因此给第一象限的左下角补上一个特殊方格,然后开始在第一象限内调用递归函数,以此类推…

    过程如下图所示:
    请添加图片描述

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

    万次阅读 多人点赞 2016-05-30 21:59:58
    分治法——棋盘覆盖问题 棋盘覆盖问题。有一个2k∗2k2^k*2^k的方格棋盘,恰有一个方格是黑色的,其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖,且任意一个白色方格不能同时被...

    分治法——棋盘覆盖问题

    棋盘覆盖问题。有一个 2k2k 的方格棋盘,恰有一个方格是黑色的,其他为白色。你的任务是用包含3个方格的L型牌覆盖所有白色方格。黑色方格不能被覆盖,且任意一个白色方格不能同时被两个或更多牌覆盖。如图所示为L型牌的4种旋转方式。
    L型牌

    分治三步骤
    划分问题:将 2k2k 的棋盘划分为 2k12k1 这样的子棋盘4块。
    递归求解:递归填充各个格子,填充分为四个情况,在下面会有解释,递归出口为 k=0 也就是子棋盘方格数为1。
    合并问题:不需要合并子问题。
    递归填充的四种情况
    如果黑方块在左上子棋盘,则递归填充左上子棋盘;否则填充左上子棋盘的右下角,将右下角看做黑色方块,然后递归填充左上子棋盘。
    如果黑方块在右上子棋盘,则递归填充右上子棋盘;否则填充右上子棋盘的左下角,将左下角看做黑色方块,然后递归填充右上子棋盘。
    如果黑方块在左下子棋盘,则递归填充左下子棋盘;否则填充左下子棋盘的右上角,将右上角看做黑色方块,然后递归填充左下子棋盘。
    如果黑方块在右下子棋盘,则递归填充右下子棋盘;否则填充右下子棋盘的右下角,将左上角看做黑色方块,然后递归填充右下子棋盘。

    棋盘覆盖问题的递归解法

    棋盘覆盖问题分治算法

    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);
        }
    
    }

    测试主程序

    #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;
    }

    输出数据

    (x,y)从(0,0)开始,输入数据为0 0 0即结束程序。
    请输入棋盘大小和黑色方格位置(x,y):2 0 0
    1       2
    
    
    2       2
    
    
    (x,y)从(0,0)开始,输入数据为0 0 0即结束程序。
    请输入棋盘大小和黑色方格位置(x,y):4 1 1
    3       3       4       4
    
    
    3       1       2       4
    
    
    5       2       2       6
    
    
    5       5       6       6
    
    
    (x,y)从(0,0)开始,输入数据为0 0 0即结束程序。
    请输入棋盘大小和黑色方格位置(x,y):8 2 2
    4       4       5       5       9       9       10      10
    
    
    4       3       3       5       9       8       8       10
    
    
    6       3       1       7       11      11      8       12
    
    
    6       6       7       7       2       11      12      12
    
    
    14      14      15      2       2       19      20      20
    
    
    14      13      15      15      19      19      18      20
    
    
    16      13      13      17      21      18      18      22
    
    
    16      16      17      17      21      21      22      22
    
    
    
    (x,y)从(0,0)开始,输入数据为0 0 0即结束程序。
    请输入棋盘大小和黑色方格位置(x,y):0 0 0
    
    Process returned 0 (0x0)   execution time : 29.988 s
    Press any key to continue.
    展开全文
  • 棋盘覆盖问题-分治法

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

    什么是棋盘覆盖方法?

        我去找其他人的解释,恰恰发现一个矛盾的地方,就是看解释比较难理解,但是看解决棋盘覆盖的过程,就很容易理解什么是棋盘覆盖问题了。所以这里就不解释了,直接给一个解决16*16的棋盘解决过程,看完过程,相信你也理解了什么是棋盘问题了。

        如下:

    首先给出一个包含一个奇异点的16*16棋盘:


    第一步是将该棋盘分为四个等大的子棋盘:


    然后将该棋盘看做是4*4的棋盘,可以看到奇异点在左上角的子棋盘中,那么这一步的任务就是用一个(真的是一个)L型的棋子(下图中红色的格子)将其他三个子棋盘构造成含奇异点的子棋盘:


    下一步是将红线分割的子棋盘又切割成四个子棋盘(白色线切开的子棋盘):


    然后对每个红色线包围在里面的子棋盘,用一个L型棋子(黄色)又构造出奇异点,使得每个子棋盘都有一个奇异点,即白色线围起来的格子看做是一个整体,里面包含一个黄色的奇异点:



    下一步是继续讲白色线包围的格子切分为4个子棋盘,这里为了方便观察,将前面所有的分割线去掉:



    同理,对黄色的棋盘构造含奇异点的子棋盘(蓝色):


    最后可以分割到2*2的格子,然后每个2*2的子棋盘都已经包含一个奇异点了,剩下的就是用L型旗子去填好剩下的三个格子。

    好了,任务完成。是不是觉得很简单呢,觉得简单的话就点个赞呗。


    具体的实现代码,请参考我的另外博客。棋盘覆盖-分治法(代码实现)

    展开全文
  • 前几天学分治算法的时候碰到了一个经典的棋盘覆盖问题,现在小周周就来总结一下解题的过程吧,加强我们对分治算法的理解。 棋盘覆盖问题 问题描述:在一个2的K次方乘以2的K次方方格组成的棋盘中,一开始恰有一个方格...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 棋盘覆盖问题: 在一个????????×???????? (????≥????)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为特殊方格。显然,特殊方格在棋盘中可能出现的位置有????^???? 种,因而有????^????种不同的...
  • //位运算,棋盘最大容量 2^10 int Board[maxn][maxn]; //棋盘 int tile = 1; //骨牌编号 void ChessBoard(int tr, int tc, int dr, int dc, int size){ if(size == 1) return; int s = si
  • 分治法的设计思想: 分治算法就是将原问题划分成n个规模较小的,并且结构与原问题详细的子问题。递归地解决这些子问题,然后再合并其结果,就可以得出问题的解。 分治算法的递归实现中,每一层递归都会涉及这样的...
  • 棋盘覆盖问题分治法

    千次阅读 2020-04-18 16:33:22
    问题描述 有一个2k×2k(k>0)的棋盘,恰好有一个方格与其他方格不同,称之为特殊方格,并且称该棋盘为一特殊棋盘。现在要用4种不同形状的三格骨牌覆盖除了特殊方格外的其他全部方格,并且任何两个三格骨牌不能...
  • ② 当k较大时,可以利用分治法的思想,将棋盘从中间一分为四,为了将其划分为四个相同的子问题,可以在分界处给无特殊方格的三个子问题补充一个特殊方格(即补充一个三格骨牌),然后继续按上述规则对子问题进行划分...
  • 分治算法求解棋盘覆盖问题
  • 棋盘覆盖问题 //tr:子棋盘x坐标,tc:子棋盘y坐标,dr:特殊方格x坐标,dc:特殊方格y坐标,size:棋盘边长 //初始tr,tc=0 public void chessBoard(int tr,int tc,int dr,int dc,int size) { if(size == 1)return; int ...
  • 棋盘覆盖问题 - 分治法(c++)

    千次阅读 2017-03-15 20:46:40
    c++ 分治法 棋盘覆盖问题
  • 棋盘覆盖问题中,要用到 4 种不同形态的 L 型骨牌覆盖特殊棋盘中出去特殊方格的所有方格,并且任意两个骨牌不能有任何重叠部分。因此,在任意一个2^k × 2^k的特殊棋盘中,要用到的 L 型骨牌个数恰为(4^k-1)/3。...
  • 【算法】分治法棋盘覆盖

    千次阅读 2020-11-05 12:43:38
    (2)在棋盘覆盖问题中,要用以下4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。 (3)例如: 我们需要用上面4种不同形态的L型骨牌覆盖给定的特殊棋盘上除...
  • 分治法-棋盘覆盖问题

    千次阅读 2019-01-02 20:28:28
    问题描述: 在一个2k×2k 个方格组成的棋盘中,有一个方格与其它不同,称该方格为特殊方格,且称该棋盘为一特殊棋盘。  k=2时的一种棋盘 要求用下图所示的4种L形态骨牌覆盖给定的特殊棋盘。 限制条件: ...
  • 标签:分治法1.问题描述:点击打开链接2.代码:#define _CRT_SECURE_NO_WARNINGS#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#...
  • 棋盘覆盖问题要求用图4.10(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何两个L型骨牌不得重复覆盖。 算法: 代码实现: 运行截图: 参考 算法分析与设计P65 4.3.2 棋盘覆盖问题 ...
  • 算法分析与设计实验报告——实现分治法求解棋盘覆盖问题 目录:算法分析与设计实验报告——实现分治法求解棋盘覆盖问题一、 实验目的二、实验要求三、 实验原理四、 实验过程(步骤)五、 运行结果六、实验分析与讨论...
  • 分治法棋盘覆盖问题java实现

    千次阅读 2020-05-14 10:25:29
    覆盖是指,用L型骨牌覆盖残缺棋盘上所有方格,覆盖是要求二任何两个L型骨牌不能重叠。 问题分析 首先分析一下用于覆盖的骨牌的情况,那么L型骨牌有几种了? 观察发现,L型骨牌是可以旋转的。经过旋转后有四种情况,...
  • 棋盘覆盖问题,是一种编程问题。如何应用分治法求解棋盘覆盖问题呢?分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖问题
  • 算法设计与分析 用分治法求解棋盘覆盖 c语言源码+分析
  • 算法分析 | 分治策略算法设计之棋盘覆盖 C语言版 声明:凡代码问题,欢迎在评论区沟通。承蒙指正,一起成长!
  • 题目:在一个(2^k)*(2^k)个方格组成的棋盘上,有一个特殊方格与其他方格...即围棋中比较忌讳的愚形三角,方向随意),切任何两个L型方块不能重叠覆盖。 [此程序在TC下课成功运行。VC下缺少头文件 ,编译时会出现错误。]
  • 这里写棋盘覆盖-经典的分治法问题一、问题概述二、适用方法三、代码展示四...在棋盘覆盖问题中,要求用图所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格,且任何两个L型骨牌不得重叠覆盖。在任何一
  • 使用JAVA解决残缺棋盘覆盖问题:一个n*n的棋盘上有一个缺陷点,该点不能被覆盖,剩下的格子全部用三盒板覆盖。应用的是分治法

空空如也

空空如也

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

分治法棋盘覆盖问题