算法实验一实验报告.doc

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

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

2、<1)

3、

4、(m<1))return0;//n，m需>1if((n==1)

5、

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

7、;while(n>=1){cout<<"请输入一个最大加数m："<>m;cout<<"正整数n的最大加数m的划分数为"<>n;}}进行编译如下：运行结果如下：四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；1．整理出实验报告。 基本题二：棋盘覆盖问题一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题：   盘覆盖问题：在一个2k×2k个方格组成的棋盘中

8、，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。三、实验提示voidchessBoard(inttr,inttc,intdr,intdc,intsize)  {     if(size==1)return;     intt=tile++, //L型骨牌号       s=size/2; //分割棋盘     //覆盖左上角子棋盘     if(dr

9、在此棋盘中        chessBoard(tr,tc,dr,dc,s);     else{//此棋盘中无特殊方格        //用t号L型骨牌覆盖右下角        board[tr+s-1][tc+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{//此棋

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

11、   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);}  }编写程序代码如下:#includeusing

12、namespacestd;intboa