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

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

2、解，直到 子问题规模小到可以直接求解。棋盘覆盖问题描述：在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方 格，想要求利用四种 L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的 将除了特殊方格外的其他方格覆盖。实验步骤:1、定义用于输入和输出的数据结构；2、完成分治算法的编写；3、测试记录结构；4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能 否不用栈，直接消除递归，为什么？六、调试过程及实验结果1-1 口卜 I实验运行结果:兀 C:DOC(TIEIMIP桌而XCHESSBEeze22337788 8228044B 2227668 3233-504*5 22

3、336067 3330555S 22306677 00100455 71779939 0 0 H 4 4 4 S 21124334 00014445 22224444七、总结通过本次实验，我更深的理解了递归和分治策略。代码是书上的算法，加上主 函数就行了，用的是C语言编写，很长时间没用了，感觉有点生疏。实验结果有 点问题，就是覆盖棋盘时，并不是按照 1, 2, 3.的字符顺序，而是按照很乱 的顺序输出字符，这个我不知道怎么解决，就没解决。八、附录#i nclude stdio.h#include conio.hint board88 =0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

4、,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;intvoidchessBoard(i nttr, int tc, int dr,dc, int size)int t=tile+,s=size/2;if (size=1) return;if (drt 叶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(t r+s,tc+s,tr+s,tc+s,s);mai n()int i ,j;chessBoard(0,0,5,5,8);for(i=0;i 8;i+)for( j=0;j 8;j