算法设计与分析实验报告-棋盘覆盖问题

1、贵州大学计算机科学与技术学院计算机科学与技术系上机实验报告课程名称：算法设计与分析班级：信计101班实验日期:2013-9-30姓名：张胜学号:1007010162指导教师：程欣宇实验序号：一实验成绩：一、实验名称分治算法实验-棋盘覆盖问题二、实验目的及要求1、熟悉递归算法编写；2、理解分治算法的特点；3、掌握分治算法的基本结构。三、实验环境visual c+四、实验内容根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验； 要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学 尝试消去递归求解。五、算法描述及实验步骤分治算法原理：分治算法将大的分解成形状结构相同的子问题，并且不断递归地

2、分解，直到 子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方 格，想要求利用四种l型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的 将除了特殊方格外的其他方格覆盖。实验步骤：1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能 否不用栈，直接消除递归，为什么？六、调试过程及实验结果实验运行结果:ca c:docuie"1hphchessb"1. exe88880000 22337788 82280440 22237668

3、32335045 22336067 33305555 22306677 77700999 00100455 71779939 00114445 21124334 00014445 22224444 00114455七、总结通过本次实验，我更深的理解了递归和分治策略。代码是书上的算法，加上主 函数就行了，用的是c语言编写，很长时间没用了，感觉有点生疏。实验结果有 点问题，就是覆盖棋盘时，并不是按照1, 2, 3.的字符顺序，而是按照很乱 的顺序输岀字符，这个我不知道怎么解决，就没解决。八、附录ttinclude "stdio. hinclude "conio.h"i

4、nt board88 =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;int tile=0;void chessboard(int tr, int tc, int dr, int de, int size)int t 二 ti le+,s=size/2;if (si

5、ze=l) return;if (dr<tr+s&&dc<tc+s)chessboard(tr, tc, dr, de, s); else boardtr+s-ltc+sl=t;chessboard(tr, tc，tr+st, tc+st, s) ;if (dr <tr+s && de >= tc+s)chessboard(tr, tc+s, dr, de, s); else boardtr+st tc+s二t;chessboard(tr, tc+s, tr+s-1, tc+s, s) ;if (dr >二 tr+s&&am

6、p;dc<tc+s)chessboard (tr+s, tc, dr, de, s);else boardtr+s tc+st二t;chessboard(tr+s, tc, tr+s, tc+st, s) ;if (dr >= tr+s &&dc>二tc+s)chessboard(tr+s, tc+s, dr, de, s); else boardtr+stc+s二t;chessboard(tr+s, tc+s, tr+s, tc+s, s) ;main()int i ,j;chessboard(0, 0, 5, 5, 8); for(i=0;i <8;i+)for( j=0;j <8;j+) if