武汉轻工大学.docx

武汉轻工大学.docx武汉轻工大学数学与计算机学院算法分析实验报告指导老师: 汤小月 专业: 信息管理与信息系统班级: 信管1201班 学号: 姓名:实验一分治与递归(2学时)基本题一:基本递归算法一、 实验目的与要求1、 熟悉C/C++语言的集成开发环境;2、 通过本实验加深对递归过程的理解二、 实验内容:掌握递归算法的概念和基本思想,分析并掌握“整数划分”问题的递归算法。三、 实验题任意输入一个整数,输出结果能够用递归方法实现整数的划分。具体程序代码如下:#include<iostream>usin呂namespacestd;intq(intn,intm) 〃正整数n的最大加数m的划分数{if((n<l)||(m<l))return0; //n,m需>1if((n==l)||(m==l))return1; 〃正整数或者最大加数二1时,只有一种划分情况if(n<m)returnq(n,n); 〃最大加数实际不能大于正整数本身if(n==m)returnq(n,m-l)+l; //递归,n的划分由其q(n,m-1)和nl二n组成returnq(nzm-l)+q(n-m/m);〃正整数n的最大加数nl不大于m的划分由nl=m的划分和nl二nvlMj划分组成}voidmain(){intnzm;cout«n请输入一个整数n(J退出):H«endl;cin>>n;while(n>=l){cout«H请输入一个最大加数m:"«endl;cin»m;cout«"正整数n的最大加数m的划分数^"«q(n/m)«endl;cout«H请输入一个整数n(-1退出):"«endl;cin»n;}}进行编译如下:ttinclude<iostrean)>usingnamespacestd;intq(intn,intn)〃正整数n的最大加数m的划分数if((n<1)||(m<1))return0;if((n==1)||(n==1))return1;if(n<n)returnq(n9n);if(n--n)returnq(n»m-1)*1;returnq(nfR-1)*q(n-ntn);//nn^>i最大rw-种划分情况〃最畫加珈孫虾丕龍犬于正整数本身〃谨归,n的划分由臺q(n,n-1)和n1・n纟耳成〃正整数n的最大加好訂不大于m的划分由rd・m的划分和n1-R-1的划分组成uoidnain()<intnvn;cout«-请输入一个整数n(Y退岀),-«endl;cin>>n;while(n>-1)<cout«・・请输入一个最大加数R:-«endl;cin»m;coutC<"正赘数n的最左加数m的划分数为ie«q(n,n)«endl;cout«-请裔入一个埜数n(Y退岀):-«endl;cin>>n;Linking 1--0error(s)»0warning(s)运行结果如下:•D:\算法\Debug\-(-1请输入一个最大加数m:4正羹朝n的罐盍加数m的劃分数为4894请(-1退岀):n(7退岀):请输入一个最大加数m:5正整数的罐盍加数m的刻分数为28796请(7退岀):57请输入一个最大加数m:2整犁n他罐盍加数m的刻分数为15944请WA—退i):请请输入一个最大加数m:2饕粼n他憨加数m的刻分数为1115数n(-丄退岀):rn四、实验步骤理解算法思想和问题要求;编程实现题目要求;上机输入和调试自己所编的程序;验证分析实验结果;。基本题二:棋盘覆盖问题一、 实验目的与要求1、 掌握棋盘覆盖问题的算法;2、 初步掌握分治算法二、 实验题:盘覆盖问题:在一个2kX2k个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,耍用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重亮覆盖。三、 实验提示voidchessBoard(inttr,inttc,intdr,intdczintsize){if(size==1)return;intt=tile++/〃L型骨牌号s=size/2;//分割棋盘//覆盖左上角子棋盘if(dr<tr+s&&de<tc+s)//特殊方格在此棋盘中chessBoardftr,tc,dr;de,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖右下角board[tr+s・l][tc+s-1]=t;//覆盖其余方格chessBoard(tr,tc,tr+s-1,tc+s-1,s);}//覆盖右上角子棋盘if(dr<tr+s&&de>=tc+s)//特殊方格在此棋盘中chessBoard(tr,tc+s,dr,de,s);else{//此棋盘中无特殊方格//用t号L型骨牌覆盖左下角board[tr+s