数据结构域算法设计-实验一 分治与递归

《数据结构域算法设计-实验一 分治与递归》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一分治与递归基本题一：基本递归算法一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。五．实验源代码：（1）//基本递归算法整数划分#include#includeusingnamespacestd;//intn;intinte

2、ger_split(intn,intm){if(m==1

3、

4、n==1){return1;}if(n=1;m--)//{count=integer_split(n,n);//}printf("%d",count);return0;}（2

5、）运行结果：Input：请输入一个待划分的整数Output：输出有多少种划分样例：Input：6Output：11；（3）算法思路：11/11首先要找出递归的公式来，首先分析几种简单的情况，n==1

6、

7、m==1可以直接得出结果为1；而当nm时，可以用q(n,m-1)+q(n-m,m),其中q(n-m,m表示的时当m固定后，求剩下可能的情况。参考下图：基本题二：二分搜索一、实验目的与要求1、熟悉二分搜索算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1

8、]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素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#include#includeusingnamespacestd;intn,x,i,j;voidBinarysearch(i

9、ntleft,intright,inta[]){i=left;j=right;if(i<=j){intmid=(i+j)/2;if(a[mid]==x)11/11{i=mid;j=mid;return;}if(a[mid]>x){j=mid-1;Binarysearch(i,j,a);}elseif(a[mid]

10、){scanf("%d",&a[k]);}printf("请输入待查的一个数据值:");scanf("%d",&x);if(x>a[n-1]

11、

12、x

13、分搜索，计算mid=left+right；若a[mid]的值小与待查元素值，则更新left=mid+1；反之，更新rightmid-1;若这个元素找不到，那么就便利到i>j的时刻点，跳出while循环，i与j分别表示大于待查元素和小于待查元素的下标.2、设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。(1)实验源