资源描述：
《算法与算法设计+棋盘覆盖问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验报告课程名称算法分析与设计实验项目棋盘覆盖实验仪器计算机系别计算机科学与工程系专业软件工程班级/学号0515107学生姓名刘帅实验日期2008年4月15日成绩指导教师一．实验目的：掌握递归和分治策略掌握设计有效算法的分治策略通过实际编程，深入了解递归和分治策略二．实验要求：在一个2^k*2^k的棋盘中有一个特殊方格，要求用L型骨牌覆盖除特殊方格以外的所有方格。三．设计实现：当k>0时,将2^k*2^k的棋盘划分成4个2^(k-1)*2^(k-1)的棋盘,特殊方格必位于4个较小的棋盘之一，其中3个棋盘无特殊方格。为了将这3个无特殊方格的棋盘变成有特殊方格的棋盘，所以用一个L型
2、骨牌覆盖其接口处，所以这四个棋盘都是带特殊方格的棋盘。由此思想，递归执行，直至全部划成1*1的棋盘主要代码清单：#include"stdio.h"#include"conio.h"intboard[8][8]={{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}};inttile=0;voidchessBoard(inttr,inttc,intd
3、r,intdc,intsize){intt=tile++,s=size/2;if(size==1)return;if(dr=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
4、=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);}}main(){inti,j;chessBoard(0,0,5,5,8);for(i=0;i<8;i++){for(j=0;j<8;j++){if(board[i][j
5、]<10)printf("0");printf("%d",board[i][j]);printf("");}printf("");}getchar();}四．实验结果：五．实验总结：通过本次实验，我更深的理解了递归和分治策略。代码是书上的算法，加上主函数就行了，用的是C语言编写，很长时间没用了，感觉有点生疏。实验结果有点问题，就是覆盖棋盘时，并不是按照1，2，3….的字符顺序，而是按照很乱的顺序输出字符，这个我不知道怎么解决，就没解决。
