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

1、算法分析与设计实验报告2016-2017年第2学期实验班级：学生姓名: 学 号: 指导老师:15软件胡*413*张*信息工程学院实验项冃1名称：分治法实验口期：2017年3月8 口一、实验类型： 13验证性设计性二、实验目的1、熟悉c/c+语言的集成开发环境；2、通过本实验加深对递归过程的理解三、实验内容及要求掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递 归算法。任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、实验程序#include <iostream>using namespace std;int main()int a,b,c;int q(int

2、n,int m);cout«m请输入整数及大于最大加数的数*«endl; /这个就是输出 请输入整数及大于最大加数的数”的值，然后再换到下一行cin»a»b; /cin是输入的意思，用于接收键盘的输入操作 c=q(a,b);cout«n所需要的划分数为vvcv vendl;return 0;int q(int n,int m)if (n<l)|(m<l) return 0;if (n=l)|(m=l) return 1;if (n<m) return q(n,n);if (n=m) return q(n,m-l)+l;retu

3、rn q(n,m l)+q(nm,m);五、实验结果1、实验图形ct kd:temp32debugzexemct mlwtewp12u)etxig2-exem请输入整数及大于最大加薮的数? 11所需要的划分数为，15press any key to continue1话输入整数及大于最大加数的数7 ?所需要的戈 '数为*坊press any jcey to continue.2、结果分析3、实验总结实验项冃2名称：棋盘覆盖冋题实验口期：2017年3月8 口一、实验类型：丿验证性设计性二、实验目的1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法三、实验内容及要求盘覆盖问题：在一个2kx2

4、k个方格组成的棋盘中，恰有一个方格与 其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的l型骨牌覆盖给定的 特殊棋盘上除特殊方格以外的所有方格,且任何2个l型骨牌不得重 叠覆盖。四、实验程序#include <iostream>using namespace std;int tile=0; /全局变量，表示特殊格的号int boardfl0001000;int main()int tr, tc, dr, de, size;int tile=0; /全局变量，表示特殊格的号void chessboard(int tr, int tc

5、, int dr, int de, int size); cout«n 输入数据 n«endl; cin»tr»tc»dr»dc»size; cout«endl«endl; chessboard(tr, tc, dr, de, size); fot(int i=l;iv二size;i+)for(int j=1 ;j v=size;j+) cout«boardij«h n;cout«endl;return 0;void chessboard(int tr, int tc, in

6、t dr, int de, int size)/左上角行号、列号,特殊格的行号、列号棋盘大小if (size = 1)return;int t = +tile, l 型骨牌号s = size/2; 分割棋盘覆盖左上角子棋盘 if (dr < tr + s && de < tc + s)/特殊方格在此棋盘中chessboard(tr, tc, dr, de, s);else此棋盘中无特殊方格/用t号l型骨牌覆盖右下角boardtr 4- s ltc + s 1 = t;/覆盖其余方格chessboard(tr, tc, tr+s-1, tc+s-1, s);/覆盖右上

7、角子棋盘if (dr < tr + s && de >= tc + s) /特殊方格在此棋盘中 chessboard(tr, tc+s, dr, de, s);else/此棋盘中无特殊方格/用t号l型骨牌覆盖左下角boardftr + s - ltc + s = t; / 覆盖其余方格 chessboard(tr, tc+s, tr+s-1, tc+s, s);/覆盖左下角子棋盘if (dr >= tr + s && de < tc + s)/特殊方格在此棋盘中chessboard(tr+s, tc, dr, de, s);else/用t

8、号l型骨牌覆盖右上角boardtr + stc + s - 1二 t;/ 覆盖其余方格 chessboard(tr+s, tc, tr+s, tc+s-1, s);/覆盖右下角子棋盘if (dr >= tr + s && de >= tc + s) /特殊方格在此棋盘中chessboard(tr+s, tc+s, dr, de, s);else/用t号l型骨牌覆盖左上角boardtr + stc + s = t;/ 覆盖其余方格 chessboard(tr+s, tc+s, tr+s, tc+s, s);五、实验结果1、实验图形13nan8n 099a71n0f908e er90n2hfl v72n&1 mi immv11m&0g&e0x0 臼1 ji1a0uhh0s10 0000t313t-l1 0)11pi191 91 31»1 h m c4 1 9 mm m 12 o m