算法实验一实验报告

《算法实验一实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数学与计算机学院算法分析实验报告指导老师：汤小月专业：信息管理与信息系统班级：信管1201班学号：姓名：实验一分治与递归(2学时)一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输山结果能够用递归方法实现整数的划分。具体程序代码如下：#includeusingnamespacestd;intq(intn,intm)//正整数n的最大加数m的划分数{if((n

2、

3、(

4、m1if((n==l)

5、

6、(m==l))return1;//正整数或者最大加数=1时，只有一种划分情况if(n

7、»n;while(n>=l){cout«n请输入一个最大加数m:"«endl;cin»m;cout<<"正整数n的最大加数m的划分数为"《q(n,m}«endl;cout<〈"请输入一个整数n(-1退出)："«endl;cin»n;}}进行编译如T:5jLinking.T.1-1.exe-0error(s),0warning(s)运行结果如下：’D:®法ebugl-l.exe'请输入一个整数n（-1退出）84请输入一个最大加数n:88醫醐颁为撕-1退出）请输入一个最大加数■磯電戸分数为28796-1退出）请输入一个最大加数■576

8、F个置■数加944请输入一个最大加数■35rw雪;数为iiis■nr►四、实验步骤1.理解算法思想和问题要求；2.编程实现题H要求；3.上机输入和调试自己所编的程序;4.验证分析实验结果；5.整理出实验报告基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法：2、初步掌握分治算法二、实验题：盘覆盖问题：在一个2kX2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不

9、得重齊覆盖。三、实验提示voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L型骨牌号s=size/2;//分割祺盘//覆盖左上角子棋盘if(dr

10、s);}//覆盖右上角子祺盘if(dr=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,dc,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s•l][tc+s]=t;//覆盖其余方格chessBoard(tr,tc+s,tr+s-1,tc+s,s);}//覆盖左下角子棋盘if(dr>=tr+s&&dc

11、+s-1]=t;//覆盖其余方格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);else{//用t号L型骨牌覆盖左上角board[tr+s][tc+s]=t;//覆盖其余方格chessBoard(tr+s,tc+s,tr+s,tc+s,s);}}编写程序代码如下：#includeusingnamespacestd;intboard[65][65],til

12、e;/*tile为纸片编号*/voidchessBoard(inttr,inttc,intdr,intdc,intsize){if(size==1)return;intt=tile++,//L