实验一 分治与递归
基本题一：基本递归算法 一、实验目的与要求
1、 熟悉C/C++语言的集成开发环境；
2、通过本实验加深对递归过程的理解 二、实验内容：
掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。 三、实验题
任意输入一个整数，输出结果能够用递归方法实现整数的划分。 四、实验步骤
1． 理解算法思想和问题要求； 2． 编程实现题目要求；
3． 上机输入和调试自己所编的程序； 4． 验证分析实验结果； 5． 整理出实验报告。 五、实验代码 #include
int q(int n,int m) //正整数n的最大加数m的划分数 { if((n<1)||(m<1)) return 0; //n，m需>1 if((n==1)||(m==1)) return 1; //正整数或者最大加数=1时，只有一种划分情况 if(n void main() { int n,m; cout<<\请输入一个整数n：\ cin>>n; while(n>=1) { cout<<\请输入一个最大加数m：\ cin>>m; cout<<\最大加数不大于m的划分个数为: \ cout< } } cin>>n; 运行结果： 六、 运行结果分析 该算法调用q（n，m）函数 （1）输入n=1，m=1时，输出结果1； （2）输入n=2，m=3，即n （4）输入n=4，m=3，即n>m>1，输出结果=q(4,2)+q(1,3)=4。 基本题二：棋盘覆盖问题 一、实验目的与要求 1、掌握棋盘覆盖问题的算法； 2、初步掌握分治算法 二、实验题： 盘覆盖问题：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。 三、 程序代码 #include int tile=1; int board[20][20]={0}; void chessBoard(int tr, int tc, int dr, int dc, int size) {//tr和tc是棋盘左上角的下标，dr和dc是特殊方格的下标，size是棋盘的大小 if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 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 < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + 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); } } int main() { int k,x,y; printf(\请输入棋盘的规模k: \ scanf(\ printf(\请输入特殊方格的下标x,y: \ scanf(\ chessBoard(0,0,x,y,pow(2,k)); for(int i=0;i } 三、 运行结果 六． 算法分析 （1） 用一个二维整型数组board表示棋盘。 （2） tile是算法中的一个全局整型变量，用来表示L型骨牌的编号，将所有L型骨 牌从1开始编号。 （3） 当k=0时，时间复杂度T（k）=O（1）；当k>0时，时间复杂度T（k）=4T（k-1） +O（1）。 提高题一：二分搜索 一、实验目的与要求 1、熟悉二分搜索算法； 2、初步掌握分治算法； 二、实验题 1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。 2、设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。 三、程序代码 1、 #include int BinarySearch(int a[],int n,int x,int &i,int &j) {//a[] 为要搜索的数组; n为数组元素的个数; x为要查询的元素值；i为小于x的最大元素位置;j为大于x的最小元素的位置 int left=0; //数组的左边界 int right=n-1; // 数组的右边界 while(left void main() { int a[]={-7,-3,-1,0,3,5,9,13,19,21};//用来测试的数组 int x; int i=0; int j=0; cout<<\输入你要判断的数：\ cin>>x; cout< 运行结果： 四、 实验分析 容易看出，每执行一次算法的while循环，待搜索数组的大小减小一半。因此，在最坏的情况下，while循环被执行了O（logn）次。循环体内运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂度为O(logn)。 五、 实验总结 本次实验让我更加深刻的了解了递归算法的思想，以及运用分治法的思想解决棋盘覆盖问题和二分搜索技术。每个递归函数都必须有非递归定义的初始值，否则，递归函数就无法计算；分治法的思想是将一个规模为n的问题分解为k个规模较小的问题，这些子问题互相独立与原问题相同；二分搜素算法思想是将n个元素分成个数大致相同的两半，取a[n/2]与x作比较。实验是我们掌握算法知识必不可少的一部分。
实验一 分治与递归
