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

《算法分析与设计(分治法)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、a,b,c;intq(intn,intm);cout«M请输入整数及大于最大加数的数*«endl;//这个就是输出〃请输入整数及大于最大加数的数”的值，然后再换到下一行cin»a»b;//cin是输入的意思，用于接收键盘的输入操作c=q(a,b);cout«n所需要的划分数为「vvcvvendl;return0;intq(intn,intm){if((n

3、

4、(m

5、

6、(m==l))return1;if(n

7、・l)+q(n・m,m);五、实验结果1、实验图形cTKD:TEMP32DebugZexeMcTMlWTEWP^12U)etxig2-exeM请输入整数及大于最大加薮的数?11所需要的划分数为，15Pressanykeytocontinue1话输入整数及大于最大加数的数7?所需要的戈'数为*坊PressanyJceytocontinue.2、结果分析3、实验总结实验项冃2名称：棋盘覆盖冋题实验口期：2017年3月8口一、实验类型：丿验证性□设计性二、实验目的1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法三、实验内容及要求盘覆盖问题：在一个

8、2kX2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。四、实验程序#includeusingnamespacestd;inttile=0;//全局变量，表示特殊格的号intboardfl000][1000];intmain(){inttr,tc,dr,de,size;inttile=0;//全局变量，表示特殊格的号voidchessBoard(inttr,i

9、nttc,intdr,intde,intsize);cout«n输入数据n«endl;cin»tr»tc»dr»dc»size;cout«endl«endl;chessBoard(tr,tc,dr,de,size);foT(inti=l;iv二size;i++){for(intj=1;jv=size;j++)cout«board[i][j]«Hn;cout«endl;}return0;}voidchessBoard(inttr,inttc,intdr,intde,intsize)//左上角行号、列号,特殊格的行号、列号棋盘大小if(size==1)re

10、turn;intt=++tile,〃L型骨牌号s=size/2;〃分割棋盘〃覆盖左上角子棋盘if(dr=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,de,s);else{//此棋

11、盘中无特殊方格//用t号L型骨牌覆盖左下角boardftr+s-l][tc+s]=t;//覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr>=tr+s&&de=tr+s&&de>=tc+s)//特殊方格在

12、此棋盘中chessBoard(tr+s,tc+s,dr,de,s);else{//用t号L型骨