算法分析与设计(分治法).doc

算法分析与设计实验报告2016-2017年第2学期实验班级： 15软件 学生姓名： 胡* 学 号： 413* 指导老师： 张* 信息工程学院实验项目1名称： 分治法 实验日期：2017年3 月8 日1、 实验类型： 验证性 设计性2、 实验目的1、熟悉C/C+语言的集成开发环境；2、通过本实验加深对递归过程的理解三、实验内容及要求掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、实验程序#include using namespace std;int main()int a,b,c;int q(int n,int m);cout请输入整数及大于最大加数的数ab; /cin是输入的意思, 用于接收键盘的输入操作 c=q(a,b);cout所需要的划分数为：cendl;return 0;int q(int n,int m)if (n1)|(m1) return 0;if (n=1)|(m=1) return 1;if (nm) return q(n,n);if (n=m) return q(n,m-1)+1;return q(n,m-1)+q(n-m,m);五、实验结果1、实验图形2、结果分析3、实验总结实验项目2名称： 棋盘覆盖问题 实验日期：2017年 3 月 8 日一、实验类型： 验证性 设计性二、实验目的1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法三、实验内容及要求盘覆盖问题：在一个2k2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。四、实验程序#include using namespace std;int tile=0; /全局变量，表示特殊格的号int board10001000;int main()int tr, tc, dr, dc, size;int tile=0; /全局变量，表示特殊格的号void chessBoard(int tr, int tc, int dr, int dc, int size);cout输入数据trtcdrdcsize;coutendlendl;chessBoard(tr, tc, dr, dc, size);for(int i=1;i=size;i+)for(int j=1;j=size;j+)coutboardij ;coutendl;return 0;void chessBoard(int tr, int tc, int dr, int dc, int size)/左上角行号、列号，特殊格的行号、列号棋盘大小 if (size = 1) return; int t = +tile, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr tr + s & dc tc + s)/ 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 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 / 此棋盘中无特殊方格/ 用 t 号L型骨牌覆盖左下角 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 / 用 t 号L型骨牌覆盖左上角 boa