精华内容
下载资源
问答
  • 棋盘覆盖问题C语言.doc
    2021-05-19 17:17:50

    实验报告

    学号

    课程

    0107

    算法分析与设计

    姓名

    高行行

    实验日期

    专业班级

    移动互联网实验时间

    14-01

    8:00-9:00

    实验情况

    备注

    棋盘覆盖问题算法:

    #include<>

    int tile=1;

    int board[100][100];

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

    {

    if(size==1)return;// 递归边界

    int t=tile++;//L型骨牌号

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

    覆盖左上角子棋盘

    if(dr

    特殊方格在此棋盘中

    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

    =tc+s)

    特殊方格在此棋盘中

    ChessBoard(tr,tc,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

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

    }

    }

    int main()

    {

    int size,r,c,row,col;

    printf(" 输入棋盘大小:\n");

    scanf("%d",&size);// 输入棋盘大小

    printf(" 输入特殊方格位置:row,col \n");

    scanf("%d,%d",&row,&col);// 输入特殊方格位置

    ChessBoard(0,0,row,col,size);

    printf(" 输出棋盘覆盖结果:\n");

    for (r = 0; r < size; r++)// 输出棋盘覆盖结果

    {

    for (c = 0; c < size; c++)

    {

    printf("%d ",board[r][c]);

    }

    printf("\n");

    }

    return 0;

    }

    运行效果:

    实验报告成绩

    老师

    注: 1)专业班级按打印课表中名称填写;2)课程名称按课表中名称填写,不能简写;

    3)实验日期格式示例: )实验时间格式示例: “第三大节” 5)实验情况包括任务(或题目)、解决方案(或者代码) 、结果等; 6)实验报告成绩按五级标准评分;

    更多相关内容
  • 算法分析 | 分治策略算法设计之棋盘覆盖 C语言版 声明:凡代码问题,欢迎在评论区沟通。承蒙指正,一起成长!

    声明:凡代码问题,欢迎在评论区沟通。承蒙指正,一起成长!

    一、实验内容与要求

    内容:(棋盘覆盖问题)在一个2k×2k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
    要求:随机输入k及特殊方格的坐标,并输出覆盖矩阵。

    二、概要设计

    1.定义整型二维数组指针全局变量,用于动态保存棋盘方格;
    2.主函数中输入3个参数,分别为棋盘的规模k及特殊方格的位置x、y;
    3.根据规模k为指针全局变量分配内存,并生成相应大小的全局变量数组;
    4.运用算法进行棋盘覆盖:当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1子棋盘,特殊方格必须位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处,从而将原问题转化为4个较小规模的棋盘覆盖问题;递归地使用这种分割,直至棋盘简化为棋盘1×1。
    5.输出棋盘矩阵:以-1为矩阵边框,0为特殊方格,L型骨牌的编号tile从1开始计数;在以-1为的方框中打印出2k×2k个整型数矩阵。

    三、直接上代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    int tile=1;
    int **board; //二维数组全局变量的指针;
    
    void Defind_Array(int Size); //声明:为全局变量分配内存;
    void ChessBoard(int tr, int tc, int dr, int dc, int siz); //声明:棋盘覆盖的函数;
    void Display(int Size); //声明:打印输出函数;
    
    int main()
    {
        int k,Size,x,y; //规模,长度(Size==2^k),特殊方格位置;
        printf("规模:");
        scanf("%d",&k);
        printf("特殊方格位置下标(x,y):");
        scanf("%d%d",&x,&y);
        Size=pow((double)2,(double)k);
        Defind_Array(Size); //定义数组;
        board[x][y]=0; //将特殊方格标记为0;
        ChessBoard(0,0,x,y,Size); //覆盖棋盘;
        Display(Size); //输出棋盘,边缘标记为-1;
        return 0;
    }
    
    void Defind_Array(int length)
    {
        int p,q;
        board=(int **)malloc(length*sizeof(int *));
        for(p=0; p<length; p++)
        {
            board[p]=(int *)malloc(length*sizeof(int));
            for(q=0; q<length; q++)
                board[p][q] = p*length+q;
        }
    }
    
    void ChessBoard(int tr, int tc, int dr, int dc, int siz)
    {
        int s, t1; //t1表示本次覆盖所用L型骨牌的编号
        if (siz == 1) return; //棋盘只有一个方格且是特殊方格
        t1 = tile++; // L型骨牌编号
        s = siz/2; // 划分棋盘
        if (dr < tr + s && dc < tc + s) //特殊方格在左上角子棋盘中
            ChessBoard(tr, tc, dr, dc, s); //递归处理子棋盘
        else  //用 t1号L型骨牌覆盖右下角,再递归处理子棋盘
        {
            board[tr + s - 1][tc + s - 1] = t1;
            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   //用 t1号L型骨牌覆盖左下角,再递归处理子棋盘
        {
            board[tr + s - 1][tc + s] = t1;
            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   //用 t1号L型骨牌覆盖右上角,再递归处理子棋盘
        {
            board[tr + s][tc + s - 1] = t1;
            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   //用 t1号L型骨牌覆盖左上角,再递归处理子棋盘
        {
            board[tr + s][tc + s] = t1;
            ChessBoard(tr+s, tc+s, tr+s, tc+s, s);
        }
    }
    
    void Display(int Size)
    {
        int i,j;
        for(i=0; i<Size+2; i++)
            printf("-1\t");
        printf("\n\n");
        for(i=0; i<Size; i++)
        {
            printf("-1\t");
            for(j=0; j<Size; j++)
            {
                printf("%d\t",board[i][j]);
            }
            printf("-1\t");
            printf("\n\n");
        }
        for(i=0; i<Size+2; i++)
            printf("-1\t");
        printf("\n");
    }
    

    四、运行结果

    在这里插入图片描述

    展开全文
  • 棋盘覆盖c语言实现)
  • 棋盘覆盖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;
    }
    
    

    结果展示:

    展开全文
  • 在一个2k*2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格位一...在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。
  • c语言棋盘覆盖问题

    2021-11-02 13:24:45
    } 思路:棋盘覆盖可以理解成找到这个特殊的方格,tr,tc分别是这个各自的左上角元素的标号,dr,dc是特殊方格的位置,tile表示用了几个骨牌了。依次划分成四个四个的区域,几个if-else语句的意思是如果特殊方格在这个...
    #include<stdio.h>
    int board[100][100];
    int tile=1;
    void chessboard(int tr,int tc,int dr,int dc,int sizee)
    {
        if(sizee==1)
           return;
        int t=tile++;
        int s=sizee/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 i,j;
        board[0][1]=0;
        chessboard(0,0,0,1,4);
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
                printf("%5d",board[i][j]);
            printf("\n");
        }
        return 0;
    }
    
    
    
    

    思路:棋盘覆盖可以理解成找到这个特殊的方格,tr,tc分别是这个各自的左上角元素的标号,dr,dc是特殊方格的位置,tile表示用了几个骨牌了。依次划分成四个四个的区域,几个if-else语句的意思是如果特殊方格在这个区域里面就继续在这个方格里进行chessboard继续划分,如果不在这个方格里就把交接的部分,也就是左上方格把右下角涂黑,右上的把左下角涂黑,左下的把右上涂黑…然后再继续在本方格里进行划分

    展开全文
  • 代码如下: #include<stdio.h> int board[100][100]; int t; void cover(int left_i,int right_j,int dot_i,int dot_j,int size) { ...//棋盘分开;s为已分方形边长 if (dot_i < left_i + s &a
  • 棋盘覆盖问题C语言实现

    千次阅读 2018-11-15 16:16:00
    #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace std; int def[101][101]={0}; static int t=0; void chess(int a,int b,int aa,int bb,int length) ... retur...
  • 分治算法之 棋盘覆盖问题(完整代码实现)我在这里是用了一个简化的方式,只是代码简化,还是分治递归思想。一分为4,直至2*2时可直接解决。四种骨牌的摆放刚好对应:dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1...
  • C语言解决棋盘覆盖问题

    千次阅读 2018-07-18 09:41:28
    棋盘覆盖问题是典型的利用分治法解决问题 把大问题分解成为相同性质的子问题 分治的技巧在于如何划分棋盘,使划分后的子棋盘的大小相同,并且每个子棋盘均包含一个特殊方格,从而将原问题分解为规模较小的棋盘覆盖...
  • 一、前言之前做了一个算法作业,叫做棋盘覆盖,本来需要用c语言来编写的,但是因为我的c语言是半桶水(哈哈),所以索性就把网上的c语言写法改成JavaScript写法,并且把它的覆盖效果显示出来二、关键代码算法作业2#num...
  • // 棋盘覆盖#include#include int Board[8][8]={0};//定义棋盘并初始化棋盘void ChessBoard(int tr,int tc,int dr,int dc,int size,int &tile);void main(){int tile=0;cout<int x,y;cin>>x>>y;...
  • C语言实现棋盘覆盖

    2012-11-15 19:18:19
    主要写的关于棋盘覆盖的问题,主要运用了动态规划算法的思想,希望对大家学习算法设计这门课程会有帮助。
  • 摘要:针对算法设计与分析课程难度较大、对学生编程能力要求较高的现状,通过对棋盘覆盖问题的分治算法求解过程进行互动教学设计,引导学生进行问题理解、算法设计、算法实现。特别是在算法实现环节,一行一行地动态...
  • 问题描述: 在一个由✖个方格组成的棋盘中,有一个方格与...要求使用不同形态的L型骨牌(四种)覆盖给定的棋盘上除特殊方格以外的所有方格,且骨牌之间不能重叠。 概要设计:使用分治思想将问题规模缩小: ...
  • 递归-PTA棋盘覆盖

    2020-11-21 13:21:44
    求用若干块这种L型骨牌实现除该特殊点棋盘的全覆盖。(本题要求采用分治算法做) 输入格式: 输入三个数,分别是aa,bb,length. 输出格式: 输出整个棋盘。其中特殊方格填为0,然后铺棋盘的顺序为:先铺四个子棋盘交界...
  • 问题一:棋盘覆盖问题  对于一个规模为的棋盘,其中有一个方格和其他方格完全不同,称这一方格为特殊方格,且称该棋盘为特殊棋盘,设计一种算法可以使用4种不同的L型骨牌来填充棋牌。 解答:采用分治策略。 第...
  • 一个小算法,拿到网上,我相信会有用的,需要的朋友顶一下啊,谢谢了
  • 残缺棋盘问题 C语言实现。给定一个2n*2n的残缺棋盘,问如何放置三格板,使得除残缺格外,棋盘中其他格子都被三格板覆盖,并且放置的三格板互不重叠。
  • 残缺棋盘问题 C语言 算法

    千次阅读 2019-03-26 10:39:07
    问题描述: Incomplete Chessboard Description TheBeet有一个块大小为(2^{N}2N*2^{N}2N)的棋盘。这个棋盘是由一个个格子...但是这个棋盘再也不能用来下棋了,于是TheBeet想把这个棋盘切成如以下的几种小块。...
  • 算法设计与分析实验报告-棋盘覆盖问题.doc贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称:算法设计与分析班级:信计101班实验日期:2013-9-30姓名: 张 胜学号:1007010162指导教师:程欣宇...
  • 棋盘覆盖执行文件

    2011-09-16 17:45:34
    java实现棋盘覆盖,该文件为可执行文件
  • 题目:NYOJ 45 棋盘覆盖 刚学习了用java解决大数的问题,又做了一遍 2018.5.3 其实这道题就是大数问题 思路:利用数组模拟笔算,求出棋盘的面积(大数),用得出的面积除以3,其实不用减1就可以 #include ...
  • 棋盘覆盖问题(附C语言实现)

    千次阅读 2009-10-11 22:27:00
    棋盘覆盖问题)在一个2k × 2k 个方格组成的棋盘中恰有一个方格与其他方格不同(图中标记为-1 的方格),称之为特殊方格。现用L 型(占3 个小格)纸片覆盖棋盘上除特殊方格的所有部分,各纸片不得重叠,于是,用到...
  • 课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的
  • 残缺棋盘(defective chessboard)是一个有2k×2k 个方格的棋盘,其中恰有一个方格残缺。图2 - 3给出k≤2时各种可能的残缺棋盘,其中残缺的...残缺棋盘的问题要求用三格板(t r i o m i n o e s)覆盖残缺棋盘(如图1 4 ...
  • 棋盘覆盖问题 问题说明 在一个2^k * 2^k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格。 棋盘覆盖问题就是要用图示的4种不同形态的L型骨牌覆盖给定棋盘上除特殊方格之外的所有方格,且...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 853
精华内容 341
关键字:

棋盘覆盖c语言

友情链接: interest.rar