伤城文章网 > 数学 > 算法设计与分析实验报告 棋盘覆盖问题

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


贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告
课程名称:算法设计与分析 姓名: 张 胜 实验序号:一 班级:信计 101 班 学号:1007010162 实验日期:2013-9-30 指导教师:程欣宇 实验成绩:

一、实验名称
分治算法实验 - 棋盘覆盖问题

二、实验目的及要求
1、熟悉递归算法编写; 2、理解分治算法的特点; 3、掌握分治算法的基本结构。

三、实验环境
Visual C++

四、实验内容 根据教材上分析的棋盘覆盖问题的求解思路,进行验证性实验; 要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学 尝试消去递归求解。 五、算法描述及实验步骤
分治算法原理: 分治算法将大的分解成形状结构相同的子问题,并且不断递归地分解,直到 子问题规模小到可以直接求解。

棋盘覆盖问题描述: 在一个 2k x 2k 个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方 格,想要求利用四种 L 型骨牌(每个骨牌可覆盖三个方格)不相互重叠覆盖的 将除了特殊方格外的其他方格覆盖。

实验步骤: 1、 定 义 用 于 输 入 和 输 出 的 数 据 结 构 ; 2、 完 成 分 治 算 法 的 编 写 ; 3、 测 试 记 录 结 构 ; 4、有 余 力 的 同 学 尝 试 不 改 变 输 入 输 出 结 构 ,将 递 归 消 除 ,并 说 明 能 否不用栈,直接消除递归,为什么?

六、调试过程及实验结果
实验运行结果:

七、总结
通过本次实验,我更深的理解了递归和分治策略。代码是书上的算法,加上主 函数就行了,用的是 C 语言编写,很长时间没用了,感觉有点生疏。实验结果有 点问题,就是覆盖棋盘时,并不是按照 1,2,3….的字符顺序,而是按照很乱 的顺序输出字符,这个我不知道怎么解决,就没解决。

八、附录
#include "stdio.h" #include "conio.h" int board[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} }; int tile=0; void chessBoard(int tr, int tc, int dr, int dc, int size) { int t=tile++, s=size/2; if (size==1) return;

if

(dr<tr+s&&dc<tc+s) chessBoard(tr,tc,dr,dc,s); { board[tr+s-1][tc+s-1]=t; chessBoard(tr,tc,tr+s-1,tc+s-1,s);}

else

if(dr <tr+s && dc >= tc+s) chessBoard(tr,tc+s,dr,dc,s); { 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); { board[tr+s][tc+s-1]=t;

else

else

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); { board[tr+s][tc+s]=t; chessBoard(tr+s,tc+s,tr+s,tc+s,s);} } main() { int i ,j;

else

chessBoard(0,0,5,5,8); for(i=0;i <8;i++) { for( j=0;j <8;j++) { if(board[i][j]<10) printf("0"); printf("%d",board[i][j]); printf(" "); } printf( "\n"); } getchar(); }


搜索更多“算法设计与分析实验报告 棋盘覆盖问题”

网站地图

All rights reserved Powered by 伤城文章网 5xts.com

copyright ©right 2010-2021。
伤城文章网内容来自网络,如有侵犯请联系客服。zhit325@126.com