棋盘覆盖问题.doc

广东金融学院实验报告课程名称：算法设计与分析实验编号及实验名称实验一 棋盘覆盖问题系 别应用数学系姓 名许夏梦学 号071612117班 级0716121实验地点新电605实验日期2009-9-16实验时数4指导教师骆世广同组其他成员成 绩一、 实验目的及要求1、熟悉C/C+语言的集成开发环境；2、掌握棋盘覆盖问题的算法；3、初步掌握分治算法。二、 实验环境及相关情况（包含使用软件、实验设备、主要仪器及材料等）使用软件：C+软件；使用实验设备：计算机：Intel(R);Pentium(R) 4 CPU 2.80GHz;2.79 GHz,0.99 GB 的内存；使用系统：Microsoft Windows XP;Professional;版本 2002；Service Pack 2.三、 实验内容及步骤（包含简要的实验步骤流程）实验内容：1、 理解掌握棋盘覆盖问题的算法；2、 棋盘覆盖问题的算法用C语言在C+程序上的编译3、 调试并运行棋盘覆盖问题程序4、 总结程序调试过程中的经验和教训实验步骤：棋盘覆盖算法：Void chessboard(int tr,int tc,int dr,int dc,int size)if(size=1)return;int t=tile+,s=size/2;if(drtr+s&dctc+s)chessBoard(tr,tc,dr,dc,s);else boardtr+s-1tc+s-1=t;chessBoard(tr,tc, tr+s-1, tc+s-1,s);if(dr=tc+s)chessboard(tr,tc+s,dr,dc,s);else boardtr+s-1tc+s=t;chessBoard(tr,tc+s, tr+s-1, tc+s,s);if(dr=tr+s&dc=tr+s&dc=tc+s)chessboard(tr+s,tc+s,dr,dc,s);else boardtr+stc+s=t;chessBoard(tr+s,tc+s, tr+s, tc+s,s);四、 实验结果（包括程序或图表、结论陈述、数据记录及分析等，可附页）程序代码：#include#define N 8int tile=0; /L型骨牌的编号 int boardNN;void ChessBoard(int k,int tr,int tc,int dr,int dc)if(k=1) return;int t=tile+; /L型骨牌号int s=k/2; /分割棋盘if(drtr+s&dctc+s) /覆盖左上角子棋盘 ChessBoard(s,tr,tc,dr,dc); /特殊方格在此棋盘中else /特殊方格不在此棋盘中 boardtr+s-1tc+s-1=t; /用L型骨牌覆盖右下角 ChessBoard(s,tr,tc,tr+s-1,tc+s-1); /覆盖其余方格if(dr=tc+s) /覆盖右上角子棋盘 ChessBoard(s,tr,tc+s,dr,dc); /特殊方格在此棋盘中else /特殊方格不在此棋盘中 boardtr+s-1tc+s=t; /用L型骨牌覆盖左下角 ChessBoard(s,tr,tc+s,tr+s-1,tc+s); /覆盖其余方格if(dr=tr+s&dc=tr+s&dc=tc+s) /覆盖右下角子棋盘 ChessBoard(s,tr+s,tc+s,dr,dc); /特殊方格在此棋盘中else /特殊方格不在此棋盘中 boardtr+stc+s=t; /用L型骨牌覆盖左上角 ChessBoard(s,tr+s,tc+s,tr+s,tc+s); /覆盖其余方格void main()int k,dr,dc;int tr=0,tc=0; /tr为子棋盘左上角方格所在行，tc为子棋盘左上角方格所在列k=N;printf(请输入特殊方格所在的行号(从0开始)n);scanf(%d,&dr);printf(请输入特殊方格所在的列号(从0开始)n);scanf(%d,&dc);ChessBoard(k,tr,tc,dr,dc);int i,j;for(i=0;iN;i+) for(j=0;jN;j+) printf(%dt,boardij); printf(n);实验结果：五、 实验总结（包括心得体会、问题回答及实验改进意见，可附页）通过在计算机实现棋盘覆盖问题，对棋盘覆盖算法有了较好的理解。实验是对书